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

About 1 year old · traced to

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 min⁡idi≥d \min_i d_i\geq d, and let G \boldsymbol{G} be uniformly distributed over graphs with degree sequence d \boldsymbol{d}, denoted G∈uGd \boldsymbol{G}\in_u\mathcal G_{ \boldsymbol{d}}.

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

lim sup⁡n→∞sup⁡d∈Sn,dPG∈uGd(diam⁡(G)>(1+ϵ)log⁡d−1n)=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.

References

Primary source

Louigi Addario-Berry and Gabriel Crudele, “Universal diameter bounds for random graphs with given degrees”, arXiv:2507.10759 (2025).

Progress summary

Never refreshed

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.