The choice number of a graph G, denoted ch(G), is the minimum integer k such that for any assignment of lists of size k to the vertices of G, there is a proper colouring of G such that every vertex is mapped to a colour in its list. For general graphs, the choice number is not bounded above by a function of the chromatic number.In this thesis, we prove a conjecture of Ohba which asserts that ch(G) = χ(G) whenever |V (G)| ≤ 2χ(G) + 1. We also prove a strengthening of Ohba's Conjecture which is best possible for graphs on at most 3χ(G) vertices, and pose several conjectures related to our work. / Le nombre de choix d'un graphe G, noté ch(G), est le plus petit entier k tel que pour toute affectation de listes de taille k au sommets de G, il y a une coloration de G tel que chaque sommet de G est coloré par une couleur de sa liste. En général, le nombre de choix n'est pas borné supérieurement par une fonction du nombre chromatique.Dans cette thèse, nous démontrons une conjecture de Ohba qui affirme que ch(G) =χ(G) dès que |V (G)| ≤ 2χ(G) + 1. Nous démontrons aussi une version plus forte de la conjecture de Ohba qui est optimale pour les graphes ayant au plus 3χ(G) sommets, et énonçons plusieurs conjectures par rapport à nos travaux.

This dissertation is a study of two independent problems from the common research area of boundary element methods used to solve elliptic boundary value problems. Both topics focus mainly on a single layer approach. For the first project we consider the Laplace-Beltrami Dirichlet problem on a subsurface of the unit sphere in R^3. We derive and analyze a boundary element method for a first-kind integral equation to solve this boundary value problem. The method can be used to study the motion of point vortices on a sphere with impenetrable walls; we compare our approach with previous methods in this field. We derive rigorous error estimates for approximations of the solution to the integral equation in appropriate Sobolev spaces which yield global error estimates for the solution of the boundary value problem. Moreover, we support the theoretical results with numerical evidence gathered from test cases. The second project is concerned with a multigrid preconditioning strategy for the acoustic single layer equation in two dimensions. As proposed in [6], we reformulate the boundary element method in a weaker base inner product and then use a V-cycle multigrid scheme with a Richardson type smoother. We provide a full convergence analysis for the proposed multigrid algorithm based on an analogous result for the single layer equation corresponding to the Laplace operator. Numerical experiments underline the performance of the algorithm. Moreover, we conduct a numerical study of the effect of the weak inner product on the oscillatory behavior of the corresponding eigenfunctions. / Cette dissertation est une étude de deux problèmes indépendants provenant du domaine commun de la recherche des méthodes d'éléments finis de frontière pour résoudre des problèmes aux limites elliptiques. Les deux sujets portent principalement sur l'approche de l'opérateur simple couche.Pour le premier projet nous considérons le problème de Laplace-Beltrami Dirichlet sur une sous-surface de la sphère de rayon 1. Nous dérivons et analysons une méthode à équations intégrales du premier type pour résoudre ce problème aux limites. Cette méthode peut être utilisée pour étudier le mouvement de tourbillons ponctuels sur une sphère avec des murs impénétrables; nous comparons notre approche avec d'autres méthodes connues pour ce problème. Nous dérivons rigoureusement des estimations d'erreur pour les équations intégrales dans les espaces de Sobolev appropriés, ce qui donne des estimations globales de l'erreur pour la solution du problème aux limites. De plus, nous appuyons ces résultats théoriques grâce à des simulations numériques obtenues à partir de tests.Le deuxième projet porte sur une stratégie de préconditionnement multigrille pour l'équation de simple couche acoustique en deux dimensions. Tel que proposé dans [6], nous transférons la formulation en termes d'éléments finis de frontière à un produit scalaire plus faible et utilisons par la suite une méthode multigrille V-cycle avec un lisseur de type Richardson. Nous fournissons une analyse complète de convergence pour l'algorithme proposé basée sur un résultat analogue pour l'équation de simple couche correspondant à l'opérateur de Laplace. Des simulations numériques soulignent la performance de l'algorithme. De plus, nous faisons une étude numérique de l'effet du produit scalaire faible sur le comportement oscillatoire des fonctions propres correspondantes.

This thesis is a survey of certain algorithmic problems in group theory and their computational complexities. In particular, it consists of a detailed review of the decidability and complexity of the word and conjugacy problems in several classes of solvable groups, followed by two original results. The first result states that the Conjugacy Problem in wreath products which satisfy certain elementary conditions is decidable in polynomial time. It is largely based on work by Jane Matthews, published in 1969. The second result, based on ideas of Remeslennikov and Sokolov (1970), and Myasnikov, Roman'kov, Ushakov and Vershik (2008) gives a uniform polynomial time algorithm to decide the Conjugacy Problem in free solvable groups. / Cette thèse est une synthèse de certains problèmes algorithmiques dans la thèoriedes groupes et leur complexité computationnelle. Plus particulièrement, elle présenteune revue détaillée de la décidabilité et de la complexité des problèmes du mot et dela conjugaison dans plusieurs classes de groupes solubles, suivie de deux nouveauxrésultats. Le premier résultat énonce que le problème de la conjugaison dans lesproduits couronne qui satisfont certaines conditions élémentaires est décidable entemps polynomial. Elle part d'une publication de Jane Matthews (1969). Le deuxièmerésultat, basé sur des idées de Remeslennikov et Sokolov (1970) et de Myasnikov, Roman'kov,Ushakov et Vershik (2008), présente un algorithme en temps polynomial uniformepour décider le problème de conjugaison dans les groupes solubles libres.

Starting with the work of Mazur, Tate and Teitelbaum, various p-adic analogues of the Birch and Swinnerton-Dyer conjecture have been formulated. The case of an elliptic curve with split multiplicative reduction at the prime p is of special interest. In this so called ``exceptional zero'' case, the order of vanishing of the Mazur-Swinnerton-Dyer p-adic L-function at the central point seems to be one higher than it is in the classical case. Greenberg and Stevens proved results about this conjecture, using properties of the two variable Mazur-Kitagawa p-adic L-function L_p(E, k, s). Their proof relies on the fact that the Mazur-Kitagawa p-adic L-function L_p(E, k, s) vanishes along the central critical line s=k/2, and the fact that the restriction to k=2 is equal to the Mazur-Swinnerton-Dyer p-adic L-function attached to E. In the case where L_p(E, k, k/2) is not identically zero, a formula of Bertolini and Darmon gives a formula for its second derivative at k=2. Their formula is also valid for twists of the L-function by quadratic characters, and their method of proof relies essentially on the fact that the twisting character is quadratic. This thesis looks into possible generalizations of the result of Bertolini and Darmon in the case of twists by Dirichlet characters of higher order. / Depuis les travaux de Mazur, Tate et Teitelbaum, diverses conjectures ont été proposées qui sont analogues à celle de Birch et Swinnerton-Dyer, dans le cas p-adique. Cette thèse traite principalement le cas d'une courbe elliptique à réduction multiplicative déployée en p; ce cas est dit ``exceptionnel''. Dans ce cas, la multiplicité de zéro de la fonction L de Mazur et Swinnerton-Dyer au point central semble être une de plus que ce qui est prédit dans le cas classique. Greenberg et Stevens ont prouvé des résultats concernant cette conjecture en utilisant la fonction L de Mazur et Kitagawa, qui est une fonction L_p(E, k, s) de deux variables. Leur preuve se base sur le fait que la fonction L de Mazur et Kitagawa s'annule sur la ligne centrale critique s=k/2 et qu'elle est égal à la fonction L de Mazur et Swinnerton-Dyer quand k=2. Quand L_p(E, k, k/2) ne s'annule pas, Bertolini et Darmon ont trouvé une formule pour la dérivée seconde de L_p(E, k, k/2) en k=2. Leur formule tient encore quand on tord par un charactère quadratique. Cette thèse considère des généralizations conjecturales des travaux de Bertolini et Darmon lorsque le caractère est d'ordre supérieur à deux.

Pyramidal finite elements can be used as "glue" to combine elements with triangular faces (e.g. tetrahedra) and quadrilateral faces (e.g. hexahedra) in the same mesh. Existing pyramidal finite elements are low order or unsuitable for mixed finite element formulations. In this thesis, two separate families of pyramidal finite elements are constructed. The elements are equipped with unisolvent degrees of freedom and shown to be compatible with existing high order tetrahedral and hexahedral elements. Importantly, the elements are shown to deliver high order approximations and to satisfy a "commuting diagram property", which ensures their suitability for problems whose mixed formulation lies in the spaces of the de Rham complex. It is shown that all pyramidal elements must use non-polynomial basis functions and that this means that the classical theory of finite elements is unable to determine what quadrature methods should be used to assemble stiffness matrices when using pyramids. This problem is resolved by extending the classical theory and a quadrature scheme appropriate for high order pyramidal elements is recommended. Finally, some numerical experiments using pyramidal elements are presented. / Les éléments finis pyramidaux peuvent servir comme «colle» pour combiner des éléments avec faces triangulaires (p. ex. tétraèdres) et avec faces quadrilaterales (p. ex. hexaèdres) dans un même maillage. Les éléments finis pyramidaux qui existent présentement sont soit de bas-ordre ou ne sont pas convenables pour les formulations mixtes d'éléments finis. Dans cette thèse, deux familles d'éléments finis pyramidaux sont construites. Les éléments sont équipés de degrés de libertés unisolvents et on démontre qu'ils sont compatibles avec les éléments pré-existantes triangulaires et quadrilaterales d'ordres élevés. On démontre notamment que les éléments produisent des approximations d'ordres élevés et satisfassent une «propriété de diagramme commutatif». Ceci assure que les éléments sont convenables pour des problèmes avec formulation mixte dans les espaces du complexe de Rham. On démontre que tous les éléments pyramidaux doivent utiliser des fonctions de base non-polynômes et que conséquemment la théorie classique des éléments finis ne peut pas déterminer quelles méthodes de quadrature devrait être employées pour assembler des matrices de rigidité lorsque les pyramides sont utilisées. Le problème est résolu en élargissant la théorie classique et une méthode de quadrature appropriée pour les éléments finis pyramidaux est suggérée. Finalement, des simulations numériques avec éléments pyramidaux sont présentées.

We define derived categories over arbitrary abelian categories and then study the particular case of the bounded derived category of coherent sheaves over a smooth projective curve. / On définit d'abord la catégorie dérivée d'une catégorie abélienne quelconque et ensuite on étudie le cas particulier de la catégorie dérivée bornée des faisceaux cohérents sur une courbe projective non-singulière.

Many problems which seek to schedule, sequence, or time-table a set of events subject to given constraints can be modelled as graph colouring problems. In this thesis, we study the edge and total colouring problems which, like all NP problems, can be formulated as integer programs and subjected to a two-pronged attack: we first solve the fractional relaxation and then use this solution to solve or obtain an approximation of the solution of the integer program. We focus on the complexity of solving the fractional relaxations of the integer programs for the edge and total colouring problems. For each ε > 0, we give a linear time algorithm which determines the fractional chromatic index of a graph $G$ with maximum degree at least ε|G|. For graphs with large maximum degree, this improves on Padberg and Rao's polynomial time algorithm to determine the fractional chromatic index for general graphs. Both algorithms rely on a theorem of Edmonds showing that the fractional chromatic index of a graph is determined by its maximum degree and overfull subgraphs. Our algorithm exploits the fact that overfull subgraphs are related to small cuts in a graph and have simple intersection patterns when the maximum degree is large. The complexity of determining the fractional total colouring number is currently unresolved. We focus on graphs with large maximum degree, applying the very successful techniques for fractional edge colouring to fractional total colouring. We characterize graphs with maximum degree Δ whose fractional total colouring number is Δ + 2, sharpening a result of Kilakos and Reed who showed it is between Δ + 1 and Δ+2. We show graphs whose fractional total colouring number is less than Δ + 2 have a special fractional vertex colouring which extends to a fractional total colouring using less than Δ + 2 colours. We extend these ideas by giving necessary conditions a fractional vertex ß-colouring must satisfy to be extendable to a fractional total ß-colouring. We conjecture these conditions are sufficient when G satisfies Δ > ½|G|. We verify a special case of this conjecture by giving a polynomial time algorithm which constructs an optimal fractional total colouring of a graph G with maximum degree at least ¾|G| and containing no overfull subgraphs. / De nombreux problèmes qui consistent à programmer, ordonner, ou encore planifier un ensemble d'événements étant données des contraintes peuvent être modilisés par un probème de coloriage de graphe. Dans cette thèse, nous étudions les problèmes du coloriage d'arêtes et du coloriage total, qui comme tous les problèmes NP, peuvent être formulés sous forme de programmation entière, et traités avec une approche en deux temps: on résoud d'abord la relaxation fractionnaire du programme entier, puis on utilise la solution du programme relaché pour déterminer ou approximer la solution du programme entier. Nous nous concentrons sur la complexité de la relaxation fractionnaire pour les problèmes du coloriage d'arêtes et du coloriage total.Pour tout ε > 0, nous donnons un algorithme linéaire qui détermine l'indice chromatique fractionnaire d'un graphe $G$ dont le degré maximal est au moins ε|G|. Pour les graphes dont le degré maximum est grand, ceci améliore l'algorithme polynomial de Padberg et Rao pour l'indice chromatique fractionnaire. Les deux algorithmes reposent sur un théorème dû à Edmonds qui montre que l'indice chromatique fractionnaire est déterminé par le degré maximum et les sous-graphes overfull. Notre algorithme exploite le fait que les sous-graphes overfull sont reliés aux petites coupes, et ont des motifs d'intersections simples lorsque le degré maximum est grand. La complexité du problème de coloriage total fractionnaire est toujours inconnue. Nous nous concentrons sur les graphes dont le degré maximum est grand, et appliquons au coloriage total fractionnaire les le techniques qui se sont avérées fructueuses pour le problème de coloriage d'arêtes. Nous charactérisons les graphes dont le degré maximum est Δ, et dont le nombre chromatique total fractionnaire est Δ+2, ce qui améliore un résultat de Kilakos et Reed qui ont montré qu'il est compris entre Δ+1 et Δ+2. Nous montrons que les graphes dont le nombre chromatique total fractionnaire est moins de Δ+2 possèdent un coloriage fractionnaire des noeuds qui s'étend en un coloriage total fractionnaire utilisant moins de Δ+2 couleurs. Nous généralisons ces idées en donnant des conditions nécéssaires que doit remplir un ß-coloriage des noeuds pour pouvoir être étendu en un ß-coloriage total fractionnaire. Nous conjecturons que ces conditions sont suffisantes lorsque Δ > ½|G|. Nous vérifions un cas particulier de cette conjecture en concevant un algorithme polynomial qui construit un coloriage total fractionnaire pour un graphe G dont le degré maximum est au moins ¾|G| et qui ne contient pas de sous-graphe overfull.

We consider the zeros of a Neumann eigenfunction φ_λ on an analytic domain­solving the equation -∆ φ_λ =λ^2 φ_λ. We count the number n(λ;H) of intersection points of the nodal lines of φ_λ (components of the nodal set) with a fixed real analytic curve H contained in the interior of the domain. We identify a large family of curves H, namely C^ω-homotopic curves to the boundary, for which the nodal intersection bound for n(λ;H) is O(λ). This bound is consistent with Yau's famous conjecture on the measure of the nodal set. / On considère les zéros d'une fonction propre de Neumann φ_λ d'un domaine analytique ­, solution de l'équation -∆ φ_λ =λ^2 φ_λ. On compte le nombre d'intersectionn (λ;H) de lignes nodales des fonctions propres de Neumann (composantes de l'ensemble nodal) avec une courbe fixe analytique réelle H contenue à l'intérieur du domaine. On identifie explicitement une grande famille de courbes pour lesquelles une borne pour l'intersection nodale n(λ;H) est O(λ). Cette borne est compatible avec la conjecture célèbre de Yau sur la mesure de l'ensemble nodal.

In statistical applications of hidden Markov models (HMMs), one may have no knowledge of the number of hidden states (or order) of the model needed to be able to accurately represent the underlying process of the data. The problem of estimating the number of states of the HMM is thus a task of major importance. We begin with a literature review of the major developments in the problem of order estimation for HMMs. We then propose a new penalized quasi-likelihood method for estimating the number of hidden states, which makes use of the fact that the marginal distribution of the HMM observations is a finite mixture model. Starting with a HMM with a large number of states, the method obtains a model of lower order by clustering and merging similar states of the model through two penalty functions. We study some of the asymptotic properties of the proposed method and present a numerical procedure for its implementation. The performance of the new method is assessed via extensive simulation studies for normal and Poisson HMMs. The new method is more computationally efficient than existing methods, such as AIC and BIC, as the order of the model is determined in a single optimization. We conclude with applications of the method to two real data sets. / Dans les applications des chaînes de Markov cachées (CMC), il se peut que les statisticiens n'aient pas l'information sur le nombre d'états (ou ordre) nécessaires pour représenter le processus. Le problème d'estimer le nombre d'états du CMC est ainsi une tâche d'importance majeure. Nous commençons avec une revue de littérature des développements majeurs dans le problème d'estimation de l'ordre d'un CMC. Nous proposons alors une nouvelle méthode de la quasi-vraisemblance pénalisée pour estimer l'ordre dans des CMC. Cette méthode utilise le fait que la distribution marginale des observations CMC est un mélange fini. La méthode débute avec un CMC avec un grand nombre d'états et obtient un modèle d'ordre inférieur en regroupant et fusionnant les états à l'aide de deux fonctions de pénalité. Nous étudions certaines propriétés asymptotiques de la méthode proposée et présentons une procédure numérique pour sa mise en œuvre. La performance est évaluée via des simulations extensives. La nouvelle méthode est plus efficace qu'autres méthodes, comme CIA et CIB, comme l'ordre du modèle est déterminé dans une seule optimisation. Nous concluons avec l'application de la méthode à deux vrais jeux de données.

Objectives: Genetic association studies have shown that genes play a role in the incidence of attention deficit hyperactivity disorder (ADHD) in children. However, the relationship between genes and response to medication (methylphenidate) has not been studied extensively, with very few findings and difficulty in replication. Possible reasons for the lack of findings could be due to the difficulty in defining a valid, objective measure of response to treatment. Furthermore, traditional statistical methods may have shortcomings when used in genetic association studies. Our objectives are: 1) compare two methods used in genetic association studies and 2) define a phenotype for response to treatment that can improve the quality of a genetic analysis.Methods: From a family study (n=416) with ADHD children, we construct a response to treatment phenotype using a latent profile analysis (LPA) clustering approach. This LPA phenotype is based on the RASS, and accelerometer (Actiwatch) data. Using the LPA phenotype and another phenotype based on clinical judgement (Clinical Consensus Rating), we perform a genetic association analysis for each phenotype individually. For the genetic analysis, we use both a case-control design (logistic regression) and a family based design (FBAT). The genes used in the study are candidate genes, known to be associated with the diagnosis of ADHD. Some notable genes include the dopamine receptor (DRD3, DRD4), dopamine transporter (DAT) and latrophilin (LPHN3).Results: Several SNPs were found to be associated with both the LPA response to medication variable and the Clinical Consensus Rating variable (CCR). Overall, the phenotype based on latent profile analysis performed better than the phenotype based on CCR, and showed highly significant findings, which the CCR was not able to do (p = 0.000189 vs p = 0.026691). The FBAT analysis approach, although providing the benefit of being immune to population stratification, was not as powerful as the logistic regression approach. This was because of smaller sample sizes due to uninformative heterozygous parents. Discussion: Our analysis showed that the way a phenotype is defined is very important to the quality of the analysis. The phenotype we constructed performed better likely due to its ability to separate heterogeneous groups of subjects. Both methods of genetic analysis have their shortcomings, and it is advisable to use both in a genetic association study. Some shortcomings of this study include limited sample size, which limited our power, and prevented alternative methods such as a haplotype analysis. / Objectifs: Des études d'association génétique ont démontré que les gènes affectent l'incidence du trouble déficitaire de l'attention avec ou sans hyperactivité (TDAH) chez les enfants. Cependant, la relation entre les gènes et la réponse aux médicaments (méthylphénidate) n'a pas été étudiée de façon approfondie. Les découvertes en la matière sont rares et difficiles à répliquer. L'absence de résultats pourrait s'expliquer par la difficulté de définir une mesure valide et objective pour quantifier la réponse au traitement. De plus, les méthodes statistiques conventionnelles pourraient avoir des lacunes dans le contexte des études d'association génétique. Nos objectifs sont les suivants: 1) comparer deux méthodes utilisées dans les études d'association génétique et 2) définir un phénotype pour la réponse au traitement ayant le potentiel d'améliorer la qualité des analyses génétiques.Méthodes: À partir d'une étude de famille (n = 416) avec des enfants TDAH, nous concevons une réponse à un phénotype de traitement à l'aide d'une approche de groupement fondée sur une analyse de profil latent (APL). Le phénotype APL est basé sur des données de RASS et d'accéléromètre (Actiwatch). À partir du phénotype APL et d'un autre phénotype basé sur un jugement clinique (évaluation de consensus clinique), nous procédons à une analyse d'association génétique pour chaque phénotype séparément. Aux fins de l'analyse génétique, nous utilisons à la fois un plan cas témoins (régression logistique) et un plan basé sur la famille (FBAT). Les gènes employés dans l'étude sont des gènes candidats reconnus pour leur association avec le diagnostic de TDAH, notamment le récepteur de la dopamine (DRD3, DRD4), le latrophilin (LPHN3) et le transporteur de la dopamine (DAT).Résultats: Nous avons détecté une association entre plusieurs SNPs et la réponse APL à la variable médication ainsi que l'évaluation du consensus clinique (CCR). Dans l'ensemble, le phénotype basé sur l'analyse du profil latent a surpassé le phénotype basé sur l'évaluation du consensus clinique (CCR) par sa capacité de produire des résultats très significatifs (p = 0,000189 contre p = 0,026691). L'approche d'analyse FBAT, malgré son insensibilité à la stratification de la population, n'était pas aussi puissante que la méthode de régression logistique, en raison de la taille restreinte des échantillons, expliquée par des parents hétérozygotes non-informatifs.Discussion: Notre analyse a démontré que la façon dont le phénotype est défini affecte sérieusement la qualité de l'analyse. Le phénotype que nous avons conçu a offert un meilleur rendement probablement en raison de sa capacité à distinguer des groupes hétérogènes de sujets. Les deux méthodes d'analyse génétique ont leurs défauts: il est donc conseillé de les utiliser conjointement dans une étude d'association génétique. Les lacunes de cette étude comprennent entre autres la taille limitée de l'échantillon, qui a limité la puissance et empêché le recours à d'autres méthodes telle l'analyse des haplotypes.