Uniform upper bound conjecture for diameters of random graphs with minimum degree

From papers

For integers nn and dd, let Sn,d \mathcal S_{n,d} be the set of degree sequences d=(d1,,dn) \boldsymbol{d}=(d_1,\ldots,d_n) with minidid \min_i d_i\geq d, and let G \boldsymbol{G} be uniformly distributed over graphs with degree sequence d \boldsymbol{d}, denoted GuGd \boldsymbol{G}\in_u\mathcal G_{ \boldsymbol{d}}.

Minimum-degree diameter conjecture. For every d3d\geq3 and ϵ>0 \epsilon>0,

lim supnsupdSn,dPGuGd(diam(G)>(1+ϵ)logd1n)=0.\limsup_{n\to\infty}\sup_{ \boldsymbol{d}\in\mathcal S_{n,d}}\mathbb P_{ \boldsymbol{G}\in_u\mathcal G_{ \boldsymbol{d}}}\left(\operatorname{diam}( \boldsymbol{G})>(1+ \epsilon)\log_{d-1}n\right)=0.

The conjecture asserts that random dd-regular graphs have, to first order, the largest diameter among random graphs whose minimum degree is at least dd, uniformly over all admissible degree sequences.

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).

Solutions 0

No solutions have been posted yet.