McDiarmid and Scott's conjecture on the diameter of block-stable random graphs

Let Cn\mathsf{C}_n be a uniform random graph from a block class, with each block receiving weight 00 or 11, and let tnt_n be a sequence tending to infinity. McDiarmid and Scott's conjecture. With high probability, every path in Cn\mathsf{C}_n passes through at most tnnt_n\sqrt{n} blocks. This conjecture predicts that the previously proved upper bound 5nlog(n)5\sqrt{n\log(n)} can be improved by replacing the factor log(n)\sqrt{\log(n)} with any sequence tending to infinity.

Sources & referencesView supporting material

Primary source

Benedikt Stufler, “Limits of random tree-like discrete structures”, arXiv:1612.02580 (2018).

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.