Stochastic diameter monotonicity conjecture for random graphs with fixed surplus

From papers

Let d \boldsymbol{d} and d \boldsymbol{d}' be degree sequences, let s(d)s( \boldsymbol{d}) denote surplus, and let nb(d)n_b( \boldsymbol{d}) denote the number of vertices of degree bb. Let G \boldsymbol{G} and G \boldsymbol{G}' be uniformly distributed over connected graphs with degree sequences d \boldsymbol{d} and d \boldsymbol{d}', respectively.

Stochastic diameter monotonicity conjecture. If

s(d)=s(d),n1(d)=n1(d),n2(d)=n2(d),nb(d)=0(b>3),s( \boldsymbol{d})=s( \boldsymbol{d}'),\qquad n_1( \boldsymbol{d})=n_1( \boldsymbol{d}'),\qquad n_2( \boldsymbol{d})=n_2( \boldsymbol{d}'),\qquad n_b( \boldsymbol{d})=0\quad(b>3),

then

diam(G)stdiam(G).\operatorname{diam}( \boldsymbol{G}')\preceq_{\operatorname{st}}\operatorname{diam}( \boldsymbol{G}).

Here st \preceq_{\operatorname{st}} 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

No solutions have been posted yet.