Stochastic diameter monotonicity conjecture for random graphs with fixed surplus
Let and be degree sequences, let denote surplus, and let denote the number of vertices of degree . Let and be uniformly distributed over connected graphs with degree sequences and , respectively.
Stochastic diameter monotonicity conjecture. If
then
Here denotes stochastic domination.
This would formalize the heuristic that, at fixed surplus and fixed numbers of degree-one and degree-two vertices, allowing higher degrees reduces diameter; the source notes that it would imply sharper expected-diameter bounds for many positive-surplus ensembles.
References
Primary source
Louigi Addario-Berry and Gabriel Crudele, “Universal diameter bounds for random graphs with given degrees”, arXiv:2507.10759 (2025).
Additional references
2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2406.12745.
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.