Algebraic certificates for graph problems

Certificats algébriques pour des problèmes de graphes Cette thèse s’intéresse à certains liens étroits qui existent entre combinatoire et algèbre. Plus spécifiquement, nous proposons de nouvelles façons d’aborder des problèmes de combinatoire sur les graphes dans la logique des travaux de De Loera. Etant donné un entier k ≥ 3 et un graphe G, la question de savoir si G admet une k-coloration, c’est-à-dire un étiquetage des sommets avec des entiers compris entre 1 et k (appelés “couleurs”)tels que deux sommets adjacents n’ont pas la même couleur, constitue un problème difficile engénéral (Sans indication sur G, le problème est NP-Complet.). A l’inverse, comment peut-on prouversimplement qu’un certain graphe G n’admet aucune k-coloration (c’est-à-dire que χ(G), le nombreminimal de couleurs tel qu’il existe une χ(G)-coloration de G vérifie χ(G) > k) ? Une telle preuve, si elle existe, est appelée certificat de non k-colorabilité. La recherche d’un certificat “canonique”, en ce sens qu’il aurait la même “forme” quel que soit le graphe, constitue le point de départ de cette thèse. Nullstellensatz et graphes puissance : La première contribution importante de cette thèse est la définition d’une extension naturelle de G, notée p^G avec p un nombre premier, dans laquelle un certificat Nullstellensatz de non p-colorabilité pour G admet une interprétation combinatoire en termes de cliques. Ce graphe a de nombreuses bonnes propriétés, notamment :i) G ⊆ p^Gii) χ(G) = p ⇔ χ(p^G ) = p. Peut-on généraliser ce résultat au cas d’un nombre non premier de couleurs ? Lorsque k = p^ℓavec p premier et ℓ ≥ 2, il existe un unique corps fini (à isomorphisme près) à k éléments noté F_k. Cela nous permet de définir de façon similaire un graphe {F_k}^G et on retrouve les mêmes propriétés. Dans le cas où le nombre de couleurs est une puissance non triviale d’un nombre premier (k = p^ℓavec ℓ ≥ 2), on dispose de deux objets : {Z_k}^G et {F_k}^G . Ces graphes sont-ils isomorphes ? Nous montrons que la réponse est non en général. Ces graphes puissance (“power graphs”) ont de nombreuses autres bonnes propriétés que nous avons étudiées durant cette thèse. Fourier : La recherche de certificats Nullstellensatz dans les graphes puissance nous a conduit à l’étude des transformées de Fourier discrètes. Il existe en effet un lien étroit entre les deux concepts. Cela nous a conduit à l’élaboration d’une méthode originale de preuve de k-colorabilité. Le principe de cette preuve s’applique particulièrement bien aux graphes dont les arêtes se décomposent naturellement en deux sous-graphes sur le même ensemble de sommets. Par exemple, nous avons pu donner une nouvelle preuve de la “cycle + triangle” conjecture d’Erdös, démontrée pour la première fois par Fleischner et Steibitz en 1992.