Block tree diameter gap beyond √(log n)

Informal Conjecture (diameter bound improvement) · arXiv:1408.4257

arXiv Informal medium confidence— first stated 2016-05-16

Authors: Colin McDiarmid, Alex Scott

Status solved high confidence

The conjecture that the $\sqrt{\log n}$ factor in the diameter bound $5\sqrt{n\log n}$ for $BT(R_n)$ can be replaced by any function tending to infinity is resolved by Addario-Berry and Donderwinkel (arXiv:2201.11773). Their paper explicitly states it resolves 'a conjecture by McDiarmid and Scott on the block-diameter of a family of random graphs called block-graphs,' and the result is in fact stronger: they prove sub-Gaussian tail bounds for the block-diameter, going beyond the asymptotic tightness that was conjectured.

Cited literature (1)

proof Random trees have height O(\sqrt{n}) (2022)

Louigi Addario-Berry, Serte Donderwinkel · arXiv preprint · arXiv:2201.11773 · doi:10.48550/arXiv.2201.11773

Theorem 25 resolves the McDiarmid–Scott conjecture on block-diameter of block-stable random graphs, and moreover provides sub-Gaussian tail bounds stronger than the original conjecture.

Reviewer notes. The resolution by Addario-Berry and Donderwinkel is stronger than the original conjecture: rather than merely showing the sqrt(log n) gap can be closed to an arbitrarily slow function, they establish sub-Gaussian tail bounds for the block-diameter. The paper arXiv:2201.11773 (v3 March 2024) was submitted to the Annals of Probability; no journal DOI was found beyond the arXiv DOI.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. The extra factor $\sqrt{\log n}$ (compared with the random tree $T_n$) in the diameter bound $5\sqrt{n \log n}$ for the block tree $BT(R_n)$ could be replaced by any function tending to $\infty$.

Context

Theorem 1.2 establishes that, for $R_n$ sampled uniformly from the connected graphs in a block-stable class, the block forest $BF(R_n)$ has diameter at most $5\sqrt{n \log n}$ whp. Random labelled trees have diameter of order $\sqrt{n}$, so a gap of $\sqrt{\log n}$ remains between the two bounds. The authors conjecture this gap can be closed down to an arbitrarily slowly growing function.

Notes. Stated in prose immediately before Theorem 1.2: 'We conjecture that the extra factor √log n (compared with the random tree Tn) could be replaced by any function tending to ∞.' No labelled conjecture environment.

Source paper

Random graphs from a block-stable class
Colin McDiarmid, Alex Scott · 2016-05-16
https://arxiv.org/abs/1408.4257 PDF source