Sandwich conjecture for random regular graphs

About 20 years old · traced to

Let NN be the number of vertices, let d=d(N)d=d(N), and let GN,d\bm{G}_{N,d} denote a uniformly random dd-regular graph. For edge probabilities p∗p_* and p∗p^*, let G∗∼GN,p∗\bm{G}_*\sim\bm{G}_{N,p_*} and G∗∼GN,p∗\bm{G}^*\sim\bm{G}_{N,p^*} be Erdős–Rényi random graphs. Sandwich conjecture. If d=d(N)d=d(N) dominates log⁡N\log N asymptotically, there exist

p∗=(1−o(1)) d/N,p∗=(1+o(1)) d/N,p_*=(1-o(1))\,d/N,\qquad p^*=(1+o(1))\,d/N,

such that

P(G∗⊆GN,d⊆G∗)=1−o(1),\mathbb{P}\bigl(\bm{G}_*\subseteq\bm{G}_{N,d}\subseteq\bm{G}^*\bigr)=1-o(1),

where ⊆\subseteq denotes inclusion of edges. The conjecture compares uniformly random regular graphs with Erdős–Rényi graphs of asymptotically matching edge density; it is known in some degree ranges, but it remains open for the missing range log⁡N≪d≪log⁡4N/log⁡3log⁡N\log N\ll d\ll \log^4 N/\log^3\log N.

References

Primary source

Marvin Lücke, Jobst Heitzig, Péter Koltai, Nora Molkenthin and Stefanie Winkelmann, “Large population limits of Markov processes on random networks”, arXiv:2210.02934 (2023).

Additional references

3 papers in this index state this conjecture (2006–2022). The statement above is taken from the most recent of them; the others are arXiv:2104.11850, arXiv:math/0611321.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.