Добірка наукової літератури з теми "Graphes en rubans métriques"

Cette thèse présente quelques contributions à l’étude des fonctions de comptage des graphes en rubans métriques. Un graphe en ruban, aussi connu sous le nom de carte combinatoire, est un plongement cellulaire d’un graphe dans une surface. On peut le représenter via le recollements de polygones ou encore via des factorisations de permutations. Une métrique sur un graphe en rubans est l’attribution d’une longueur strictement positive à chaque arête. Les fonctions de comptage donnent le nombre de graphes en rubans avec une métrique entière et combinatoire fixée (genre de la surface, degré des sommets, nombre de bords) en fonction des périmètres des bords. Notre approche à l’étude de ces fonctions est purement combinatoire et repose sur l’utilisation des bijections et chirurgies pour les graphes en rubans. Dans un premier temps, on montre que ces fonctions sont (quasi-)polynomiales par morceaux, et on précise les régions de (quasi-)polynomialité. Ensuite, on étudie les cas où leur termes de plus haut degré sont de vrais polynômes. Notre intérêt dans ces cas vient du fait que les polynômes correspondants sont utiles pour l’énumération des surfaces à petits carreaux, qui correspondent aux points entiers des strates des surfaces de (demi-)translation (de manière équivalent, states des différentielles sur les surfaces de Riemann). Par conséquent, on peut donner des formules raffinées/alternatives pour les volumes de Masur-Veech des strates. Un exemple connu sont les polynômes de Kontsevich, qui comptent les graphes en rubans métriques trivalents de genre et périmètres des bords fixés. Ils ont été utilisés récemment par Delecroix, Goujard, Zograf et Zorich pour obtenir une formule combinatoire pour les volumes des strates principales des différentielles quadratiques. On se concentre sur les graphes en rubans métriques face-bipartis, qui apparaissent dans l’étude des différentielles Abéliennes. On montre que pour les graphes à un sommet, les termes de plus haut degré des fonctions de comptage sur certains sous-espaces sont des polynômes explicites. En conséquence, on obtient la série génératrice des contributions des surfaces à petits carreaux à n cylindres aux volumes des strates minimales des différentielles Abéliennes, raffinant un résultat précédent de Sauvaget. Ensuite, on présente un résultat de polynomialité similaire pour les deux sous-familles de graphes qui correspondent ou composants connexes de strates minimales de parité spin paire/impaire. Cela donne un raffinement d’une formule pour les différences des volumes correspondants obtenue précédemment par Chen, Möller, Sauvaget et Zagier. Puis on conjecture que le phénomène de polynomialité reste vrai pour les familles de graphes à plusieurs sommets, si chaque graphe est pondéré par le comptage de certains arbres couvrants. On prouve cette conjecture dans le cas planaire. En chemin, on construit des familles d’arbres plans qui correspondent à certaines triangulations de produits de simplexes qui représentent un intérêt du point de vue de la théorie des polytopes. Finalement, on présente une contribution au projet commun avec Duryev et Goujard, où la formule combinatoire de Delecroix, Goujard, Zograf et Zorich est généralisée aux strates des différentielles quadratiques aux singularités impaires. La contribution est une preuve combinatoire de la formule pour les coefficients qui comptent certaines dégénérescences des graphes en ruban métriques non-face-biparti
This thesis presents several contributions to the study of counting functions for metric ribbon graphs. Ribbon graphs, also known as combinatorial maps, are cellular embeddings of graphs in surfaces modulo homeomorphisms. They are combinatorial objects that can be represented as gluings of polygons or factorizations of permutations. Metric on a ribbon graph is an assignment of positive lengths to its edges. The counting functions give the number of integral metric ribbon graphs with fixed combinatorics (genus of the surface, degrees of vertices, number of boundaries) as a function of the perimeters of the boundaries. Our approach to their study is purely combinatorial and relies on bijections and surgeries for ribbon graphs. Firstly, we show that these functions are piecewise (quasi-)polynomials, specifying exactly the regions of (quasi-)polynomiality. We then study the cases when their top-degree terms are honest polynomials. Our interest in such cases comes from the fact that the corresponding polynomials can be used for refined enumeration of square-tiled surfaces, which correspond to integer points in the strata of (half-)translations surfaces (equivalently, strata of differentials on Riemann surfaces). Consequently, one can give refined/alternative formulas for Masur-Veech volumes of strata. One known example are the Kontsevich polynomials, counting trivalent metric ribbon graphs of given genus and perimeters of boundaries. They were recently used by Delecroix, Goujard, Zograf and Zorich to give a combinatorial formula for the volumes of principal strata of quadratic differentials. We concentrate on face-bipartite metric ribbon graphs, which appear in the study of Abelian differentials. We show that in the case of one-vertex graphs the top-degree terms of the counting functions on certain subspaces are in fact (explicit) polynomials. As a consequence, we deduce the generating function for the contributions of n-cylinder square-tiled surfaces to the volumes of minimal strata of Abelian differentials, refining a previous result of Sauvaget. We then present a similar polynomiality result for the two subfamilies of graphs corresponding to even/odd spin connected components of the minimal strata. This also gives a refinement of a formula for the corresponding volume differences previously obtained by Chen, Möller, Sauvaget and Zagier. Next we conjecture that the polynomiality phenomenon holds for families of graphs with several vertices, if each graph is weighted by the count of certain spanning trees. We prove the conjecture in the planar case. In the process, we construct families of plane trees which correspond to certain triangulations of the product of two simlpices, which are interesting from the point of view of the theory of polytopes. Finally, we present a contribution to a joint work with Duryev and Goujard, where the combinatorial formula of Delecroix, Goujard, Zograf and Zorich is generalized to all strata of quadratic differentials with odd singularities. The contribution is a combinatorial proof of the formula for coefficients counting certain degenerations of (non-face-bipartite) metric ribbon graphs

Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité
Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel . Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature".

Cette thèse concerne l'étude des graphes quantiques, c'est à dire, des systèmes quantiques dans lesquels une particule non relativiste est confinée sur un graphe. Nous proposons une nouvelle voie pour représenter des conditions aux limites, et à l'aide de ce résultat nous résolvons le problème, resté longtemps ouvert, d'approximation par des graphes réguliers de tous les couplages singuliers aux sommets dans un graphe quantique. Nous présentons une construction dans laquelle les arêtes sont disjointes et les paires d'extrémités ainsi obtenues sont raccordés par des arêtes additionnelles de longueur 2d. Chacune de ces arêtes porte un potentiel delta et un potentiel vectoriel. Nous montrons que lorsque d tend vers zéro et les potentiels dépendent convenablement de d, la limite peut produire tout couplage singulier de sommets requis. Ce type de conditions aux limites est utilisé pour examiner les propriétés de diffusion par des sommets singuliers de degré 3. Nous montrons que les couplages entre chaque paire de lignes issues du sommet sont réglables individuellement ce qui pourrait permettre la conception de filtre quantique de type "aiguillage spectral". Nous étudions aussi les opérateurs de Schrödinger sur un graphe infini en forme de chaîne composée de cercles identiques couplés aux points de contact par les interactions. Delta Si le graphe est périodique, l'hamiltonien a un spectre de bande. Nous considérons une déformation "courbée" de la chaîne qui consiste en un changement de la position du point de contact entre deux cercles. On montre que cette déformation a pour conséquence la naissance de valeurs propres et analyse leur dépendance par rapport à l"angle de courbature"
This thesis is devoted to investigation of quantum graphs, in other words, quantum systems in which a nonrelativistic particle is confined to a graph. We propose a new way to represent the boundary conditions, and with the help of this result we solve the longstanding open problemof approximating by regular graphs all singular vertex couplings in quantum graph vertices. We present a construction in which the edges are disjunct and the pairs of the so obtained endpoints are joined by additional connecting edges of lengths 2d. Each connecting edge carries a delta potential and a vector potential. It is shown that when the lengths 2d of the connecting edges shrink to zero and the added potentials properly depend on d, the limit can yield any requested singular vertex coupling. This type of boundary conditions is used to examine scattering properties of singular vertices of degrees 2 and 3. We show thar the couplings between each pair of the outgoing edges are individually tunable, which could enable the design of quantum spectral junctions filters. We also study Schrödinger operators on an infinite quantum graph of a chain form which consists of identical rings connected at the touching points by delta-couplings. If the graph is periodic, the Hamiltonian has a band spectrum. We consid a "bending" deformation of the chain consisting in changing the position of the point of contact between two rings. We show that this deformation gives rive to eigenvalues and analyze their dependence on the "bending angle"

Le thème central de cette thèse est l'étude d'espaces métriques aléatoires dont la structure est apparentée à celle d'un arbre. On étudie d'abord une façon aléatoire de recoller une suite d'espaces métriques itérativement, en attachant à chaque étape de la procédure un nouveau bloc sur la structure construite jusque là. Sous certaines conditions sur les blocs que l'on agglomère, on calcule la dimension de Hausdorff de la structure obtenue et son expression est surprenante ! On s'intéresse ensuite à certaines propriétés asymptotiques (degrés, hauteur, profil) de deux modèles d'arbres discrets construits récursivement, les arbres récursifs pondérés et les arbres à attachement préférentiel affine à poids initiaux. Les premiers encodent la structure discrète sous-jacente aux recollements des blocs dans la construction précédente, et les seconds ont un rôle similaire pour des modèles de graphes discrets construits de façon analogues. On exploite cette connexion afin de montrer des résultats de limites d'échelle pour certains modèles de graphes discrets vers des espaces métriques continus construits par recollement itératif. Enfin, dans un travail en collaboration avec Christina Goldschmidt et Bénédicte Haas, on prouve des résultats concernant la composante alpha-stable à surplus fixé. Cet espace métrique aléatoire apparaît comme la limite d'échelle des grandes composantes connexes de modèles de configuration critique à queue lourde. L'objets obtenu est presque un arbre à l'exception d'un nombre fini de cycles dont nous étudions la structure
The subject of this thesis is the study of some random metric spaces with a tree-like structure. We first study a construction in which we glue a sequence of metric spaces onto each other in a sequential manner. Under some conditions on the spaces that we aggregate, we compute the Hausdorff dimension of the obtained structure and it has a surprising expression ! We then investigate some asymptotic properties (degrees, height,profile) of two models of growing discrete trees, the weighted recursive trees and the preferential attachment trees with additive fitnesses. The former encodes the underlying discrete structure in the construction described above and the latter have a similar interpretation for some models of discrete growing graphs. We make use of this connection in order to prove scaling limit results for these random discrete graphs towards continuous metric space constructed by a gluing procedure. Last, in a joint work with Christina Goldschmidt and Bénédicte Haas, we investigate the behaviour of the alpha­stable component with fixed surplus. This random metric space appears as the scaling limit of large connected components of the configuration model with heavy-tailed degrees. This abject is almost a tree except for a finite number of cycles. We compute the distribution of the cyclic structure and give a description of the whole space as trees glued along this structure

Cette these presente un point de vue categorique des systemes de transitions et illustre sa pertinence par des applications en theorie des graphes. Ce point de vue consiste, d'apres m. Pouzet et i. Rosenberg a considerer un systeme de transitions comme une sorte d'espace metrique; la distance entre deux etats etant, non pas un nombre, mais le langage accepte par l'automate constitue du systeme de transitions et de ces deux etats comme etats initiaux et finaux. Par exemple, voyant un graphe comme un systeme de transitions sur l'alphabet a deux lettres a et b muni de l'involution echangeant a et b, on retrouve la distance zigzag introduite par quilliot en 1983 pour les graphes. Si on ordonne les langages par l'ordre inverse de l'inclusion, alors les morphismes de systeme de transitions deviennent des applications contractantes; ainsi les idees issues de l'abondante etude des contractions d'espaces metriques peuvent etre appliquees aux systemes de transitions. Considerant des systemes de transitions involutifs nous decrivons les langages acceptes; notre description utilise un ordre sous les mots qui peut se definir a partir d'une regle de reecriture possedant la propriete de church-rosser. Nous en tirons une caracterisation des retractes absolus parmi ces systemes, semblable a celle obtenue par aronszajn et panichpakdi en 1956 pour les espaces metrique. Comme application nous obtenons, en collaboration avec h. -j. Bandelt et m. Pouzet, que la classe des graphes antisymetriques est la plus large classe de graphes ayant les retractes de produits de zigzags (reflexifs et antisymetriques) comme retractes absolus

Ce travail se situe dans le domaine de l'optimisation combinatoire. Nous étudions plus particulièrement des caractérisations d'objets pour lesquels des problèmes, qui dans le cas général sont NP-complets, deviennent polynomiaux. Nous traitons d'abord le problème de la faisabilité d'un multiflot, qui possède des applications trés importantes en recherche opérationnelle. C'est à dire, étant donnée la spécification du problème, avec le réseau, les capacités et les demandes, on veut démontrer l'existence ou la non-existence d'une solution. Une façon d'aborder ce problème est de donner des conditions nécessaires et suffisantes pour l'existence d'un multiflot, comme celle connue par condition de coupe. Nous présentons la condition (CC, K_5, F_7), qui généralise la condition de coupe et "raffine" une autre condition existante, la (CC3). La structure du problème de multiflot nous permet aussi de regarder un problème étroitement associé, celui du "packing" de métriques. Nous traitons le cas des packing entiers et demi-entiers, quand la famille de métriques comprend les métriques CC3 et les métriques K_5 et F_7. Nous caractérisons la classe de graphes, et plus généralement de matroïdes, ou l'on peut trouver des packings entiers et demi-entiers, sous quelques hypothèses additionnelles. Puis nous nous intéressons aux propriétés générales des graphes h- et t-parfaits, et au problème de coloration associé. Les résultats que nous présentons donnent des bornes pour leur nombres chromatiques, et des classes qui satisfont une conjecture de Shepherd. Enfin nous présentons la hiérarchie des graphes étudiés, qui est obtenu grâce à des outils comme les graphes faiblement bipartis, les clutters binaires et les matrices à composantes 0,1. Nous clôturons ce mémoire en précisant quelques directions de recherche qui pourront donner suite à ce travail, aussi bien sur le sujet de la faisabilité des problèmes de multiflot, que sur la coloration des graphes h- et t-parfaits.

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes
This Ph. D. Manuscript is built around the notion of graph embedding. An embedding of a graph G is an application mapping the vertices of G to elements of another structure, and preserving some properties of G. There are two types of embeddings. The combinatorial embeddings map the vertices of a graph G to the vertices of a graph H. The usual property that is preserved is the adjacency between vertices. In this thesis, we consider the isometric embeddings, preserving in addition the distances between vertices. We give some structural characterizations for families of graphs isometrically embeddable in hypercubes or Hamming graphs. The topological embeddings aim at drawing a graph G on some surface. Vertices are mapped to distinct points of the surface and the edges are represented by continuous curves linking these points. Is it possible to draw a graph G so that the edges do not cross eachother ? If not, what is the minimum number of crossings of a drawing of G ? We deal with these questions on different surfaces, or in relation with some graph operations as direct product or zip product

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.