Student Probability Seminar

---

Trees in Random Sparse Graphs with Given Degree Sequence

Speaker: Behzad Mehrdad

Location: Warren Weaver Hall 1314

Date: Thursday, March 7, 2013, 3:30 p.m.

Synopsis:

Let \(G^D\) be the set of graphs \(G(V, E)\), \(|V| = n\), with degree sequence equal to \(D = (d_1, d_2, . . . , d_n)\). What does a graph look like when it is chosen uniformly out of \(G^D\)? This has been studied when \(G\) is a dense graph ,\(|E| = O(n^2)\), in the sense of graphons or when \(G\) is very sparse, \((d_n)^2 = o(|E|)\). We investigate this question in the case of sparse graphs with almost given degree sequence, and give the finite tree subgraph structure of \(G\), under some mild conditions. For graphs with given degree sequence, we re-derive the tree structure in dense and very sparse case to give a continuous picture. Moreover, we are able to show the result for general bipartite graphs with given degree sequence without any further conditions.