2020/10/29 by Tereza Klimošová, Klimošová, Tereza, Christian Reiher +5 · 2 citations
Mathematics · #05C80 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2010.15751
openalex publication_date 2020/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G(n,n,m) be a uniformly random m-edge subgraph of the complete bipartite graph Kn,n with bipartition (V1, V2), where ni = |Vi|. Given a real number p ∈ [0,1] such that d1 := pn2 and d2 := pn1 are integers, let R(n,n,p) be a random subgraph of Kn,n such that every v ∈ Vi has degree di, for i = 1, 2. In this paper we determine sufficient conditions on n1,n2,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 n1 = n2, we show that if p ≫ log n/n and 1 - p ≫ (log n/n )1/4, then for some m ∼ pn2, asymptotically almost surely one can embed G(n,n,m) into R(n,n,p), while for p ≫ (log3 n/n)1/4 and 1-p ≫ 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.