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.