BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 pr
obability 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 e
nough range of degree sequences. From these enumeration formulae one can th
en 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 f
ormulae should hold for the gap range. A particular consequence of both con
jectures is that the degree sequence of the random graph G(n\,p) can be app
roximated 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 wi
ll describe the problem and survey some of the earlier methods to showcase
the differences to our new methods. I shall also report on enumeration res
ults of other discrete structures\, such as bipartite graphs and hypergraph
s\, that are obtained by adjusting our methods to those settings.
DTSTAMP:20190320T171200
DTSTART:20190708T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Anita Liebenau (University of New South Wales\, Sydney): Enumeratin
g graphs and other discrete structures by degree sequence
UID:95691323@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190708-L-Liebenau.html
END:VEVENT
END:VCALENDAR