Sandwich conjecture for random regular graphs
Sandwich conjecture for random regular graphs
Let be the number of vertices, let , and let denote a uniformly random -regular graph. For edge probabilities and , let and be Erdős–Rényi random graphs. Sandwich conjecture. If dominates asymptotically, there exist
such that
where 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 .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.