Sequential Sweeps and High Dimensional Expansion

Ori Parzanchevski; Vedat Levi Alev

arxiv: 2312.02089 · v3 · submitted 2023-12-04 · 💻 cs.DM

Sequential Sweeps and High Dimensional Expansion

Vedat Levi Alev , Ori Parzanchevski This is my paper

Pith reviewed 2026-05-24 04:54 UTC · model grok-4.3

classification 💻 cs.DM

keywords sequential sweephigh dimensional expandersspectral gapGlauber dynamicssimplicial complexeslocal spectral expansionentropy contraction

0 comments

The pith

Under strong local spectral assumptions, the sequential sweep on n-partite complexes achieves spectral gap arbitrarily close to 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Standard down-up walks on n-partite simplicial complexes are limited to spectral gaps of order 1/n by obstructions such as coboundaries. The paper studies the sequential sweep, which updates coordinates in a fixed deterministic order instead of selecting them randomly. When the complex satisfies a sufficiently strong local spectral assumption, one full sweep attains a spectral gap that can be made arbitrarily close to 1. The same local condition also implies an entropy contraction inequality for the walk. The argument extends known rapid mixing of sequential sweeps on Ramanujan complexes to the broader setting of high-dimensional expanders.

Core claim

Under the strong local spectral assumption of Gur, Lifschitz, Liu, the spectral gap of the sequential sweep walk can be made arbitrarily close to 1, while the spectral gap of the n-th power of the down-up walk remains bounded by a constant. Under local entropy contraction assumptions, the sequential sweep satisfies an entropy contraction inequality. This generalizes the rapid mixing result for sequential sweeps on Ramanujan complexes to suitable high dimensional expanders.

What carries the argument

The sequential sweep (systematic scan Glauber dynamics), which traverses the n coordinates in a fixed deterministic order and applies the local update to each coordinate in turn.

If this is right

The mixing time of the sequential sweep becomes independent of n under the local spectral assumption.
High dimensional expanders admit rapid mixing via systematic scan Glauber dynamics.
The walk satisfies an entropy contraction inequality under the related local entropy contraction condition.
Rapid mixing results extend from Ramanujan complexes to all high dimensional expanders meeting the local spectral condition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Ordered update schemes may be preferable to random coordinate selection for sampling on certain expanders.
The local-to-global spectral lifting technique could apply to other deterministic scan orders in Markov chain analysis.
Constructions of high dimensional expanders can be checked directly for the local spectral strength required to reach gap near 1.

Load-bearing premise

The n-partite simplicial complex satisfies the strong local spectral assumption defined in Gur, Lifschitz, Liu (STOC 2022).

What would settle it

An explicit n-partite simplicial complex that satisfies the strong local spectral assumption yet has sequential sweep spectral gap bounded strictly below 1.

read the original abstract

It is well known that the spectral gap of the down-up walk over an $n$-partite simplicial complex (also known as Glauber dynamics) cannot be better than $O(1/n)$ due to natural obstructions such as coboundaries. We study an alternative random walk over partite simplicial complexes known as the sequential sweep or the systematic scan Glauber dynamics: Whereas the down-up walk at each step selects a random coordinate and updates it based on the remaining coordinates, the sequential sweep goes through each of the coordinates one by one in a deterministic order and applies the same update operation. It is natural, thus, to compare $n$-steps of the down-up walk with a single step of the sequential sweep. Interestingly, while the spectral gap of the $n$-th power of the down-up walk is still bounded from above by a constant, under a strong enough local spectral assumption (in the sense of Gur, Lifschitz, Liu, STOC 2022) we can show that the spectral gap of this walk can be arbitrarily close to 1. We also study other isoperimetric inequalities for these walks, and show that under the assumptions of local entropy contraction (related to the considerations of Gur, Lifschitz, Liu), these walks satisfy an entropy contraction inequality. Concretely, we generalize a result of Lubetzky, Lubotzky, and Parzanchevski (Journal of the EMS) about the rapid mixing of sequential sweep in Ramanujan complexes to suitable high dimensional expanders.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extends rapid mixing for sequential sweeps to general high-dim expanders under Gur et al local assumption, generalizing the Ramanujan case while staying conditional on that premise.

read the letter

This paper shows that sequential sweeps achieve spectral gap close to 1 on n-partite complexes when the strong local spectral assumption from Gur-Lifschitz-Liu holds, beating the O(1/n) cap on standard down-up walks. It also gets entropy contraction under the related local entropy condition. The main new piece is carrying the Lubetzky-Lubotzky-Parzanchevski rapid-mixing result over from Ramanujan complexes to arbitrary high-dimensional expanders that meet the local assumption. The write-up does a clean job contrasting the fixed-order sweep with random coordinate selection and explaining how the deterministic order sidesteps coboundary obstructions. The argument stays consistent with the cited prior work and does not introduce circular steps or self-referential fitting. The central limitation is that everything is conditional on the local assumption being strong enough; the paper does not claim the assumption holds for most complexes, so applicability stays narrow if the premise is rare or hard to check. No load-bearing gaps appear in the abstract or stress-test description. Readers working on high-dimensional expanders, mixing times, or sampling algorithms will get value from the concrete improvement under the stated conditions. I would bring this to a reading group as maybe, since the conditional framing makes it worth discussing but not essential for everyone. I would not cite it in my own work in the next year unless I am directly in this subfield. It deserves peer review because the extension is substantive and the claims rest on external verifiable assumptions rather than internal contradictions.

Referee Report

0 major / 3 minor

Summary. The paper studies an alternative to the down-up walk on n-partite simplicial complexes called the sequential sweep (systematic scan Glauber dynamics), in which coordinates are updated in a fixed deterministic order rather than randomly. It claims that, while the n-step down-up walk remains bounded by a constant spectral gap, the sequential sweep achieves spectral gap arbitrarily close to 1 under a sufficiently strong local spectral assumption (Gur-Lifschitz-Liu, STOC 2022). The manuscript also derives entropy contraction for these walks under local entropy contraction assumptions and generalizes the rapid-mixing result of Lubetzky-Lubotzky-Parzanchevski (JEMS) from Ramanujan complexes to suitable high-dimensional expanders.

Significance. If the local spectral and entropy assumptions hold for the n-partite complexes under consideration, the result supplies a concrete mechanism for obtaining near-optimal mixing via systematic scan on high-dimensional expanders, extending prior work on Ramanujan complexes. The conditional framing and explicit dependence on the Gur et al. assumption are stated clearly, which strengthens the contribution by avoiding over-claim. No machine-checked proofs or parameter-free derivations are present, but the generalization to HDX and the entropy-contraction extension are substantive if the premises apply.

minor comments (3)

Abstract, line 8: the phrase 'arbitrarily close to 1' should be accompanied by a brief parenthetical indicating the dependence on the strength of the local spectral assumption (e.g., 'as the local gap parameter tends to 1').
The manuscript should add a short paragraph in the introduction clarifying whether the Gur-Lifschitz-Liu local spectral assumption is known to hold for any explicit infinite family of n-partite complexes beyond Ramanujan complexes, or whether this remains open.
Notation: the distinction between the single-step sequential sweep operator and its n-fold composition should be denoted consistently (e.g., P_seq vs P_seq^n) throughout the proofs to avoid reader confusion when comparing to the n-step down-up operator.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. The review correctly identifies the core contributions and the conditional nature of the results under the Gur-Lifschitz-Liu assumptions.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central results on spectral gap and entropy contraction for the sequential sweep are explicitly conditional on the external local spectral assumption from Gur-Lifschitz-Liu (STOC 2022) and generalize an independent prior result on Ramanujan complexes from Lubetzky-Lubotzky-Parzanchevski. No derivation step reduces by the paper's own equations to a fitted input, self-definition, or unverified self-citation chain; the cited works supply independent external support rather than closing a loop within this manuscript.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the external local spectral assumption from Gur et al. and standard facts about simplicial complexes and random walks; no free parameters are fitted and no new entities are postulated.

axioms (1)

domain assumption Strong local spectral assumption as defined in Gur, Lifschitz, Liu, STOC 2022
Invoked to transfer local expansion to global spectral gap close to 1 for the sequential sweep.

pith-pipeline@v0.9.0 · 5805 in / 1339 out tokens · 31589 ms · 2026-05-24T04:54:11.546251+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

under a strong enough local spectral assumption (in the sense of Gur, Lifschitz, Liu, STOC 2022) we can show that the spectral gap of this walk can be arbitrarily close to 1
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

σ₂(P_seq)² ≤ 1 − ∏_{j=2}^n (1 − (ε_{[j−1]→j})²)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

En- tropic independence ii: optimal sampling and concentratio n via restricted modiﬁed log- sobolev inequalities

[AJK+21] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pha m, and Thuy-Duong V uong. En- tropic independence ii: optimal sampling and concentratio n via restricted modiﬁed log- sobolev inequalities. arXiv preprint arXiv:2111.03247 ,

work page arXiv
[2]

Random walks on ﬁnite groups and rapid ly mixing Markov chains

[Ald83] David Aldous. Random walks on ﬁnite groups and rapid ly mixing Markov chains. In Séminaire de Probabilités XVII 1981/82 , pages 243–297. Springer,

work page 1981
[3]

Spe ctral independence in high- dimensional expanders and applications to the hardcore mod el

[ALO20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spe ctral independence in high- dimensional expanders and applications to the hardcore mod el. CoRR, abs/2001.00303,

work page arXiv 2001
[4]

On mixing of markov chains: Coupling, spectral inde pendence, and entropy fac- torization

[BCC+22] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Pa risi, Daniel Štefankoviˇ c, and Eric Vigoda. On mixing of markov chains: Coupling, spectral inde pendence, and entropy fac- torization. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA), pages 3670–3692. SIAM,

work page 2022
[5]

High dimensional expanders: Eigenstripping, pseudorandomness, and unique games

[BHKL22a] Mitali Bafna, Max Hopkins, T ali Kaufman, and Shac har Lovett. High dimensional expanders: Eigenstripping, pseudorandomness, and unique games. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1069–1128. SIAM,

work page 2022
[6]

Modiﬁed log -Sobolev inequalities for strongly log-concave distributions

[CGM19] Mary Cryan, Heng Guo, and Giorgos Mousa. Modiﬁed log -Sobolev inequalities for strongly log-concave distributions. CoRR, abs/1903.06081,

work page arXiv 1903
[7]

Rapid mixing for colorings via spectral independence

[CGSV20] Zongchen Chen, Andreas Galanis, Daniel Stefankov ic, and Eric Vigoda. Rapid mixing for colorings via spectral independence. CoRR, abs/2007.08058,

work page arXiv 2007
[8]

Rapid mi xing of Glauber dynamics up to uniqueness via contraction

[CLV20] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mi xing of Glauber dynamics up to uniqueness via contraction. arXiv preprint arXiv:2004.09083 ,

work page arXiv 2004
[9]

Improved b ounds for randomly colouring simple hypergraphs

[FGW22] W eiming Feng, Heng Guo, and Jiaheng W ang. Improved b ounds for randomly colouring simple hypergraphs. arXiv preprint arXiv:2202.05554 ,

work page arXiv
[10]

Rapid mixing from spectral independence beyond the boolean domain

[FGYZ20] W eiming Feng, Heng Guo, Yitong Yin, and Chihao Zhan g. Rapid mixing from spectral independence beyond the boolean domain. arXiv preprint arXiv:2007.08091 ,

work page arXiv 2007
[11]

A simple condition implying rapid mi xing of single-site dynamics on spin systems

[Hay06] Thomas P Hayes. A simple condition implying rapid mi xing of single-site dynamics on spin systems. In 2006 47th Annual IEEE Symposium on Foundations of Computer S cience (FOCS’06) , pages 39–46. IEEE,

work page 2006
[12]

From coupling to spectral independence and blackbox comparison with the down-up walk

[Liu21] Kuikui Liu. From coupling to spectral independence and blackbox comparison with the down-up walk. arXiv preprint arXiv:2103.11609 ,

work page arXiv
[13]

Banach zuk’s criterion for partit e complexes with application to random groups

[Opp21] Izhar Oppenheim. Banach zuk’s criterion for partit e complexes with application to random groups. arXiv preprint arXiv:2112.02929 ,

work page arXiv

[1] [1]

En- tropic independence ii: optimal sampling and concentratio n via restricted modiﬁed log- sobolev inequalities

[AJK+21] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pha m, and Thuy-Duong V uong. En- tropic independence ii: optimal sampling and concentratio n via restricted modiﬁed log- sobolev inequalities. arXiv preprint arXiv:2111.03247 ,

work page arXiv

[2] [2]

Random walks on ﬁnite groups and rapid ly mixing Markov chains

[Ald83] David Aldous. Random walks on ﬁnite groups and rapid ly mixing Markov chains. In Séminaire de Probabilités XVII 1981/82 , pages 243–297. Springer,

work page 1981

[3] [3]

Spe ctral independence in high- dimensional expanders and applications to the hardcore mod el

[ALO20] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spe ctral independence in high- dimensional expanders and applications to the hardcore mod el. CoRR, abs/2001.00303,

work page arXiv 2001

[4] [4]

On mixing of markov chains: Coupling, spectral inde pendence, and entropy fac- torization

[BCC+22] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Pa risi, Daniel Štefankoviˇ c, and Eric Vigoda. On mixing of markov chains: Coupling, spectral inde pendence, and entropy fac- torization. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discre te Algorithms (SODA), pages 3670–3692. SIAM,

work page 2022

[5] [5]

High dimensional expanders: Eigenstripping, pseudorandomness, and unique games

[BHKL22a] Mitali Bafna, Max Hopkins, T ali Kaufman, and Shac har Lovett. High dimensional expanders: Eigenstripping, pseudorandomness, and unique games. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1069–1128. SIAM,

work page 2022

[6] [6]

Modiﬁed log -Sobolev inequalities for strongly log-concave distributions

[CGM19] Mary Cryan, Heng Guo, and Giorgos Mousa. Modiﬁed log -Sobolev inequalities for strongly log-concave distributions. CoRR, abs/1903.06081,

work page arXiv 1903

[7] [7]

Rapid mixing for colorings via spectral independence

[CGSV20] Zongchen Chen, Andreas Galanis, Daniel Stefankov ic, and Eric Vigoda. Rapid mixing for colorings via spectral independence. CoRR, abs/2007.08058,

work page arXiv 2007

[8] [8]

Rapid mi xing of Glauber dynamics up to uniqueness via contraction

[CLV20] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mi xing of Glauber dynamics up to uniqueness via contraction. arXiv preprint arXiv:2004.09083 ,

work page arXiv 2004

[9] [9]

Improved b ounds for randomly colouring simple hypergraphs

[FGW22] W eiming Feng, Heng Guo, and Jiaheng W ang. Improved b ounds for randomly colouring simple hypergraphs. arXiv preprint arXiv:2202.05554 ,

work page arXiv

[10] [10]

Rapid mixing from spectral independence beyond the boolean domain

[FGYZ20] W eiming Feng, Heng Guo, Yitong Yin, and Chihao Zhan g. Rapid mixing from spectral independence beyond the boolean domain. arXiv preprint arXiv:2007.08091 ,

work page arXiv 2007

[11] [11]

A simple condition implying rapid mi xing of single-site dynamics on spin systems

[Hay06] Thomas P Hayes. A simple condition implying rapid mi xing of single-site dynamics on spin systems. In 2006 47th Annual IEEE Symposium on Foundations of Computer S cience (FOCS’06) , pages 39–46. IEEE,

work page 2006

[12] [12]

From coupling to spectral independence and blackbox comparison with the down-up walk

[Liu21] Kuikui Liu. From coupling to spectral independence and blackbox comparison with the down-up walk. arXiv preprint arXiv:2103.11609 ,

work page arXiv

[13] [13]

Banach zuk’s criterion for partit e complexes with application to random groups

[Opp21] Izhar Oppenheim. Banach zuk’s criterion for partit e complexes with application to random groups. arXiv preprint arXiv:2112.02929 ,

work page arXiv