Uniform upper bound conjecture for diameters of random graphs with minimum degree
Uniform upper bound conjecture for diameters of random graphs with minimum degree
For integers and , let be the set of degree sequences with , and let be uniformly distributed over graphs with degree sequence , denoted .
Minimum-degree diameter conjecture. For every and ,
The conjecture asserts that random -regular graphs have, to first order, the largest diameter among random graphs whose minimum degree is at least , 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
Sign in to submit a solution.
No solutions have been posted yet.