Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes.... Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge....

Ce document présente une vue synthétique de mes travaux de recherche menés ces cinq dernières années, au sein du LaBRI.<br />Les activités de recherche d'un enseignant-chercheur ne s'inscrivent pas souvent dans un plan de recherche soigneusement pensé. Elles évoluent en fonction de multiples impondérables, dont notamment les rencontres avec d'autres chercheurs ou encore les opportunités ``stratégiques'' de financement. De ce fait, il n'est pas toujours facile de dégager un fil conducteur qui permette de regrouper un ensemble des résultats obtenus ``au fil de l'eau'' sans avoir recours à des raccourcis un peu ``artificiels''. <br /><br />Lorsque je me suis efforcé de dégager un point commun à mes travaux, je me suis aperçu que des objets mathématiques bien particuliers n'étaient jamais très loin de mes activités: les groupes cycliques finis. En creusant un peu plus cette perception, il m'est apparu que mes travaux accordent une place considérable à des graphes élémentaires associés aux groupes cycliques, dits graphes ou encore webs.<br /><br />Ce document est donc consacré à la mise en valeur des multiples facettes de ces graphes. ``Facettes'' est ici à double sens, puisqu'une partie conséquente de mes résultats est précisément dédiée à la détermination des facettes de certains polytopes associés aux graphes!<br /><br />Sur la forme, les preuves ont été omises afin d'alléger le texte, à l'exception de quelques preuves sélectionnées pour leur brièveté et pour la pertinence du résultat qu'elles procurent. Des hyperliens pointent vers la version anglaise des preuves manquantes, telles qu'elles figurent dans le recueil d'articles en annexe. Pour faciliter également la lecture, l'index à la fin de l'ouvrage redonne toutes les principales définitions.<br /><br />Sur le fond, ce document est structuré de la manière suivante.<br /><br />Le premier chapitre est consacré aux principaux résultats connus sur les graphes parfaits. Ceci permet de définir les objets mathématiques utilisés par la suite, et de rappeler l'extraordinaire richesse conceptuelle des graphes parfaits.<br /><br />Dans le second chapitre, nous abordons un raffinement de la coloration usuelles des graphes, appelé ``coloration circulaire''. Cette coloration est à l'origine d'une généralisation récente des graphes parfaits: les ``graphes circulaires-parfaits''. Nous étudions la possibilité d'une caractérisation analogue à celles des graphes parfaits, que ce soit par sous-graphes exclus ou bien polyédrale. <br /><br />Dans le troisième chapitre, nous nous intéressons à une généralisation naturelle des webs: ``les graphes quasi-adjoints''. Il s'agit d'une sous-famille des graphes sans griffe, et à ce titre, l'étude de leur polytope des stables est de première importance.<br /><br />Dans le quatrième chapitre, nous menons des investigations directes sur le polytope des stables des graphes sans griffe.<br /><br />La conclusion est donnée dans le dernier et cinquième chapitre, qui contient également une brève présentation de quelques résultats préliminaires quant au calcul en temps polynomial du nombre circulaire-chromatique des graphes circulaires-parfaits et au calcul du nombre de stabilité des graphes quasi-adjoints. Tout repose sur l'introduction d'un nouveau polytope construit à partir des webs ...

L'objectif visé dans ce travail consiste en la présentation du polynôme de Tutte, et ce à la manière de son idéateur, M. William Thomas Tutte. Nous dressons également un portrait de l'éventail des applications possibles de ce polynôme, notamment en théorie des graphes, en physique de la mécanique statistique, de même qu'en théorie des noeuds. À cet égard, nous faisons la démonstration que le polynôme de Tutte admet une spécialisation en terme de la fonction de partition d'un modèle de Potts, ainsi qu'en terme du polynôme de Jones d'un entrelacs alterné. Ce travail se conclut par une série de calculs sur les graphes 2-connexes et connexes, pour lesquels nous utilisons une équation fonctionnelle bien connue de la théorie des espèces, de même que des fonctions de poids bloc-multiplicatives. Ces calculs nous ont permis, entre autres, d'établir l'égalité entre le poids total des λ-flots à flux non nuls sur les graphes 2-connexes à quatre sommets et le nombre de marelles de longueur trois dans l'hypercube de dimension λ -1. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Polynôme de Tutte, Polynôme chromatique, Polynôme de flot, Polynôme de fiabilité, Polynôme de Jones, Entrelacs alterné, Fonction de partition, Modèle de Potts, Graphes 2-connexes.

La science des réseaux est notamment à la recherche de modèles mathématiques capables de reproduire le comportement de systèmes complexes empiriques. Cependant, la représentation usuelle, le graphe, est parfois inadéquate étant donné sa limitation à encoder uniquement les relations par paires. De nombreux travaux récents suggèrent que l'utilisation de l'hypergraphe, une généralisation décrivant les interactions d'ordre supérieur (plus de deux composantes), permet d'expliquer des phénomènes auparavant incompris avec le graphe. Or, la structure de ces réseaux complexes est rarement ou difficilement observée directement. De fait, on mesure plutôt une quantité intermédiaire, comme la fréquence de chaque interaction, pour ensuite reconstruire la structure originale. Bien que de nombreuses méthodes de reconstruction de graphes aient été développées, peu d'approches permettent de retrouver les interactions d'ordre supérieur d'un système complexe. Dans ce mémoire, on développe une nouvelle approche de reconstruction pouvant déceler les interactions connectant trois noeuds parmi des observations dyadiques bruitées. Basée sur l'inférence bayésienne, cette méthode génère la distribution des hypergraphes les plus plausibles pour un jeu de données grâce à un algorithme de type Metropolis-Hastings-within-Gibbs, une méthode de Monte-Carlo par chaînes de Markov. En vue d'évaluer la pertinence d'un modèle d'interactions d'ordre supérieur pour des observations dyadiques, le modèle d'hypergraphe développé est comparé à un second modèle bayésien supposant que la structure sous-jacente est un graphe admettant deux types d'interactions par paires. Les résultats obtenus pour des hypergraphes synthétiques et empiriques indiquent que la corrélation intrinsèque à la projection d'interactions d'ordre supérieur améliore le processus de reconstruction lorsque les observations associées aux interactions dyadiques et triadiques sont semblables. / Network science is looking for mathematical models capable of reproducing the behavior of empirical complex systems. However, the usual representation, the graph, is sometimes inadequate given its limitation to encode only pairwise relationships. Many recent works suggest that the use of the hypergraph, a generalization describing higher-order interactions (more than two components), allows to explain phenomena previously not understood with graphs. However, the structure of these complex networks is seldom or hardly observed directly. Instead, we measure an intermediate quantity, such as the frequency of each interaction, and then reconstruct the original structure. Although many graph reconstruction methods have been developed, few approaches recover the higher-order interactions of a complex system. In this thesis, we develop a new reconstruction approach which detects interactions connecting three vertices among noisy dyadic observations. Based on Bayesian inference, this method generates the distribution of the most plausible hypergraphs for a dataset using a Metropolis-Hastings-within-Gibbs algorithm, a Markov chain Monte Carlo method. In order to evaluate the relevance of a higher-order interaction model for dyadic observations, the developed hypergraph model is compared to a second Bayesian model assuming that the underlying structure is a graph admitting two types of pairwise interactions. Results for synthetic and empirical hypergraphs indicate that the intrinsic correlation to the projection of higher-order interactions improves the reconstruction process when observations associated with dyadic and triadic interactions are similar.

Dans ce mémoire, nous allons nous intéresser aux graphes obtenus en considérant l'image inverse d'un polygone (en particulier d'un segment) dont les sommets sont les valeurs critiques d'un polynôme. Nous allons commencer par des rappels de notions préliminaires sur les polynômes complexes, la topologie algébrique et la théorie des espèces. Ensuite, nous allons voir le lien entre les arbres plans bicolorés et les polynômes de Shabat, qui sont des polynômes ayant au plus deux valeurs critiques, mis à part l'infini. Subséquemment, nous étudierons quelques notions portant sur les cactus. Finalement nous bouclerons le tout par une exploration, à l'aide du logiciel Maple, des concepts élaborés dans les chapitres précédents. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : point critique, valeur critique, revêtement, polynôme de Shabat, arbre plan bicoloré, cactus, constellation, fonction symétrique, espèce de structures, itération de Newton-Raphson.

Dans cette thèse, nous étudions plusieurs problèmes de théorie des graphes concernant la coloration et la convexité des graphes. La plupart des résultats gurant ici sont liés à la complexité de calcul de ces problèmes pour certaines classes de graphes. Dans la première, et principale, partie de cette thèse, nous traitons de coloration des graphes qui est l'un des domaines les plus étudiés de théorie des graphes. Nous considérons d'abord trois problèmes de coloration appelés coloration gloutone, coloration pondérée et coloration pondérée impropre. Ensuite, nous traitons un probl ème de décision, appelé bon étiquetage de arêtes, dont la dé nition a été motivée par le problème d'affectation de longueurs d'onde dans les réseaux optiques. La deuxième partie de cette thèse est consacrée à un paramètre d'optimisation des graphes appelé le nombre enveloppe (géodésique). La dé nition de ce paramètre est motivée par une extension aux graphes des notions d'ensembles et d'enveloppes convexes dans l'espace Euclidien. En n, nous présentons dans l'annexe d'autres travaux développées au cours de cette thèse, l'un sur les hypergraphes orientés Eulériens et Hamiltoniens et l'autre concernant les systèmes de stockage distribués.

Soit un langage composé par tous les mots d'une longueur donnée $n$. Un cycle de de Bruijn d'ordre $n$ est un mot cyclique tel que tous les mots du langage apparaissent exactement une fois comme facteurs de ce cycle. Un algorithme pour construire le cycle de de Bruijn lexicographiquement minimal est dû à Fredricksen et Maiorana, il utilise les mots de Lyndon du langage. Cette thèse étudie comment généraliser le concept de cycles de de Bruijn pour un langage composé par un sous-ensemble de mots de longueur $n$, en particulier les langages de tous les mots de longueur $n$ sans facteurs dans une liste de facteurs interdits. Premièrement, nous étudions le cas des mots sans le facteur 11. Nous fournissons de nouvelles preuves de l'algorithme de Fredricksen et Maiorana qui nous permettent de prolonger ce resultat au cas des mots sans le facteur $1^i$ pour n'importe quel $i$. Nous caractérisons pour quels langages de mots de longueur $n$ existe un cycle de de Bruijn, et nous étudions également quelques propriétés de la dynamique symbolique de ces langages, en particulier des langages définis par des facteurs interdits. Pour ces genres de langages, nous présentons un algorithme pour produire un cycle de de Bruijn, en utilisant les mots de Lyndon du langage. Ces résultats utilisent la notion du graphe de de Bruijn et réduit le problème à construire un cycle eulérien dans ce graphe. Nous étudions le problème de la construction du cycle minimal dans un langage avec des facteurs interdits en employant le graphe de de Bruijn. Nous étudions deux algorithmes, un algorithme glouton simple et efficace qui fonctionne avec quelques familles de langages, et un algorithme plus complexe qui résout ce problème pour n'importe quel graphe eulérien.

Dans ce document, nous proposons un algorithme heuristique efficace pour résoudre le problème de partage spectral dynamique dans les réseaux de radios cognitives. Cet algorithme fonctionne selon les principes du paradigme de transmissions cognitives simultanées (en anglais underlay) où des utilisateurs primaires et des utilisateurs secondaires transmettent simultanément sur la même bande spectrale. L'algorithme proposé est basé sur un modèle théorique de graphe. Premièrement., le réseau de radios cognitives est modélisé en un graphe dont les sommets possèdent des poids. Le problème de partage spectral se réduit à colorier les sommets du graphe. Les décisions de partage spectral sont prises au niveau d'un serveur spectral qui coordonne les transmissions secondaires afin de trouver les paires (transmission secondaire/bande spectrale) qui maximisent le débit global du système. Le serveur spectral est aussi responsable de protéger les transmissions des utilisateurs primaires de l'interférence causée par les transmissions des utilisateurs secondaires. La réussite de cette tâche se base sur une allocation appropriée des puissances de transmission pour les utilisateurs secondaires. Grâce à des simulations bien élaborées, nous démontrons que les performances de l'algorithme proposé en terme de débit global sont proches de celles de l'algorithme optimal. Les performances de notre algorithme illustrent le gain en performances dû à une augmentation de la diversité de sélection de bande passante et à une diversité de sélection d'utilisateurs secondaires. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : algorithme de partage spectral, réseau de radios cognitives, théorie des graphes, systèmes de communication sans fil, simulation des réseaux.

Nous étudions les poids de graphes (c'est-à-dire, les invariants de graphes) qui apparaissent naturellement dans la théorie de Mayer et la théorie de Ree-Hoover pour le développement du viriel dans le contexte d'un gaz imparfait. Nous portons une attention particulière au deuxième poids ωM(C) de Mayer et au poids ωRH(C) de Ree-Hoover d'un graphe 2-connexe c dans le cas d'un gaz à noyaux durs et à positions continues en une dimension. Ces poids sont calculés à partir de volumes signés de polytopes convexes associés au graphe c en utilisant la méthode des homomorphismes de graphes, que nous avons aussi adaptée au cas du poids de Ree-Hoover, ainsi que les transformées de Fourier. En faisant appel à l'inversion de Möbius, nous présentons des relations entre les poids de Mayer et de Ree-Hoover. Ces relations nous permettent de donner une définition simple explicite du concept du "star content" introduit par Ree-Hoover et d'analyser certaines de ses propriétés fondamentales. Parmi nos résultats, nous donnons des tables contenant les valeurs du poids de Mayer et du poids de Ree-Hoover pour tous les graphes 2-connexes de taille au plus 8 ainsi que d'autres paramètres descriptifs. Nous développons aussi des formules explicites pour les poids de Mayer et de Ree-Hoover pour certaines familles de graphes 2-connexes simplement, doublement et triplement infinies, incluant par exemple, le poids de Mayer des graphes bipartis complets K m,n. En analysant les tables précédentes à l'aide du logiciel Maple, nous montrons que les poids de Mayer et de Ree-Hoover ne sont pas exprimables comme des fonctions faisant seulement appel à certains paramètres classiques de la théorie des graphes. Finalement, nous présentons une méthode générale pour le calcul du poids de Mayer d'un graphe connexe quelconque basée sur les arborescences couvrantes en utilisant les transformées de Fourier. Nous illustrons cette méthode sur des cas particuliers incluant les particules dures en dimension quelconque d. Cette méthode donne aussi lieu à un algorithme de calcul basé sur les différences divisées pour le cas des particules dures en dimension d = 1. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poids de Mayer, Poids de Ree-Hoover, Mécanique statistique, Méthode des homomorphismes de graphes, Transformées de Fourier, Gaz imparfaits.

En développant des outils pour étudier les chaînes de Markov réversibles ainsi qu’une classification des arbres par leur constante de branchement, on pourra traiter du problème du retour à l’origine d’une marche aléatoire sur un arbre. Ces mêmes outils nous permettront d’étudier la percolation sur les arbres. En particulier, il sera possible de relier explicitement la constante de branchement d’un arbre à la valeur critique pour la marche aléatoire biaisée et à la valeur critique de percolation. Par la suite, on détaille comment en arriver à des bornes intéressantes pour deux valeurs critiques du processus de contact sur l’arbre homogène, un résultat de Pemantle. On généralise aussi un résultat de Schinazi qui nous permet de trouver une borne inférieure pour la valeur critique de survie du processus de contact sur le recouvrement universel d’un graphe fini.