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

Less than 1 year old · traced to

Let mm be the number of edges, let n0(D)n_0(\mathcal D) denote the number of vertices of degree zero, let m≠2m^{\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)(log⁡m≠2)2max⁡(Δ2m,(mm≠2)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.

References

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).

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.