Sandwiching biregular random graphs

Abstract

Let $G(n,n,m)$ be a uniformly random $m$-edge subgraph of the complete bipartite graph $K_{n,n}$ with bipartition $(V_1,V_2)$, where $n_i=|V_i|$. Given a real number $p\in [0,1]$ such that $d_1:=p{n}_2$ and $d_2:=p{n}_1$ are integers, let $R(n,n,p)$ be a random subgraph of $K_{n,n}$ such that every $v\in V_i$ has degree $d_i$, for $i=1,2$. In this paper we determine sufficient conditions on $n_1,n_2,p$, and $m$ under which one can embed $G(n,n,m)$ into $R(n,n,p)$ and vice versa with probability tending to $1$. In particular, in the balanced case $n_1=n_2$, we show that if $p\gg \log n/n$ and $1-p\gg {\left(\log n/n\right)}^{1/4}$, then for some $m\sim p{n}^2$, asymptotically almost surely one can embed $G(n,n,m)$ into $R(n,n,p)$, while for $p\gg {\left({\log }^{3}n/n\right)}^{1/4}$ and $1-p\gg \log n/n$ we have the opposite embedding. As an extension, we confirm the Kim--Vu Sandwich Conjecture for degrees growing faster than $(n\log n{)}^{3/4}$.

Added extension to non-bipartite regular graphs