Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

Jason Gaitonde Department of Computer Science, Cornell University. Email: [email protected]. 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 protected]. Supported by NSF Award DGE-1650112. Tali Kaufman Department of Computer Science, Bar-Ilan University. Email: [email protected]. Supported by ERC and BSF. Shachar Lovett Department of Computer Science and Engineering, UCSD, CA 92092. Email: [email protected]. Supported by NSF Award CCF-1909634. Ruizhe Zhang Department of Computer Science, UT Austin. Email: [email protected].

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 regularity¹¹1We 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$ elements²²2We 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.³³3For 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.⁴⁴4While 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$ .⁵⁵5This 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.⁶⁶6For 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.⁷⁷7It 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$ :⁸⁸8We 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 if⁹⁹9Throughout, $\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.¹⁰¹⁰10Note 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.

$r$ preserves “ $<$ ”: if $y<x$ , then $r(y)<r(x)$ .
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.

They have a unique minimal element, i.e. $|X(0)|=1$ .
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)$ chains¹¹¹¹11Such 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 combinations¹²¹²12An 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,¹³¹³13The 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-lazy¹⁴¹⁴14One 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.

$\mathbb{E}[f]\neq 0$ ,
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.

\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]:¹⁵¹⁵15Formally 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$ .¹⁶¹⁶16We 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$
		$\displaystyle\in\frac{1}{\langle\mathbbm{1}_{\tau},\mathbbm{1}_{\tau}\rangle}\sum\limits_{\ell=0}^{i}\lambda_{j}(N^{k-i}_{i})\langle\mathbbm{1}_{X^{i}_{\tau}},\mathbbm{1}_{X^{i}_{\tau},\ell}\rangle+c\gamma$
		$\displaystyle\in\lambda_{j}(N^{k-i}_{i})\frac{\langle\mathbbm{1}_{\tau},\mathbbm{1}_{\tau,j}\rangle}{\langle\mathbbm{1}_{\tau},\mathbbm{1}_{\tau}\rangle}+\sum\limits_{j=0}^{i}err_{1}$
		$\displaystyle\in\lambda_{j}(N^{k-i}_{i})+err_{2}$

where as in the proof of Theorem 6.3, $c,err_{1},err_{2}\leq O\left(\frac{i^{4}k^{2}R_{\text{max}}}{\delta_{i-j}^{i}(1-\delta_{j-1})}\gamma\right)$ . ∎

4.4 follows immediately from observing that $\rho^{k}_{i}=\lambda_{i}(N^{k-i}_{i})$ (by Proposition 4.2). Theorem 4.7 follows from observing that $\widehat{N}_{i}^{k-i}$ and $\widecheck{N}_{k}^{k-i}$ have the same approximate eigenvalues (similarly by Proposition 4.2).

Finally we close out the section by discussing the connection between non-laziness and a variant of eposets called local-spectral expanders [32]. To start, let’s recall this latter definition.

Definition A.6 (Local-Spectral Expander [18, 32]).

A $d$ -dimensional measured poset $(X,\Pi)$ is a $\gamma$ -local-spectral expander if the graph underlying every link¹⁷¹⁷17Here the link of $\tau$ is not just its top level faces, but the complex given by taking this set, removing $\tau$ from each face, and downward closing. of dimension at most $d-2$ is a $\gamma$ -spectral expander.¹⁸¹⁸18A graph is a $\gamma$ -spectral expander if its weighted adjacency matrix has no non-trivial eigenvalues greater than $\gamma$ in absolute value.

Under suitable regularity conditions (see [32]), local-spectral expansion is equivalent to the notion of expanding posets used in this work. A simple argument shows that $\gamma$ -local-spectral expanders are $\gamma$ -non-lazy.

Lemma A.7.

Let $(X,\Pi)$ be a $d$ -dimensional $\gamma$ -local-spectral expander, and $0<i<d$ . The laziness of the lower walk on level $i$ is at most:

\max_{\sigma\in X(i)}\left\{\frac{\langle\mathbbm{1}_{\sigma},U_{i-1}D_{i}\mathbbm{1}_{\sigma}\rangle}{\langle\mathbbm{1}_{\sigma},\mathbbm{1}_{\sigma}\rangle}\right\}\leq\gamma.

Proof.

Through direct computation, the laziness probability of the lower walk at $\sigma\in X(i)$ is exactly

\frac{\langle\mathbbm{1}_{\sigma},U_{i-1}D_{i}\mathbbm{1}_{\sigma}\rangle}{\langle\mathbbm{1}_{\sigma},\mathbbm{1}_{\sigma}\rangle}=\frac{1}{R(i,i-1)}\sum\limits_{\tau\lessdot\sigma}\pi_{\tau}(\sigma\setminus\tau)

It is therefore enough to argue that $\pi_{\tau}(\sigma\setminus\tau)\leq\gamma$ . This follows from the fact that the graph underlying the link $X_{\tau}$ is a $\gamma$ -spectral expander. In particular, recall that an equivalent formulation of this definition states that:

\left\lVert A_{\tau}-UD_{\tau}\right\rVert\leq\gamma,

where $A_{\tau}$ is the standard (non-lazy upper) walk and $UD_{\tau}$ is the lower walk on the graph underlying $X_{\tau}$ . This implies that the weight of any vertex $v$ in the graph is at most $\gamma$ , as:

\frac{\langle\mathbbm{1}_{v},UD_{\tau}\mathbbm{1}_{v}\rangle}{\langle\mathbbm{1}_{v},\mathbbm{1}_{v}\rangle}=\frac{\langle\mathbbm{1}_{v},(UD_{\tau}-A_{\tau})\mathbbm{1}_{v}\rangle}{\langle\mathbbm{1}_{v},\mathbbm{1}_{v}\rangle}\leq\left\lVert A_{\tau}-UD_{\tau}\right\rVert\leq\gamma

where we have used the fact that $A_{\tau}$ is non-lazy by definition. Since $\pi_{\tau}(\sigma\setminus\tau)$ is exactly the weight of the vertex $\sigma\setminus\tau$ in $X_{\tau}$ , this completes the proof. ∎

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

Abstract

1 Introduction

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

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

1.1 Background

1.2 Results

1.2.1 Eigenstripping

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

Theorem 1.4 (Eigenstripping (informal Theorem 3.2)).

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

1.2.2 Characterizing Edge Expansion

Definition 1.6 (Edge Expansion).

Definition 1.7 (Link).

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

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

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

Theorem 1.11 (Level-ii inequality (informal Theorem 5.7)).

1.2.3 Application: qq-eposets and the Grassmann Graphs

Definition 1.12 (Grassmann Poset).

Corollary 1.13 (Grassmann level-ii inequality (informal Theorem 7.7)).

Definition 1.14 (Grassmann Graphs).

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

Corollary 1.16 (qq-eposets Edge-Expansion (informal Corollary 7.10)).

1.3 Related Work

Higher Order Random Walks.

High Dimensional Expansion Beyond Hypergraphs.

Expansion and Unique Games.

2 Preliminaries

2.1 Graded Posets

Definition 2.1 (Downward Regularity).

Definition 2.2 (Middle Regularity).

2.2 Measured Posets and The Random Walk Operators

2.3 Higher Order Random Walks

Definition 2.3 (kk-Dimensional Pure Walk [1, 3, 14]).

Definition 2.4 (HD-walk).

Definition 2.5 (Canonical Walk).

2.4 Expanding Posets and the HD-Level-Set Decomposition

Definition 2.6 (eposet [3]).

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

Definition 2.8 (β\beta-non-Lazy Eposets).

2.5 The Grassmann Poset and qq-eposets

Definition 2.9 (qq-simplicial complex).

Definition 2.10 (γ\gamma-qq-eposet [3]).

Definition 2.11 (Partial-Swap Walk).

3 Approximate Eigendecompositions and Eigenstripping

Definition 3.1 (Approximate Eigendecomposition [15]).

Theorem 3.2 (Eigenstripping).

Proof.

Claim 3.3.

Proof of 3.3.

4 Spectra of HD-walks

Lemma 4.1 ([3, Claim 8.8]).

Proposition 4.2.

Proof.

Lemma 4.3 ([3, Lemma 8.11]).

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

Corollary 4.5.

Corollary 4.6 (Spectrum of Lower Canonical Walks).

Proof.

Theorem 4.7.

5 Pseudorandomness and the HD-Level-Set Decomposition

Corollary 5.1.

Proof.

5.1 ℓ2\ell_{2}-pseudorandomness

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

Theorem 5.3.

Proof.

Corollary 5.4.

Proof.

5.2 ℓ∞\ell_{\infty}-pseudorandomness

Definition 5.5 (ℓ∞\ell_{\infty}-Pseudorandom functions).

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

Theorem 5.7.

Lemma 5.8.

Proof.

Proof of Theorem 5.7.

6 Expansion of HD-walks

Definition 6.1 (Weighted Edge Expansion).

Definition 6.2 (Monotonic HD-walk).

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

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

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

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

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

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

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

2.5 The Grassmann Poset and $q$ -eposets

Definition 2.9 ( $q$ -simplicial complex).

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

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

5.1 $\ell_{2}$ -pseudorandomness

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

5.2 $\ell_{\infty}$ -pseudorandomness

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

7 The Grassmann and $q$ -eposets

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

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

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

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

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