Abstract
Let G(n(1), n(2), m) be a uniformly random m-edge subgraph of the complete bipartite graph K-n1,K-n2 with bipartition (V-1, V-2), where ni = |V-i|, i= 1, 2. Given a real number p is an element of [0, 1] such that d(1) := pn(2) and d(2) := pn(1) are integers, let R(n(1), n(2), p) be a random subgraph of K-n1,(n2) with every vertex v subset of V-i of degree d(i), i= 1, 2.
In this paper we determine sufficient conditions on n1, n2, p and m under which one can embed G(n(1), n(2), m) into R(n(1), n(2), p) and vice versa with probability tending to 1. In particular, in the balanced case n(1) = n(2), we show that if p >> log n/n and 1- p >> (log n/n) (1/4), then for some m similar to pn(2), asymptotically almost surely one can embed G(n(1), n(2), m) into R(n(1), n(2), p), while for p >> ( log(3) n/n) (1/4) and 1- p >> log n/n the opposite embedding holds.
As an extension, we confirm the Kim-Vu Sandwich Conjecture for degrees growing faster than(n log n)(3/4).