Kim–Vu sandwich conjecture for random regular graphs
Let be a degree parameter satisfying . For sequences and , consider a random -regular graph and binomial random graphs and . Kim–Vu sandwich conjecture. There is a joint distribution of these graphs such that, with high probability,
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
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.