Title: On a random graph evolving by degrees
Speaker: Boris Pittel (Ohio State University)
When: October 19, 15:30-16:30
Where: Wean Hall 5302
Abstract:
We consider a random (multi)graph growth process ${G_m}$ on a vertex set $[n]$, which is a special case of a more general process suggested by Laci Lovasz several years ago. $G_0$ is empty, and $G_{m+1}$ is obtained from $G_m$ by inserting a new edge $e$ at random. Specifically, the conditional probability that $e$ joins two currently disjoint vertices, $i$ and $j$ , is proportional to $(d_i + \alpha)(d_j + \alpha)$, where $d_i$ , $d_j$ are the degrees of $i$ ,$ $j in $G_m$, and $\alpha > 0$ is a fixed parameter. The limiting case $\alpha = \infty$ is the Erdos-Renyi graph process. We show that whp $G_m$ contains a unique giant component iff $c := 2m/n > c_{\alpha} = \alpha/(1 + \alpha)$, and the size of this giant is asymptotic to $n [1-(\frac{\alpha+c^*}{\alpha+c})^{\alpha}]$, where $c^* < c_{\alpha}$ is the root of $\frac{c}{(\alpha+c)^{2+\alpha}} = \frac{c^*}{(\alpha+c^*)^{2+\alpha}}$ . For the multigraph version, ${MG_m}$, we show that $MG_m$ is connected whp iff $m \gg m_n := n^{1+\alpha^{-1}}$, and we conjecture that, for $\alpha > 1$, $m_n$ is the threshold for connectedness of $G_m$ itself.
