Springe direkt zu Inhalt

Lecture by Anita Liebenau (University of New South Wales, Sydney): Enumerating graphs and other discrete structures by degree sequence

Jul 08, 2019 | 02:15 PM

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with probability p?

Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for the number of graphs with a given degree sequence, for a wide enough range of degree sequences. From these enumeration formulae one can then deduce asymptotic formulae for the second question.

McKay and Wormald showed that the formulae for the sparse case and the dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent binomial variables Bin(n − 1, p').

In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the  differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings.

Time & Location

Jul 08, 2019 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)