1 · The essentials
Imagine a set of labeled points, with a prescribed number of connections for each point. The task is to choose fairly among all undirected connection patterns that meet those requirements, with no self-connections or repeated connections. The main result says that repeated random changes preserving those requirements approach a fair choice in a number of steps bounded by a polynomial in the number of points. It applies to every list of connection counts for which at least one such pattern exists. For the particular random procedure in the manuscript, the stated bound is steps at a specified level of closeness, where is the number of points. The manuscript also presents a different guarantee: an exactly fair sampling algorithm that finishes with probability one and has polynomial expected running time measured in bit operations. The main mixing result has a Lean formalization; this should not be taken to mean that every additional claim is formalized.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine rearranging a network of friendships while keeping each person's number of friends unchanged. The random rearrangement procedure eventually comes close to choosing fairly among all allowed networks, rather than favoring the one you started with. The image is imperfect because the result concerns a precisely specified mathematical procedure, not how real friendships change.
Why it matters
The result gives a single polynomial mixing guarantee for every feasible degree sequence in the simple-undirected setting, rather than requiring additional restrictions on those sequences. The manuscript describes this as resolving the simple-undirected form of the Kannan–Tetali–Vempala conjecture. Its exact-sampling result also distinguishes obtaining an approximately uniform graph after a bounded number of steps from obtaining an exactly uniform graph with polynomial expected bit cost.
2 · Going further
The precise setting is the collection of simple undirected graphs on labeled vertices with a fixed graphical degree sequence: each vertex has a prescribed degree, and at least one graph satisfies those prescriptions. The switch chain randomly changes edges while keeping these degrees fixed. For the lazy version that proposes switches uniformly on four vertices, the manuscript states that the total-variation mixing time at distance is at most . This is a polynomial bound for every graphical degree sequence in this setting.
The source identifies this statement as the simple-undirected form of the Kannan–Tetali–Vempala conjecture. The abstract describes the random procedure and its bound, but does not give the mechanism of the mixing argument. Thus, the central construction visible in the supplied material is the uniformly proposed four-vertex switch procedure; a more detailed explanation of how its mixing bound is established would require material not supplied here.
The same manuscript also presents an exactly uniform sampler for every graphical labeled degree vector. It uses unbiased random bits, terminates almost surely, and has expected polynomial bit running time. Only one manuscript is supplied, so there is no companion-manuscript relationship to describe. The main mixing result has a Lean formalization, but the supplied material does not specify whether that formalization also covers the exact sampler.
Useful notions
- Graphs as vertices joined by edges
- Vertex degrees and prescribed degree sequences
- Uniform random sampling
- Random processes and mixing time
- Polynomial running time
What was known before / what is new
Before
The source names the Kannan–Tetali–Vempala conjecture as the problem being addressed, specifically its simple-undirected form. It does not describe earlier partial results, earlier bounds, or the history of the conjecture.
New
The main result supplies a polynomial mixing bound for every graphical degree sequence in the simple-undirected setting. For the stated lazy four-vertex proposal chain, the explicit bound is at total-variation distance . The manuscript additionally shows an exactly uniform sampling algorithm using unbiased random bits with almost-sure termination and expected polynomial bit running time.
Limits and assumptions
The graphs must be simple, undirected, and labeled, and the prescribed degree sequence must be graphical. The explicit mixing bound concerns the lazy chain with uniformly proposed four-vertex switches and the stated distance threshold of ; it is an approximate-uniformity guarantee, not exact sampling after that many steps. Exact uniformity is a separate algorithmic claim, with an expected polynomial bit cost rather than a stated worst-case running-time bound. The main mixing result has a Lean formalization, but its detailed scope and coverage of the sampling claim are not specified in the supplied material. The source does not identify remaining open questions or assert corresponding results outside the simple-undirected setting.
Mini glossary
- Simple undirected graph —
- A collection of vertices connected by edges without direction, self-connections, or repeated edges.
- Graphical degree sequence —
- A list of prescribed vertex degrees that can be realized by at least one graph in the specified setting.
- Switch chain —
- A random process that changes a graph's edges through switches while preserving its prescribed vertex degrees.
- Lazy chain —
- A random process that allows a step to leave its current state unchanged.
- Total-variation mixing time —
- The number of steps needed for the process's distribution to be within a specified total-variation distance of its target distribution.
- Exactly uniform sampler —
- An algorithm that outputs each allowed labeled graph with the same probability.
Keywords : Switch chain · Degree sequence · Uniform sampling
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Resolves the simple-undirected Kannan–Tetali–Vempala conjecture: the lazy edge-switch chain mixes in time for every graphical labeled degree sequence. The same degree-constrained graphs can also be sampled exactly uniformly by an almost-surely terminating algorithm with expected polynomial bit running time.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Polynomial mixing of the switch chain for every graphical degree sequence
25/09/2026We prove the simple-undirected form of the Kannan–Tetali–Vempala conjecture: the switch chain on simple undirected graphs mixes in polynomial time for every graphical degree sequence. For a lazy chain that proposes switches uniformly on four vertices, the total-variation mixing time at distance 1/4 is at most . We also give an exactly uniform sampler for every graphical labeled degree vector. It uses unbiased random bits, terminates almost surely, and has expected polynomial bit running time.