Mixing-time bound for giant components of random graphs with given degrees

From papers

Let mm be the number of edges, let n0(D)n_0(\mathcal D) denote the number of vertices of degree zero, let m2m^{\neq 2} denote the number of edges incident to vertices whose degrees are not equal to 22, and let Δ\Delta be the maximum degree. A degree sequence is feasible if it is realizable by a graph, and a graph has a giant component if it has a component of linear order. For any function hh tending to infinity with mm, let (D)1(\mathcal D_{\ell})_{\ell\geq 1} be a sequence of feasible degree sequences. Mixing-time conjecture. If n0(D)=0n_0(\mathcal D_{\ell})=0 and G(D)G(\mathcal D_{\ell}) has a giant component, then with high probability the mixing time of every component is

O(h(m)(logm2)2max(Δ2m,(mm2)2)).O\left(h(m)(\log m^{\neq 2})^2\max\left(\frac{\Delta^2}{m},\left(\frac{m}{m^{\neq 2}}\right)^2\right)\right).

The conjecture would give a near-optimal general upper bound for mixing times while accounting for large degrees and long degree-two chains; the examples preceding it show why restrictions on the degree sequence are necessary. Its resolution status is not specified in the source.

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, Bruce Reed and Corrine Yap, “Diameters and mixing times for giant components of random graphs with given degrees”, arXiv:2605.16511 (2026).

Solutions 0

No solutions have been posted yet.