RESEARCH IN RESIDENCE
Enumeration on structural graph parameters via analytic combinatorics
Énumération des paramètres de graphes structurels via la combinatoire analytique
Énumération des paramètres de graphes structurels via la combinatoire analytique
16 – 25 June 2021
Description
|
In structural graph theory, several graph parameters have been introduced in order to express graph-topological properties. Such parameters are known as “width parameters” and measure there semblance of a graph to the structure of a tree or of a path, such as treewidth, pathwidth, branchwidth, cutwidth, carving-width, linear-width and others. The study of width parameters is quite extended: it spans topics on structural graph theory, graph algorithms, model theory, and computational complexity. However, only few results exist on the combinatorial enumeration of graphs classes where such parameters are bounded. Our aim is to initiate such a project by using tools and techniques from analytic combinatorics combined with results and insight from structural graph theory. We plan to provide asymptotic estimates on the number of graphs in the corresponding graph classes but also on the asymptotic behaviour of their main structural characteristics. As a first step we will investigate whether known “forbidden-graph characterizations” (partial or complete) of the corresponding graph classes can be the departure point for the development of enumeration theorems using the symbolic method. The use of analytic techniques to obtain enumerative results will be exploited later to study random graphs (with the uniform distribution) in the graph classes under consideration.
Mots clés: Paramètres de graphe, Théorie des graphes structurels, Combinatoire analytique, Enumération combinatoire, Lois limites, Graphes aléatoires, Obstructions. |
Dans la théorie structurelle des graphes, plusieurs paramètres ont été introduits afin d’exprimer les propriétés topologiques des graphes. Ces paramètres sont appelés «paramètres de largeur» et mesurent la ressemblance d’un graphe avec la structure d’un arbre ou d’un chemin, tel que treewidth, pathwidth, branchwidth, cutwidth, carving-width, linear-width, et d’autres. L’étude des paramètres de largeur est assez étendue : elle couvre des sujets sur la théorie des graphes structurels, les algorithmes de graphes, la théorie des modèles et la complexité computationnelle. Cependant, seuls quelques résultats existent sur l’énumération combinatoire des classes de graphes où ces paramètres sont bornés. Notre objectif est d’initier un tel projet en utilisant des outils et des techniques d’analyse combinatoire. Nous prévoyons de fournir des estimations asymptotiques sur le nombre de graphes dans une certaine classe, mais aussi sur le comportement asymptotique de leurs principales caractéristiques structurelles. Comme une première étape, nous examinerons si les «caractérisations de graphes interdits» connues (partielles ou complètes) de classes de graphes correspondantes peuvent être le point de départ pour le développement de théorèmes d’énumération suivant la méthode symbolique. L’utilisation de techniques analytiques pour obtenir des résultats énumératifs sera exploitée plus tard pour étudier les graphes aléatoires (avec la distribution uniforme) dans les classes de graphes considérées.
Keywords: Graph parameters, Structural Graph Theory, Analytic Combinatorics, Combinatorial Enu-meration, Limit laws, Random Graphs, Obstructions. |
Participants
Marc Noy (Polytechnic University of Catalonia)
Juanjo Rué (Polytechnic University of Catalonia
Dimitrios Thilikos Touloupas (CNRS, Université Montpellier)
|
Sponsor
|
