Graph enumeration and random graphs

Abstract

In this thesis we use analytic combinatorics to deal with two related problems: graph enumeration and random graphs from constrained classes of graphs. We are interested in drawing a general picture of some graph families by determining, first, how many elements are there of a given possible size (graph enumeration), and secondly, what is the typical behaviour of an element of fixed size chosen uniformly at random, when the size tends to infinity (random graphs). The problems concern graphs subject to global conditions, such as being planar and/or with restrictions on the degrees of the vertices.

In Chapter 2 we analyse random planar graphs with minimum degree two and three. Using techniques from analytic combinatorics and the concepts of core and kernel of a graph, we obtain precise asymptotic estimates and analyse relevant parameters for random graphs, such as the number of edges or the size of the core, where we obtain Gaussian limit laws. More challenging is the extremal parameter equal to the size of the largest tree attached to the core. In this case we obtain a logarithmic estimate for the expected value together with a concentration result.

In Chapter 3 we study the number of subgraphs isomorphic to a fixed graph in subcritical classes of graphs. We obtain Gaussian limit laws with linear expectation and variance when the fixed graph is 2-connected. The main tool is the analysis of infinite systems of equations by Drmota, Gittenberger and Morgenbesser, using the theory of compact operators. Computing the exact constants for the first estimates of the moments is in general out of reach. For the class of series-parallel graphs we are able to compute them in some particular interesting cases.

In Chapter 4 we enumerate (arbitrary) graphs where the degree of every vertex belongs to a fixed subset of the natural numbers. In this case the associated generating functions are divergent and our analysis uses instead the so-called configuration model. We obtain precise asymptotic estimates for the number of graphs with given number of vertices and edges and subject to the degree restriction. Our results generalize widely previous special cases, such as d-regular graphs or graphs with minimum degree at least d.

En aquesta tesi utilitzem l'analítica combinatòria per treballar amb dos problemes relacionats: enumeració de grafs i grafs aleatoris de classes de grafs amb restriccions. En particular ens interessa esbossar un dibuix general de determinades famílies de grafs determinant, en primer lloc, quants grafs hi ha de cada mida possible (enumeració de grafs), i, en segon lloc, quin és el comportament típic d'un element de mida fixa triat a l'atzar uniformement, quan aquesta mida tendeix a infinit (grafs aleatoris). Els problemes en què treballem tracten amb grafs que satisfan condicions globals, com ara ésser planars, o bé tenir restriccions en el grau dels vèrtexs. En el Capítol 2 analitzem grafs planar aleatoris amb grau mínim dos i tres. Mitjançant tècniques de combinatòria analítica i els conceptes de nucli i kernel d'un graf, obtenim estimacions asimptòtiques precises i analitzem paràmetres rellevants de grafs aleatoris, com ara el nombre d'arestes o la mida del nucli, on obtenim lleis límit gaussianes. També treballem amb un paràmetre que suposa un repte més important: el paràmetre extremal que es correspon amb la mida de l'arbre més gran que penja del nucli. En aquest cas obtenim una estimació logarítmica per al seu valor esperat, juntament amb un resultat sobre la seva concentració. En el Capítol 3 estudiem el nombre de subgrafs isomorfs a un graf fix en classes de grafs subcrítiques. Quan el graf fix és biconnex, obtenim lleis límit gaussianes amb esperança i variància lineals. L'eina principal és l'anàlisi de sistemes infinits d'equacions donada per Drmota, Gittenberger i Morgenbesser, que utilitza la teoria d'operadors compactes. El càlcul de les constants exactes de la primera estimació dels moments en general es troba fora del nostre abast. Per a la classe de grafs sèrie-paral·lels podem calcular les constants en alguns casos particulars interessants. En el Capítol 4 enumerem grafs (arbitraris) el grau de cada vèrtex dels quals pertany a un subconjunt fix dels nombres naturals. En aquest cas les funcions generatrius associades són divergents i la nostra anàlisi utilitza l'anomenat model de configuració. El nostre resultat consisteix a obtenir estimacions asimptòtiques precises per al nombre de grafs amb un nombre de vèrtexs i arestes donat, amb la restricció dels graus. Aquest resultat generalitza àmpliament casos particulars existents, com ara grafs d-regulars, o grafs amb grau mínim com a mínim d.