# Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

Jason Gaitonde Department of Computer Science, Cornell University. Email:
<EMAIL_ADDRESS>Supported by NSF Award CCF-1408673 and AFOSR Award
FA9550-19-1-0183. Max Hopkins Department of Computer Science and Engineering,
UCSD, CA 92092. Email<EMAIL_ADDRESS>Supported by NSF Award
DGE-1650112. Tali Kaufman Department of Computer Science, Bar-Ilan University.
Email<EMAIL_ADDRESS>Supported by ERC and BSF. Shachar Lovett Department
of Computer Science and Engineering, UCSD, CA 92092. Email:
<EMAIL_ADDRESS>Supported by NSF Award CCF-1909634. Ruizhe Zhang
Department of Computer Science, UT Austin. Email<EMAIL_ADDRESS>
###### Abstract

We study the relationship between the underlying structure of posets and the
spectral and combinatorial properties of their higher-order random walks.
While fast mixing of random walks on hypergraphs (simplicial complexes) has
led to myriad breakthroughs throughout theoretical computer science in the
last five years, many other important applications (e.g. to locally testable
codes, 2-2 games) rely on the more general non-simplicial structure of posets.
These works make it clear that the global expansion properties of posets
depend strongly on their underlying architecture (e.g. simplicial, cubical,
linear algebraic), but the overall phenomenon remains poorly understood. In
this work, we quantify the advantage of different poset architectures,
highlighting how structural _regularity_ controls the spectral decay and edge-
expansion of corresponding random walks.

In particular, we show that the spectra of walks on expanding posets
(Dikstein, Dinur, Filmus, Harsha RANDOM 2018) concentrate in strips around a
small number of approximate eigenvalues controlled by the regularity of the
underlying poset. This gives a simple condition to identify poset
architectures (e.g. the Grassmann) that exhibit fast (exponential rate) decay
of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay
slowly (linear rate)—a crucial distinction in applications to hardness of
approximation and agreement testing such as the recent proof of the 2-2 Games
Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a
tight variance-based characterization of edge-expansion on expanding posets
generalizing (Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay
special attention to the case of the Grassmann where we show our results are
tight for a natural set of sparsifications of the Grassmann graphs. We note
for clarity that our results do not recover the characterization used in the
proof of the 2-2 Games Conjecture which relies on $\ell_{\infty}$ rather than
$\ell_{2}$-structure.

##  1 Introduction

Random walks on high dimensional expanders (HDX) have been the object of
intense study in theoretical computer science in recent years. Starting with
their original formulation by Kaufman and Mass [1], a series of works on the
spectral structure of these walks [2, 3, 4] led to significant breakthroughs
in approximate sampling [5, 4, 6, 7, 8, 9, 10, 11, 12, 13], CSP-approximation
[14, 15], error-correcting codes [16, 17], agreement testing [18, 19, 20], and
more. Most of these works focus on the structure of expansion in hypergraphs
(typically called simplicial complexes in the HDX literature). On the other
hand, it has become increasingly clear that hypergraphs are not always the
right tool for the job—recent breakthroughs in locally testable [21] and
quantum LDPC codes [22, 23, 24], for instance, all rely crucially on cubical
structure not seen in hypergraphs, while many agreement testing results like
the proof of the 2-2 Games Conjecture [25] rely crucially on linear algebraic
rather than simplicial structure.

In this work, we study a generalized notion of high dimensional expansion on
partially ordered sets (posets) introduced by Dikstein, Dinur, Filmus, and
Harsha (DDFH) [3] called expanding posets (eposets). Random walks on eposets
capture a broad range of important structures beyond their hypergraph analogs,
including natural sparsifications of the Grassmann graphs that recently proved
crucial to the resolution of the 2-2 Games Conjecture [25, 26, 27, 28, 29,
30]. DDFH’s notion of eposets is a _global_ definition of high dimensional
expansion based on a relaxation of Stanley’s [31] sequentially differential
posets, a definition originally capturing both the Grassmanian and complete
simplicial complex. More recently, Kaufman and Tessler (KT) [32] have extended
the study of eposets in two important aspects. First, in contrast to DDFH’s
original global definition, KT introduced the local-to-global study of high
dimensional expansion in eposets. Second, they identified regularity as a key
parameter controlling expansion. In particular, the authors showed
strengthened local-to-global theorems for strongly regular posets like the
Grassmann, giving the first general formulation for characterizing expansion
based on an eposet’s underlying architecture.

While analysis of the second eigenvalue is certainly an important
consideration (e.g. for mixing applications), a deeper understanding of the
spectral structure of eposets is required for applications like the proof of
the 2-2 Games Conjecture. As such, our main focus in this work lies in
characterizing the spectral and combinatorial behavior of random walks on
eposets beyond the second eigenvalue. Strengthening DDFH and recent work of
Bafna, Hopkins, Kaufman, and Lovett (BHKL) [15], we prove that at a coarse
level (walks on) eposets indeed exhibit the same spectral and combinatorial
characteristics as expanding hypergraphs (e.g. spectral stripping, expansion
of pseudorandom sets). On the other hand, as in KT, we show that the finer-
grained properties of these objects are actually controlled by the underlying
poset’s regularity, including the rate of decay of the spectrum and
combinatorial expansion of associated random walks. This gives a stronger
separation between structures like hypergraphs with weak (linear) eigenvalue
decay, and Grassmann-based eposets with strong (exponential) eigenvalue decay
(a crucial property in the proof of the 2-2 Games Conjecture [25]).

In slightly more detail, we show that all eposets exhibit a behaviour called
“eigenstripping” [2, 3, 15]: the spectrum of any associated random walk
concentrates around a few unique approximate eigenvalues. Moreover, the
approximate eigenvalues of walks on eposets are tightly controlled by the
poset architecture’s regularity111We will additionally assume a slightly
stronger condition introduced in KT [32] called middle regularity throughout.
See Section 2.1 for details. $R(j,i)$, which denotes the total number of
rank-$i$ elements222We consider regular graded posets, where each element has
a corresponding rank. In a hypergraph, for instance, rank is given by the size
of a set, while in the Grassmann poset it is given by subspace dimension. less
than any fixed rank-$j$ element (see Section 1.1 for standard definitions).
For simplicity, we specialize our result below to the popular “lower” or
“down-up” walk (this simply corresponds to taking a random step down and back
up the poset, again see Section 1.1); a more involved version holds for higher
order random walks in full generality.

######  Theorem 1.1 (Eigenstripping and Regularity (informal Corollary 4.5 and
Theorem 4.7)).

The spectrum of the lower walk $UD$ on a $k$-dimensional $\gamma$-eposet is
concentrated in $(k+1)$ strips:

$Spec(UD)\in\\{1\\}\cup\bigcup\limits_{i=1}^{k}[\lambda_{i}(UD)+O_{k}(\gamma),\lambda_{i}(UD)-O_{k}(\gamma)],$

where the approximate eigenvalues $\lambda_{i}(UD)$ are determined by the
poset’s regularity:

$\lambda_{i}(UD)=\frac{R(k-1,i)}{R(k,i)}.$

Theorem 1.1 generalizes and tightens recent work on expanding hypergraphs of
BHKL [15, Theorem 2.2] (which itself extended a number of earlier works on the
topic [2, 3, 14]). Additionally, our result on the connection between
regularity and approximate eigenvalues generalizes the work of KT [32], who
show an analogous result for $\lambda_{2}$. Theorem 1.1 reveals a stark
contrast between the spectral behavior of eposets with different regularity
parameters. As a prototypical example, consider the case of hypergraphs versus
subsets of the Grassmann ($k$-dimensional vector spaces over
$\mathbb{F}_{q}^{n}$). In the former, each $k$-set contains ${k\choose i}$
$i$-sets, leading to approximate eigenvalues that decay linearly
($\lambda_{i}\approx(k-i)/k$). On the other hand, each $k$-dimensional vector
space contains ${k\choose i}_{q}$ $i$-dimensional subspaces, which leads to
eigenvalues that decay exponentially ($\lambda_{i}\approx q^{-i}$). The latter
property, which we call strong decay is often crucial in applications (e.g.
for hardness of approximation [25] or fast algorithms [15]), and while it is
possible to recover strong decay on weaker posets by increasing the length of
the walk [15], this is often untenable in application due to the additional
degrees of freedom it affords.333For instance such a walk might take
exponential time to implement, or correspond to a more complicated agreement
test than desired.

The spectral structure of walks on eposets is closely related to their edge-
expansion, an important combinatorial property that has recently played a
crucial role both in algorithms for [33, 15] and hardness of unique games
[25]. The key insight in both cases lay in understanding the structure of non-
expanding sets. We give a tight understanding of this phenomenon across all
eposets in the so-called $\ell_{2}$-regime [15], where we show that expansion
is tightly controlled by the behavior of local restrictions called links (see
Definition 1.7).

######  Theorem 1.2 (Expansion in the $\ell_{2}$-Regime (informal Theorem
6.7)).

The expansion of any $i$-link is almost exactly $1-\lambda_{i}(M)$.
Conversely, any set with expansion less than $1-\lambda_{i+1}(M)$ has high
variance across $i$-links.

In [15], it was shown this characterization allows for the application of a
local-to-global algorithmic framework for unique games on such walks. This
remains true on eposets, and it is an interesting open question whether there
are significant applications beyond those given in BHKL’s original
work.444While one can apply the framework to playing unique games on the
Grassmann poset (or sparsifications thereof), the spectral parameters are such
that this does not give a substantial improvement over standard algorithms
[34].

Finally, as an application of our structure theorems, we give an in-depth
analysis of the $\ell_{2}$-structure of walks on expanding subsets of the
Grassmann poset called $q$-eposets (first studied in [3]). We focus in
particular on the natural $q$-analog of an important set of walks called
partial-swap walks introduced by Alev, Jeronimo, and Tulsiani [14] that
generalize the Johnson graphs when applied to expanding hypergraphs. We show
that applied to $q$-eposets, these objects give a natural set of walks
generalizing the Grassmann graphs and further prove that our generic analysis
for eposets gives a tight characterization of non-expansion in this setting.
We note that this does not recover the result used for the proof of the 2-2
Games Conjecture which lies in the $\ell_{\infty}$-regime (replacing variance
above with maximum) and requires a dimension-independent bound. This issue was
recently (and independently) resolved for simplicial complexes in [35] and
[36], and we view our work as an important step towards a more general
understanding for families like the Grassmann beyond hypergraphs.

###  1.1 Background

Before jumping into our results in any further formality, we’ll briefly
overview the theory of expanding posets and higher order random walks. All
definitions are covered in full formality in Section 2. A $d$-dimensional
graded poset is a set $X$ equipped with a partial order “<” and a ranking
function $r:X\to[d]$ that respects the partial order and partitions $X$ into
levels $X(0)\cup\ldots\cup X(d)$. When $x<y$ and $r(y)=r(x)+1$, we write
$x\lessdot y$ or equivalently $y\gtrdot x$.555This is traditionally called a
‘covering relation.’ Finally, we will assume throughout this work that our
posets are downward regular: there exists a regularity function $R(k,i)$ such
that every $k$-dimensional element is greater than exactly $R(k,i)$
$i$-dimensional elements.666For notational convenience, we also define
$R(i,i)=1$ and $R(j,i)=0$ whenever $j<i$.

Graded posets come equipped with a natural set of averaging operators called
the up and down operators. Namely, for any function $f:X(i)\to\mathbb{R}$,
these operators average $f$ up or down one level of the poset respectively:

$\displaystyle U_{i}f(x)$ $\displaystyle=\underset{y\lessdot
x}{\mathbb{E}}[f(y)],$ $\displaystyle D_{i}f(y)$
$\displaystyle=\underset{x\gtrdot y}{\mathbb{E}}[f(x)].$

Composing the averaging operators leads to a natural notion of random walks on
the underlying poset called higher order random walks (HD-walks). The simplest
example of such a walk is the upper walk $D_{i+1}U_{i}$ which moves between
elements $x,x^{\prime}\in X(i)$ via a common element $y\in X(i+1)$ with
$y>x,x^{\prime}$. Similarly, the lower walk $U_{i-1}D_{i}$ walks between
$x,x^{\prime}\in X(i)$ via a common $y\in X(i-1)$ with $y<x,x^{\prime}$. It
will also be useful at points to consider longer variants of the upper and
lower walks called canonical walks
$\widehat{N}_{k}^{i}=D_{k+1}\circ\ldots\circ D_{k+i}\circ
U_{k+i-1}\circ\ldots\circ U_{k}$ and
$\widecheck{N}_{k}^{i}=U_{k}\circ\ldots\circ U_{k-i}\circ
D_{k-i+1}\circ\ldots\circ D_{k}$ which similarly walk between $k$-dimensional
elements in $X(k)$ via a shared element in $X(k+i)$ or $X(k-i)$ respectively.

Following DDFH [3], we call a poset a $(\delta,\gamma)$-expander for
$\delta\in[0,1]^{d-1}$ and $\gamma\in\mathbb{R}_{+}$ if the upper and lower
walks are spectrally similar up to a laziness factor:

$\left\lVert
D_{i+1}U_{i}-(1-\delta_{i})I-\delta_{i}U_{i-1}D_{i}\right\rVert\leq\gamma.$

This generalizes standard spectral expansion which can be equivalently defined
as looking at the spectral norm of $A_{G}-U_{0}D_{1}$, where $A_{G}$ (the
adjacency matrix) is exactly the non-lazy upper walk. We note that under
reasonable regularity conditions (see [32, 3]), this definition is equivalent
to local-spectral expansion [18], which requires every local restriction of
the poset to be an expander graph. While most of our results hold more
generally, it will also be useful to assume a weak non-laziness condition on
our underlying posets throughout that holds in most cases of interest (see
Definition 2.8).

###  1.2 Results

With these definitions in mind, we can now cover our results in somewhat more
formality. We split this section into three parts for readability: spectral
stripping, characterizing edge expansion, and applications to the Grassmann.

####  1.2.1 Eigenstripping

We start with our generalized spectral stripping theorem for walks on
expanding posets.

######  Theorem 1.3 (Spectrum of HD-Walks (informal Corollary 4.5)).

Let $M$ be an HD-walk on the $k$th level of a $(\delta,\gamma)$-eposet. Then
the spectrum of $M$ is highly concentrated in $k+1$ strips:

$\text{Spec}(M)\in\\{1\\}\cup\bigcup_{i=1}^{k}\left[\lambda_{i}(M)-e,\lambda_{i}(M)+e\right]$

where $e\leq O_{k,\delta}(\gamma)$. Moreover, the span of eigenvectors in the
$i$th strip approximately correspond to functions lifted from $X(i)$ to
$X(k)$.

This generalizes and improves an analogous result of BHKL [15] on expanding
hypergraphs, which had sub-optimal error dependence of $O_{k}(\gamma^{1/2})$.
The main improvement stems from an optimal spectral stripping result for
arbitrary inner product spaces of independent interest.

######  Theorem 1.4 (Eigenstripping (informal Theorem 3.2)).

Let $M$ be a self-adjoint operator over an inner product space $V$, and
$V=V^{1}\oplus\ldots\oplus V^{k}$ be an “approximate eigendecomposition” in
the sense that there exist $\\{\lambda_{i}\\}_{i=1}^{k}$ and sufficiently
small error factors $\\{c_{i}\\}_{i=1}^{k}$ such that for all $f_{i}\in
V^{i}$:

$\left\lVert Mf_{i}-\lambda_{i}f_{i}\right\rVert_{2}\leq c_{i}\left\lVert
f_{i}\right\rVert.$

Then the spectrum of $M$ is concentrated around each $\lambda_{i}$:

$\text{Spec}(M)\subseteq\bigcup_{i=1}^{k}\left[\lambda_{i}-c_{i},\lambda_{i}+c_{i}\right].$

Note that this result is tight—when there is $c_{i}$ “error” in our basis we
cannot expect to have better than $c_{i}$ error in the resulting spectral
strips. Theorem 1.4 improves over a preliminary result to this effect in [15]
which had substantially worse dependence on $c_{i}$ and required much stronger
assumptions.777It is also worth noting that the proof in this work is
substantially simplified from [15], requiring no linear algebraic
manipulations at all. Theorem 1.3 then follows by work of DDFH ([3, Theorem
8.6]), who introduced a natural approximate eigendecomposition on eposets we
call the HD-Level-Set Decomposition.

In full generality, the approximate eigenvalues in Theorem 1.3 depend on the
eposet parameters $\delta$, and can be fairly difficult to interpret. However,
we show that under weak assumptions (see Section 2) the eigenvalues can be
associated with the regularity of the underlying poset. We focus on the lower
walks for simplicity, though the result can be similarly extended to general
walks on eposets.

######  Theorem 1.5 (Regularity Controls Spectral Decay (informal Theorem
4.7)).

The approximate eigenvalues of the lower walk $\widecheck{N}_{k}^{k-i}$ on a
$(\delta,\gamma)$-eposet are controlled by the poset’s regularity function:

$\lambda_{j}(\widecheck{N}_{k}^{k-i})\in\frac{R(i,j)}{R(k,j)}\pm
O_{k,\delta}(\gamma).$

As discussed in Section 1, this generalizes work of Kaufman and Tessler [32]
for the second eigenvalue of the upper/lower walks, and reveals a major
distinction among poset architectures: posets with higher regularity enjoy
faster decay of eigenvalues. We note that Theorem 1.1 can also be obtained by
combining Theorem 1.4 with recent independent work of Dikstein, Dinur, Filmus,
and Harsha on connections between eposets and regularity (namely in the recent
update of their seminal eposet paper, see [3, Section 8.4.1]).

On a more concrete note, Theorem 1.5 gives a new method of identifying
potential poset architectures exhibiting strong spectral decay in the sense
that for any $\delta>0$, the lower walk only contains $O_{\delta}(1)$
approximate eigenvalues larger than $\delta$ (rather than a number growing
with dimension). This property, referred to as constant ST-Rank in the context
of hypergraphs in [15], is an important factor not only for the run-time of
approximation algorithms on HDX [15], but also for the soundness of the
Grassmann-based agreement test in the proof of the 2-2 Games Conjecture [25].

####  1.2.2 Characterizing Edge Expansion

Much of our motivation for studying the spectrum of HD-walks comes from the
desire to understand a fundamental combinatorial quantity of graphs called
edge expansion.

######  Definition 1.6 (Edge Expansion).

Let $X$ be a graded poset and $M$ an HD-Walk on $X(k)$. The edge expansion of
a subset $S\subset X(k)$ with respect to $M$ is

$\Phi(S)=\underset{v\sim S}{\mathbb{E}}\left[M(v,X(k)\setminus S)\right],$

where

$M(v,X(k)\setminus S)=\sum\limits_{y\in X(k)\setminus S}M(v,y)$

and $M(v,y)$ denotes the transition probability from $v$ to $y$.

As mentioned in the introduction, characterizing the edge-expansion of sets in
HD-walks has recently proven crucial to understanding both algorithms for [33,
15] and hardness of unique games [25]. On expanding hypergraphs, it has long
been known that links give the canonical example of small non-expanding sets.

######  Definition 1.7 (Link).

Let $X$ be a $d$-dimensional graded poset. The $k$-dimensional link of an
element $\sigma\in X$ is the set of rank $k$ elements greater than
$\sigma$:888We note that in the literature a link is usually defined to be all
such elements, not just those of rank $k$. We adopt this notation since we are
mostly interested in working at a fixed level of the complex.

$X^{k}_{\sigma}=\\{y\in X(k):y>\sigma\\}.$

We call the link of a rank-$i$ element an “$i$-link.” When the level $k$ is
clear from context, we write $X_{\sigma}$ for $X^{k}_{\sigma}$ for simplicity.

In greater detail, BHKL [15] proved that on hypergraphs, the expansion of
links is exactly controlled by their corresponding spectral strip. While their
proof of this fact relied crucially on simplicial structure, we show via a
more general analysis that the result can be recovered for eposets.

######  Theorem 1.8 (Expansion of Links (informal Theorem 6.3)).

Let $X$ be a $(\delta,\gamma)$-eposet and $M$ an HD-walk on $X(k)$. Then for
all $0\leq i\leq k$ and $\tau\in X(i)$:

$\Phi(X_{\tau})=1-\lambda_{i}(M)\pm O_{M,k,\delta}(\gamma).$

As an immediate consequence, we get that when $M$ is not a small-set expander,
links are examples of small non-expanding sets. One might reasonably wonder
whether the converse is true as well: are all non-expanding sets explained by
links? This requires a bit of formalization. Following BHKL’s exposition [15],
given a set $S$ consider the function $L_{S,i}:X(i)\to\mathbb{R}$ that encodes
the behavior of $S\subset X(k)$ on links:

$\forall\tau\in
X(i):L_{S,i}(\tau)=\underset{X_{\tau}}{\mathbb{E}}[\mathbbm{1}_{S}]-\mathbb{E}[\mathbbm{1}_{S}].$

The statement “Non-expansion is explained by links” can then be interpreted as
saying that a non-expanding set $S$ should be detectable by some simple
measure of $L_{S,i}$. There are two standard formalizations of this idea
studied in the literature: the $\ell_{2}$-regime, and the
$\ell_{\infty}$-regime. These are captured by the following notion of
pseudorandomness based on $L_{S,i}$.

######  Definition 1.9 (Pseudorandom Sets [15] (informal Definitions 5.2,
5.5)).

We say a set $S$ is $(\varepsilon,\ell)$-$\ell_{2}$-pseudorandom
if999Throughout, $\left\lVert\cdot\right\rVert_{2}$ will always refer to the
expectation norm $\left\lVert f\right\rVert_{2}=\mathbb{E}[f^{2}]^{1/2}$.

$\forall i\leq\ell:\left\lVert
L_{S,i}\right\rVert_{2}^{2}\leq\varepsilon\mathbb{E}[\mathbbm{1}_{S}].$

A set is $(\varepsilon,\ell)$-$\ell_{\infty}$-pseudorandom if:

$\forall i\leq\ell:\left\lVert L_{S,i}\right\rVert_{\infty}\leq\varepsilon.$

In cases that $\ell_{2}$ and $\ell_{\infty}$-pseudorandomness can be used
interchangeably, we will simply write $(\varepsilon,\ell)$-pseudorandom.

We prove that pseudorandom sets expand near-optimally.

######  Theorem 1.10 (Pseudorandom Sets Expand (informal Theorem 6.7)).

Let $X$ be a $(\delta,\gamma)$-eposet and $M$ a walk on $X(k)$. Then the
expansion of any $(\varepsilon,i)$-pseudorandom set $S$ is at least:

$\Phi(S)\geq
1-\lambda_{i+1}-O_{\delta}(R(k,i)\varepsilon)-O_{k,\delta,M}(\gamma).$

In other words, any set with expansion less than $1-\lambda_{i+1}$ must have
appreciable variance across links at level $i$. We note that the formal
version of this result is essentially tight in the $\ell_{2}$-regime, but can
be improved in many important cases in the $\ell_{\infty}$-regime. We’ll
discuss this further in the next section, especially in the context of the
Grassmann poset.

Before this, however, it is worth separately mentioning the main technical
component behind Theorem 1.10, a result traditionally called a “level-$i$”
inequality.

######  Theorem 1.11 (Level-$i$ inequality (informal Theorem 5.7)).

Let $X$ be a $(\delta,\gamma)$-eposet and $S\subset X(k)$ a
$(\varepsilon,\ell)$-pseudorandom set. Then for all $1\leq i\leq\ell$:

$|\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle|\leq\left(R(k,i)\varepsilon+O_{k,\delta}(\gamma)\right)\langle\mathbbm{1}_{S},\mathbbm{1}_{S}\rangle$

where $\mathbbm{1}_{S,i}$ is the projection of $\mathbbm{1}_{S}$ onto the
$i$th eigenstrip.101010Note that since walks on eposets are simultaneously
diagonalizable, the decomposition of $X$ into eigenstrips is independent of
the choice of walk.

In other words, pseudorandomness controls the projection of $S$ onto
eigenstrips. Theorems 1.10 and 1.11 recover the analogous optimal bounds for
simplicial high dimensional expanders in [15], where the regularity parameter
$R(k,i)={k\choose i}$, and are tight in a number of other important settings
such as the Grassmann (discussed below). Theorem 1.10 and Theorem 1.11 can
also be viewed as another separation between eposet architectures, this time
in terms of combinatorial rather than spectral properties.

####  1.2.3 Application: $q$-eposets and the Grassmann Graphs

Finally, we’ll discuss the application of our results to a particularly
important class of eposets called “$q$-eposets.” Just like standard high
dimensional expanders arise from expanding subsets of the complete complex
(hypergraph), $q$-eposets arise from expanding subsets of the Grassmann Poset.

######  Definition 1.12 (Grassmann Poset).

The Grassmann Poset is a graded poset $(X,<)$ where $X$ is the set of all
subspaces of $\mathbb{F}_{q}^{n}$ of dimension at most $d$, the partial
ordering “$<$” is given by inclusion, and the rank function is given by
dimension.

We call a (downward-closed) subset of the Grassmann poset a $q$-simplicial
complex, and an expanding $q$-simplicial complex a $q$-eposet (see Section 2.5
for exact details). Using our machinery for general eposets, we prove a tight
level-$i$ inequality for pseudorandom sets.

######  Corollary 1.13 (Grassmann level-$i$ inequality (informal Theorem
7.7)).

Let $X$ be a $\gamma$-$q$-eposet and $S\subseteq X(k)$. If $S$ is
$(\varepsilon,\ell)$-pseudorandom, then for all $1\leq i\leq\ell$:

$|\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle|\leq\left({k\choose
i}_{q}\varepsilon+O_{q,k}(\gamma)\right)\langle\mathbbm{1}_{S},\mathbbm{1}_{S}\rangle$

where
$\binom{k}{i}_{q}=\frac{(1-q^{k})\cdots(1-q^{k-i+1})}{(1-q^{i})\cdots(1-q)}$
is the Gaussian binomial coefficient.

Corollary 1.13 is tight in a few senses. First, we prove the bound cannot be
improved by any constant factor, even in the $\ell_{\infty}$-regime. In other
words, for every $c<1$, it is always possible to find an
$(\varepsilon,i)$-pseudorandom function satisfying:

$|\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle|>c\left({k\choose
i}_{q}\varepsilon+O_{q,k}(\gamma)\right)\langle\mathbbm{1}_{S},\mathbbm{1}_{S}\rangle.$

Furthermore, it is well known the dependence on $k$ in this result is
necessary [26], even if one is willing to suffer a worse dependence on the
pseudorandomness $\varepsilon$. This is different from the case of standard
simplicial complexes, where the dependence can be removed in the
$\ell_{\infty}$-regime [30, 35, 36]. However, there is a crucial subtlety
here. It is likely that the $k$-dependence in this result can be removed by
changing the definition of pseudorandomness. On the Grassmann poset itself,
for instance, it is known that this can be done by replacing links with a
closely related but finer-grained local structure known as “zoom-in zoom-outs”
[25]. Indeed, more generally it is an interesting open problem whether there
always exists a notion of locality based on the underlying poset structure
that gives rise to $k$-independent bounds in the $\ell_{\infty}$-regime.

We close out the section by looking at an application of this level-$i$
inequality to studying edge-expansion in an important class of walks that give
rise to the well-studied Grassmann graphs.

######  Definition 1.14 (Grassmann Graphs).

The Grassmann Graph $J_{q}(n,k,t)$ is the graph on $k$-dimensional subspaces
of $\mathbb{F}_{q}^{n}$ where $(V,W)\in E$ exactly when $\text{dim}(V\cap
W)=t$.

It is easy to see that the non-lazy upper walk on the Grassmann poset is
exactly the Grassmann graph $J_{q}(n,k,k-1)$. In fact, it is possible to
express any $J_{q}(n,k,t)$ as a sum of standard higher order random walks.

######  Proposition 1.15 (Grassmann Graphs are HD-Walks (informal Proposition
7.5)).

The Grassmann graphs are a hypergeometric sum of canonical walks:

$J_{q}(n,k,t)=\frac{1}{q^{(k-t)^{2}}{k\choose
t}_{q}}\sum\limits_{i=0}^{k-t}(-1)^{k-t-i}q^{{k-t-i\choose 2}}{k-t\choose
i}_{q}{k+i\choose i}_{q}N_{k}^{i}.$

In Section 7 we prove a more general version of this result for any
$q$-simplicial complex. This leads to a set of natural sparsifications of the
Grassmann graphs that may be of independent interest for agreement testing,
PCPs, and hardness of approximation. For simplicity, on a given $q$-simplicial
complex $X$, we’ll refer to these “sparsified” Grassmann graphs as
$J_{X,q}(n,k,t)$ for the moment (more formally they are the “partial-swap
walks,” see Section 2.5). With this in mind, let’s take a look at what our
level-$i$ inequality implies for the edge-expansion of these graphs.

######  Corollary 1.16 ($q$-eposets Edge-Expansion (informal Corollary 7.10)).

Let $X$ be a $d$-dimensional $\gamma$-$q$-eposet and $S\subset X(k)$ a
$(\varepsilon,\ell)$-pseudorandom set. Then the expansion of $S$ with respect
to the sparsified Grassmann graph $J_{X,q}(n,k,t)$ is at least:

$\Phi(S)\geq
1-\mathbb{E}[\mathbbm{1}_{S}]-\varepsilon\sum\limits_{i=1}^{\ell}{t\choose
i}_{q}-q^{-(\ell+1)j}-O_{q,k}(\gamma).$

In practice, $t$ is generally thought of as being $\Omega(k)$ (or even
$k-O(1)$), which results in a $k$-dependent bound. It remains an open problem
whether a $k$-independent version can be proved for any $q$-eposet beyond the
Grassmann poset itself. We conjecture such a result should indeed hold (albeit
under a different notion of pseudorandomness), and may follow from $q$-analog
analysis of recent work proving $k$-independent bounds for standard expanding
hypergraphs [35, 36].

###  1.3 Related Work

##### Higher Order Random Walks.

Higher order random walks were first introduced in 2016 by Kaufman and Mass
[1]. Their spectral structure was later elucidated in a series of works by
Kaufman and Oppenheim [2], DDFH [3], Alev, Jeronimo, and Tulsiani [14], Alev
and Lau [4], and finally BHKL [15]. With the exception of DDFH (who only
worked with approximate eigenvectors without analyzing the true spectrum), all
of these works focused on hypergraphs rather than general posets. Our spectral
stripping theorem for eposets essentially follows from combining eposet
machinery developed by DDFH with our improved variant of BHKL’s general
spectral stripping theorem.

Higher order random walks have also seen an impressive number of applications
in recent years, frequently closely tied to analysis of their spectral
structure. This has included breakthrough works on approximate sampling [5, 4,
6, 7, 8, 9, 10, 11, 12, 13], CSP-approximation [14, 15], error-correcting
codes [16, 17], and agreement testing [18, 19, 20]. In this vein, our work is
most closely related to that of Bafna, Barak, Kothari, Schramm, and Steurer
[33], and BHKL [15], who used the spectral and combinatorial structure of HD-
walks to build new algorithms for unique games. As previously discussed, the
generalized analysis in this paper also lends itself to the algorithmic
techniques developed in those works, but we do not know of any interesting
examples beyond those covered in BHKL.

##### High Dimensional Expansion Beyond Hypergraphs.

Most works listed above (and indeed in the high dimensional expansion
literature in general) focus only on the setting of hypergraphs. However,
recent years have also seen the nascent development and application of
expansion beyond this setting [37, 22, 23, 24, 38], including the seminal work
of DDFH [3] on expanding posets as well as more recent breakthroughs on
locally testable and quantum codes [21, 22]. While DDFH largely viewed eposets
as having similar structure (with the exception of the Grassmann), we
strengthen the case that different underlying poset architectures exhibit
different properties. This complements the recent result of Kaufman and
Tessler [32], who showed that expanding posets with strong regularity
conditions such as the Grassmann exhibit more favorable properties with
respect to the second eigenvalue. Our results provide a statement of the same
flavor looking at the entire spectrum, along with additional separations in
more combinatorial settings. We note that a related connection between poset
regularity and the approximate spectrum of walks on eposets was independently
developed by DDFH in a recent update of their seminal work [3].

##### Expansion and Unique Games.

One of the major motivations behind this work is towards building a more
general framework for understanding the structure underlying the Unique Games
Conjecture [39], a major open problem in complexity theory that implies
optimal hardness of approximation results for a large swath of combinatorial
optimization problems (see e.g. Khot’s survey [40]). In 2018, Khot, Minzer,
and Safra [25] made a major breakthrough towards the UGC in proving a weaker
variant known as the 2-2 Games Conjecture, completing a long line of work in
this direction [26, 27, 28, 29, 30, 25]. The key to the proof lay in a result
known as the “Grassmann expansion hypothesis,” which stated that any non-
expanding set in the Grassmann graph $J_{q}(d,k,k-1)$ had to be non-trivially
concentrated inside a local-structure called “zoom-in zoom-outs.” As noted in
the previous section, this result differs from our analysis in two key ways:
it lies in the $\ell_{\infty}$-regime, and must be totally independent of
dimension.

Unfortunately, very little progress has been made towards the UGC since this
result. This is in part because KMS’ proof of the Grassmann expansion
hypothesis, while a tour de force, is complicated and highly tailored to the
exact structure of the Grassmann. To our knowledge, the same proof cannot be
used, for instance, to resolve the related “shortcode expansion hypotheses”
beyond degree-2, similar conjectures offered by Barak, Kothari, and Steurer
[29] in an effort to push beyond hardness of 2-2 Games. Just as the
$\ell_{2}$-regime analysis of DDFH and BHKL recently lead to a dimension
independent bound in the $\ell_{\infty}$-regime for standard HDX [35, 36], we
expect the groundwork laid in this paper will be important for proving
generalized dimension independent expansion hypotheses in the
$\ell_{\infty}$-regime beyond the special case of the Grassmann graphs.

##  2 Preliminaries

Before jumping into the details in full formality, we give a more careful
review of background definitions regarding expanding posets, higher order
random walks, and the Grassmann.

###  2.1 Graded Posets

We start with eposets’ underlying structure, graded posets. A partially
ordered set (poset) $P=(X,<)$ is a set of elements $X$ endowed with a partial
order “$<$”. A graded poset comes equipped additionally with a rank function
$r:X\to\mathbb{N}$ satisfying two properties:

  1. 1.

$r$ preserves “$<$”: if $y<x$, then $r(y)<r(x)$.

  2. 2.

$r$ preserves cover relations: if $x$ is the smallest element greater than
$y$, then $r(x)=r(y)+1$.

In other words, the function $r$ partitions $X$ into subsets by rank:

$X(0)\cup\ldots\cup X(d),$

where $\max_{X}(r)=d$, and $X(i)=r^{-1}(i)$. We refer to a poset with maximum
rank $d$ as “$d$-dimensional”, and elements in $X(i)$ as “$i$-faces”.
Throughout this work, we will consider only $d$-dimensional graded posets with
two additional restrictions:

  1. 1.

They have a unique minimal element, i.e. $|X(0)|=1$.

  2. 2.

They are “pure”: all maximal elements have rank $d$.

Finally, many graded posets of interest satisfy certain regularity conditions
which will be crucial to our analysis. The first condition of interest is a
natural notion called downward regularity.

######  Definition 2.1 (Downward Regularity).

We call a $d$-dimensional graded poset downward regular if for all $i\leq d$
there exists some constant $R(i)$ such that every element $x\in X(i)$ covers
exactly $R(i)$ elements $y\in X(i-1)$.

Second, we will also need a useful notion called middle regularity that
ensures uniformity across multiple levels of the poset.

######  Definition 2.2 (Middle Regularity).

We call a $d$-dimensional graded poset middle-regular if for all $0\leq i\leq
k\leq d$, there exists a constant $m(k,i)$ such that for any $x_{k}\in X(k)$
and $x_{i}\in X(i)$ satisfying $x_{k}>x_{i}$, there are exactly $m(k,i)$
chains111111Such objects are sometimes called flags, e.g. in the case of the
Grassmann poset. of elements $x_{k}>x_{k-1}>\ldots>x_{i+1}>x_{i}$ where each
$x_{j}\in X(j)$.

We call a poset regular if it is both downward and middle regular. We note
that regular posets also have the nice property that for any dimensions $i<k$,
there exists a higher order regularity function $R(k,i)$ such that any $x\in
X(k)$ is greater than exactly $R(k,i)$ elements in $X(i)$ (see Appendix A). We
will use this notation throughout. For notational convenience, we also define
$R(i,i)=1$ and $R(j,i)=0$ whenever $j<i$.

Important examples of regular posets include pure simplicial complexes and the
Grassmann poset (subspaces of $\mathbb{F}^{n}_{q}$ ordered by inclusion). We
will assume all posets we discuss in this work are regular from this point
forward.

###  2.2 Measured Posets and The Random Walk Operators

Higher order random walks may be defined over posets in a very similar fashion
to simplicial complexes. The main difference is simply that “inclusion” is
replaced with the poset order relation. Just as we might want these walks on
HDX to have non-uniform weights, the same is true for posets, which can be
analogously endowed with a distribution over levels. In slightly more detail,
a measured poset is a graded poset $X$ endowed with a distribution
$\Pi=(\pi_{0},\ldots,\pi_{d})$, where each marginal $\pi_{i}$ is a
distribution over $X(i)$. While measured posets may be defined in further
generality (cf. [3, Definition 8.1]), we will focus on the case in which the
distribution $\Pi$ is induced entirely from $\pi_{d}$, analogous to weighted
simplicial complexes. More formally, we have that for every $0\leq i<d$:

$\pi_{i}(x)=\frac{1}{R(i+1,i)}\sum\limits_{y\gtrdot x}\pi_{i+1}(y).$

In other words, each lower dimensional distribution $\pi_{i}$ may be induced
through the following process: an element $y\in X(i+1)$ is selected with
respect to $\pi_{i+1}$, and an element $x\in X(i)$ such that $x<y$ is then
chosen uniformly at random.

The averaging operators $U$ and $D$ are defined analogously to their notions
on simplicial complexes, with the main change being the use of the general
regularity function $R(i+1,i)$:

$\displaystyle U_{i}f(y)=$
$\displaystyle~{}\frac{1}{R(i+1,i)}\sum\limits_{x\lessdot y}f(x),$
$\displaystyle D_{i+1}f(x)=$
$\displaystyle~{}\frac{1}{\pi_{i+1}(X_{x})}\sum\limits_{y\gtrdot
x}\pi_{i+1}(y)f(y),$

where for $i<k$ and $x\in X(i)$,

$\pi_{k}(X_{x})=\sum\limits_{y\in X(k):y>x}\pi_{k}(y)=R(k,i)\pi_{i}(x)$

is the appropriate normalization factor (we will use this notation
throughout). On regular posets, it is useful to note that the up operators
compose nicely, and in particular that:

$U^{k}_{i}f(y)\coloneqq U_{k-1}\circ\ldots\circ
U_{i}f(y)=\frac{1}{R(k,i)}\sum\limits_{x\in X(i):x<y}f(x)$

(see Appendix A). Furthermore, just like on simplicial complexes, the down and
up operators are adjoint with respect to the standard inner product on
measured posets:

$\langle f,g\rangle_{X(k)}=\sum\limits_{\tau\in
X(k)}\pi_{k}(\tau)f(\tau)g(\tau),$

that is to say for any $f:X(k)\to\mathbb{R}$ and $g:X(k-1)\to\mathbb{R}$:

$\langle f,U_{k-1}g\rangle_{X(k)}=\langle D_{k}f,g\rangle_{X(k-1)}.$

Note that we’ll generally drop the $X(k)$ from the notation when clear from
context. This useful fact allows us to define basic self-adjoint notions of
higher order random walks just like on simplicial complexes.

###  2.3 Higher Order Random Walks

Let $C_{k}$ denote the space of functions $f:X(k)\to\mathbb{R}$. We define a
natural set of random walk operators via the averaging operators.

######  Definition 2.3 ($k$-Dimensional Pure Walk [1, 3, 14]).

Given a measured poset $(X,\Pi)$, a $k$-dimensional pure walk $Y:C_{k}\to
C_{k}$ on $(X,\Pi)$ (of height $h(Y)$) is a composition:

$Y=Z_{2h(Y)}\circ\cdots\circ Z_{1},$

where each $Z_{i}$ is a copy of $D$ or $U$, and there are $h(Y)$ of each type.

Following AJT and BHKL, we define general higher order random walks to be
affine combinations121212An affine combination is a linear combination whose
coefficients sum to $1$. of pure walks.

######  Definition 2.4 (HD-walk).

Let $X$ be a graded poset. Let $\mathcal{Y}$ be a family of pure walks
$Y:C_{k}\to C_{k}$ on $(X,\Pi)$. We call an affine combination

$M=\sum\limits_{Y\in\mathcal{Y}}\alpha_{Y}Y$

a $k$-dimensional HD-walk on $(X,\Pi)$ if it is stochastic and self-adjoint.
The height of $M$, denoted $h(M)$, is the maximum height of any pure
$Y\in\mathcal{Y}$ with a non-zero coefficient. The weight of $M$, denoted
$w(M)$, is $|\alpha|_{1}$.

While most of our results will hold for general HD-walks (or at least some
large subclass), we pay special attention to a basic class of pure walks that
have seen the most study in the literature: canonical walks.

######  Definition 2.5 (Canonical Walk).

Given a $d$-dimensional measured poset $(X,\Pi)$ and parameters $k+j\leq d$,
the upper canonical walk $\widehat{N}_{k}^{j}$ is:

$\widehat{N}_{k}^{j}=D^{k+j}_{k}U^{k+j}_{k},$

and for $j\leq k$ the lower canonical walk $\widecheck{N}^{j}_{k}$ is:

$\widecheck{N}^{j}_{k}=U_{k-j}^{k}D^{k}_{k-j},$

where $U^{k}_{\ell}=U_{k-1}\ldots U_{\ell}$, and
$D^{k}_{\ell}=D_{\ell+1}\ldots D_{k}$.

Since the non-zero spectrum of $\widehat{N}_{k}^{j}$ and
$\widecheck{N}_{k+j}^{j}$ are equivalent (c.f. [4]), we focus in this work
mostly on the upper walks which we write simply as $N_{k}^{j}$.

For certain specially structured posets, we will also study an important class
of HD-walks known as (partial) swap walks. We will introduce these well-
studied walks in more detail in Section 2.5, and for now simply note that they
give a direct generalization of the Johnson and Grassmann graphs when applied
to the complete complex and Grassmann poset respectively.

###  2.4 Expanding Posets and the HD-Level-Set Decomposition

Dikstein, Dinur, Filmus, and Harsha [3] observed that one can use the
averaging operators to define a natural extension of spectral expansion to
graded posets. Their definition is inspired by the fact that $\gamma$-spectral
expansion on a standard graph $G$ can be restated as a bound on the spectral
norm of the adjacency matrix minus its stationary operator:

$\left\lVert A_{G}-UD\right\rVert\leq\gamma.$

Informally, DDFH’s definition can be thought of as stating that this relation
holds for every level of a higher dimensional poset.

######  Definition 2.6 (eposet [3]).

Let $(X,\Pi)$ be a measured poset, $\delta\in[0,1]^{d-1}$, and $\gamma<1$. $X$
is an $(\delta,\gamma)$-eposet if for all $1\leq i\leq d-1$:

$\left\lVert
D_{i+1}U_{i}-(1-\delta_{i})I-\delta_{i}U_{i-1}D_{i}\right\rVert\leq\gamma$

.

We note that for a broad range of posets, this definition is actually
equivalent (up to constants) to local-spectral expansion, a popular notion of
high dimensional expansion introduced by Dinur and Kaufman [18]. This was
originally proved for simplicial complexes by DDFH [3], and later extended to
a more general class of posets by Kaufman and Tessler [32]. It is also worth
noting that when $\gamma=0$, posets satisfying the guarantee in Definition 2.6
are known as sequentially differential, and were actually introduced much
earlier by Stanley [31] in the late 80s.

Much of our analysis in this work will be based off of an elegant approximate
Fourier decomposition for eposets introduced by DDFH [3].

######  Theorem 2.7 (HD-Level-Set Decomposition, Theorem 8.2 [3]).

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet with $\gamma$
sufficiently small. For all $0\leq k\leq d$, let

$H^{0}=C_{0},H^{i}=\text{Ker}(D_{i}),V_{k}^{i}=U^{k}_{i}H^{i}.$

Then:

$C_{k}=V^{0}_{k}\oplus\ldots\oplus V^{k}_{k}.$

In other words, every $f\in C_{k}$ has a unique decomposition
$f=f_{0}+\ldots+f_{k}$ such that $f_{i}=U^{k}_{i}g_{i}$ for
$g_{i}\in\text{Ker}(D_{i})$.

It is well known that the HD-Level-Set Decomposition is approximately an
eigenbasis for HD-walks on simplicial complex [3, 14, 15]. We show this
statement extends to all eposets in Section 4 (extending DDFH’s similar
analysis of the upper walk $N_{k}^{1}$).

Finally, before moving on, we will assume for simplicity throughout this work
an additional property of eposets we called (approximate) non-laziness.

######  Definition 2.8 ($\beta$-non-Lazy Eposets).

Let $(X,\Pi)$ be a $d$-dimensional measured poset. We call $(X,\Pi)$
$\beta$-non-lazy if for all $1\leq i\leq d$, the laziness of the lower walk
satisfies:

$\max_{\sigma\in
X(i)}\\{\mathbbm{1}_{\sigma}^{T}U_{i-1}D_{i}\mathbbm{1}_{\sigma}\\}\leq\beta.$

Another way to think about this condition is that no element in the poset
carries too much weight, even upon conditioning. All of our results hold for
general eposets,131313The one exception is the lower bound of Theorem 1.8. but
their form is significantly more interpretable when the poset is additionally
non-lazy. In fact, most $\gamma$-eposets of interest are $O(\gamma)$-non-lazy.
It is easy to see for instance that any “$\gamma$-local-spectral” expander
satisfies this condition, an equivalent notion of expansion to
$\gamma$-eposets under suitable regularity conditions [32]. We discuss this
further in Appendix A.

###  2.5 The Grassmann Poset and $q$-eposets

At the moment, there are only two known families of expanding posets of
significant interest in the literature: those based on pure simplicial
complexes (the downward closure of a $k$-uniform hypergraph), and pure
$q$-simplicial complexes (the analogous notion over subspaces). The
$\ell_{2}$-structure of the former set of objects is studied in detail in
[15]. In this work, we will focus on the latter which has seen less attention
in the literature, but is responsible for a number of important results
including the resolution of the 2-to-2 Games Conjecture [25].

######  Definition 2.9 ($q$-simplicial complex).

Let $G_{q}(n,d)$ denote the $d$-dimensional subspaces of $\mathbb{F}_{q}^{n}$.
A weighted, pure $q$-simplicial complex $(X,\Pi)$ is given by a family of
subspaces $X\subseteq G_{q}(n,d)$ and a distribution $\Pi$ over $X$. We will
usually consider the downward closure of $X$ in the following sense:

$X=X(0)\cup\ldots\cup X(d),$

where $X(i)\subseteq G_{q}(n,i)$ consists of all $i$-dimensional subspaces
contained in some element in $X=X(d)$. Further, on each level $X(i)$, $\Pi$
induces a natural distribution $\pi_{i}$:

$\forall V\in X(i):\pi_{i}(V)=\frac{1}{{d\choose i}_{q}}\sum\limits_{W\in
X(d):W\supset V}\pi_{d}(W),$

where $\pi_{d}=\Pi$ and
$\binom{d}{i}_{q}=\frac{(1-q^{d})\cdots(1-q^{d-i+1})}{(1-q^{i})\cdots(1-q)}$
is the Gaussian binomial coefficient.

The most basic example of a $q$-simplicial complex is the Grassmann poset,
which corresponds to taking $X=G_{q}(n,d)$. This is the $q$-analog of the
complete simplicial complex. The Grassmann poset is well known to be a
expander in this sense (see e.g. [31])—in fact it is a sequentially
differential poset with parameters

$\delta_{i}=\frac{(q^{i}-1)(q^{n-i+1}-1)}{(q^{i+1}-1)(q^{n-i}-1)},$

the $q$-analog of the eposet parameters for the complete complex [3]. With
this in mind, let’s define a special class of eposets based on $q$-simplicial
complexes.

######  Definition 2.10 ($\gamma$-$q$-eposet [3]).

A pure, $d$-dimensional weighted $q$-simplicial complex $(X,\Pi)$ is a
$\gamma$-$q$-eposet if it is a $(\delta,\gamma)$-eposet satisfying
$\delta_{i}=q\frac{q^{i}-1}{q^{i+1}-1}$ for all $1\leq i\leq d-1$.

Constructing bounded-degree $q$-eposets (a problem proposed by DDFH [3])
remains an interesting open problem. Kaufman and Tessler [32] recently made
some progress in this direction, but the expansion parameter of their
construction is fairly poor (around $1/2$).

Finally, in our applications to the Grassmann we’ll focus our attention on a
particularly important class of walks called partial-swap walks. These should
essentially be thought of as non-lazy variants of the upper canonical walks.

######  Definition 2.11 (Partial-Swap Walk).

Let $(X,\Pi)$ be a weighted, $d$-dimensional $q$-simplicial complex. The
partial-swap walk $S^{j}_{k}$ is the restriction of the canonical walk
$N^{j}_{k}$ to faces whose intersection has dimension $k-j$. In other words,
if $|V\cap W|>k-j$ then $S^{j}_{k}(V,W)=0$, and otherwise $S^{j}_{k}(V,W)\
\propto\ N^{j}_{k}(V,W)$.

When applied to the Grassmann poset itself, it is clear by symmetry that the
partial-swap walk $S_{k}^{j}$ returns exactly the Grassmann graph
$J_{q}(d,k,k-j)$. On the other hand, it is not immediately obvious these
objects are even HD-walks when applied to a generic $q$-simplicial complex. We
prove this is the case in Section 7.

##  3 Approximate Eigendecompositions and Eigenstripping

With preliminaries out of the way, we can move on to understanding HD-walks’
spectral structure. It turns out that on expanding posets, these walks exhibit
almost exactly the same properties as on the special case of simplicial
complexes studied in [2, 3, 14, 15]: a walk’s spectrum lies concentrated in
strips corresponding to levels of the HD-Level-Set Decomposition. The key to
proving this lies in a more general theorem characterizing the spectral
structure of any inner product space admitting a “approximate
eigendecomposition.”

######  Definition 3.1 (Approximate Eigendecomposition [15]).

Let $M$ be an operator over an inner product space $V$. A decomposition
$V=V^{1}\oplus\ldots\oplus V^{k}$ is called a
$(\\{\lambda_{i}\\}_{i=1}^{k},\\{c_{i}\\}_{i=1}^{k})$-approximate
eigendecomposition if for all $i$ and $v_{i}\in V^{i}$, $Mv_{i}$ is close to
$\lambda_{i}v_{i}$:

$\left\lVert Mv_{i}-\lambda_{i}v_{i}\right\rVert\leq c_{i}\left\lVert
v_{i}\right\rVert.$

We will always assume for simplicity (and without loss of generality) that the
$\lambda_{i}$ are sorted: $\lambda_{1}\geq\ldots\geq\lambda_{k}$.

BHKL [15] proved that as long as the $c_{i}$ are sufficiently small, each
$V^{i}$ (loosely) corresponds to an “eigenstrip,” the span of eigenvectors
with eigenvalue closely concentrated around $\lambda_{i}$, and that these
strips account of the entire spectrum of $M$. While sufficient for their
purposes, their proof of this result was complicated and resulted in a variety
of sub-optimal parameters. We give a tight variant of this result and
significantly simplify the proof.

######  Theorem 3.2 (Eigenstripping).

Let $M$ be a self-adjoint operator over an inner product space $V$, and
$V=V^{1}\oplus\ldots\oplus V^{k}$ a
$(\\{\lambda_{i}\\}_{i=1}^{k},\\{c_{i}\\}_{i=1}^{k})$-approximate
eigendecomposition. Then as long as $c_{i}+c_{i+1}<\lambda_{i}-\lambda_{i+1}$,
the spectrum of $M$ is concentrated around each $\lambda_{i}$:

$\text{Spec}(M)\subseteq\bigcup_{i=1}^{k}\left[\lambda_{i}-c_{i},\lambda_{i}+c_{i}\right]$

###### Proof.

The idea is to examine for each $i$ the operator
$M_{i}^{2}=(M-\lambda_{i}I)^{2}$. In particular, we claim it is enough to show
the following:

######  Claim 3.3.

For all $1\leq i\leq k$, $\text{Spec}(M_{i}^{2})$ contains $dim(V^{i})$
eigenvalues less than $c_{i}^{2}$.

Let’s see why this implies the desired result. Notice that the eigenvalues of
$M_{i}^{2}$ are exactly $(\mu-\lambda_{i})^{2}$ for each $\mu$ in $Spec(M)$
(with matching multiplicities), and therefore that any eigenvalue $\mu_{i}\in
Spec(M_{i}^{2})$ less than $c_{i}^{2}$ implies the existence of a
corresponding eigenvalue of $M$ in $[\lambda_{i}\pm c_{i}]$. If each
$M_{i}^{2}$ has $\text{dim}(V^{i})$ eigenvalues less than $c_{i}^{2}$, then
$M$ has at least $\text{dim}(V^{i})$ eigenvalues in each interval
$[\lambda_{i}\pm c_{i}]$. Moreover, since these intervals are disjoint by
assumption and $\sum\text{dim}(V^{i})=\text{dim}(V)$, this must account for
all eigenvalues of $M$.

It remains to prove the claim, which is essentially an immediate application
of Courant-Fischer theorem [41].

###### Proof of 3.3.

The Courant-Fischer theorem states that the $k$th smallest eigenvalue of a
self-adjoint operator $A$ is:

$\lambda_{n-k+1}=\min_{U}\left\\{\max_{f\in U}\left\\{\frac{\langle
f,Af\rangle}{\langle
f,f\rangle}\right\\}~{}\middle|~{}\text{dim}(U)=k\right\\}.$

Setting $U=V^{i}$, $A=M_{i}^{2}$ and $k=\dim(V^{i})$ gives the claim:

$\lambda_{n-k+1}(M_{i}^{2})\leq\max_{f\in V^{i}}\left\\{\frac{\langle
f,M_{i}^{2}f\rangle}{\langle f,f\rangle}\right\\}=\max_{f\in
V^{i}}\left\\{\frac{\left\lVert(M-\lambda_{i}I)f\right\rVert_{2}^{2}}{\langle
f,f\rangle}\right\\}\leq c_{i}^{2}$

since $(M-\lambda_{i}I)$ is self-adjoint and $\bigoplus_{i\in[k]}V^{i}$ is a
$(\\{\lambda_{i}\\}_{i=1}^{k},\\{c_{i}\\}_{i=1}^{k})$-approximate
eigendecomposition. ∎

∎

Note that this result is also trivially tight, as any true eigendecomposition
is also a $(\\{\lambda_{i}\pm c_{i}\\},\\{c_{i}\\})$-approximate
eigendecomposition. We also note that similar strategies have been used in the
numerical analysis literature (see e.g. [42]).

##  4 Spectra of HD-walks

Given Theorem 3.2, it is enough to prove that the HD-Level-Set Decomposition
is an approximate eigenbasis for any HD-walk. This follows by the same
inductive argument as for local-spectral expanders in [15], where the only
difference is that somewhat more care is required to deal with general eposet
parameters. To start, it will be useful to lay out some notation along with a
simple observation from repeated application of Definition 2.6.

######  Lemma 4.1 ([3, Claim 8.8]).

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet. Then

$\left\lVert
D_{k+1}U^{k+1}_{k-j}-(1-\delta^{k}_{j})U^{k}_{k-j}-\delta_{j}^{k}U^{k}_{k-j-1}D_{k-j}\right\rVert\leq\gamma^{k}_{j},$

where

$\delta^{k}_{-1}=1,~{}\delta_{j}^{k}=\prod\limits_{i=k-j}^{k}\delta_{i},~{}\gamma^{k}_{j}=\gamma\sum\limits^{j-1}_{i=-1}\delta^{k}_{i}.$

Applying this fact inductively implies that functions in the HD-Level-Set
Decomposition are close to being eigenvectors.

######  Proposition 4.2.

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet, and $Y$ the pure balanced walk of
height $j$, with down operators at positions $(i_{1},\ldots,i_{j})$. For
$1\leq\ell\leq k$, let $f_{\ell}=U^{k}_{\ell}g_{\ell}$ for some $g_{\ell}\in
H^{\ell}$, and let

$\delta_{j}^{k}=\prod\limits_{i=k-j}^{k}\delta_{i},~{}\gamma^{k}_{j}=\gamma\sum\limits^{j-1}_{i=-1}\delta^{k}_{i},$

where $\delta_{i}^{k}=1$ for any $i<0$ for notational convenience. Then
$f_{\ell}$ is an approximate eigenvector of $Y$:

$\left\lVert
Yf_{\ell}-\prod\limits_{s=1}^{j}\left(1-\delta_{k-2s+i_{s}-\ell}^{k-2s+i_{s}}\right)f_{\ell}\right\rVert\leq\left\lVert
g_{\ell}\right\rVert\sum\limits_{s=1}^{j}\gamma^{k-2s+i_{s}}_{k-2s+i_{s}-\ell}\prod\limits_{t=1}^{s-1}\left(1-\delta_{k-2t+i_{t}-\ell}^{k-2t+i_{t}}\right)\leq(j+k)j\gamma\left\lVert
g_{\ell}\right\rVert.$

###### Proof.

We prove a slightly stronger statement to simplify the induction. For $b>0$,
let $Y_{j}^{b}:C_{\ell}\to C_{\ell+b}$ denote an unbalanced walk with $j$ down
operators, and $j+b$ up operators. If $Y_{j}^{b}$ has down operators in
positions $(i_{1},\ldots,i_{j})$ and $g_{\ell}\in H^{\ell}$, we claim:

$\left\lVert
Y^{b}_{j}g_{\ell}-\prod\limits_{s=1}^{j}\left(1-\delta^{i_{s}+\ell-2s}_{i_{s}-2s}\right)Y_{0}^{b}g_{\ell}\right\rVert\leq\left\lVert
g_{\ell}\right\rVert\sum\limits_{s=1}^{j}\gamma_{i_{s}-2s}^{i_{s}+\ell-2s}\prod\limits_{t=1}^{s-1}\left(1-\delta^{i_{t}+\ell-2t}_{i_{t}-2t}\right),$

which implies the result (notice that the indices $i_{s}$ shift by
$b=k-\ell$). The base case $j=0$ is trivial. Assume the inductive hypothesis
holds for all $Y^{b}_{i},i<j$. By Lemma 4.1 and recalling
$g_{\ell}\in\ker(D_{\ell})$, we have:

$\displaystyle
Y^{b}_{j}g_{\ell}=\left(1-\delta^{i_{1}+\ell-2}_{i_{1}-2}\right)Y^{b}_{j-1}g_{\ell}+\Gamma
g_{\ell},$

where $\Gamma$ has spectral norm

$\left\lVert\Gamma\right\rVert\leq\gamma^{i_{1}+\ell-2}_{i_{1}-2}.$

Notice that $Y^{b}_{j-1}$ has down operator indices
$\\{i_{2}-2,\ldots,i_{j}-2\\}$. The inductive hypothesis then implies:

$\displaystyle Y^{b}_{j}g_{\ell}$
$\displaystyle=\left(1-\delta^{i_{1}+\ell-2}_{i_{1}-2}\right)\prod\limits_{s=2}^{j}\left(1-\delta^{i_{s}+\ell-2s}_{i_{s}-2s}\right)Y^{b}_{0}g_{\ell}+\left(1-\delta^{i_{1}+\ell-2}_{i_{1}-2}\right)\Gamma^{\prime}g_{\ell}+\Gamma
g_{\ell}$
$\displaystyle=\prod\limits_{s=1}^{j}\left(1-\delta^{i_{s}+\ell-2s}_{i_{s}-2s}\right)g_{\ell}+\left(1-\delta^{i_{1}+\ell-2}_{i_{1}-2}\right)\Gamma^{\prime}g_{\ell}+\Gamma
g_{\ell},$

where $\Gamma^{\prime}g_{\ell}$ has norm

$\left\lVert\Gamma^{\prime}g_{\ell}\right\rVert\leq\left\lVert
g_{\ell}\right\rVert\sum\limits_{s=2}^{j}\gamma^{i_{s}+\ell-2s}_{i_{s}-2s}\prod_{t=2}^{s-1}\left(1-\delta^{i_{t}+\ell-2t}_{i_{t}-2t}\right).$

Thus we may bound the norm of the righthand error term by:

$\displaystyle\left\lVert\left(1-\delta^{i_{1}+\ell-2}_{i_{1}-2}\right)\Gamma^{\prime}g_{\ell}+\Gamma
g_{\ell}\right\rVert$
$\displaystyle\leq\left(1-\delta^{i_{1}+\ell-2}_{i_{1}-2}\right)\left\lVert\Gamma^{\prime}\right\rVert\left\lVert
g_{\ell}\right\rVert+\left\lVert\Gamma\right\rVert\left\lVert
g_{\ell}\right\rVert$
$\displaystyle\leq\sum\limits_{s=1}^{j}\gamma_{i_{s}-2s}^{i_{s}+\ell-2s}\prod\limits_{t=1}^{s-1}\left(1-\delta^{i_{t}+\ell-2t}_{i_{t}-2t}\right)\left\lVert
g_{\ell}\right\rVert,$

as desired. Recalling the shift in $i_{s}$ by $k-\ell$, we can then bound the
resulting error by $(j+k)j\gamma\left\lVert g_{\ell}\right\rVert$ since
$\delta\in[0,1]^{d-1}$. ∎

It is worth noting that when $\gamma=0$, this implies that the HD-Level-Set
decomposition is a true eigendecomposition. Since balanced walks are simply
affine combinations of pure walks, this immediately implies a similar result
for the more general case. To align with our definition of approximate
eigendecompositions and Theorem 3.2, we’ll also need the following general
relation between $\left\lVert g_{\ell}\right\rVert$ and $\left\lVert
f_{\ell}\right\rVert$ for eposets proved in [3] (albeit without the exact
parameter dependence).

######  Lemma 4.3 ([3, Lemma 8.11]).

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet, $0\leq\ell\leq
k<d$, and let

$\rho^{k}_{\ell}=\prod\limits^{k-\ell}_{i=1}\left(1-\delta_{k-\ell-i}^{k-i}\right),\
\ \rho_{\text{min}}=\min_{0\leq\ell\leq k}\\{\rho^{k}_{\ell}\\}.$

Then for any $f_{\ell}=U^{k}_{\ell}g_{\ell}$ for
$g_{\ell}\in\text{Ker}(D_{\ell})$ we have:

$\langle f_{\ell},f_{\ell}\rangle\in(\rho^{k}_{\ell}\pm k^{2}\gamma)\langle
g_{\ell},g_{\ell}\rangle,$

and for all $i\neq\ell$:

$\langle f_{\ell},f_{i}\rangle\leq
O\left(\frac{k^{2}}{\rho_{\text{min}}}\gamma\left\lVert
f_{\ell}\right\rVert\left\lVert f_{i}\right\rVert\right).$

As an aside, we remark that the parameter $\rho^{k}_{\ell}$ turns out to be a
crucial throughout much of our work, and while it is difficult to interpret on
general eposets, we prove it has a very natural form as long as non-laziness
holds.

######  Claim 4.4 ($\rho^{k}_{\ell}$ for regular eposets).

Let $(X,\Pi)$ be a regular, $\gamma$-non-lazy141414One can prove this claim
more generally for any $\beta$-non-laziness, but most $\gamma$-eposets of
interest are additionally $\gamma$-non-lazy, so this simplified version is
generally sufficient. $d$-dimensional $(\delta,\gamma)$-eposet. Then for any
$i\leq k<d$, we have:

$\rho^{k}_{i}\in\frac{1}{R(k,i)}\pm err,$

where $err\leq
O\left(\frac{i^{3}k^{2}R_{\text{max}}}{\delta_{i}(1-\delta_{i-1})}\gamma\right)$.
Likewise as long as $\gamma\leq
O\left(\frac{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}{i^{3}k^{2}R^{2}_{\text{max}}}\right)$
we have

$\rho_{\text{min}}^{-1}\leq O(R_{\text{max}}),$

where $R_{\text{max}}\coloneqq\max_{0\leq i\leq k}\\{R(k,i)\\}$.

This gives a nice generalization of the interpretation of $\rho^{k}_{i}$ on
hypergraphs, which is well known to be $\frac{1}{{k\choose i}}$ [3]. We prove
this claim in Appendix A. For simplicity, we will assume throughout the rest
of this work that our eposets are $\gamma$-non-lazy, which is true for most
cases of interest (see Appendix A). All results holds in the more general case
using $\rho^{k}_{i}$ unless otherwise noted.

Combining Proposition 4.2 and Lemma 4.3 immediately implies that the HD-Level-
Set Decomposition is an approximate eigendecomposition in the sense of
Definition 3.1.

######  Corollary 4.5.

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet and let
$M=\sum\limits_{Y\in\mathcal{Y}}\alpha_{Y}Y$ be an HD-walk. For $1\leq\ell\leq
k$, if $f_{\ell}=U^{k}_{\ell}g_{\ell}$ for some $g_{\ell}\in H^{\ell}$, then
for $\gamma\leq
O\left(\frac{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}{k^{5}R^{2}_{\text{max}}}\right)$:

$\left\lVert
Mf_{\ell}-\left(\sum\limits_{Y\in\mathcal{Y}}\alpha_{Y}\lambda_{Y,\delta,\ell}\right)f_{\ell}\right\rVert\leq
c\gamma\left\lVert f_{\ell}\right\rVert,$

where $\lambda_{Y,\delta,\ell}$ is the corresponding eigenvalues of the pure
balanced walk $Y$ on a $(\delta,0)$-eposet (the form of which are given in
Proposition 4.2), and $c\leq O\left((h(M)+k)h(M)R(k,\ell)w(M)\right)$.

Thus as long as the walk in question is self-adjoint (e.g. canonical or swap
walk), Theorem 3.2 immediately implies that the true spectrum is concentrated
around these approximate eigenvalues.

Before moving on it is instructive (and as we will soon see quite useful) to
give an example application of Corollary 4.5 to a basic higher order random
walk.

######  Corollary 4.6 (Spectrum of Lower Canonical Walks).

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet. The approximate eigenvalues of
the canonical lower walk $\widecheck{N}_{k}^{k-\ell}$ are:

$\lambda_{j}(\widecheck{N}_{k}^{k-\ell})=\prod_{s=1}^{k-\ell}(1-\delta^{k-s}_{k-s-j}).$

###### Proof.

The lower canonical walk $\widecheck{N}_{k}^{k-\ell}=U^{k}_{\ell}D^{k}_{\ell}$
is of height $k-\ell$, and has down operator at positions
$\\{1,\ldots,k-\ell\\}$. In the language of Proposition 4.2 we therefore have
$i_{s}=s$, which therefore gives:

$\lambda_{j}(\widecheck{N}_{k}^{k-\ell})=\prod_{s=1}^{k-\ell}(1-\delta^{k-s}_{k-s-j}).$

Note this is $0$ when $j>\ell$. ∎

Similar to the case of $\rho^{k}_{i}$, while this is difficult to interpret in
the general setting, the eigenvalues have a very natural form on non-lazy
eposets given by the regularity parameters.

######  Theorem 4.7.

Let $(X,\Pi)$ be a $\gamma$-non-lazy $(\delta,\gamma)$-eposet. The approximate
eigenvalues of the canonical lower walk $\widecheck{N}_{k}^{k-i}$ are:

$\lambda_{j}(\widecheck{N}_{k}^{k-i})\in\frac{R(i,j)}{R(k,j)}\pm c\gamma,$

where $c\leq
O\left(\frac{i^{4}k^{2}R_{\text{max}}}{\delta_{i}(1-\delta_{i-1})}\gamma\right)$.

The proof requires machinery developed in Section 6 and Appendix A, and is
given in Appendix A.

##  5 Pseudorandomness and the HD-Level-Set Decomposition

Now that we know the spectral structure of HD-walks, we shift to studying
their combinatorial structure. In particular, we will focus on how natural
notions of pseudorandomness control the projection of functions onto the HD-
Level-Set Decomposition.

Before proceeding, we state a simple corollary of Lemma 4.3 that will prove
useful going forward:

######  Corollary 5.1.

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet and suppose $f\in C_{k}$ has HD-
Level-Set Decomposition $f=f_{0}+\ldots+f_{k}$. If
$\gamma\leq\frac{c^{\prime}\rho_{\min}}{k^{3}}$ for a sufficiently small
constant $c^{\prime}>0$, then

$\sum_{j=0}^{k}\|f_{j}\|\leq O(\sqrt{k}\|f\|).$ (1)

Moreover, for any subset of indices $I$, it holds that

$-\sum_{j\in I}\langle f,f_{j}\rangle\leq
O\left(\frac{k^{3}\gamma\|f\|^{2}}{\rho_{min}}\right).$

In particular, if $I=\\{j:\langle f,f_{j}\rangle\leq 0\\}$, then

$\sum_{j\in I}|\langle f,f_{j}\rangle|\leq
O\left(\frac{k^{3}\gamma\|f\|^{2}}{\rho_{min}}\right).$

###### Proof.

For the first claim, recall that by the approximate orthogonality of the HD-
Level-Set Decomposition (Lemma 4.3), we have for all $i\neq j$:

$|\langle f_{i},f_{j}\rangle|\leq
O\left(\frac{k^{2}}{\rho_{\text{min}}}\gamma\left\lVert
f_{i}\right\rVert\left\lVert f_{j}\right\rVert\right).$

Then, applying Cauchy-Schwarz gives:

$\displaystyle\left(\sum\limits_{j=1}^{k}\left\lVert
f_{j}\right\rVert\right)^{2}$ $\displaystyle\leq
k\sum\limits_{j=1}^{k}\left\lVert f_{j}\right\rVert^{2}$ $\displaystyle\leq
k\langle f,f\rangle-k\sum\limits_{i\neq j\neq 0}\langle f_{i},f_{j}\rangle$
$\displaystyle\leq k\langle f,f\rangle+c\gamma\sum\limits_{i\neq j\neq
0}\left\lVert f_{i}\right\rVert\left\lVert f_{j}\right\rVert$
$\displaystyle\leq k\langle
f,f\rangle+c\gamma\left(\sum\limits_{j=1}^{k}\left\lVert
f_{j}\right\rVert\right)^{2}$

where $c\leq O\left(\frac{k^{3}}{\rho_{\text{min}}}\right)$. By our assumption
on $\gamma$, we have $c\gamma\leq\frac{1}{2}$, and therefore rearranging
yields

$\sum\limits_{i=1}^{k}\left\lVert f_{j}\right\rVert\leq O(\sqrt{k}\left\lVert
f\right\rVert).$

We now show how the second claim is a consequence of the first. For any subset
$I$, we have

$\displaystyle-\sum_{j\in I}\langle f,f_{j}\rangle$
$\displaystyle\leq-\sum_{j\in I}\sum_{i\neq j}\langle f,f_{j}\rangle$
$\displaystyle\leq\frac{Ck^{2}\gamma}{\rho_{\min}}\sum_{i,j}\left\lVert
f_{i}\right\rVert\left\lVert f_{j}\right\rVert$
$\displaystyle=\frac{O(k^{2}\gamma)}{\rho_{\min}}\left(\sum_{i=0}^{k}\left\lVert
f_{i}\right\rVert\right)^{2}$ $\displaystyle\leq
O\left(\frac{k^{3}\gamma\left\lVert f\right\rVert}{\rho_{\min}}\right).$

∎

###  5.1 $\ell_{2}$-pseudorandomness

We start with pseudorandomness in the $\ell_{2}$-regime, which measures the
variance of a set across links.

######  Definition 5.2 ($\ell_{2}$-Pseudorandom functions [15]).

A function $f\in C_{k}$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{2}$-pseudorandom if its
variance across $i$-links is small for all $1\leq i\leq\ell$:

$\mathrm{Var}(D^{k}_{i}f)\leq\varepsilon_{i}|\mathbb{E}[f]|.$

In their work on simplicial complexes, BHKL [15] observed a close connection
between $\ell_{2}$-pseudorandomness, the HD-Level-Set Decomposition, and the
spectra of the lower canonical walks. We’ll show the same connection holds in
general for eposets.

######  Theorem 5.3.

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet with $\gamma\leq
O\left(\frac{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}{k^{5}R^{2}_{\text{max}}}\right)$.
If $f\in C_{k}$ has HD-Level-Set Decomposition $f=f_{0}+\ldots+f_{k}$, then
for any $\ell\leq k$, $\mathrm{Var}(D^{k}_{\ell}f)$ is controlled by its
projection onto $V_{k}^{0}\oplus\ldots\oplus V_{k}^{\ell}$ in the following
sense:

$\displaystyle\mathrm{Var}(D^{k}_{\ell}f)$
$\displaystyle\in\sum\limits_{j=1}^{\ell}\lambda_{j}(\widecheck{N}_{k}^{k-\ell})\langle
f,f_{j}\rangle\pm c_{k}\gamma\|f\|^{2},$

where $c_{k}\leq O(k^{5/2}R_{\text{max}})$ and
$\lambda_{j}(\widecheck{N}_{k}^{k-\ell})=\prod_{s=1}^{k-\ell}(1-\delta^{k-s}_{k-s-j})$.

###### Proof.

To start, notice that since $\langle
D^{k}_{\ell}f,D^{k}_{\ell}f\rangle=\langle\widecheck{N}_{k}^{k-\ell}f,f\rangle$
it is enough to analyze the application of $\widecheck{N}_{k}^{k-\ell}$ to
$f$. By Corollary 4.6, we know that each $f_{j}$ is an approximate eigenvector
satisfying:

$\left\lVert\widecheck{N}_{k}^{k-\ell}f_{j}-\lambda_{j}(\widecheck{N}_{k}^{k-\ell})f_{j}\right\rVert\leq
O(k^{2}R(k,\ell)\gamma)\left\lVert f_{j}\right\rVert,$

where $\lambda_{j}(\widecheck{N}_{k}^{k-\ell})=0$ for $j>\ell$. Combining
these observations gives:

$\displaystyle\text{Var}(D^{k}_{\ell}f)$ $\displaystyle=\left\langle
D^{k}_{\ell}f,D^{k}_{\ell}f\right\rangle-\mathbb{E}[D^{k}_{\ell}f]^{2}$
$\displaystyle=\left\langle f,U^{k}_{\ell}D^{k}_{\ell}f\right\rangle-\langle
f,f_{0}\rangle$ $\displaystyle=\sum\limits_{j=1}^{k}\langle
f,U^{k}_{\ell}D^{k}_{\ell}f_{j}\rangle$
$\displaystyle\in\sum\limits_{j=1}^{\ell}\lambda_{j}(\widecheck{N}_{k}^{k-\ell})\langle
f,f_{j}\rangle\pm O\left(\frac{k^{2}}{\rho_{\text{min}}}\gamma\left\lVert
f\right\rVert\sum\limits_{j=1}^{k}\left\lVert f_{j}\right\rVert\right).$

where we have additionally used the fact that $\langle
f,f_{0}\rangle=\mathbb{E}[f]^{2}=\mathbb{E}[D^{k}_{\ell}f]^{2}$ and
$\lambda_{0}(\widecheck{N}_{k}^{k-\ell})=1$. Applying Equation 1 from
Corollary 5.1 to bound the sum in the error term and replacing $\rho$ with the
relevant regularity parameters by 4.4 then gives the result. ∎

As an immediate corollary, we get a level-$i$ inequality for pseudorandom
functions.

######  Corollary 5.4.

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet with $\gamma\leq
O\left(\frac{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}{k^{5}R^{2}_{\text{max}}}\right)$
and let $f\in C_{k}$ be an
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{2}$-pseudorandom
function. Then for any $1\leq i\leq\ell$:

$|\langle f,f_{i}\rangle|\leq
R(k,i)\varepsilon_{i}|\mathbb{E}[f]|+c\gamma\|f\|^{2},$

where $c\leq
O\left(\frac{k^{5}R_{\text{max}}^{2}}{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}\right)$.

###### Proof.

By Corollary 5.1, for any given $1\leq i\leq k$, it holds that $-\sum_{j\neq
i}\langle f,f_{j}\rangle\leq
O\left(\frac{k^{3}}{\rho_{\text{min}}}\gamma\|f\|^{2}\right)$. It follows from
Theorem 5.3 that for all $0\leq i\leq k$, the variance of $D_{i}^{k}f$ is
lower bounded by its projection onto $f_{i}$:

$\displaystyle\text{Var}(D_{i}^{k}f)\geq\lambda_{i}(\widecheck{N}_{k}^{k-i})\langle
f,f_{i}\rangle-c\gamma\langle f,f\rangle,$

where $c\leq O(\frac{k^{3}}{\rho_{\text{min}}})$. Noting that
$\lambda_{i}(\widecheck{N}_{k}^{k-i})=\rho^{k}_{i}$, if $i\leq\ell$, re-
arranging the above and applying the pseudorandomness assumption gives:

$\displaystyle\langle f,f_{i}\rangle$
$\displaystyle\leq\frac{1}{\rho^{k}_{i}}\text{Var}(D_{i}^{k}f)+c_{2}\gamma\langle
f,f\rangle$
$\displaystyle\leq\frac{1}{\rho^{k}_{i}}\varepsilon_{i}|\mathbb{E}[f]|+c_{2}\gamma\langle
f,f\rangle,$

where $c_{2}\leq O(\frac{k^{3}}{\rho^{2}_{\text{min}}})$. The lower bound on
$\langle f,f_{i}\rangle$ is immediate from Corollary 5.1 with the set
$I=\\{i\\}$. Applying 4.4 then gives the result. ∎

As mentioned previously, this also recovers the tight inequality for
simplicial complexes given in [15] where $R(k,i)={k\choose i}$, as well as
providing the natural $q$-analog for $q$-simplicial complexes where
$R(k,i)={k\choose i}_{q}$.

###  5.2 $\ell_{\infty}$-pseudorandomness

While $\ell_{2}$-pseudorandomness is useful in its own right (e.g. for local-
to-global algorithms for unique games [33, 15]), there is also significant
interest in a stronger $\ell_{\infty}$-variant in the hardness of
approximation literature [30, 25].

######  Definition 5.5 ($\ell_{\infty}$-Pseudorandom functions).

A function $f\in C_{k}$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{\infty}$-pseudorandom if
for all $1\leq i\leq\ell$ its local expectation is close to its global
expectation:

$\left\|D^{k}_{i}f-\mathbb{E}[f]\right\|_{\infty}\leq\varepsilon_{i}.$

In their recent work on $\ell_{2}$-structure of expanding simplicial
complexes, BHKL prove a basic reduction from $\ell_{\infty}$ to
$\ell_{2}$-pseudorandomness that allows for an analogous level-$i$ inequality
for this notion as well. Here, we’ll show the same result holds for general
eposets. As in their work, we’ll take advantage of a weak local-consistency
property called locally-constant sign.

######  Definition 5.6 (locally-constant sign [15]).

Let $(X,\Pi)$ be a graded poset. We say a function $f\in C_{k}$ has
$\ell$-local constant sign if:

  1. 1.

$\mathbb{E}[f]\neq 0$,

  2. 2.

$\forall s\in X(\ell)$ s.t. $~{}\underset{X_{s}}{\mathbb{E}}[f]\neq
0:\text{sign}\left(\underset{X_{s}}{\mathbb{E}}[f]\right)=\text{sign}\left(\mathbb{E}[f]\right)$.

With this in mind, we now state $\ell_{\infty}$-variant of Corollary 5.4:

######  Theorem 5.7.

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet with $\gamma\leq
O\left(\frac{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}{k^{5}R^{2}_{\text{max}}}\right)$
and let $f\in C_{k}$ have HD-Level-Set Decomposition $f=f_{0}+\ldots+f_{k}$.
If $f$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{\infty}$-pseudorandom,
then for all $1\leq i\leq\ell$:

$|\langle
f,f_{i}\rangle|\leq\left(R(k,i)+c\gamma\right)\varepsilon_{i}^{2}+c\gamma\left\lVert
f\right\rVert^{2},$

and if $f$ has $i$-local constant sign:

$|\langle
f,f_{i}\rangle|\leq\left(R(k,i)+c\gamma\right)\varepsilon_{i}|\mathbb{E}[f]|+c\gamma\left\lVert
f\right\rVert^{2}$

where in both cases $c\leq
O\left(\frac{k^{5}R_{\text{max}}^{2}}{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}\right)$.

We note that when $f$ is boolean, this bound simplifies to

$|\langle
f,f_{i}\rangle|\leq\left(R(k,i)\varepsilon_{i}+c\gamma\right)\mathbb{E}[f],$

which we’ll see in the next section is a particularly useful form for
analyzing edge expansion. The proof of Theorem 5.7 relies mainly on a
reduction to the $\ell_{2}$-variant for functions with locally-constant sign.
This reduction is almost exactly the same as in [15], but we include it for
completeness.

######  Lemma 5.8.

Let $(X,\Pi)$ be a graded poset and $f\in C_{k}$ a
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{\infty}$-pseudorandom
function with $i$-local constant sign for any $i\leq\ell$. Then $f$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{2}$-pseudorandom.

###### Proof.

As in [15], the idea is to notice that locally constant sign allows us to
rewrite $\left\lVert D^{k}_{i}f\right\rVert_{2}^{2}$ as an expectation over
some related distribution $P_{i}$:

$\displaystyle\frac{1}{\mathbb{E}[f]}\langle D^{k}_{i}f,D^{k}_{i}f\rangle$
$\displaystyle=\sum\limits_{s\in
X(i)}\pi_{i}(s)\left(\frac{1}{\mathbb{E}[f]}\sum\limits_{t\in
X_{s}}\frac{\pi_{k}(t)f(t)}{\pi_{k}(X_{s})}\right)D^{k}_{i}f(s)$
$\displaystyle=\sum\limits_{s\in X(i)}\left(\frac{1}{R(k,i)}\frac{\sum_{t\in
X_{s}}\pi_{k}(t)f(t)}{\mathbb{E}[f]}\right)D^{k}_{i}f(s)$
$\displaystyle=\underset{P_{i}}{\mathbb{E}}[D^{k}_{i}f],$

where $P_{i}$ being a probability distribution follows from the locally-
constant sign of $f$, and the second step follows from the fact that
$\pi_{k}(X_{s})=\sum_{t\in X_{s}}\pi_{k}(t)=R(k,i)\pi_{i}(s)$. The result then
follows easily from averaging:

$\left|\frac{1}{\mathbb{E}[f]}\text{Var}(D^{k}_{i}f)\right|=\left|\underset{P_{i}}{\mathbb{E}}[D^{k}_{i}f]-\mathbb{E}[f]\right|\leq\|D^{k}_{i}f-\mathbb{E}[f]\|_{\infty}.$

When $\mathbb{E}[f]>0$, the $\ell_{\infty}$-norm here may be replaced with
maximum. ∎

The proof of Theorem 5.7 now follows from reducing to the case of locally-
constant sign. The argument is exactly as in the proof of [15, Theorem 8.7],
but we include it for completeness.

###### Proof of Theorem 5.7.

We focus on the general bound, since the result for functions with locally
constant sign is immediate from Lemma 5.8 and Corollary 5.4. The argument for
general functions $f$ follows simply from noting that we can always shift $f$
to have locally constant sign. With this in mind, assume $\mathbb{E}[f]\geq 0$
for simplicity (the negative case is similar). Let
$f^{\prime}=f+(\varepsilon_{i}-\mathbb{E}[f])\mathbbm{1}$ be the
aforementioned shift. As long as $\varepsilon_{i}>0$, it is easy to see that
$f^{\prime}$ has $i$-local constant sign and further that

$f^{\prime}=f_{0}^{\prime}+f_{i}+\ldots+f_{k},$

where $f_{0}^{\prime}=f_{0}+(\varepsilon_{i}-\mathbb{E}[f])\mathbbm{1}$. Since
shifts have no effect on $\ell_{\infty}$-pseudorandomness, $f^{\prime}$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{\infty}$-pseudorandom by
assumption, and therefore
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{2}$-pseudorandom by Lemma
5.8. We can now apply Corollary 5.4 to get:

$\displaystyle\langle
f+(\varepsilon_{i}-\mathbb{E}[f])\mathbbm{1},f_{i}\rangle$
$\displaystyle\leq\frac{1}{\rho^{k}_{i}}\varepsilon_{i}\mathbb{E}[f+(\varepsilon_{i}-\mathbb{E}[f])\mathbbm{1}]+c\gamma\langle
f+(\varepsilon_{i}-\mathbb{E}[f])\mathbbm{1},f+(\varepsilon_{i}-\mathbb{E}[f])\mathbbm{1}\rangle$
$\displaystyle\leq\left(\frac{1}{\rho^{k}_{i}}+c\gamma\right)\varepsilon_{i}^{2}+c\gamma\langle
f,f\rangle,$

since $\langle f_{i},\mathbbm{1}\rangle=0$ for all $i>0$. Finally, as this
holds for all $\varepsilon_{i}>0$, a limiting argument implies the result for
$\varepsilon_{i}=0$. Applying 4.4 completes the proof. ∎

##  6 Expansion of HD-walks

It is well known that higher order random walks on simplicial complexes (e.g.
the Johnson graphs) are not small-set expanders. BHKL gave an exact
characterization of this phenomenon for local-spectral expanders: they showed
that the expansion of any $i$-link with respect to an HD-walk $M$ is almost
exactly $1-\lambda_{i}(M)$. Moreover, using the level-$i$ inequality from the
previous section, BHKL proved a tight converse to this result in an
$\ell_{2}$-sense: any non-expanding set must have high variance across links.
This gave a complete $\ell_{2}$-characterization of non-expanding sets on
local-spectral expanders, and lay the structural groundwork for new algorithms
for unique games over HD-walks.

In this section, we’ll show that these results extend to general expanding
posets. To start, let’s recall the definition of edge expansion.

######  Definition 6.1 (Weighted Edge Expansion).

Let $(X,\Pi)$ be a graded poset and $M$ a $k$-dimensional HD-Walk. The
weighted edge expansion of a subset $S\subset X(k)$ with respect to $M$ is

$\Phi(S)=\underset{v\sim\pi_{k}|_{S}}{\mathbb{E}}\left[M(v,X(k)\setminus
S)\right],$

where

$M(v,X(k)\setminus S)=\sum\limits_{y\in X(k)\setminus S}M(v,y)$

and $M(v,y)$ denotes the transition probability from $v$ to $y$.

Before we prove the strong connections between links and expansion, we need to
introduce an important property of HD-walks, monotonic eigenvalue decay.

######  Definition 6.2 (Monotonic HD-walk).

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet. We call an HD-walk $M$ monotonic
if its approximate eigenvalues $\lambda_{i}(M)$ (given in Corollary 4.5) are
non-increasing.

Most HD-walks of interest (e.g. pure walks, partial-swap walks on simplicial
or $q$-simplicial complexes, etc.) are monotonic. This property will be
crucial to understanding expansion. To start, let’s see how it allows us to
upper bound the expansion of links.

######  Theorem 6.3 (Local Expansion vs Global Spectra).

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet and $M$ be a $k$-dimensional
monotonic HD-walk. Then for all $0\leq i\leq k$ and $\tau\in X(i)$:

$\Phi(X_{\tau})\in 1-\lambda_{i}(M)\pm c\gamma,$

where $c\leq
O\left(\frac{k^{5}R^{2}_{\text{max}}(h(M)+k)h(M)w(M)}{\delta^{k}_{k-i}(1-\delta_{i-1})}\right)$.

The key to proving Theorem 6.3 is to show that the weight of an $i$-link lies
almost entirely on level $i$ of the HD-Level-Set Decomposition. To show this,
we’ll rely another connection between regularity and eposet parameters for
non-lazy posets.

######  Claim 6.4.

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet. Then for every
$1\leq k\leq d$ and $0\leq i\leq k$, the following approximate relation
between the eposet and regularity parameters holds:

$\lambda_{i}(N_{k}^{1})\in\frac{R(k,i)}{R(k+1,i)}\pm\left(\gamma^{k}_{k-i}+R(k,i)\delta^{k}_{k-i}\gamma\right)$

where we recall $\lambda_{i}(N_{k}^{1})=1-\prod\limits^{k}_{j=i}\delta_{j}$.

We prove this relation in Appendix A. With this in hand, we can show links
project mostly onto their corresponding level.

######  Lemma 6.5.

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet with $\gamma\leq
O\left(\frac{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}{k^{5}R^{2}_{\text{max}}}\right)$.
Then for all $0\leq i\leq k<d$ and $\tau\in X(i)$, $\mathbbm{1}_{X_{\tau}}$
lies almost entirely in $V_{k}^{i}$. That is for all $j\neq i$:

$\left|\frac{\langle\mathbbm{1}_{X_{\tau},i},\mathbbm{1}_{X_{\tau},j}\rangle}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}\right|\leq
O\left(\frac{k^{3}R_{\text{max}}}{\delta^{k}_{k-i}(1-\delta_{i-1})}\gamma\right).$

###### Proof.

We’ll show that the expansion of $\mathbbm{1}_{X_{\tau}}$ with respect to the
upper walk $N_{k}^{1}$ is almost exactly $1-\lambda_{i}(N_{k}^{1})$, which
implies most of the weight must lie on $V^{k}_{i}$. We’ll start by analyzing
the expansion of $\mathbbm{1}_{X_{\tau}}$ through a simple combinatorial
argument. First, since $D$ and $U$ are adjoint we have:

$\displaystyle\bar{\Phi}(\mathbbm{1}_{X_{\tau}})$
$\displaystyle=\frac{\langle\mathbbm{1}_{X_{\tau}},D_{k+1}U_{k}\mathbbm{1}_{X_{\tau}}\rangle}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}$
$\displaystyle=\frac{\langle
U_{k}\mathbbm{1}_{X_{\tau}},U_{k}\mathbbm{1}_{X_{\tau}}\rangle}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}.$

The trick is now to notice that
${\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}=R(k,i)\pi_{i}(\tau)$,
and $\langle
U_{k}\mathbbm{1}_{X_{\tau}},U_{k}\mathbbm{1}_{X_{\tau}}\rangle=\frac{R(k,i)^{2}}{R(k+1,i)}\pi_{i}(\tau)$.
As a result, applying 6.4 gives:

$\bar{\Phi}(\mathbbm{1}_{X_{\tau}})\in\lambda_{i}(N_{k}^{1})\pm(c\gamma+R(k,i)\gamma),$

for $c\leq k\gamma$. To see why this implies that most of the weight lies on
$V^{k}_{i}$, note that we can also unfold the expansion of
$\mathbbm{1}_{X_{\tau}}$ in terms of the HD-Level-Set decomposition:

$\displaystyle\bar{\Phi}(\mathbbm{1}_{X_{\tau}})$
$\displaystyle=\frac{1}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}\sum\limits_{j=0}^{i}\langle\mathbbm{1}_{X_{\tau}},N^{1}_{k}\mathbbm{1}_{X_{\tau},j}\rangle$
$\displaystyle\in\frac{1}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}\sum\limits_{j=0}^{i}\lambda_{i}(N^{1}_{k})\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau},j}\rangle\pm
c_{2}\gamma$

where $c_{2}\leq\frac{k\sqrt{k}}{\rho_{\text{min}}}$. Recall from Corollary
5.1 that for the set $I$ of indices with negative inner product, it holds that
$-\sum_{j\in
I}\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau},j}\rangle\leq
O\left(\frac{k^{3}}{\rho_{\text{min}}}\gamma\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle\right)$.
Moreover, the positive inner products (i.e. the indices not in $I$) must sum
to at least $\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle$.
Then if there exists some $j\neq i$ such that
$\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau},j}\rangle>c_{3}\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle$
for large enough $c_{3}\leq
O\left(\frac{1}{\delta^{k}_{k-i}(1-\delta_{i-1})}\cdot\left(\frac{k^{3}}{\rho_{\text{min}}}\gamma+R(k,i)\gamma\right)\right)$,
the non-expansion would be strictly larger than
$\lambda_{i}(N_{k}^{1})+c\gamma+R(k,i)\gamma$ giving the desired contradiction
(note that $(1-\delta_{i-1})\delta^{k}_{k-1}$ is the gap between the $i-1$st
and $i$th approximate eigenvalue). The form in the theorem statement then
follows from applying 4.4. ∎

We note that the above is the only result in our work that truly relies on
non-laziness (it is used only to replace $\rho$ with regularity in all other
results). It is possible to recover the upper bound in Theorem 6.3 for general
eposets via arguments used in [15], but the lower bound remains open for
concentrated posets. With that in mind, we now prove Theorem 6.3.

###### Proof of Theorem 6.3.

By the previous lemma, we have

$\left|\frac{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau},j}\rangle}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}\right|\leq
O\left(\frac{1}{\delta^{k}_{k-i}(1-\delta_{i-1})}\cdot\left(\frac{k^{3}}{\rho_{\text{min}}}\gamma+R(k,i)\gamma\right)\right).$

Expanding out $\bar{\Phi}(\mathbbm{1}_{X_{\tau}})$ then gives:

$\displaystyle\bar{\Phi}(\mathbbm{1}_{X_{\tau}})$
$\displaystyle=\frac{1}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}\sum\limits_{j=0}^{i}\langle\mathbbm{1}_{X_{\tau}},M\mathbbm{1}_{X_{\tau},j}\rangle$
$\displaystyle\leq\frac{1}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}\sum\limits_{j=0}^{i}\lambda_{i}(M)\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau},j}\rangle+c_{2}\gamma$
$\displaystyle\leq\lambda_{i}(M)\frac{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau},i}\rangle}{\langle\mathbbm{1}_{X_{\tau}},\mathbbm{1}_{X_{\tau}}\rangle}+err_{1}$
$\displaystyle\leq\lambda_{i}(M)+err_{2}.$

where $c_{2},err_{1},err_{2}\leq
O\left(\frac{k}{\delta^{k}_{k-i}(1-\delta_{i-1})}\left(\frac{k^{2}(h(M)+k)h(M)w(M)}{\rho_{\text{min}}}\gamma+R(k,i)\gamma\right)\right)$
and the last step follows from the approximate orthogonality. As usual, the
form in the theorem statement then follows from applying 4.4. ∎

Altogether, we’ve seen that for sufficiently nice expanding posets, the
expansion of any $i$-link with respect to an HD-walk is almost exactly
$1-\lambda_{i}(M)$. Since HD-walks are generally poor expanders (have large
$\lambda_{1}(M)$), Theorem 6.3 implies that links are examples of small, non-
expanding sets. Following BHKL, we’ll now prove a converse to this result: any
non-expanding set must be explained by some structure inside links. To help
give a precise statement, we first recall BHKL’s notion of Stripped Threshold
Rank (specialized to eposets for convenience).

######  Definition 6.6 (Stripped Threshold Rank [15]).

Let $(X,\Pi)$ be a $(\delta,\gamma)$-eposet and $M$ a $k$-dimensional HD-walk
with $\gamma$ small enough that Theorem 3.2 implies the HD-Level-Set
Decomposition has a corresponding decomposition of disjoint eigenstrips
$C_{k}=\bigoplus W_{k}^{i}$. The ST-Rank of $M$ with respect to $\eta$ is the
number of strips containing an eigenvector with eigenvalue at least $\eta$:

$R_{\eta}(M)=|\\{W_{k}^{i}:\exists f\in V^{i},Mf=\lambda f,\lambda>\eta\\}|.$

We often write just $R_{\eta}$ when $M$ is clear from context.

With this in mind, we’ll show a converse to Theorem 6.3 in both $\ell_{2}$ and
$\ell_{\infty}$ senses (respectively that any non-expanding set must have high
variance over links, and must be more concentrated than expected in some
particular link). It is convenient to express these results through their
contrapositives: that pseudorandom sets expand. The proof is the same as in
[15] for simplicial complexes, but we include it for completeness.

######  Theorem 6.7.

Let $(X,\Pi)$ $(\delta,\gamma)$-eposet, $M$ a $k$-dimensional, monotonic HD-
walk, and $\gamma$ small enough that the eigenstrip intervals of Theorem 3.2
are disjoint. For any $\eta>0$, let $r=R_{\eta}(M)-1$. Then the expansion of a
set $S\subset X(k)$ of density $\alpha$ is at least:

$\Phi(S)\geq
1-\alpha-(1-\alpha)\eta-\sum\limits_{i=1}^{r}(\lambda_{i}(M)-\eta)R(k,i)\varepsilon_{i}-c\gamma$

where $S$ is $(\varepsilon_{1},\ldots,\varepsilon_{r})$-pseudorandom and
$c\leq
O\left(\frac{k^{5}R^{2}_{\text{max}}(h(M)+k)h(M)w(M)}{\max_{i}\\{\delta_{i}(1-\delta_{i-1})\\}}\right)$.

###### Proof.

Let $\mathbbm{1}_{S}=\mathbbm{1}_{S,0}+\ldots+\mathbbm{1}_{S,k}$ be the HD-
Level-Set Decomposition of the indicator of $S$. By linearity of the inner
product, we may then write:

$\displaystyle\Phi(S)$
$\displaystyle=1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\langle\mathbbm{1}_{X_{\tau}},M\mathbbm{1}_{X_{\tau}}\rangle$
$\displaystyle=1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\langle\mathbbm{1}_{S},M\mathbbm{1}_{S,j}\rangle$
$\displaystyle=1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\lambda_{j}(M)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,j}\rangle-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\langle\mathbbm{1}_{S},\Gamma_{j}\mathbbm{1}_{S,j}\rangle$

where $\left\lVert\Gamma_{j}\right\rVert\leq
O\left((h(M)+k)h(M)\frac{w(M)}{\rho_{\text{min}}}\right)$. The trick is now to
notice we can bound the righthand error term using Cauchy-Schwarz:

$\displaystyle\left|\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\langle\mathbbm{1}_{S},\Gamma_{j}\mathbbm{1}_{S,j}\rangle\right|$
$\displaystyle\leq\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\left|\langle\mathbbm{1}_{S},\Gamma_{j}\mathbbm{1}_{S,j}\rangle\right|$
$\displaystyle\leq\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\left\lVert\Gamma_{j}\right\rVert\left\lVert\mathbbm{1}_{S}\right\rVert\left\lVert\mathbbm{1}_{S,j}\right\rVert$
$\displaystyle\leq
c\gamma\frac{\left\lVert\mathbbm{1}_{S}\right\rVert}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{j=0}^{k}\left\lVert\mathbbm{1}_{S,j}\right\rVert$
$\displaystyle\leq c_{1}\gamma,$

where $c\leq O\left((h(M)+k)h(M)\frac{w(M)}{\rho_{\text{min}}}\right)$ and
$c_{1}\leq O(\sqrt{k}c)$ by Equation 1. Since $M$ is a monotonic walk, we can
further write:

$\displaystyle\Phi(S)$ $\displaystyle\geq
1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=0}^{r}\lambda_{i}(M)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=r+1}^{k}\lambda_{i}(M)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-
c_{1}\gamma$ $\displaystyle\geq
1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=0}^{r}\lambda_{i}(M)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-\frac{\eta}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=r+1}^{k}\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-
c_{2}\gamma$
$\displaystyle=1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=0}^{r}\lambda_{i}(M)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-\eta\left(1-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=0}^{r}\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle\right)-c_{2}\gamma$
$\displaystyle=1-\eta-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=0}^{r}(\lambda_{i}(M)-\eta)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-
c_{2}\gamma$
$\displaystyle=1-\eta-(1-\eta)\alpha-\frac{1}{\mathbb{E}[\mathbbm{1}_{S}]}\sum\limits_{i=1}^{r}(\lambda_{i}(M)-\eta)\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle-
c_{2}\gamma,$

where $c_{2}\leq
O\left(k^{2}(h(M)+k)h(M)\frac{w(M)}{\rho_{\text{min}}}\right)$. To justify the
second inequality, observe that for any $r<i\leq k$ such that
$\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle\geq 0$, replacing
$\lambda_{i}(M)$ with $\eta$ is valid. For the set $I$ of $r<i\leq k$ with
negative inner product, Corollary 5.1 implies that the sum over $I$ is
$O(k^{3}\gamma/\rho_{\min})$, so the inequality remains valid by absorbing the
small error into $c_{2}$. Applying Corollary 5.4 to bound
$\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle$ then gives the
$\ell_{2}$-variant result, Theorem 5.7 gives the $\ell_{\infty}$-variant, and
4.4 gives the form given in the theorem statement. ∎

We note that Theorem 6.7 recovers the analogous result for simplicial complex
in [15] by plugging in the appropriate value $R(k,i)={k\choose i}$. BHKL also
prove this special case is tight in two senses. First, they show that if one
wants to retain linear dependence on the pseudorandomness parameter
$\varepsilon$, Theorem 6.7 is tight in both the $\ell_{2}$ and
$\ell_{\infty}$-regimes. Second, they show that the dependence on $k$ is
necessary in the $\ell_{2}$-regime, even if we allow sub-optimal dependence on
$\varepsilon$. In the next section, we’ll generalize this result to
$q$-simplicial complexes as well. In both cases the proofs are highly
structural and depend on the underlying structure of the poset—it remains an
interesting open problem whether this bound is tight for all poset structures.

##  7 The Grassmann and $q$-eposets

In this section, we examine the specification of our results on eposets to
expanding subsets of the Grassmann poset. We show that our analysis is tight
in this regime via a classic example of a small non-expanding set in the
Grassmann graphs called co-links.

###  7.1 Spectra

We’ll start by examining the spectrum of HD-walks on the Grassmann and
$q$-eposets. We’ll focus our attention in this section on the most widely used
walks in the literature, the canonical and partial-swap walks. To start,
recall that the Grassmann poset itself is sequentially differential with
parameters

$\delta_{i}=\frac{(q^{i}-1)(q^{n-i+1}-1)}{(q^{i+1}-1)(q^{n-i}-1)}.$ (2)

Plugging this into Proposition 4.2 gives a nice exact form for the spectra of
canonical walks.

######  Corollary 7.1 (Grassmann Poset $N_{k}^{j}$ Spectra).

Let $X=G_{q}(n,d)$ be the Grassmann Poset, $k+j\leq d$, and
$f_{\ell}=U_{\ell}^{k}g_{\ell}$ for some $g_{\ell}\in H^{\ell}$. Then:

$N_{k}^{j}f_{\ell}=\lambda_{\ell}f_{\ell},$

where,

$\lambda_{\ell}=q^{\ell j}\frac{{k+j-\ell\choose j}_{q}}{{k+j\choose
j}_{q}}\frac{{n-k-\ell\choose j}_{q}}{{n-k\choose j}_{q}}\approx q^{-\ell j}.$

###### Proof.

By Proposition 4.2 we have that

$\displaystyle\lambda_{\ell}(N^{j}_{k})$
$\displaystyle=\prod\limits_{s=1}^{j}\left(1-\prod^{k-s+j}_{i=\ell}\delta_{i}\right)$
$\displaystyle=\prod\limits_{s=1}^{j}\left(1-\prod^{k-s+j}_{i=\ell}\frac{(q^{i}-1)(q^{n-i+1}-1)}{(q^{i+1}-1)(q^{n-i}-1)}\right).$

The result then follows from telescoping the interior product and simplifying:

$\displaystyle=\prod\limits_{s=1}^{j}\left(1-\frac{(q^{\ell}-1)(q^{n-\ell+1}-1)}{(q^{k-s+j+1}-1)(q^{n+s-k-j}-1)}\right)$
$\displaystyle=q^{\ell
j}\left(\prod\limits_{s=1}^{j}\frac{\left(q^{k+j-s-\ell+1}-1\right)}{\left(q^{k+j-s+1}-1\right)}\right)\left(\prod\limits_{s=1}^{j}\frac{\left(q^{n+s-k-j-\ell}-1\right)}{\left(q^{n+s-k-j}-1\right)}\right)$
$\displaystyle=q^{\ell j}\frac{{k+j-\ell\choose j}_{q}}{{k+j\choose
j}_{q}}\frac{{n-k-\ell\choose j}_{q}}{{n-k\choose j}_{q}}$

as desired. ∎

This recovers a very simple proof of classical results to this effect (see
e.g. [43]). An analogous computation gives an approximate bound on the
spectrum of $N^{j}_{k}$ on $q$-eposets as well.

######  Corollary 7.2 ($q$-eposets $N_{k}^{j}$ Spectra).

Let $(X,\Pi)$ be a $d$-dimensional $\gamma$-$q$-eposet with $\gamma\leq
q^{-\Omega(k^{2})}$, $k+j\leq d$, and $f_{\ell}=U_{\ell}^{k-1}g_{\ell}$ for
some $g_{\ell}\in H^{\ell}$. Then:

$\displaystyle\left\lVert N_{k}^{j}f_{\ell}-\frac{{k+j-\ell\choose
j}_{q}}{{k+j\choose j}_{q}}f_{\ell}\right\rVert\leq
O\left(j(j+k){k\choose\ell}_{q}\right)\gamma\left\lVert f_{\ell}\right\rVert$

Note that for small enough $\gamma$, Theorem 3.2 implies that the true spectra
is then concentrated around these values as well. It is also worth noting that
these eigenvalues are, as one would expect, the natural $q$-analog of the
corresponding eigenvalues on simplicial complexes.

It turns out that this fact will carry over to the important class of partial-
swap walks as well. Partial-swap walks on simplicial complexes were originally
analyzed by AJT [14], who showed they can be written as a hypergeometric
combination of canonical walks. Their proof is specific to the structure of
simplicial complexes, and some work is required to generalize their ideas to
the Grassmann case. Following the overall proof strategy of AJT, it will be
helpful to first show that the canonical walks themselves can be written as an
expectation of swap walks over a $q$-hypergeometric distribution, and then use
the $q$-binomial inversion theorem to derive the desired result.

######  Lemma 7.3 ($q$-analog of [14, Lemma 4.11]).

Let $(X,\Pi)$ be a pure, measured $q$-simplicial complex. Then:

$N_{k}^{j}=\sum\limits_{i=0}^{j}q^{i^{2}}\frac{{j\choose i}_{q}{k\choose
k-i}_{q}}{{k+j\choose k}_{q}}S_{k}^{i}$

###### Proof.

We follow the structure and notation of [14, Lemma 4.11]. Assume that the
canonical walk starts at a subspace $V\in X(k)$, and walks up to $W\in
X(k+j)$. We wish to analyze the probability that upon walking back down to
level $k$, a subspace $V^{\prime}$ with intersection $k-i$ is chosen, that is:

$dim(V\cap V^{\prime})=k-i.$

Let such an event be denoted $\mathcal{E}_{i}(W)$. It follows from elementary
$q$-combinatorics (see e.g. [44, Lemma 9.3.2]) that

$\Pr_{V^{\prime}\subset
W}[\mathcal{E}_{i}(W)~{}|~{}W]=q^{i^{2}}\frac{{j\choose i}_{q}{k\choose
k-i}_{q}}{{k+j\choose k}_{q}},$

where $V^{\prime}\in X(k)$ is drawn uniformly from the $k$-dimensional
subspaces of $W$. In essence, we wish to relate this process to the swap walk
$S_{k}^{i}$. To do so, note that while the swap walk (as defined) only walks
up to $X(k+i)$, walking up to $X(k+j)$ and conditioning on intersection $i$, a
process called the $i$-swapping $j$-walk by [14], is exactly the same due to
symmetry (via the regularity condition, see [14][Proposition 4.9] for a more
detailed explanation). Thus consider the $i$-swapping $j$-walk, and let
$T^{\prime}_{i}$ denote the variable standing for the subspace chosen by the
walk. Conditioned on picking the same $W$ as the canonical walk in its ascent,
we may relate $T^{\prime}_{i}$ to the canonical walk:

$\Pr[T^{\prime}_{i}=T~{}|~{}W]=\Pr[V^{\prime}=T~{}|~{}W~{}\text{and}~{}\mathcal{E}_{i}(W)]$

We may now decompose the canonical walk by intersection size:

$\displaystyle N_{k}^{j}(V,T)$
$\displaystyle=\sum\limits_{i=0}^{j}\sum\limits_{W\in
X(k+j)}\Pr[W]\Pr[\mathcal{E}_{i}(W)~{}|~{}W]\Pr[V^{\prime}=T~{}|~{}W~{}\text{and}~{}\mathcal{E}_{i}(W)]$
$\displaystyle=\sum\limits_{i=0}^{j}\sum\limits_{W\in
X(k+j)}q^{i^{2}}\frac{{j\choose i}_{q}{k\choose k-i}_{q}}{{k+j\choose
k}_{q}}\underset{W\supset
V}{\mathbb{E}}[\Pr[V^{\prime}=T~{}|~{}W~{}\text{and}~{}\mathcal{E}_{i}(W)]]$
$\displaystyle=\sum\limits_{i=0}^{j}\sum\limits_{W\in
X(k+j)}q^{i^{2}}\frac{{j\choose i}_{q}{k\choose k-i}_{q}}{{k+j\choose
k}_{q}}\underset{W\supset V}{\mathbb{E}}[\Pr[T^{\prime}_{i}=T~{}|~{}W~{}]]$
$\displaystyle=\sum\limits_{i=0}^{j}\sum\limits_{W\in
X(k+j)}q^{i^{2}}\frac{{j\choose i}_{q}{k\choose k-i}_{q}}{{k+j\choose
k}_{q}}\Pr[T_{i}^{\prime}=T]$
$\displaystyle=\sum\limits_{i=0}^{j}\sum\limits_{W\in
X(k+j)}q^{i^{2}}\frac{{j\choose i}_{q}{k\choose k-i}_{q}}{{k+j\choose
k}_{q}}S_{k}^{i}(V,T)$

∎

This results in the $q$-analog of the analogous result on simplicial complexes
[14, Lemma 4.11]. To recover the analogous statement writing partial-swap
walks in terms of canonical walks, we can now apply a $q$-Binomial inversion
theorem.

######  Lemma 7.4 ($q$-Binomial Inversion (Theorem 2.1 [45])).

Suppose $\\{a_{i}\\}_{i\geq 1}$, $\\{b_{i}\\}_{i\geq 1}$ are two sequences.
If:

$a_{j}=\sum\limits_{i=1}^{j}(-1)^{i}{j\choose i}_{q}b_{i},$

then

$b_{j}=\sum\limits_{i=1}^{j}(-1)^{i}q^{{j-i\choose 2}}{j\choose i}_{q}a_{i}$

We note that [45, Theorem 2.1] is stated in slightly more generality in the
original work, but the above lemma is an immediate application. With this in
hand, we can finally prove that swap walks on the Grassmann poset are indeed
HD-walks:

######  Proposition 7.5.

Let $(X,\Pi)$ be a weighted pure $q$-simplicial complex. Then for $k+j\leq d$:

$S_{k}^{j}=\frac{1}{q^{j^{2}}{k\choose
k-j}_{q}}\sum\limits_{i=0}^{j}(-1)^{j-i}q^{{j-i\choose 2}}{j\choose
i}_{q}{k+i\choose i}_{q}N_{k}^{i},$

and similarly,

$J_{q}(n,k,t)=S_{k}^{k-t}=\frac{1}{q^{(k-t)^{2}}{k\choose
t}_{q}}\sum\limits_{i=0}^{k-t}(-1)^{k-t-i}q^{{k-t-i\choose 2}}{k-t\choose
i}_{q}{k+i\choose i}_{q}N_{k}^{i}$

###### Proof.

The proof is an easy application of Lemma 7.4 and the $q$-Binomial theorem. In
particular, for any $V,V^{\prime}\in X(k)$, let

$a_{i}=(-1)^{i}q^{i^{2}}{k\choose k-i}_{q}S_{k}^{i}(V,V^{\prime}).$

Noting that $N_{0}^{j}=S_{0}^{j}=I$, Lemma 7.3 gives the following equality:

${k+j\choose k}_{q}\left(N_{k}^{j}(V,V^{\prime})-\frac{1}{{k+j\choose
k}_{q}}I(V,V^{\prime})\right)=\sum\limits_{i=1}^{j}(-1)^{i}{j\choose
i}_{q}a_{i}.$

Setting the second sequence $\\{b_{i}\\}_{i\geq 1}$ to

$b_{i}={k+i\choose k}_{q}\left(N_{k}^{i}(V,V^{\prime})-\frac{1}{{k+i\choose
k}_{q}}I(V,V^{\prime})\right),$

Lemma 7.4 then implies:

$\displaystyle q^{j^{2}}{k\choose k-j}_{q}S_{k}^{j}(V,V^{\prime})$
$\displaystyle=\sum\limits_{i=1}^{j}(-1)^{j-i}q^{{j-i\choose 2}}{k+i\choose
k}\left(N_{k}^{i}(V,V^{\prime})-\frac{1}{{k+i\choose
k}_{q}}I(V,V^{\prime})\right)$
$\displaystyle=\sum\limits_{i=1}^{j}(-1)^{j-i}q^{{j-i\choose 2}}{k+i\choose
k}N_{k}^{i}(V,V^{\prime})-\sum\limits_{i=1}^{j}(-1)^{j-i}q^{{j-i\choose
2}}I(V,V^{\prime})$
$\displaystyle=\sum\limits_{i=0}^{j}(-1)^{j-i}q^{{j-i\choose 2}}{k+i\choose
k}N_{k}^{i}(V,V^{\prime})$

where the last step follows from the $q$-Binomial theorem. ∎

Once again, we note that this is unsurprisingly the $q$-analog of the
analogous statement on simplicial complexes (see [14, Corollary 4.13]).
Finally, we’ll use this to show that the eigenvalues of partial-swap walks on
$q$-simplicial complexes are given by the natural $q$-analog of the simplicial
complex case.

######  Corollary 7.6.

Let $(X,\Pi)$ be a $d$-dimensional $\gamma$-$q$-eposet with $\gamma$
sufficiently small, $k+j\leq d$, and $f_{\ell}=U^{k}_{\ell}g_{\ell}$ for some
$g_{\ell}\in H^{\ell}$. Then:

$\left\lVert
S_{k}^{j}f_{\ell}-\frac{{k-j\choose\ell}_{q}}{{k\choose\ell}_{q}}f_{\ell}\right\rVert\leq
O\left(\left(\frac{q}{q-1}\right)^{\min(j,k-j)+2}k^{2}{k\choose\ell}_{q}\right)\gamma\left\lVert
f_{\ell}\right\rVert$

###### Proof.

This follows from combining Corollary 4.5, Corollary 7.1, and Proposition 7.5.
Let $t=k-j$. In particular, it is sufficient to note that (in the notation of
Corollary 4.5):

$\displaystyle\sum\limits_{Y\in\mathcal{Y}}\alpha_{Y}\lambda_{Y,\delta,\ell}$
$\displaystyle=\frac{1}{q^{(k-t)^{2}}{k\choose
t}_{q}}\sum\limits_{i=0}^{k-t}(-1)^{k-t-i}q^{{k-t-i\choose 2}}{k-t\choose
i}_{q}{k+i-\ell\choose i}_{q}$
$\displaystyle=\frac{{k-j\choose\ell}_{q}}{{k\choose\ell}_{q}}.$

and further that:

$\displaystyle w(S^{j}_{k})$ $\displaystyle=\frac{1}{q^{j^{2}}{k\choose
k-j}_{q}}\sum\limits_{i=0}^{j}q^{{j-i\choose 2}}{j\choose i}_{q}{k+i\choose
i}_{q}$ $\displaystyle\leq\frac{q^{jk}}{q^{j^{2}}{k\choose
k-j}_{q}}\sum\limits_{i=0}^{j}q^{-i}$
$\displaystyle\leq\left(\frac{q}{q-1}\right)^{\min(j,k-j)+1}$

∎

Again, since the swap walks are self-adjoint Theorem 3.2 implies that for
small enough $\gamma$ the true spectra is closely concentrated around these
values as well. It is worth noting that if the above analysis is repeated
using the exact eposet parameters for the Grassmann (see Equation 2), this
recovers the standard eigenvalues of the Grassmann graphs (see e.g. [43]).

###  7.2 Pseudorandom Functions and Small Set Expansion

With an understanding of the spectra of HD-walks on $q$-simplicial complexes,
we move to studying its combinatorial structure. By direct computation, it is
not hard to show that on $q$-eposets,
$\rho^{k}_{\ell}=\frac{1}{{k\choose\ell}_{q}}$ (4.4 would only imply this is
approximately true). As a result, we get a level-$i$ inequality for
$q$-simplicial complexes that is the natural $q$-analog of BHKL’s inequality
for basic simplicial complexes.

######  Theorem 7.7.

Let $(X,\Pi)$ be a $\gamma$-$q$-eposet with $\gamma\leq q^{-\Omega(k^{2})}$,
and let $f:C_{k}\to\mathbb{R}$ be any function on $k$-faces with HD-Level-Set
Decomposition $f=f_{0}+\ldots+f_{k}$. If $f$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{\infty}$-pseudorandom,
then for all $1\leq i\leq\ell$:

$|\langle f,f_{i}\rangle|\leq\left({k\choose
i}_{q}+c\gamma\right)\varepsilon_{i}^{2}+c\gamma\left\lVert
f\right\rVert^{2}.$

If $f$ additionally has $i$-local constant sign or is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-$\ell_{2}$-pseudorandom, then

$|\langle f,f_{i}\rangle|\leq{k\choose
i}_{q}\varepsilon_{i}|\mathbb{E}[f]|+c\gamma\left\lVert f\right\rVert^{2}$

where in both cases $c\leq q^{O(k^{2})}$

For large enough $q,\gamma^{-1}$, this result is exactly tight. The key to
showing this fact is to examine a local structure unique to the Grassmann
called co-links. The co-link of an element $W\in X(k^{\prime})$, is all of the
subspaces contained in $W$:

$\bar{X}_{W}=\\{V\in X(k):V\subseteq W\\}.$

Just like links, co-links of dimension $i$ (that is $k^{\prime}=d-i$) also
come through levels $0$ through $i$ of the complex, although this is somewhat
trickier to see.

######  Lemma 7.8 (HD-level-set decomposition of co-links).

Let $X=G_{q}(d,k)$ and ${\cal S}=\overline{X}_{W}$ be a co-link of dimension
$i$ for $W\in X(d-i)$. Then, we have

$\displaystyle\mathbbm{1}_{\cal S}\in V_{k}^{0}\oplus\cdots\oplus V_{k}^{i}.$

###### Proof.

Since we know that $V_{k}^{0}\oplus\cdots\oplus
V_{k}^{i}=\mathrm{Im}(U_{i}^{k}C_{i})$ (see e.g. [3]), all we need to do is to
show that there exists an $f\in C_{i}$ such that $\mathbbm{1}_{\cal
S}=U_{i}^{k}f$. More specifically, we can write $f=\sum_{U\in
X(i)}\alpha_{U}\mathbbm{1}_{U}$. Then, we have

$\displaystyle(U_{i}^{k}f)(V)=~{}\sum_{U\in
X(i)}\alpha_{U}(U_{i}^{k}\mathbbm{1}_{U})(V)=~{}\frac{1}{R(k,i)}\sum_{U\in
X(i),U\subset V}\alpha_{U}.$

Suppose $\alpha_{U}=g(\dim(U\cap W))$ for some function
$g:\\{0,\dots,i\\}\rightarrow\mathbb{R}$. We will prove that there exists a
unique $g$ that satisfies the desired equations.

Consider the dimension of $V\cap W$. If $V\subset W$, i.e., $\dim(V\cap W)=k$,
then for all $U\in X(i)$ s.t. $U\subset V$, $\dim(U\cap W)=i$. Then, for all
$V\subset W$ we must have:

$\displaystyle U_{i}^{k}\mathbbm{1}_{V}=\frac{1}{R(k,i)}\sum_{U\in
X(i),U\subset V}g(i)=g(i)=1.$

On the other hand, consider $V\not\subset W$. In this case we must have
$\dim(V\cap W)=k-j$ for some $i\geq j>0$ and further that $\dim(U\cap
W)\in\\{i-j,\dots,i\\}$ for all $U\in X(i)$ s.t. $U\subset V$. This gives the
following set of linear equations:

$\displaystyle
U_{i}^{k}\mathbbm{1}_{V}=\sum_{\ell=i-j}^{i-1}c_{j,\ell}g(\ell)+c_{j,i}=0~{}~{}~{}\forall
1\leq j\leq i,$

where $c_{j,\ell}:=R(k,i)^{-1}\cdot|\\{U\in X(i):U\subset V,\dim(U\cap
W)=\ell,\dim(V\cap W)=k-j\\}|$ is a constant for all
$\ell\in\\{i-j,\dots,i\\}$. Since this system can be written as a triangular
form with positive diagonal, it is invertible and there exists a unique
solution for $g(0),\dots,g(i-1)$ as desired. By definition, such a solution
must satisfy $f=\sum_{U\in X(i)}g(\dim(U\cap W))\mathbbm{1}_{U}$, so we have
constructed $f\in C_{i}$ such that $U_{i}^{k}f=\mathbbm{1}_{\cal S}$, which
completes the proof of the claim. ∎

Using this fact, we can show that our level-$i$ inequality is exactly tight.

######  Proposition 7.9.

Let $X=G_{q}(d,k)$ be the Grassmann poset. For any $i\leq k\in\mathbb{N}$ and
$c<1$, there exist large enough $q,d$ and a set $S\subset X(k)$ such that

$\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle>c{k\choose
i}_{q}\varepsilon_{i}\langle\mathbbm{1}_{S},\mathbbm{1}_{S}\rangle$

where $S$ is $(i,\varepsilon_{i})$-pseudorandom.

###### Proof.

The proof goes through examining a “co-link” of dimension $i$, that is for
$W\in X(d-i)$:

$\bar{X}_{W}=\\{V\in X(k):V\subset W\\}.$

For simplicity, let $S\coloneqq\bar{X}_{W}$. The density of the co-link $S$ in
any $j$-link $X_{V}$ is:

$\alpha_{j}=\frac{(q^{d-i-j}-1)\ldots(q^{d-k+1-i}-1)}{(q^{d-j}-1)\ldots(q^{d-k+1}-1)}=q^{-i(k-j)}+o_{q,d}(1).$

The idea is now to examine the (non)-expansion of the co-link with respect to
the lower walk $U_{k-1}D_{k}$. By direct computation, the probability of
returning to $\bar{X}_{W}$ after moving to a $(k-1)$-dimensional subspace is
exactly:

$\bar{\Phi}(\bar{X}_{W})=\frac{q^{d-i}-q^{k-1}}{q^{d}-q^{k-1}}=q^{-i}\pm
q^{-\Omega(d)}$ (3)

On the other hand, by Proposition 4.2 the approximate eigenvalues of the lower
walk are given by

$\lambda_{j}=\frac{q^{k-j}-1}{q^{k}-1}=q^{-j}-O(q^{-k})$

Since a dimension-$i$ co-link has no projection onto levels $i+1$ through $k$,
we can also write the non-expansion as:

$\displaystyle\bar{\Phi}(\bar{X}_{W})=\frac{1}{\langle\mathbbm{1}_{S},\mathbbm{1}_{S}\rangle}\sum\limits_{j=0}^{i}q^{-j}\langle\mathbbm{1}_{S},\mathbbm{1}_{S,j}\rangle-O(q^{-k})$

for large enough $q,d$. Combining this with our previous formula for the non-
expansion in Equation 3, we get that there exists a universal constant
$c^{\prime}$ such that for large enough $q$ and $d$,
$\mathbbm{1}_{\bar{X}_{W}}$ cannot have more than a $\frac{c^{\prime}}{q}$
fraction of its mass on levels $1$ through $i-1$. Finally, noticing that:

${k\choose i}_{q}\alpha_{i}=1+o_{q}(1)$

we have

$\displaystyle\frac{\langle\mathbbm{1}_{S},\mathbbm{1}_{S,i}\rangle}{\langle\mathbbm{1}_{S},\mathbbm{1}_{S}\rangle}\geq\frac{q-c^{\prime}}{q}\geq
c{k\choose i}_{q}\alpha_{i}$

since the latter is strictly bounded away from $1$ for large enough $q$. This
completes the result since $\bar{X}_{W}$ is $(\alpha_{i},i)$-pseudorandom. ∎

We’ll close the section by giving an immediate application of Theorem 7.7 to
the expansion of pseudorandom sets, and briefly discuss connections with the
proof of the 2-2 Games Conjecture and algorithms for unique games. Namely, as
corollary of Theorem 7.7, we show that for both the canonical and partial-swap
walks, sufficiently pseudorandom functions expand near perfectly.

######  Corollary 7.10 ($q$-eposets Edge-Expansion).

Let $(X,\Pi)$ be a $d$-dimensional $\gamma$-$q$-eposet, $S\subset X(k)$ a
subset whose indicator function $\mathbbm{1}_{S}$ is
$(\varepsilon_{1},\ldots,\varepsilon_{\ell})$-pseudorandom. Then the edge
expansion of $S$ with respect to the canonical walk $N_{k}^{j}$ is bounded by:

$\Phi_{\pi_{k}}(N^{j}_{k},S)\geq
1-\mathbb{E}[\mathbbm{1}_{S}]-\sum\limits_{i=1}^{\ell}\frac{{k+j-i\choose
j}_{q}}{{k+j\choose j}_{q}}{k\choose
i}_{q}\varepsilon_{i}-q^{-(\ell+1)j}-q^{O(k^{2})}\gamma$

Further, the edge expansion of $S$ with respect to the partial-swap walk
$S_{k}^{j}$ is bounded by:

$\Phi_{\pi_{k}}(S^{j}_{k},S)\geq
1-\mathbb{E}[\mathbbm{1}_{S}]-\sum\limits_{i=1}^{\ell}{k-j\choose
i}_{q}\varepsilon_{i}-q^{-(\ell+1)j}-q^{O(k^{2})}\gamma$

Note that $S^{j}_{k}$ on $q$-eposets is a generalization of the Grassmann
Graphs (and are equivalent when $X$ is the Grassmann Poset). While our
definition of pseudorandomness is weaker than that of [25] and therefore
necessarily depends on the dimension $k$, we take the above as evidence that
the framework of expanding posets may be important for making further progress
on the Unique Games Conjecture. In particular, combined with recent works
removing this $k$-dependence on simplicial complexes [35, 36], it seems
plausible that the framework of expanding posets may lead to a more general
understanding of the structure underlying the unique games conjecture.

## References

  * Kaufman and Mass [2016] Tali Kaufman and David Mass.  High dimensional combinatorial random walks and colorful expansion.  _arXiv preprint arXiv:1604.02947_ , 2016.
  * Kaufman and Oppenheim [2020] Tali Kaufman and Izhar Oppenheim.  High order random walks: Beyond spectral gap.  _Combinatorica_ , pages 1–37, 2020.
  * Dikstein et al. [2018] Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha.  Boolean function analysis on high-dimensional expanders.  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * Alev and Lau [2020] Vedat Levi Alev and Lap Chi Lau.  Improved analysis of higher order random walks and applications.  _arXiv preprint arXiv:2001.02827_ , 2020.
  * Anari et al. [2019] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1–12, 2019.
  * Anari et al. [2020] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  _arXiv preprint arXiv:2001.00303_ , 2020.
  * Chen et al. [2020] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Rapid mixing of glauber dynamics up to uniqueness via contraction.  _arXiv preprint arXiv:2004.09083_ , 2020.
  * Chen et al. [2021a] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1537–1550, 2021a.
  * Chen et al. [2021b] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Rapid mixing for colorings via spectral independence.  In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 1548–1557. SIAM, 2021b.
  * Feng et al. [2021] Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang.  Rapid mixing from spectral independence beyond the boolean domain.  In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 1558–1577. SIAM, 2021.
  * Jain et al. [2021] Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong.  Spectral independence, coupling with the stationary distribution, and the spectral gap of the glauber dynamics.  _arXiv preprint arXiv:2105.01201_ , 2021.
  * Liu [2021] Kuikui Liu.  From coupling to spectral independence and blackbox comparison with the down-up walk.  _arXiv preprint arXiv:2103.11609_ , 2021.
  * Blanca et al. [2021] Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda.  On mixing of markov chains: Coupling, spectral independence, and entropy factorization.  _arXiv preprint arXiv:2103.07459_ , 2021.
  * Alev et al. [2019] Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani.  Approximating constraint satisfaction problems on high-dimensional expanders.  In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 180–201. IEEE, 2019.
  * Bafna et al. [2020a] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett.  High dimensional expanders: Eigenstripping, pseudorandomness, and unique games.  _arXiv e-prints_ , pages arXiv–2011, 2020a.
  * Jeronimo et al. [2020] Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani.  Unique decoding of explicit epsilon-balanced codes near the gilbert-varshamov bound.  _arXiv preprint arXiv:2011.05500_ , 2020.
  * Jeronimo et al. [2021] Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani.  Near-linear time decoding of ta-shma’s codes via splittable regularity.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1527–1536, 2021.
  * Dinur and Kaufman [2017] Irit Dinur and Tali Kaufman.  High dimensional expanders imply agreement expanders.  In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 974–985. IEEE, 2017.
  * Dikstein and Dinur [2019] Yotam Dikstein and Irit Dinur.  Agreement testing theorems on layered set systems.  In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 1495–1524. IEEE, 2019.
  * Kaufman and Mass [2020] Tali Kaufman and David Mass.  Local-to-global agreement expansion via the variance method.  In _11th Innovations in Theoretical Computer Science Conference (ITCS 2020)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * Dinur et al. [2021a] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes.  Locally testable codes with constant rate, distance, and locality.  _arXiv preprint arXiv:2111.04808_ , 2021a.
  * Panteleev and Kalachev [2021] Pavel Panteleev and Gleb Kalachev.  Asymptotically good quantum and locally testable classical ldpc codes.  _arXiv preprint arXiv:2111.03654_ , 2021.
  * Lin and Hsieh [2022] Ting-Chun Lin and Min-Hsiu Hsieh.  c3-local testable codes from lossless expanders.  _arXiv preprint arXiv:2201.11369_ , 2022.
  * Leverrier and Zémor [2022] Anthony Leverrier and Gilles Zémor.  Quantum tanner codes.  _arXiv preprint arXiv:2202.13641_ , 2022.
  * Subhash et al. [2018] Khot Subhash, Dor Minzer, and Muli Safra.  Pseudorandom sets in grassmann graph have near-perfect expansion.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 592–601. IEEE, 2018.
  * Khot et al. [2017] Subhash Khot, Dor Minzer, and Muli Safra.  On independent sets, 2-to-2 games, and grassmann graphs.  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 576–589, 2017.
  * Dinur et al. [2018a] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  Towards a proof of the 2-to-1 games conjecture?  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 376–389, 2018a.
  * Dinur et al. [2018b] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  On non-optimally expanding sets in grassmann graphs.  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , pages 940–951, 2018b.
  * Barak et al. [2018] Boaz Barak, Pravesh K Kothari, and David Steurer.  Small-set expansion in shortcode graph and the 2-to-2 conjecture.  _arXiv preprint arXiv:1804.08662_ , 2018.
  * Khot et al. [2018] Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra.  Small set expansion in the johnson graph.  In _Electronic Colloquium on Computational Complexity (ECCC)_ , volume 25, page 78, 2018.
  * Stanley [1988] Richard P Stanley.  Differential posets.  _Journal of the American Mathematical Society_ , 1(4):919–961, 1988.
  * Kaufman and Tessler [2021] Tali Kaufman and Ran J Tessler.  Local to global high dimensional expansion and garland’s method for general posets.  _arXiv preprint arXiv:2101.12621_ , 2021.
  * Bafna et al. [2020b] Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, and David Steurer.  Playing unique games on certified small-set expanders.  _arXiv preprint arXiv:2006.09969_ , 2020b.
  * Arora et al. [2008] Sanjeev Arora, Subhash A Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K Vishnoi.  Unique games on expanding constraint graphs are easy.  In _Proceedings of the fortieth annual ACM symposium on Theory of computing_ , pages 21–28, 2008.
  * Bafna et al. [2021] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett.  Hypercontractivity on high dimensional expanders: a local-to-global approach for higher moments.  _arXiv preprint arXiv:2111.09444_ , 2021.
  * Gur et al. [2021] Tom Gur, Noam Lifshitz, and Siqi Liu.  Hypercontractivity on high dimensional expanders: Approximate efron-stein decompositions for epsilon-product spaces.  _arXiv preprint arXiv:2111.09375_ , 2021.
  * Dinur et al. [2021b] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes.  Locally testable codes with constant rate, distance, and locality.  _arXiv preprint arXiv:2111.04808_ , 2021b.
  * Hopkins and Lin [2022] Max Hopkins and Ting-Chun Lin.  Explicit lower bounds against $\omega(n)$-rounds of sum-of-squares.  2022\.
  * Khot [2002] Subhash Khot.  On the power of unique 2-prover 1-round games.  In _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_ , pages 767–775, 2002.
  * Khot and Vishnoi [2005] Subhash Khot and Nisheeth K Vishnoi.  On the unique games conjecture.  In _FOCS_ , volume 5, page 3. Citeseer, 2005.
  * Fischer [1905] Ernst Fischer.  Über quadratische formen mit reellen koeffizienten.  _Monatshefte für Mathematik und Physik_ , 16(1):234–249, 1905.
  * Horn et al. [1998] Roger A Horn, Noah H Rhee, and So Wasin.  Eigenvalue inequalities and equalities.  _Linear Algebra and its Applications_ , 270(1-3):29–44, 1998.
  * Delsarte [1976] Philippe Delsarte.  Association schemes and t-designs in regular semilattices.  _Journal of Combinatorial Theory, Series A_ , 20(2):230–243, 1976.
  * Brouwer and Haemers [2012] Andries E Brouwer and Willem H Haemers.  Distance-regular graphs.  In _Spectra of graphs_ , pages 177–185. Springer, 2012.
  * Zou [2017] Qing Zou.  The q-binomial inverse formula and a recurrence relation for the q-catalan–qi numbers.  _J. Math. Anal_ , 8(1):176–182, 2017.

##  Appendix A Eposet Parameters and Regularity

In this appendix we will discuss connections between notions of regularity,
the averaging operators, and eposet parameters. To start, we’ll show that
downward and middle regularity (which are defined only on adjacent levels of
the poset) imply extended regularity between any two levels.

######  Proposition A.1.

Let $(X,\Pi)$ be a $d$-dimensional regular measured poset. Then for any
$i<k\leq d$, there exist regularity constant $R(k,i)$ such that for any
$x_{k}\in X(k)$, there are exactly $R(k,i)$ elements $x_{i}\in X(i)$ such that
$x_{k}>x_{i}$.

###### Proof.

Given any element $x_{k}\in X(k)$, downward regularity promises there are
exactly $\prod_{j=i+1}^{k}R(j)$ unique chains
$x_{k}<x_{k-1}<\ldots<x_{i+1}<x_{i}$. By middle regularity, any fixed
$x_{i}\in X(i)$ which appears in this fashion appears in exactly $m(k,i)$
chains. Noting that $x_{i}<x_{k}$ if and only if $x_{i}$ appears in such a
chain, the total number of $x_{i}<x_{k}$ must be exactly:

$R(k,i)=\frac{\prod_{j=i+1}^{k}R(j)}{m(k,i)}.$

∎

A similar argument shows that regularity allows the up operators to compose in
the natural way.

######  Proposition A.2.

Let $(X,\Pi)$ be a $d$-dimensional regular measured poset. Then for any
$i<k\leq d$ we have:

$U^{k}_{i}f(x_{k})=\frac{1}{R(k,i)}\sum\limits_{x_{i}<x_{k}}f(x_{i})$

###### Proof.

Expanding out $U^{k}_{i}f(y)$ gives:

$\displaystyle
U^{k}_{i}f(x_{k})=\frac{1}{\prod\limits_{j=i+1}^{k}R(j)}\sum\limits_{x_{k-1}<x_{k}}\ldots\sum\limits_{x_{i}<x_{i+1}}f(x_{i})$

The number of times each $x_{i}$ appears in this sum is exactly the number of
chains starting at $x_{k}$ and ending at $x_{i}$, so by middle regularity:

$\displaystyle\frac{1}{\prod\limits_{j=i+1}^{k}R(j)}\sum\limits_{x_{k-1}<x_{k}}\ldots\sum\limits_{x_{i+1}<x_{i}}f(x_{i})$
$\displaystyle=\frac{m(k,i)}{\prod\limits_{j=i+1}^{k}R(j)}\sum\limits_{x_{i}<x_{k}}f(x_{i})$
$\displaystyle=\frac{1}{R(k,i)}\sum\limits_{x_{i}<x_{k}}f(x_{i}).$

as desired. ∎

We’ll now take a look at the connection between eposet parameters and
regularity. It is convenient to first start with a lemma stating that non-
laziness is equivalent to bounding the maximum transition probability of the
lower walk.

######  Lemma A.3.

Let $(X,\Pi)$ be a $d$-dimensional measured poset. Then for any $0<i\leq d$,
the maximum laziness of the lower walk is also the maximum transition
probability:

$\max_{\sigma\in
X(i)}\left\\{\mathbbm{1}_{\sigma}^{T}U_{i-1}D_{i}\mathbbm{1}_{\sigma}\right\\}=\max_{\sigma,\tau\in
X(i)}\left\\{\mathbbm{1}_{\sigma}^{T}U_{i-1}D_{i}\mathbbm{1}_{\tau}\right\\}.$

###### Proof.

Assume that $\tau\neq\sigma$. Then the transition probability from $\tau$ to
$\sigma$ is exactly

$\displaystyle\mathbbm{1}_{\sigma}^{T}U_{i-1}D_{i}\mathbbm{1}_{\tau}$
$\displaystyle=\frac{\pi_{\tau}(\sigma\setminus\tau)}{R(i,i-1)}$
$\displaystyle\leq\frac{1}{R(i,i-1)}\sum\limits_{\tau\lessdot\sigma}\pi_{\tau}(\sigma\setminus\tau)$
$\displaystyle=\mathbbm{1}_{\sigma}^{\tau}U_{i-1}D_{i}\mathbbm{1}_{\sigma},$

which implies the result. ∎

We now prove our two claims relating the eposet parameters to regularity.

######  Claim A.4.

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet. Then for every
$1\leq k\leq d$ and $0\leq i\leq k$, the following approximate relation
between the eposet and regularity parameters holds:

$\lambda_{i}(N_{k}^{1})\in\frac{R(k,i)}{R(k+1,i)}\pm\left(\gamma^{k}_{k-i}+R(k,i)\delta^{k}_{k-i}\gamma\right)$

where we recall $\lambda_{i}(N_{k}^{1})=1-\prod\limits^{k}_{j=i}\delta_{j}$.

###### Proof.

One of our main analytical tools so far has been the relation between the
upper and lower walks given in Lemma 4.1:

$\left\lVert
D_{k+1}U^{k+1}_{i}-(1-\delta^{k}_{k-i})U^{k}_{i}-\delta_{k-i}^{k}U^{k}_{i-1}D_{i}\right\rVert\leq\gamma^{k}_{k-i}.$

For this result, we’ll actually need a refinement of this result given in [15,
Lemma A.1]:151515Formally the result is only stated for simplicial complexes
in [15], but the same proof holds for eposets.

$D_{k+1}U^{k+1}_{i}=(1-\delta^{k}_{k-i})U^{k}_{i}+\delta_{k-i}^{k}U^{k}_{i-1}D_{i}+\sum\limits_{j=-1}^{k-i-1}U^{k}_{k-j-1}\Gamma_{j}U^{k-j-1}_{i}$
(4)

where $\sum\left\lVert\Gamma_{j}\right\rVert\leq\gamma^{k}_{k-i}$. The idea is
now to examine the “laziness” of the two sides of this equality. In other
words, given a starting $k$-face $\tau$, what is the probability that the
resulting $i$-face $\sigma$ satisfies $\sigma<\tau$?

To start, we’ll argue that the laziness of the lefthand side is exactly
$\frac{R(k,i)}{R(k+1,i)}$. This follows from noting that there are $R(k,i)$
$i$-faces $\sigma$ satisfying $\sigma<\tau$, and $R(k+1,i)$ options after
taking the initial up-step of the walk to $\tau^{\prime}>\tau$. After the
down-steps, the resulting $i$-face is uniformly distributed over these
$R(k+1,i)$ options $\sigma<\tau^{\prime}$, and since every
$\sigma<\tau<\tau^{\prime}$, all original $R(k,i)$ lazy options are still
viable after the up-step to $\tau^{\prime}$.

Analyzing the right-hand side is a bit trickier. The initial term
$(1-\delta^{k}_{k-i})U^{k}_{i}$ is completely lazy, so it contributes exactly
$(1-\delta^{k}_{k-i})=\lambda_{i}(N_{k}^{1})$. We’ll break the second term
into two steps: walking from $X(k)$ to $X(i)$ via $U^{k}_{i}$, then from
$X(i)$ to $X(i)$ via the lower walk $U_{i-1}D_{i}$. Starting at a $k$-face
$\tau$, notice that after applying the down step $U^{k}_{i}$ we are uniformly
spread over $\sigma<\tau$. Computing the laziness then amounts to asking what
the probability of staying in this set is after the application of $UD$, which
one can naively bound by the maximum transition probability times the set size
$R(k,i)$. By non-laziness, the maximum transition probability is at most
$\gamma$ (see Lemma A.3).

The third term can be handled similarly. The first down step $U^{k}_{k-j-1}$
spreads $\tau$ evenly across $\sigma<\tau$ in $X(k-j-1)$. The resulting
$i$-face $\sigma^{\prime}$ after applying $\Gamma_{j}U^{k-j-1}_{i}$ is less
than $\tau$ if and only if the intermediary $(k-j-1)$-face after applying
$\Gamma_{j}$ is less than $\tau$, which is bounded by the spectral norm
$\left\lVert\Gamma_{j}\right\rVert$.161616We note that $\Gamma_{j}$ is not
stochastic, but it is self-adjoint and an easy exercise to see that the
analogous reasoning still holds.

Putting everything together, since both sides of Equation 4 must have
equivalent laziness, we get that $\lambda_{i}(N_{k}^{1})$ must be within
$\sum\left\lVert\Gamma_{j}\right\rVert+\delta^{k}_{k-i}R(k,i)\gamma$ as
desired. ∎

4.4 and Theorem 4.7 can both be proving an analogous theorem for the upper
walk.

######  Claim A.5 (Regularity and Upper Walk Spectrum).

Let $(X,\Pi)$ be a $d$-dimensional $(\delta,\gamma)$-eposet. Then for any
$j\leq i\leq k<d$, we have:

$\lambda_{j}(N^{k-i}_{i})\in\frac{R(i,j)}{R(k,i)}\pm err,$

where $err\leq
O\left(\frac{i^{4}k^{2}R_{\text{max}}}{\delta_{i}(1-\delta_{i-1})}\gamma\right)$.

###### Proof.

This follows almost immediately from the fact that $i$-links lie almost
entirely on the $i$th eigenstrip (Lemma 6.5). In particular, it is enough to
examine the expansion of $i$-links with respect to the upper canonical walk
$N_{i}^{k-i}$. On the one hand, for any $j\leq i$ and $\tau\in X(j)$ we have:

$\displaystyle\bar{\Phi}(X^{i}_{\tau})$
$\displaystyle=\frac{\langle\mathbbm{1}_{X^{i}_{\tau}},N^{k-i}_{i}\mathbbm{1}_{X^{i}_{\tau}}\rangle}{\langle\mathbbm{1}_{X^{i}_{\tau}},\mathbbm{1}_{X^{i}_{\tau}}\rangle}$
$\displaystyle=\frac{\langle
U^{k}_{j}\mathbbm{1}_{\tau},U^{k}_{j}\mathbbm{1}_{\tau}\rangle}{\langle
U^{i}_{j}\mathbbm{1}_{\tau},U_{j}^{i}\mathbbm{1}_{\tau}\rangle}$
$\displaystyle=\frac{R(i,j)^{2}}{R(k,i)^{2}}\frac{\langle\mathbbm{1}_{X^{k}_{\tau}},\mathbbm{1}_{X^{k}_{\tau}}\rangle}{\langle\mathbbm{1}_{X^{i}_{\tau}},\mathbbm{1}_{X^{i}_{\tau}}\rangle}$
$\displaystyle=\frac{R(i,j)}{R(k,i)}\frac{\langle\mathbbm{1}_{\tau},\mathbbm{1}_{\tau}\rangle}{\langle\mathbbm{1}_{\tau},\mathbbm{1}_{\tau}\rangle}$
$\displaystyle=\frac{R(i,j)}{R(k,i)}.$

where we have applied the fact that $\langle
X^{\ell}_{\tau},X^{\ell}_{\tau}\rangle=R(\ell,j)\langle\mathbbm{1}_{\tau},\mathbbm{1}_{\tau}\rangle$.
On the other hand, by Lemma 6.5 we also have that:

$\displaystyle\bar{\Phi}(\mathbbm{1}_{X^{i}_{\tau}})$
$\displaystyle=\frac{1}{\langle\mathbbm{1}_{X^{i}_{\tau}},\mathbbm{1}_{X^{i}_{\tau}}\rangle}\sum\limits_{\ell=0}^{i}\langle\mathbbm{1}_{X^{i}_{\tau}},N^{k-i}_{i}\mathbbm{1}_{X^{i}_{\tau},\ell}\rangle$