Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Prime Rational Functions and Integral Polynomials

Let f(x) be a complex rational function. In this work, we study conditions under which f(x) cannot be written as the composition of two rational functions which are not units under the operation of function composition. In this case, we say that f(x) is prime. We give sufficient conditions for complex rational functions to be prime in terms of their degrees and their critical values, and we derive some conditions for the case of complex polynomials. We consider also the divisibility of integral polynomials, and we present a generalization of a theorem of Nieto. We show that if f(x) and g(x) are integral polynomials such that the content of g divides the content of f and g(n) divides f(n) for an integer n whose absolute value is larger than a certain bound, then g(x) divides f(x) in Z[x]. In addition, given an integral polynomial f(x), we provide a method to determine if f is irreducible over Z, and if not, find one of its divisors in Z[x].

Socio-demographic factors, smoking, symptoms, morbidities and pulmonary function and quality of life in individuals with a heavy smoking history

Objective: To determine which socio-demographic, exposure, morbidity and symptom variables are associated with health-related quality of life among former and current heavy smokers. Methods: Cross sectional data from 2537 participants were studied. All participants were at ≥2% risk of developing lung cancer within 6 years. Linear and logistic regression models utilizing a multivariable fractional polynomial selection process identified variables associated with health-related quality of life, measured by the EQ-5D. Results: Upstream and downstream associations between smoking cessation and higher health-related quality of life were evident. Significant upstream associations, such as education level and current working status and were explained by the addition of morbidities and symptoms to regression models. Having arthritis, decreased forced expiratory volume in one second, fatigue, poor appetite or dyspnea were most highly and commonly associated with decreased HRQoL. Discussion: Upstream factors such as educational attainment, employment status and smoking cessation should be targeted to prevent decreased health-related quality of life. Practitioners should focus treatment on downstream factors, especially symptoms, to improve health-related quality of life.

Reduced power output in skeletal muscles devoid of skMLCK: RLC phosphorylation contributes to peak performance

Regulatory light chain (RLC) phosphorylation in fast twitch muscle is catalyzed by skeletal myosin light chain kinase (skMLCK), a reaction known to increase muscle force, work, and power. The purpose of this study was to explore the contribution of RLC phosphorylation on the power of mouse fast muscle during high frequency (100 Hz) concentric contractions. To determine peak power shortening ramps (1.05 to 0.90 Lo) were applied to Wildtype (WT) and skMLCK knockout (skMLCK-/-) EDL muscles at a range of shortening velocities between 0.05-0.65 of maximal shortening velocity (Vmax), before and after a conditioning stimulus (CS). As a result, mean power was increased to 1.28 ± 0.05 and 1.11 ± .05 of pre-CS values, when collapsed for shortening velocity in WT and skMLCK-/-, respectively (n = 10). In addition, fitting each data set to a second order polynomial revealed that WT mice had significantly higher peak power output (27.67 ± 1.12 W/ kg-1) than skMLCK-/- (25.97 ± 1.02 W/ kg-1), (p < .05). No significant differences in optimal velocity for peak power were found between conditions and genotypes (p > .05). Analysis with Urea Glycerol PAGE determined that RLC phosphate content had been elevated in WT muscles from 8 to 63 % while minimal changes were observed in skMLCK-/- muscles: 3 and 8 %, respectively. Therefore, the lack of stimulation induced increase in RLC phosphate content resulted in a ~40 % smaller enhancement of mean power in skMLCK-/-. The increase in power output in WT mice suggests that RLC phosphorylation is a major potentiating component required for achieving peak muscle performance during brief high frequency concentric contractions.

Sur l'inégalité de Visser

Soit p un polynôme d'une variable complexe z. On peut trouver plusieurs inégalités reliant le module maximum de p et une combinaison de ses coefficients. Dans ce mémoire, nous étudierons principalement les preuves connues de l'inégalité de Visser. Nous montrerons aussi quelques généralisations de cette inégalité. Finalement, nous obtiendrons quelques applications de l'inégalité de Visser à l'inégalité de Chebyshev.

Problème centre-foyer et application

Dans ce mémoire, nous étudions le problème centre-foyer sur un système polynomial. Nous développons ainsi deux mécanismes permettant de conclure qu’un point singulier monodromique dans ce système non-linéaire polynomial est un centre. Le premier mécanisme est la méthode de Darboux. Cette méthode utilise des courbes algébriques invariantes dans la construction d’une intégrale première. La deuxième méthode analyse la réversibilité algébrique ou analytique du système. Un système possédant une singularité monodromique et étant algébriquement ou analytiquement réversible à ce point sera nécessairement un centre. Comme application, dans le dernier chapitre, nous considérons le modèle de Gauss généralisé avec récolte de proies.

Représentation d'un polynôme par un circuit arithmétique et chaînes additives

Un circuit arithmétique dont les entrées sont des entiers ou une variable x et dont les portes calculent la somme ou le produit représente un polynôme univarié. On assimile la complexité de représentation d'un polynôme par un circuit arithmétique au nombre de portes multiplicatives minimal requis pour cette modélisation. Et l'on cherche à obtenir une borne inférieure à cette complexité, et cela en fonction du degré d du polynôme. A une chaîne additive pour d, correspond un circuit arithmétique pour le monôme de degré d. La conjecture de Strassen prétend que le nombre minimal de portes multiplicatives requis pour représenter un polynôme de degré d est au moins la longueur minimale d'une chaîne additive pour d. La conjecture de Strassen généralisée correspondrait à la même proposition lorsque les portes du circuit arithmétique ont degré entrant g au lieu de 2. Le mémoire consiste d'une part en une généralisation du concept de chaînes additives, et une étude approfondie de leur construction. On s'y intéresse d'autre part aux polynômes qui peuvent être représentés avec très peu de portes multiplicatives (les d-gems). On combine enfin les deux études en lien avec la conjecture de Strassen. On obtient en particulier de nouveaux cas de circuits vérifiant la conjecture.

Modélisation procédurale par composants

Le réalisme des images en infographie exige de créer des objets (ou des scènes) de plus en plus complexes, ce qui entraîne des coûts considérables. La modélisation procédurale peut aider à automatiser le processus de création, à simplifier le processus de modification ou à générer de multiples variantes d'une instance d'objet. Cependant même si plusieurs méthodes procédurales existent, aucune méthode unique permet de créer tous les types d'objets complexes, dont en particulier un édifice complet. Les travaux réalisés dans le cadre de cette thèse proposent deux solutions au problème de la modélisation procédurale: une solution au niveau de la géométrie de base, et l’autre sous forme d'un système général adapté à la modélisation des objets complexes. Premièrement, nous présentons le bloc, une nouvelle primitive de modélisation simple et générale, basée sur une forme cubique généralisée. Les blocs sont disposés et connectés entre eux pour constituer la forme de base des objets, à partir de laquelle est extrait un maillage de contrôle pouvant produire des arêtes lisses et vives. La nature volumétrique des blocs permet une spécification simple de la topologie, ainsi que le support des opérations de CSG entre les blocs. La paramétrisation de la surface, héritée des faces des blocs, fournit un soutien pour les textures et les fonctions de déplacements afin d'appliquer des détails de surface. Une variété d'exemples illustrent la généralité des blocs dans des contextes de modélisation à la fois interactive et procédurale. Deuxièmement, nous présentons un nouveau système de modélisation procédurale qui unifie diverses techniques dans un cadre commun. Notre système repose sur le concept de composants pour définir spatialement et sémantiquement divers éléments. À travers une série de déclarations successives exécutées sur un sous-ensemble de composants obtenus à l'aide de requêtes, nous créons un arbre de composants définissant ultimement un objet dont la géométrie est générée à l'aide des blocs. Nous avons appliqué notre concept de modélisation par composants à la génération d'édifices complets, avec intérieurs et extérieurs cohérents. Ce nouveau système s'avère général et bien adapté pour le partionnement des espaces, l'insertion d'ouvertures (portes et fenêtres), l'intégration d'escaliers, la décoration de façades et de murs, l'agencement de meubles, et diverses autres opérations nécessaires lors de la construction d'un édifice complet.

Superintégrabilité avec intégrales d'ordre trois, algèbres polynomiales et mécanique quantique supersymétrique

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Optimisation quadratique en variables binaires : quelques résultats et techniques

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Systèmes superintégrables avec spin et intégrales du mouvement d’ordre deux

Ce mémoire est une partie d’un programme de recherche qui étudie la superintégrabilité des systèmes avec spin. Plus particulièrement, nous nous intéressons à un hamiltonien avec interaction spin-orbite en trois dimensions admettant une intégrale du mouvement qui est un polynôme matriciel d’ordre deux dans l’impulsion. Puisque nous considérons un hamiltonien invariant sous rotation et sous parité, nous classifions les intégrales du mouvement selon des multiplets irréductibles de O(3). Nous calculons le commutateur entre l’hamiltonien et un opérateur général d’ordre deux dans l’impulsion scalaire, pseudoscalaire, vecteur et pseudovecteur. Nous donnons la classification complète des systèmes admettant des intégrales du mouvement scalaire et vectorielle. Nous trouvons une condition nécessaire à remplir pour le potentiel sous forme d’une équation différentielle pour les cas pseudo-scalaire et pseudo-vectoriel. Nous utilisons la réduction par symétrie pour obtenir des solutions particulières de ces équations.

On some Density Theorems in Number Theory and Group Theory

Gowers, dans son article sur les matrices quasi-aléatoires, étudie la question, posée par Babai et Sos, de l'existence d'une constante $c>0$ telle que tout groupe fini possède un sous-ensemble sans produit de taille supérieure ou égale a $c|G|$. En prouvant que, pour tout nombre premier $p$ assez grand, le groupe $PSL_2(\mathbb{F}_p)$ (d'ordre noté $n$) ne posséde aucun sous-ensemble sans produit de taille $c n^{8/9}$, il y répond par la négative. Nous allons considérer le probléme dans le cas des groupes compacts finis, et plus particuliérement des groupes profinis $SL_k(\mathbb{Z}_p)$ et $Sp_{2k}(\mathbb{Z}_p)$. La premiére partie de cette thése est dédiée à l'obtention de bornes inférieures et supérieures exponentielles pour la mesure suprémale des ensembles sans produit. La preuve nécessite d'établir préalablement une borne inférieure sur la dimension des représentations non-triviales des groupes finis $SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ et $Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Notre théoréme prolonge le travail de Landazuri et Seitz, qui considérent le degré minimal des représentations pour les groupes de Chevalley sur les corps finis, tout en offrant une preuve plus simple que la leur. La seconde partie de la thése à trait à la théorie algébrique des nombres. Un polynome monogéne $f$ est un polynome unitaire irréductible à coefficients entiers qui endengre un corps de nombres monogéne. Pour un nombre premier $q$ donné, nous allons montrer, en utilisant le théoréme de densité de Tchebotariov, que la densité des nombres premiers $p$ tels que $t^q -p$ soit monogéne est supérieure ou égale à $(q-1)/q$. Nous allons également démontrer que, quand $q=3$, la densité des nombres premiers $p$ tels que $\mathbb{Q}(\sqrt[3]{p})$ soit non monogéne est supérieure ou égale à $1/9$.

Estimation utilisant les polynômes de Bernstein

Ce mémoire porte sur la présentation des estimateurs de Bernstein qui sont des alternatives récentes aux différents estimateurs classiques de fonctions de répartition et de densité. Plus précisément, nous étudions leurs différentes propriétés et les comparons à celles de la fonction de répartition empirique et à celles de l'estimateur par la méthode du noyau. Nous déterminons une expression asymptotique des deux premiers moments de l'estimateur de Bernstein pour la fonction de répartition. Comme pour les estimateurs classiques, nous montrons que cet estimateur vérifie la propriété de Chung-Smirnov sous certaines conditions. Nous montrons ensuite que l'estimateur de Bernstein est meilleur que la fonction de répartition empirique en terme d'erreur quadratique moyenne. En s'intéressant au comportement asymptotique des estimateurs de Bernstein, pour un choix convenable du degré du polynôme, nous montrons que ces estimateurs sont asymptotiquement normaux. Des études numériques sur quelques distributions classiques nous permettent de confirmer que les estimateurs de Bernstein peuvent être préférables aux estimateurs classiques.

Formules de quadrature pour les fonctions entières de type exponentiel

Ce mémoire contient quelques résultats sur l'intégration numérique. Ils sont liés à la célèbre formule de quadrature de K. F. Gauss. Une généralisation très intéressante de la formule de Gauss a été obtenue par P. Turán. Elle est contenue dans son article publié en 1948, seulement quelques années après la seconde guerre mondiale. Étant données les circonstances défavorables dans lesquelles il se trouvait à l'époque, l'auteur (Turán) a laissé beaucoup de détails à remplir par le lecteur. Par ailleurs, l'article de Turán a inspiré une multitude de recherches; sa formule a été étendue de di érentes manières et plusieurs articles ont été publiés sur ce sujet. Toutefois, il n'existe aucun livre ni article qui contiennent un compte-rendu détaillé des résultats de base, relatifs à la formule de Turán. Je voudrais donc que mon mémoire comporte su samment de détails qui puissent éclairer le lecteur tout en présentant un exposé de ce qui a été fait sur ce sujet. Voici comment nous avons organisé le contenu de ce mémoire. 1-a. La formule de Gauss originale pour les polynômes - L'énoncé ainsi qu'une preuve. 1-b. Le point de vue de Turán - Compte-rendu détaillé des résultats de son article. 2-a. Une formule pour les polynômes trigonométriques analogue à celle de Gauss. 2-b. Une formule pour les polynômes trigonométriques analogue à celle de Turán. 3-a. Deux formules pour les fonctions entières de type exponentiel, analogues à celle de Gauss pour les polynômes. 3-b. Une formule pour les fonctions entières de type exponentiel, analogue à celle de Turán. 4-a. Annexe A - Notions de base sur les polynômes de Legendre. 4-b. Annexe B - Interpolation polynomiale. 4-c. Annexe C - Notions de base sur les fonctions entières de type exponentiel. 4-d. Annexe D - L'article de P. Turán.

Amplification de l'amplitude : analyse et applications

Ce mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement.