Stochastic diameter monotonicity conjecture for random graphs with fixed surplus
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.