Sandwich conjecture for random regular graphs

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 pp_* and pp^*, let GGN,p\bm{G}_*\sim\bm{G}_{N,p_*} and GGN,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 logN\log N asymptotically, there exist

p=(1o(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(GGN,dG)=1o(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 logNdlog4N/log3logN\log N\ll d\ll \log^4 N/\log^3\log N.

Sources & referencesView supporting material

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.