Kim–Vu sandwich conjecture for random regular graphs

About 6 years old · traced to

Let dd be a degree parameter satisfying d≫log⁡nd\gg\log n. For sequences p1=p1(n)∼d/np_1=p_1(n)\sim d/n and p2=p2(n)∼d/np_2=p_2(n)\sim d/n, consider a random dd-regular graph R(n,d)\mathbb R(n,d) and binomial random graphs G(n,p1)\mathbb G(n,p_1) and G(n,p2)\mathbb G(n,p_2). Kim–Vu sandwich conjecture. There is a joint distribution of these graphs such that, with high probability,

G(n,p1)⊆R(n,d)⊆G(n,p2).\mathbb G(n,p_1)\subseteq\mathbb R(n,d)\subseteq\mathbb G(n,p_2).

The conjecture seeks to couple a random regular graph between two binomial random graphs with asymptotically matching edge probabilities. Such a sandwiching result would provide a different route to proving that the paper's Bi-uniform construction yields a suitable point set; the source does not state whether the conjecture has been resolved.

References

Primary source

Benedek Kovács, Zoltán Lóránt Nagy and Dávid R. Szabó, “Settling the no-(k+1)-in-line problem when k is not small”, arXiv:2502.00176 (2025).

Additional references

4 papers in this index state this conjecture (2020–2025). The statement above is taken from the most recent of them; the others are arXiv:2402.17857, arXiv:2302.09729, arXiv:2011.09449.

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.