论文标题
夹心双毛随机图
Sandwiching biregular random graphs
论文作者
论文摘要
令$ g（n，n，m）$为一个均匀的随机$ m $ - edge子图$ k_ {n，n} $，带有双色$（v_1，v_2）$，其中$ n_i = | v_i | $。给定一个实际数字$ p \在[0,1] $中，以至于$ d_1：= pn_2 $和$ d_2：= pn_1 $是整数，让$ r（n，n，p）$是$ k_ {n，n，n} $的随机子graph，in V_i $ in v_i $ n in v_i $ d_i $ d_i $ $ $ d_i $，$ y $ i y y y $ i y y y y $ i y = 1，2 $ i c.在本文中，我们确定了$ n_1，n_2，p $和$ m $的足够条件，根据该条件，可以将$ g（n，n，m）$嵌入$ r（n，n，n，p）$，反之亦然，概率为$ 1 $。特别是，在均衡的情况下，$ n_1 = n_2 $，我们表明，如果$ p \ gg \ log n/n $和$ 1- p \ gg \ weft（\ log n/n/n/n \ right）^{1/4} $，那么对于某些$ m \ sim pn^2 $，几乎是$ g（n n $ s sy $ g（n） $ p \ gg \ left（\ log^{3} n/n \ right）^{1/4} $和$ 1-p \ gg \ gg \ log n/n $我们具有相反的嵌入。作为扩展名，我们确认Kim--Vu三明治的猜想，其学位的生长速度快于$（n \ log n）^{3/4} $。
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 := pn_2$ and $d_2 := pn_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 pn^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}$.
