Enumerating graphs and other discrete structures by degree sequence

Speaker(s)

Anita Liebenau

Affiliation

University of New South Wales

Date

June 13, 2019, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

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 range of degree sequences that is wide enough to 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.

---