The degree sequence of a random graph
01.07.2016, 11.00
– Haus 9, Raum 2.22
Arbeitsgruppenseminar Analysis
Anita Liebenau
The random graph G(n,p) is obtained from a set of n isolated vertices between which edges are inserted with probability p=p(n) each, all choices being independent.
The degrees of the vertices of G form the so called degree sequence of the random graph, which is an important invariant.
We show that the distribution of the degree sequence of G(n,p) can be approximated by a sequence of n independent binomial variables Bin(n-1,p) for a large range of p. In fact, we prove an asymptotic formula for the number of graphs of a given degree sequence, which implies the result about the degree sequence of the random graph. Previous work covers the remaining ranges.
In this talk, we will survey previous results, give a glimpse of the methods and some applications.
This is joint work with Nick Wormald.