This thesis concerns tree decompositions. Trees are one of the simplest and most well understood class of graphs. A tree decomposition of a graph improves our understanding of the graph in a similar way. For example, as a consequence of Robertson and Seymour's groundbreaking work in the theory of graph minors, there are linear time algorithms for NP-hard problem on graphs that admit a tree decomposition of a certain type. We classify existing tree decompositions and examine what makes a tree decomposition unique.The first result of this thesis is a linear time algorithm for building a tree decomposition for the class of graphs that exclude K5 as a minor. The second result is a significant modification to this algorithm which results in a linear time algorithm to construct the tree decomposition for graphs which exclude a special set of paths. These are vertex disjoint paths between two pairs of input vertices (s_1, t_1), (s_2, t_2), one from s_1 to t_1 and the other from s_2 to t_2.We then use these tree decompositions to improve the running time of existing algorithms and extend the allowed input of other algorithms from planar graphs to graphs that exclude K_5 as a minor. / Cette thèse traite de décompositions arborescentes. Les arbres font partie des classes de graphes les mieux comprises. La décomposition arborescente d'un graphe améliore notre compréhension de ce dernier. Par exemple, grâce aux travaux de Robertson et Seymour sur les mineurs d'un graphe, nous savons qu'il existe, pour des problèmes qui sont en général NP-difficiles, un algorithme linéaire pour les graphes admettant une certaine décomposition arborescente. Nous classons les décompositions arborescentes connues et déterminons les propiétés qui rendent cette décomposition unique.Comme premier résultat, nous donnons un algorithme linéaire pour construire une décomposition arborescente d'un graphe sans mineur du graphe complet K_5. Notre deuxième resultat repose sur une modification de cet algorithme afin d'obtenir un autre algorithme linéaire. Ce dernier permet la construction d'une décomposition arborescente d'un graphe qui ne contient pas deux chemins à sommets disjoints entre deux paires de sommets données (s_1, t_1) et (s_2, t_2).Nous utilisons ces deux décompositions pour améliorer le temps de calcul des algorithmes existants et modifions des algorithmes pour graphes planaires pour leur permettre de prendre comme donnée des graphes sans mineur K_5.

We study the geometry of median graphs and CAT(0) cube complexes by introducing two combinatorial objects: the contact graph and the simplicial boundary. The first of these encodes the intersections of hyperplane-carriers. We prove that this graph is always quasi-isometric to a tree, and deduce that groups acting properly and cocompactly on cube complexes are weakly hyperbolic relative to the collection of hyperplane-stabilizers. Using diagrammatic techniques of Casson-Sageev-Wise, we study complete bipartite subgraphs of the contact graph, and prove a cubical version of the flat plane theorem. Similar considerations lead to a characterization of strong relative hyperbolicity of cocompactly cubulated groups relative to the hyperplane stabilizers. Motivated by the question of which contact graphs are quasi-isometric to bounded trees, we introduce the simplicial boundary of a locally finite cube complex, which is a combinatorial analogue of the Tits boundary and encodes, roughly, the cubical flat sectors in the cube complex. We establish basic properties of the simplicial boundary, and use these to characterize locally finite, essential, one-ended cube complexes with bounded contact graph. This leads to a reinterpretation and modified proof of the Caprace-Sageev rank-rigidity theorem. Finally, we relate the graph metric on the 1-skeleton of the simplicial boundary of the cube complex X to the divergence of geodesic rays in the median graph X. We show that a group G acting properly, cocompactly, and essentially on the geodesically complete cube complex X has linear divergence function if and only if the simplicial boundary of X is connected. Otherwise, the divergence function of G is at least quadratic; this partially generalizes a result of Behrstock-Charney on the divergence of right-angled Artin groups. / Nous étudions la geometrie des graphes medians et des complexes cubiques CAT(0) en introduisant deux objets combinatoires: le graphe de contact et la frontière simpliciale. Le premier de ces objets encode les intersections des porteurs des hyperplans. Nous prouvons que ce graphe est toujours quasi-isométrique à un arbre, et en déduisons que les groupes agissant de manière propre et cocompacte sur les complexes cubiques sont faiblement hyperboliques relativement à la famille des stabilisateurs des hyperplans. En utilisant des techniques diagrammatiques de Casson-Sageev-Wise, nous étudions les sous-graphes bipartis complets du graphes de contact, et prouvons une version du théorème sur l'existence d'un plongement d'un plan (le "flat plane theorem"). Des considérations similaires nous mènent à une caractérisation des groupes cocompactement cubulés qui sont fortement hyperboliques relativement aux stabilisateurs des hyperplans. Motivés par la désir de savoir quels graphes de contact sont quasi-isométriques à des pointes, nous introduisons la frontière simpliciale d'un complexe cubique localement fini, qui est un analogue combinatoire de la frontière de Tits, et encode les secteurs cubiques plats du complexe cubique. Nous établissons les propriétés élémentaires de la frontière simpliciale, et utilisons celles-ci pour caractériser les complexes cubiques localement finis, essentiels et à un bout, qui ont un graphe de contact borné. Cela nous mène à une interpretation alternative du théorème de rigidité de rang de Caprace-Sageev. Nous mettons une relation entre la frontière simpliciale d'un complexe cubique X, et la divergence des rayons géodésiques dans le graphe médian X1. Nous montrons qu'un groupe G qui agit proprement, cocompactement et essentiellement sur X, diverge demanière linéaire si et seulement si la frontière simpliciale de X est connexe. Cela généralise un résultat de Behrstock-Charney sur la divergence desgroupes d'Artin à angle droit.

This thesis has two main parts: both of which aim at computing the Zeta function of some curves. The first part contains the theoretical and practical considerations to make K. Kedlaya's algorithm and some of its generalizations work. We review important properties of the Monsky-Washnitzer cohomology, the Weil conjectures and piece the bits together in order to provide an algorithm that would compute the Zeta function of a superelliptic curve, due to P. Gaudry and N. Gürel. In the second part, we present an algorithm to compute the Zeta function of a Cab curve using deformation theory. The general strategy, due to A. Lauder, is to study the variation of the Frobenius action along a certain family. This almost fully practical algorithm generalizes similar work by R. Gerkmann and H. Hubrechts. / Cette thèse comporte deux parties principales: les deux ont pour objet de calculer la fonction Zêta de certains types de courbes. La première partie contient des considérations théoriques et pratiques pour faire fonctionner l'algorithme de K. Kedlaya et certaines de ses généralisations. On résume les propriétés importantes de la cohomologie de Monsky et Washnitzer, les conjectures de Weil et on rassemble les pièces du casse-tête pour en arriver à un algorithme de P. Gaudry et N. Gürel pour calculer la fonction Zêta d'une courbe superelliptique. Dans la deuxième partie, nous présentons un algorithme pour calculer la fonction Zêta d'une courbe Cab en utilisant la théorie de la déformation. La stratégie générale, attribuée à A. Lauder, est d'étudier la variation de l'action de Frobenius le long d'une certaine famille de courbes. Cet algorithme, presque prêt à utiliser, généralise des travaux similaires de R. Gerkmann et H. Hubrechts.

Though the tryptophan operon has received a fair amount of experimental study over recent decades, modeling e?orts have been relatively few and disparate in some of their conclusions regarding the behavior of the operon. We consider a selection of existing models of the tryptophan operon and analyze them from the standpoints of stability, response to periodic signals in the biochemistry, and existence of attracting invariant manifolds in the model state space. We ?nd that the stability properties of these models may depend greatly upon small changes in parameters that are in keeping with updated experimental data. Further, we show the ability of the tryptophan operon to act as a classical band-pass ?lter to periodic ?uctuations ostensibly caused by the periodic nature of the cell cycle. Finally, a functional iteration technique for the approximate computation of attracting invariant manifolds is presented and the manifold for one of the models is computed. / Bien que l'opéron de tryptophane ait fait l'objet d'un nombre d'essais expérimentaux considérables dans les dernières décennies, les e?orts dans la modélisation ont été rel- ativement peu et disparates quant à leurs conclusions concernant le comportement de l'opéron. Nous considérons un choix de modèles existants de l'opéron de tryptophane et les analysons des points de vue de leur stabilité, de leur réponse aux signaux périodiques en biochimie, et de l'existence d'attractions de variétés invariantes dans l'espace d'états du modèle. Nous constatons que les propriétés de stabilité de ces modèles peuvent dépendre considérablement de petits changements des paramètres qui sont en accord avec des données expérimentales mises à jour. De plus, nous montrons la capacité de l'opéron de tryptophane à agir comme ?ltre passe-bande classique aux ?uctuations périodiques en apparence provoquées par la nature périodique du cycle cellulaire. En conclusion, une technique fonctionnelle d'itération pour le calcul approximatif de l'attraction de variété invariante est présentée et la variété pour un des modèles est calculée. fr

Roth's theorem, proved by Roth in 1953, states that when A is a subset of the integers [1,N] with A dense enough, A has a three term arithmetic progression (3-AP). Since then the bound originally given by Roth has been improved upon by number theorists several times. The theorem can also be generalized to finite abelian groups. In 1994 Meshulam worked on finding an upper bound for subsets containing only trivial 3-APs based on the number of components in a finite abelian group. Meshulam’s bound holds for finite abelian groups of odd order. In 2003 Lev generalised Meshulam’s result for almost all finite abelian groups. In 2009 Liu and Spencer generalised the concept of a 3-AP to a linear equation and obtained a similar bound depending on the number of components of the group. In 2011, Liu, Spencer and Zhao generalised the 3-AP to a system of linear equations. This thesis is an overview of these results.

We recast the theory of labelled Markov processes in a new setting, in a way "dual" to the usual point of view. Instead of considering state transitions as a collection of subprobability distributions on the state space, we view them as transformers of real-valued functions. By generalizing the operation of conditional expectation, we build a category consisting of labelled Markov processes viewed as a collection of operators; the arrows of this category behave as projections on a smaller state space. We define a notion of equivalence for such processes, called bisimulation, which is closely linked to the usual definition for probabilistic processes. We show that we can categorically construct the smallest bisimilar process, and that this smallest object is linked to a well-known modal logic. We also expose an approximation scheme based on this logic, where the state space of the approximants is finite; furthermore, we show that these finite approximants categorically converge to the smallest bisimilar process. / Nous reconsidérons les processus de Markov étiquetés sous une nouvelle approche, dans un certain sens "dual'' au point de vue usuel. Au lieu de considérer les transitions d'état en état en tant qu'une collection de distributions de sous-probabilités sur l'espace d'états, nous les regardons en tant que transformations de fonctions réelles. En généralisant l'opération d'espérance conditionelle, nous construisons une catégorie où les objets sont des processus de Markov étiquetés regardés en tant qu'un rassemblement d'opérateurs; les flèches de cette catégorie se comportent comme des projections sur un espace d'états plus petit. Nous définissons une notion d'équivalence pour de tels processus, que l'on appelle bisimulation, qui est intimement liée avec la définition usuelle pour les processus probabilistes. Nous démontrons que nous pouvons construire, d'une manière catégorique, le plus petit processus bisimilaire à un processus donné, et que ce plus petit object est lié à une logique modale bien connue. Nous développons une méthode d'approximation basée sur cette logique, où l'espace d'états des processus approximatifs est fini; de plus, nous démontrons que ces processus approximatifs convergent, d'une manière catégorique, au plus petit processus bisimilaire.

In this thesis, we explain the connection between completely integrable systems of evolution equations and the evolution of the differential invariants of group actions in the particular case of a curve in Rⁿ acted on by an affine group defined as the semidirect product of G and Rⁿ, where G is semisimple, as it is presented in the work of Marì-Beffa. This connection involves Fels and Olver's work on the theory of moving frames, infinite-dimensional Hamiltonian systems and Poisson brackets, and centrally extended loop groups and algebras. We also summarize the relevant theory both of Lie groups and Lie algebras and of differential invariants and symmetries of differential equations. groups and algebras. We also summarize the relevant theory both of Lie groups and Lie algebras and of differential invariants and symmetries of differential equations. / Dans cette thèse, on explique le lien entre les systèmes d'équations d'évolution complètement intégrables et l'évolution des invariants différentiels de l'action d'un groupe dans le cas particulier d'une courbe dans Rⁿ , sous l'action du produit semidirect d'un groupe G avec Rⁿ, où G est semisimple, tel que présenté par Marì-Beffa. Cette connection fait intervenir la théorie de repères mobiles de Fels et Olver, les systèmes hamiltoniens de dimension infinie et les crochets de Poisson, ainsi que les groupes et algèbres de lacets à extension centrale. On présente aussi un ré́sumé de la théorie pertinente des groupes et algèbres Lie et des invariants différentiels ainsi que les symmétries d'équations différentielles.

The short form SF-36 survey is a widely used survey of patient health related quality of life. It yields eight subscale scores of functional health and well-being that are summarized by two physical and mental component summary scores. However, recent studies have reported inconsistent results between the eight subscales and the two component summary measures when the scores are from a sick population. They claim that this problem is due to the method used to compute the SF-36 component summary scores, which is based on principal component analysis with orthogonal rotation.In this thesis, we explore various methods in order to identify a method that is more accurate in obtaining the SF-36 physical and mental component component summary scores (PCS and MCS), with a focus on diseased patient subpopulations. We first explore traditional data analysis methods such as principal component analysis (PCA) and factor analysis using maximum likelihoodestimation and apply orthogonal and oblique rotations with both methods to data from the Canadian Scleroderma Research Group registry. We compare these common approaches to a recently developed data analysis method from signal processing and neural network research, independent component analysis (ICA). We found that oblique rotation is the only method that reduces the meanmental component scores to best match the mental subscale scores. In order to try to better elucidate the differences between the orthogonal and oblique rotation, we studied the performance of PCA with the two approaches for recovering the true physical and mental component summary scores in a simulated diseased population where we knew the truth. We explored the methods in situations where the true scores were independent and when they were also correlated. We found that ICA and PCA with orthogonal rotation performed very similarly when the data were generated to be independent, but differently (with ICA performing worse) when the data were generated to be correlated. PCA with oblique rotation tended to perform worse than both methods when the data were independent, but better when the data were correlated. We also discuss the connection between ICA and PCA with orthogonal rotation, which lends strength to the use of the varimax rotation for the SF-36.Finally, we applied ICA to the scleroderma data and found relatively low correlation between ICA and unrotated PCA in estimating the PCS and MCS scores and very high correlation between ICA and PCA with varimax rotation. PCA with oblique rotation also had a relatively high correlation with ICA. Hence, we concluded that ICA could be seen as a compromise solution between the two methods. / La version abrégée du questionnaire SF-36 est largement utilisée pour valider la qualité de vie reliée à la santé. Ce questionnaire fournit huit scores s'attardant à la capacité fonctionnelle et au bien-être, lesquels sont regroupés en cotes sommaires attribuées aux composantes physiques et mentales. Cependant, des études récentes ont rapporté des résultats contradictoires entre les huit sous-échelles et les deux cotes sommaires lorsque les scores sont obtenus auprès de sujets malades. Cette discordance serait due à la méthode utilisée pour calculer les cotes sommaires du SF-36 qui est fondée sur l'analyse en composantes principales avec rotation orthogonale.Dans cette thèse, nous explorons diverses méthodes dans le but d'identifier une méthode plus précise pour calculer les cotes sommaires du SF-36 attribuées aux composantes physiques et mentales (CCP et CCM), en mettant l'accent sur des sous-populations de sujets malades. Nous évaluerons d'abord des méthodes traditionnelles d'analyse de données, telles que l'analyse en composantes principales (ACP) et l'analyse factorielle, en utilisant l'étude de l'estimation du maximum de vraisemblance et en appliquant les rotations orthogonale et oblique aux deux méthodes sur les données du registre du Groupe de recherche canadien sur la sclérodermie. Nous comparons ces approches courantes à une méthode d'analyse de données développée récemment à partir de travaux de recherche sur le réseau neuronal et le traitement du signal, l'analyse en composantes indépendantes (ACI).Nous avons découvert que la rotation oblique est la seule méthode qui réduit les cotes attribuées aux composantes mentales moyennes afin de mieux les corréler aux scores de la sous-échelle des symptômes mentaux. Dans le but de mieux comprendre les différences entre la rotation orthogonale et la rotation oblique, nous avons étudié le rendement de l'ACP avec deux approches pour déterminer les véritables cotes sommaires attribuées aux composantes physiques et mentales dans une population simulée de sujets malades pour laquelle les données étaient connues. Nous avons exploré les méthodes dans des situations où les scores véritables étaient indépendants et lorsqu'ils étaient corrélés. Nous avons conclu que le rendement de l'ACI et de l'ACP associées à la rotation orthogonale était très similaire lorsque les données étaient indépendantes, mais que le rendement différait lorsque les données étaient corrélées (ACI étant moins performante). L'ACP associée à la rotation oblique a tendance à être moins performante que les deux méthodes lorsque les données étaient indépendantes, mais elle est plus performante lorsque les données étaient corrélées. Nous discutons également du lien entre l'ACI et l'ACP avec la rotation orthogonale, ce qui appuie l'emploi de la rotation varimax dans le questionnaire SF 36.Enfin, nous avons appliqué l'ACI aux données sur la sclérodermie et nous avons mis en évidence une corrélation relativement faible entre l'ACI et l'ACP sans rotation dans l'estimation des scores CCP et CCM, et une corrélation très élevée entre l'ACI et l'ACP avec rotation varimax. L'ACP avec rotation oblique présentait également une corrélation relativement élevée avec l'ACI. Par conséquent, nous en avons conclu que l'ACI pourrait servir de solution de compromis entre ces deux méthodes.

Confounder adjustment is the key in the estimation of exposure effect in observational studies. Two well known causal adjustment techniques are the propensity score and the inverse probability of treatment weighting. We have compared the asymptotic properties of these two estimators and showed that the former method results in a more efficient estimator. Since ignoring important confounders result in a biased estimator, it seems beneficial to adjust for all the covariates. This, however, may result in an inflation of the variance of the estimated parameters and induce bias as well. We present a penalization technique based on the joint likelihood of the treatment and response variables to select the key covariates that need to be included in the treatment assignment model. Besides the bias induced by the non-randomization, we discuss another source of bias induced by having a non-representative sample of the target population. In particular, we study the effect of length-biased sampling in the estimation of the treatment effect. We introduced a weighted and a double robust estimating equations to adjust for the biased sampling and the non-randomization in the generalized accelerated failure time model setting. Large sample properties of the estimators are established.We conduct an extensive simulation studies to study the small sample properties of the estimators. In each Chapter, we apply our proposed technique on real data sets and compare the result with those obtained by other methods. / L'ajustement du facteur de confusion est la clé dans l'estimation de l'effet de traitement dans les études observationelles. Deux techniques bien connus d'ajustement causal sont le score de propension et la probabilité de traitement inverse pondéré. Nous avons comparé les propriétés asymptotiques de ces deux estimateurs et avons démontré que la première méthode est un estimateur plus efficace. Étant donné que d'ignorer des facteurs de confusion importants ne fait que biaiser l'estimateur, il semble bénéfique de tenir compte de tous les co-variables. Cependant, ceci peut entrainer une inflation de la variance des paramètres estimés et provoquer des biais également. Par conséquent, nous présentons une pénalisation technique basée conjointement sur la probabilité du traitement et sur les variables de la réponse pour sélectionner la clé co-variables qui doit être inclus dans le modèle du traitement attribué. Outre le biais introduit par la non-randomisation, nous discutons d'une autre source de biais introduit par un échantillon non représentatif de la population cible. Plus précisément, nous étudions l'effet de la longueur du biais de l'échantillon dans l'estimation de la résultante du traitement. Nous avons introduit une pondération et une solide équation d'estimation double pour ajuster l'échantillonnage biaisé et la non-randomisation dans la généralisation du modèle à temps accéléré échec réglage. Puis, les propriétés des estimateurs du vaste échantillon sont établies. Nous menons une étude étendue pour examiner la simulation des propriétés des estimateurs du petit échantillon. Dans chaque chapitre, nous appliquons notre propre technique sur de véritables ensembles de données et comparons les résultats avec ceux obtenus par d'autres méthodes.

This dissertation reports on two independent studies in the fields of deterministic and stochastic partial differential equations.In the first part, we introduce a novel spatio-temporal model of the bone remodelling process. Bone remodelling is crucial for the removal of fatigue damage and the renewal of old bone tissue in the vertebrate skeleton. Responsible for remodelling are the bone multicellular units (BMUs), complex entities consisting of several interacting cell types. We develop a nonlinear mixed PDE model capturing the dynamics of a single BMU in trabecular bone. Several pathological remodelling events are studied numerically, and new insights into the RANKL/RANK/OPG pathway are presented. Finally, the model is adapted to study the role of OPG in bone metastases. In silico experiments demonstrate that depending on the expression rate, tumour-derived OPG can increase or decrease osteolysis and tumour growth. In particular, this mechanism is able to explain a set of seemingly contradictory experimental studies. In the second part, we study the well-posedness of the two-dimensional Allen-Cahn equation with additive space-time white noise. We first introduce a high frequency cut-off in the noise field and then study the corresponding regularized problems in the limit where the cut-off goes to infinity. Based on numerical experiments and heuristic arguments, we conjecture that the approximations converge to the zero-distribution. A rigorous proof of the conjecture is provided. The result demonstrates that a series of published numerical studies are problematic: shrinking the mesh size in these simulations does not lead to the recovery of a physically meaningful limit. / Au sein de cette thèse nous présentons deux études indépendantes dans le contexte général des équations aux dérivées partielles (EDP), déterministes ainsi que stochastiques. Lors de la première partie nous développons un nouveau modèle spatio-temporel du processus de remodelage osseux. Le remodelage osseux est essentiel pour la réparation de fissures microscopiques ainsi que le renouvellement périodique du tissu osseux à travers le squelette vertébré. Le remodelage est effectué par les unités fonctionelles de remodelage (UFR): des entités complexes constituées de plusieurs types de cellules interagissantes. Nous développons un modèle mixte d'EDP nonlinéaires pour décrire l'évolution d'une UFR à travers le tissu trabéculaire. A l'aide de simulations numériques, nous étudions plusieurs régimes pathologiques de remodelage, et nous présentons de nouvelles perspectives concernant la voie biochimique RANKL/RANK/OPG. Enfin, le modèle est adapté pour étudier le rôle d'OPG dans les métastases osseuses. Les expériences numériques démontrent que, selon le taux d'expression, OPG exprimée par le tumeur peut soit augmenter soit diminuer l'ostéolyse et ainsi la croissance tumorale. En particulier, ce mécanisme est capable d'expliquer un ensemble d'études expérimentales apparemment contradictoires. Lors de la deuxième partie, nous investigons l'équation d'Allen-Cahn soujette à un bruit blanc additif, et cela en deux dimensions spatiales. Après avoir regularisé le bruit par une coupure à hautes fréquences, nous étudions la suite de problèmes regularisés ainsi obtenue. A l'aide d'expériences numériques et d'arguments heuristiques, nous faisons la conjécture que ces approximations convergent vers la distribution nulle dans la limite du bruit blanc. Une preuve rigoureuse de cette conjécture est fournie. Le résultat démontre que toute une série de travaux numériques publiés dans la litérature sont problématiques: en effet, lorsque la taille de la grille tend vers zéro, on obtient une limite sans signification physique.