CS Paper Radar

Mixing Times of Switch Chains via High-Dimensional Expansion

Sawyer Jack Robertson

cs.DM math.PRmath.CO ·submitted 2026-10-07 06:05 UTC · v1

Abstract

The switch chain is a Markov chain defined on the set of labelled realizations of a given graphical degree sequence. At each step, a pair of vertex-disjoint edges is chosen at random and the process attempts to replace them with a uniformly chosen perfect matching of the same four vertices, rejecting any proposal that would create a multiple edge. The resulting process is reversible with respect to the uniform distribution on all realizations. We investigate the mixing time of this chain by viewing realizations as the facets of a simplicial complex and studying a variant of the original process called the simplicial switch chain, which we analyze using tools from the theory of high-dimensional expansion. Our technical contributions include a proof that links of faces of sufficiently high codimension are strong spectral expanders and a comparison between the Dirichlet energies of large block updates and two-edge updates. Our main result is an $O(Δ^{2}m\log m)$ bound on the mixing time of both simplicial and classical switch chains whenever $m\ge CΔ^{8}$, where $m$ is the number of edges, $Δ$ is the maximum prescribed degree, and $C>0$ is an absolute constant. For sequences on $n$ vertices with fixed maximum degree, this proves that the chain mixes in $O(n\log n)$ steps, resolving a longstanding conjecture of Cooper, Dyer, and Greenhill and extending its conclusion to irregular degree sequences.

Comment
52 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

On the self-intersection time of non-backtracking random walks

cs.DS math.PRmath.CO ·2026-08-10 ·Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen, Mark Jerrum, Gabor Pete +2 more
theory similarity 0.65
Abstract

We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ\geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $Δ$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $Ω(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $Δ$-regular graphs at the tree uniqueness threshold.

0.40

Spectral Gap of Down-Up Walks via Trickle-Down: A Simplified and Sharpened Analysis

cs.DS cs.DMmath.COmath.PR ·2026-09-17 ·Xiaoyu Chen, Kuikui Liu
theoryhighly cited similarity 0.64
Abstract

Local-to-global techniques for establishing spectral gaps have played a central role in the modern theory of Markov chain mixing times and the theory of high-dimensional expanders. One of the most striking results in this burgeoning literature is that a spectral gap for the global down-up walk on the facets of a pure simplicial complex can be reduced to sufficiently strong spectral expansion of just the codimension-2 links of the complex, a phenomenon colloquially referred to as "trickle-down". These types of theorems have had many important applications, including rapid mixing of the exchange walk on the bases of any matroid. In this primarily expository article, we give streamlined proofs of two such theorems in the literature, one by Oppenheim (2018) and one by Leake and Oveis Gharan (2025), via an integrated Bochner method. Moreover, in the latter setting, we quantitatively strengthen the dependence of the global spectral gap on the dimension of the complex and the spectral influence, resolving an open question of Leake and Oveis Gharan. Disclaimer: The proofs were developed through a couple of rounds of interaction with GPT-5.6 Sol Ultra. We later discovered that Guo and Zhang (2026) had independently proven the same strengthening of the trickle-down theorem of Leake and Oveis Gharan using an extremely similar argument, also found by GPT-5.6 Sol Ultra. The focus of their paper is the complexity of approximating the partition function of spin systems on planar graphs, not on the trickle-down phenomenon itself. In contrast, our motivation is primarily expository, and we hope to bring Bochner-type methods and their connections with the trickle-down phenomenon to the attention of a wider community of researchers.

0.49

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$-Uniform Directed Graphs

cs.DS ·2026-10-13 ·Richard Peng, Sushant Sachdeva, Junzhao Yang, Yibin Zhao
similarity 0.64
Abstract

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $γ$, we give a $(1\pm\varepsilon)$ effective-resistance data structure with expected update time $O(γ^{-4}\varepsilon^{-2}\log n\log^4(n/\varepsilon))$ and expected $O(1)$ query time. For directed graphs, somewhat surprisingly, the OMv conjecture precludes a fast data structure based on rapid mixing conditions alone. To address this, we introduce the notion of $κ$-uniform directed graphs, which requires the stationary distribution to $κ$-approximate the uniform distribution, and show that in this setting, random walk based data structures with $\text{poly}(κ, \log{n}, \varepsilon^{-1})$ update/query times are possible.

0.21

Local-to-Global Theorems Based on Cones with Applications to Graph Coloring

cs.DM math.PRcs.DSmath.CO ·2026-10-27 ·Anqi Li, Shayan Oveis Gharan
similarity 0.61
Abstract · 26 pages

Local-to-Global theorems are a cornerstone of many of recent developments in theoretical computer science from coding theory and PCPs all the way to analyzing mixing time of Markov chains. Building on trickledown theorems on simplicial complexes, several techniques have been established to obtain tighter local-to-global theorems to analyze the spectral gap of the Glauber dynamics, namely matrix trickledown, ${\mathcal C}$-Lorentzian polynomials and more recently Bochner type inequalities. In this paper, we adopt non-local local-to-global/Bochner type inequalities on "cones", corresponding to the local neighborhood of a given vertex, to show that the Glauber dynamics mixes in polynomial time to sample proper colorings of maximum degree $Δ$ graphs as long as $q\geq 1.7408Δ$.

0.46

A Tale of Two Walks: From Kac to KMP and Back

cs.DS quant-phmath.PR ·2026-09-29 ·Qian Chen, Jingcheng Liu, Minglong Qin, Leonard J. Schulman, Fang Song +2 more
theory similarity 0.59
Abstract · 79 pages, 2 figures

We reveal an unexpected connection between two interacting particle systems: Kac's walk and the Kipnis-Marchioro-Presutti (KMP) process. We first establish a mixing-time analogue of Aldous's conjecture for the KMP process on general graphs: the mixing time of the $t$-particle process on any connected $d$-vertex graph is at most $O(\log d)$ times the corresponding single-particle mixing time, uniformly in $t$. As an application, we improve the mixing-time bound for coordinate hit-and-run on the $n$-dimensional standard simplex from $\widetilde{O}(n^3)$ [KV26] to $O(n\log n)$, while removing the dependence on the initial distribution. We then show that the twirling channel induced by the parallel Kac's walk on the symmetric subspace can be exactly encoded by a Markov chain on partitions, which naturally lifts to a parallel KMP chain on the complete graph. We prove that $O(\log d+\log(1/\varepsilon))$ repetitions of the parallel Kac's walk suffice to approximate Haar twirling on the symmetric subspace of $(\mathbb{C}^d)^{\otimes t}$ to error $\varepsilon$, uniformly in all $t$. Our main technical contribution is a new structural property of KMP-type dynamics: conditional product structure, which holds for both the standard KMP processes on general graphs and the parallel KMP processes on complete graphs. Conditioned on suitable auxiliary randomness, the evolution of the labeled KMP process factorizes into independent single-particle updates. Combining this structure with an exact coupling, we remove the dependence on the number of particles from the mixing bounds for both unlabeled KMP models. This bypasses the $\log(π_{\min}^{-1})$ dependency from spectral-gap arguments, which is often prohibitively large for many-particle systems. Using this framework, we prove mixing bounds that are sharp up to logarithmic factors for both unlabeled KMP models.

0.26

Degenerating orbits of the Longest Edge Bisection process

cs.CG math.DSmath.COmath.PR ·2026-09-08 ·Karim A. Adiprasito, Daniel Kalmanovich, Yaar Solomon
theoryhighly cited similarity 0.58
Abstract · 30 pages, comments are welcome!

We study the Longest Edge Bisection (LEB) process as a dynamical system on the projective shape space of simplices. A long-standing conjecture going back to Adler and Rivara-Levin and motivated by finite-element mesh refinement, often taken as a standing assumption, is that this procedure is non-degenerate and, in fact, in a certain way periodic. We prove: \begin{itemize} \item There are 3-dimensional simplices such that the longest edge-bisection algorithm degenerates. \item There is an open set of 4-dimensional simplices on which the longest edge-bisection algorithm degenerates. \item If parametrizing the space of $d$-dimensional simplices by independent standard Gaussian vectors, then as $d$ increases, a random simplex degenerates asymptotically almost surely. \end{itemize} This is realized through exhibiting hyperbolic behaviour of the LEB process. We also exhibit elliptic behaviour that is nonperiodic.

0.60

Optimal mixing of random-to-random shuffling on linear extensions

cs.DS math.PR ·2026-11-15 ·Haoran Wang
theory similarity 0.58
Abstract

Uniform sampling of linear extensions is a basic problem in randomized algorithms and the study of finite posets. We prove that the random-to-random shuffle of Ayyer, Schilling, and Thiéry mixes in $O(n\log n+n\log(1/\varepsilon))$ steps on every $n$-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an $\varepsilon$-approximate uniform sampler using $O(n^2(\log n+\log(1/\varepsilon)))$ elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor $1-1/n$ for the promotion half-step. Consequently, the uniform extended-promotion chain has the same mixing order. We represent complete promotion scans as reflected coordinate paths in the order polytope and prove that a convex potential with gradients in the same polytope has diagonal Hessian mass at most one along each path. Applying this estimate to an optimal transport potential yields a sharp entropy factorization for every finite-entropy input. Linearization also gives the spectral-gap lower bound $(n+1)/n^2$.

0.32

Single-Vertex Metropolis on Minor-Free Graphs: A General EPTAS

cs.DS math.CO ·2026-11-17 ·Daniel Skachkov, Yuriy Dorn
theory similarity 0.58
Abstract

We consider a class of combinatorial optimization problems where the goal is to find a largest induced subgraph with a prescribed property. We assume that the property is preserved by taking induced subgraphs and disjoint unions, holds for all edgeless graphs, and can be tested in polynomial time. We study the single-vertex Metropolis process for this class of problems. We show that on graphs excluding an arbitrary fixed minor $H$, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with $n$ vertices, it finds a $(1-\varepsilon)$-approximation within $\exp(O_H(\varepsilon^{-2})) n(n+\log(1/δ))$ steps with probability at least $1-δ$. This includes maximum independent set, maximum induced forest, maximum induced bipartite subgraph, and maximum induced subgraph of degree at most one. The proof uses improving exchanges on one fixed division of the input graph into regions. A recursive separator construction performs each exchange inside a region of size $r$ in at most $2r$ moves, with temporary loss $O_H(\sqrt r)$. We count move sequences through each transition and bound the probability of avoiding all near-optimal states. The general theorem bounds the number of Metropolis steps in terms of the temporary loss along improvement paths. We extend the result to bounded weight imbalance and give a weighted-star obstruction for unrestricted weights.

0.18