Cette thèse s'inscrit dans le cadre de la théorie des graphes, et porte plus particulièrement sur des problèmes de coloration de graphes. Dans cette thèse, nous nous intéressons à l'utilisation et au développement de la méthode de déchargement, un argument de comptage qui exploite fortement la structure du graphe. Cette méthode est décisive dans la preuve du Théorème des Quatre Couleurs. Nous donnons d'abord une vue d'ensemble des outils de déchargement que nous utilisons dans ce travail, entre les méthodes élégantes mises en application, et les astuces développées. Dans le cadre de la coloration d'arêtes par liste, nous résolvons la Conjecture de Coloration par Liste faible dans le cas des graphes planaires de degré maximum 8, en prouvant qu'on peut colorier par liste les arêtes de ces derniers avec 9 couleurs seulement. Ceci améliore un résultat de Borodin de 1990. Enfin, nous présentons nos résultats dans le cadre de la coloration de carrés, où il s'agit de colorier les sommets sans qu'il y ait deux sommets adjacents ou avec un voisin commun qui soient de la même couleur. On s'intéresse en particulier à des conditions suffisantes sur la densité du graphe (c-à-d le degré moyen maximum d'un sous-graphe) pour qu'on puisse colorier son carré avec peu de couleurs. / This thesis falls within graph theory, and deals more precisely with graph coloring problems. In this thesis, we use and develop the discharging method, a counting argument that makes strong advantage of the graph structure. This method is decisive in the proof of the Four Color Theorem. We first give an illustrated overview of the discharging tools that are used for this work: nice methods that we apply, and handy tricks that we develop. In the realm of list edge coloring, we most notably prove that the weak List Coloring Conjecture is true for planar graphs of maximum degree 8 (i.e. that they are edge 9-choosable), thus improving over a result of Borodin from 1990. We finally present our results about square coloring, where the goal is to color the vertices in such a way that two vertices that are adjacent or have a common neighbor receive different colors. We look in particular into sufficient conditions on the density of a graph (i.e. the maximum average degree of a subgraph) for its square to be colorable with few colo

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.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Dans de multiples domaines, des structures qui semblent à première vue très simples sont très mal comprises. Un exemple qui nous vient vite à l'esprit, c'est la structure de l'ADN qui n'est qu'une suite d'un alphabet de quatre bases azotées, mais dont la combinaison cache encore de nombreux mystères. Dans ce mémoire nous nous sommes attardés à la rotation, la réflexion et à la permutation des lettres d'un mot. Si l'on ne prend que la rotation, l'ensemble de tous les mots que l'on peut fabriquer par rotation des lettres d'un mot donné est appelé collier. Cette notion mathématique bien connu revient, dans le concret, à écrire notre mot donné sur les perles d'un collier et à constater que le fait de tourner le collier autour de notre cou ne change pas l'objet lui-même. En ajoutant la réflexion à la rotation, on obtient les bracelets. Toutefois, lorsque l'on combine la permutation des lettres de l'alphabet aux bracelets ou aux colliers, on obtient des objets beaucoup moins connus et moins bien compris. Au cours de ce mémoire, nous nous sommes donc intéressés aux mots dont la permutation des lettres est combinée à d'autres actions. Deux principaux problèmes ont occupés nos recherches: le comptage de ces objets ainsi que l'énumération de ceux-ci. Ces deux avenues ont été fructueuses et nous ont donné de nouveaux résultats. Nous avons de plus trouvé divers domaines où ces objets semblent être un modèle pertinent et où nos résultats pourraient s'appliquer. / Simple structures seem to emerge from many different sciences. However, we still have a limited undertanding of those structures. A good exemple is DNA structure which is simply a series of nitrogenous bases taken from a four letter alphabet. Unfortunately, even if its structure is very simple, DNA still keeps many secrets to the scientific community. A better understanding of basic structures seems to be the basis to a better understanding of our environment. This is why we have focused on words under the action of rotation, reflexion and permutation of letters. Words under the action of rotation are called necklaces and are well studied. If the reflection is added to necklaces, bracelets are obtained. However, if we combine alphabet permutation with rotation and/or reflection, less understood objects are obtained. We focused on two major problems: counting objets and generating them. In both directions we have found interesting new results. We also found some fields in which our results could contribute.

Les problèmes de recherche sur un graphe peuvent être exprimés sous la forme d’un jeu où un ensemble de chercheurs tentent de capturer un ensemble de fugitifs. Lorsqu’un tel jeu est joué en alternance par les deux ensembles de joueurs, nous parlons alors de jeux des policiers et des voleurs (« Cops and Robbers games ») ou plus simplement de jeux policiers-voleurs. Nowakowski et Winkler [28], et indépendamment Quilliot [45], ont introduit la première version des jeux policiers-voleurs dans laquelle un seul policier tente de capturer un seul voleur, les deux se déplaçant à tour de rôle vers des sommets adjacents de leurs positions courantes. Ils ont notamment proposé une jolie caractérisation des graphes gagnants pour le policier qui est basée sur l’existence d’un démantèlement particulier des sommets du graphe ; un démantèlement consistant à retirer un à un les sommets du graphe suivant une certaine règle. Cette caractérisation par démantèlement est par ailleurs intéressante puisqu’elle donne directement un algorithme polynomial de type diminuer pour régner pour résoudre le problème du policier et du voleur. Dans ce mémoire, nous proposons une nouvelle version d’un jeu policier-voleur dans laquelle le voleur se déplace arbitrairement vite dans le graphe et dans laquelle le policier possède une zone de surveillance qui limite le voleur dans ses déplacements. Nous caractérisons les graphes gagnants pour le policier dans ce nouveau jeu en utilisant un concept de démantèlement d’un graphe, similaire à celui de Nowakowski et Winkler [28], Quilliot [45], mais adapté aux conditions de notre nouveau jeu. Nous devons notamment généraliser la définition d’un graphe classique à celle d’un graphe clandestin, qui possède un ensemble de sommets clairs et un ensemble de sommets sombres, afin d’obtenir notre caractérisation par démantèlement. Nous donnons par ailleurs un algorithme qui permet de bâtir une stratégie monotone gagnante pour le policier en nous assurant que le policier sécurise de plus en plus de sommets à chaque tour. / Graph searching problems can be expressed as a game where a group of searchers is trying to capture a group of fugitives on a graph. When players move alternately in such a game, we are then referring to games of Cops and Robbers. Nowakowski and Winkler [28], and independently Quilliot [45], introduced the very first version of cops and robbers games in which a single cop tries to capture a single robber, both players moving alternately from their current positions to neighboring vertices. They notably proposed a very nice characterization of graphs that are winning for the cop, which is based on a particular dismantling scheme of the graph’s vertices; a dismantling scheme consisting in removing one by one each vertex of the graph by following a given rule. This dismantling-like characterization is furthermore interesting since it directly yields a divide-and-conquer algorithm that is polynomial, to solve the cop and robber problem. In this master thesis, we propose a new version of cops and robbers games in which the robber is able to move arbitrarily fast in the graph and in which the cop has a watching area that limits the robber’s moving capabilities. We characterize the cop-winning graphs for this new game by using some dismantling scheme similar to the one given by Nowakowski and Winkler [28], Quilliot [45], but that better fits our new game’s conditions. To obtain this dismantling-like characterization, we particularly need to generalize the definition of a classical graph to an undergrounded graph, whose vertices are split in a set of light vertices and a set of dark vertices. We also give an algorithm that provides a monotonous cop-winning strategy by making sure the cop is securing more and more vertices at each turn.

Pour une bonne modélisation mathématique de l'occurrence de phénomènes aléatoires, part fondamentale de la discipline actuarielle, il est nécessaire d'employer des distributions multivariées permettant de capturer adéquatement les relations de dépendance présentes entre les phénomènes. Celles qu'offrent les champs aléatoires markoviens, une famille de modèle probabilistes graphiques, répondent à ce besoin, les relations de dépendance qu'elles introduisent se calquant à un arbre ou à un graphe. Les champs aléatoires markoviens misent ainsi sur les riches possibilités de topologies d'arbres et de graphes pour offrir cette même richesse en termes de dépendance. Une nouvelle famille de champs aléatoires markoviens arborescents, c'est-à-dire se basant sur des arbres, est proposée. Les membres de cette famille se distinguent par le fait qu'ils ont des distributions marginales fixes de Poisson, « fixes » dans le sens que la dépendance introduite n'a pas d'impact sur elles. Des distribution marginales fixes sont inhabituelles pour un champ aléatoire markovien, bien que généralement désirables pour fins de modélisation. Cette caractéristique est possible par l'encapsulation, dans les arêtes de l'arbre, de la dynamique de propagation induite par l'opérateur d'amincissement binomial. Cela mène également à une représentation stochastique intuitive des champs aléatoires markoviens de la famille, à des méthodes simples de simulation et à des expressions analytiques pour leur fonction de masses de probabilités conjointe et leur fonction génératrice de probabilités conjointe, notamment. Quantités importantes dans un contexte actuariel, la somme des composantes du champ aléatoire markovien, interprétable comme le nombre total d'événement s'étant produits, et les contributions individuelles de ces composantes sont étudiées en profondeur. Cette analyse passe notamment par l'établissement d'ordres stochastiques. À cet effet, un nouvel ensemble partiellement ordonné est défini pour comparer des arbres aux topologies différentes selon la distribution qu'ils induisent pour la somme, ce qui est, à notre connaissance, novateur dans le contexte de modèles pobabilistes graphiques. Est offerte une comparaison de cet ensemble partiellement ordonné avec quelques autres en lien avec la théorie spectrale des graphes. / For adequate mathematical modeling of random phenomena's occurrences, it is necessary to employ multivariate distributions that appropriately capture the existing dependence relations between those phenomena. The multivariate distributions granted by Markov random fields, a family of probabilistic graphical models, answer to this need, by encrypting the dependence scheme they introduce on a tree or a graph. Markov random fields thus leverage on the rich possibilities of tree shapes and graph shapes to provide these possibilities in terms of dependence schemes. We propose a new family of tree-based Markov random fields, characterized by their Poisson marginal distributions. The marginal distributions are also fixed, meaning they are not affected by the introduced dependence. This fixedness is uncommon for Markov random fields, while being desirable for modeling purposes. It is obtained from the encapsulation, in the edges of the tree, of the propagation dynamic induced by the binomial thinning operator. This leads to an intuitive stochastic representation of Markov random fields from the proposed family, simple methods of simulation, and analytic expressions for their joint probability mass function and their joint probability generating function, notably. Important quantities in an actuarial context are the sum of the components of the Markov random field, interpreted as the total number of occurring phenomena, and the individual contributions of these components. They are thoroughly studied, notably via the use of stochastic order relations. We incidently design a new partially ordered set (poset) of trees, in order to compare trees of different shapes based on the distribution of the sum they respectively convey. To our knowledge, this approach is innovative in the context of probabilistic graphical models. We provide comparisons of the newly defined poset with some other posets of trees fetched from spectral graph theory.

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.

Thèse ou mémoire avec insertion d'articles. / Le but de la science des réseaux est de modéliser les systèmes complexes et d'expliquer leurs propriétés émergentes, telles que la propagation d'épidémies ou la formation de la mémoire dans le cerveau. Cependant, ces systèmes complexes peuvent parfois atteindre des tailles immenses, rendant leur étude difficile. La théorie spectrale des graphes est un outil majeur dans l'étude de tels réseaux, car les valeurs propres d'un réseau sont relativement faciles à calculer en plus de nous renseigner sur sa structure globale et sa dynamique à grande échelle. L'objectif de ce projet de maîtrise était d'analyser l'effet de propriétés structurelles, souvent négligées, présentes dans les réseaux de neurones sur le spectre des graphes qui leur sont associés. Plus spécifiquement, les propriétés étudiées sont la directionnalité, l'inhibition, le principe de Dale et la densité. Pour cela, différentes techniques de théorie des graphes ont été utilisées afin de créer des graphes aléatoires respectant les propriétés étudiées. Ensuite, une analyse spectrale approfondie de ces graphes aléatoires a été réalisée afin de déterminer l'effet des propriétés structurelles des réseaux de neurones sur leur spectre. On a d'abord abordé le problème à l'aide des théories mathématiques existantes, mais les calculs analytiques se sont avérés ardus et moins instructifs que prévu. Afin de combler ces lacunes, une analyse numérique a été réalisée. L'effet majeur provoqué par les propriétés structurelles étudiées est la présence d'une transition dans le spectre. La distribution de la valeur propre ayant la plus grande norme passe d'une distribution réelle à une distribution complexe pour ensuite revenir à une distribution réelle en fonction de la fraction d'inhibiteurs dans le réseau. La distribution changeante de la valeur propre dominante a alors été caractérisée numériquement, ce qui a permis l'identification et l'analyse de nombreuses autres propriétés empiriques. La transition dans le spectre, étant particulièrement significative dans les réseaux de taille finie, a donc une grande influence sur le comportement des réseaux de neurones et est directement influencée par les propriétés structurelles introduites. / The goal of network science is to model complex systems and explain their emergent properties, such as epidemic spreading or memory formation in the brain. However, these complex systems can sometimes reach immense sizes, making their study challenging. Graph spectral theory is a significant tool in the investigation of such networks, as the eigenvalues of a network are relatively easy to compute and provide insights into its overall structure and large-scale dynamics. The objective of this master's project was to analyze the effect of often overlooked structural properties present in neural networks on the spectrum of the associated graphs. More specifically, the studied properties include directionality, inhibition, Dale's principle, and density. To achieve this, various graph theory techniques were employed to generate random graphs that adhere to the studied properties. Subsequently, an in-depth spectral analysis of these random graphs was conducted to determine the impact of the structural properties of neural networks on their spectrum. Initially, the problem was approached using existing mathematical theories, but the analytical calculations proved to be challenging and less informative than anticipated. To address these gaps, a numerical analysis was performed. The major effect induced by the studied structural properties is the presence of a transition in the spectrum. The distribution of the eigenvalue with the largest norm transitions from a real distribution to a complex distribution, and then returns to a real distribution based on the fraction of inhibitors in the network. The changing distribution of the dominant eigenvalue was numerically characterized, wich enabled the empirical observation and analysis of many other properties. The spectrum transition, particularly significant in networks of finite size, thus has a substantial influence on the behavior of neural networks and is directly influenced by the introduced structural properties.