Random graphs with a fixed maximum degree

Abstract

We study the component structure of the random graph $G=G_{n,m,d}$. Here $d=O(1)$ and $G$ is sampled uniformly from ${\mathcal{G}}_{n,m,d}$, the set of graphs with vertex set $[n]$, $m$ edges and maximum degree at most $d$. If $m=\mu n/2$ then we establish a threshold value ${\mu }_{\star }$ such that if $\mu <{\mu }_{\star }$ then w.h.p. the maximum component size is $O(\log n)$. If $\mu >{\mu }_{\star }$ then w.h.p. there is a unique giant component of order $n$ and the remaining components have size $O(\log n)$.