Mixing-time bound for giant components of random graphs with given degrees
Mixing-time bound for giant components of random graphs with given degrees
Let be the number of edges, let denote the number of vertices of degree zero, let denote the number of edges incident to vertices whose degrees are not equal to , and let 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 tending to infinity with , let be a sequence of feasible degree sequences. Mixing-time conjecture. If and has a giant component, then with high probability the mixing time of every component is
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
Sign in to submit a solution.
No solutions have been posted yet.