Abstract 1 Introduction 2 Preliminaries 3 Subpolynomial degree Cayley local spectral expanders 4 Johnson complexes and local spectral expansion 5 Coboundary expansion and a van Kampen lemma 6 Coboundary expansion 7 Induced Grassmann posets References Appendix A The decomposition lemma Appendix B Intermediate subspaces of the expanding matrix Grassmann poset Appendix C Elementary properties of matrix poset Appendix D Properties of the graphs induced by the matrix poset Appendix E Second largest eigenvalue of 𝑱(𝒏,𝒌,𝒌/𝟐) Appendix F Sparsifying the Johnson complexes Appendix G Proof of the van Kampen lemma Appendix H Expansion of containment walks in the Grassmann poset Appendix I A degree lower bound

Sparser Abelian High Dimensional Expanders

Yotam Dikstein ORCID Institute for Advanced Study, Princeton, NJ, USA Siqi Liu ORCID Institute for Advanced Study, Princeton, NJ, USA Avi Wigderson ORCID Institute for Advanced Study, Princeton, NJ, USA
Abstract

The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽2n. Our expansion proofs use only linear algebra and combinatorial arguments.

The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(nε) for every ε>0, improving on a construction by Golowich [50] which achieves ε=1/2. [50] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph.

Our second construction gives a 2-dimensional HDX of any polynomial degree exp(εn) for any constant ε>0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [74]. Establishing coboundary expansion through Gromov’s “cone method” and the associated isoperimetric inequalities is the most intricate aspect of this construction.

While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such “Hadamard-like” constructions in the hope that it will yield new HDXs.

Keywords and phrases:
Local spectral expander, coboundary expander, Grassmannian expander
Funding:
Yotam Dikstein: This material is based upon work supported by the National Science Foundation under Grant No. DMS-1926686.
Siqi Liu: Supported by Minerva Research Foundation Member Fund. This work was partially conducted at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) with support from DIMACS and Rutgers University.
Avi Wigderson: Supported by NSF grant CCF-1900460.
Copyright and License:
[Uncaptioned image] © Yotam Dikstein, Siqi Liu, and Avi Wigderson; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation
; Mathematics of computing Spectra of graphs
Related Version:
Full Version: https://arxiv.org/abs/2411.08839
Acknowledgements:
We thank Louis Golowich for helpful discussions and Gil Melnik for assistance with the figures.
Editors:
Srikanth Srinivasan

1 Introduction

Expander graphs are of central importance in many diverse parts of computer science and mathematics. Their structure and applications have been well studied for half a century, resulting in a rich theory (see e.g. [56, 76]). First, different definitions of expansion (spectral, combinatorial, probabilistic) are all known to be essentially equivalent. Second, we know that expanders abound; a random sparse graph is almost surely an expander [89]. Finally, there is a variety of methods for constructing and analyzing explicit expander graphs. Initially, these relied on deep algebraic and number theoretic methods [84, 45, 78]. However, the quest for elementary (e.g. combinatorial and linear-algebraic) constructions has been extremely fertile, and resulted in major breakthroughs in computer science and math; the zigzag method of [93] lead to [33, 92, 96], and the lifting method of [14] lead to [83, 82].

In contrast, the expansion of sparse high dimensional complexes (or simply hypergraphs) is still a young and growing research topic. The importance of high dimensional expanders (HDXs) in computer science and mathematics is consistently unfolding, with a number of recent breakthroughs which essentially depend on them, such as locally testable codes [34, 88], quantum coding [6] and Markov chains [5] as a partial list. High dimensional expanders differ from expander graphs in several important ways. First, different definitions of expansion are known to be non-equivalent [53]. Second, they seem rare, and no natural distributions of complexes are known which almost surely produce bounded-degree expanding complexes. Finally, so far the few existing explicit constructions of bounded degree HDXs use algebraic methods [12, 16, 72, 79, 68, 86, 25]. No elementary constructions are known where high dimensional expansion follows from a clear (combinatorial or linear algebraic) argument. This demands further understanding of HDXs and motivates much prior work as well as this one.

In this work we take a step towards answering this question by constructing sparser HDXs by elementary means. We construct sparse HDXs with two central notions of high dimensional expansion: local spectral expansion and coboundary expansion.

To better discuss our results, we define some notions of simplicial complexes and expansion. For simplicity, we only define them in the 2-dimensional case, though many of our results extend to arbitrary constant dimensions. For the full definitions see Section 2. A 2-dimensional simplicial complex is a hypergraph X=(V,E,T) with vertices V, edges E and triangles T (sets of size 3). We require that if tT then all its edges are in E, and all its vertices are in V. We denote by N the number of vertices. Given a vertex uV, its degree is the number of edges adjacent to it. An essential notion for HDXs is the local property of its links. A link of a vertex u is the graph Gu=(Vu,Eu) whose set of vertices is the neighborhood of u,

Vu={vV{u,v}E}.

The edges correspond to the triangles incident on u:

Eu={{v,w}{u,v,w}T}.

In this paper we focus on a particularly simple class of complexes, called Cayley complexes over 𝔽2n. These are simplicial complexes whose underlying graph (V,E) is a Cayley graph over 𝔽2n, and so have N=2n vertices. It is well-known that constant-degree Cayley complexes over abelian groups cannot be high dimensional expanders . In fact, logarithmic degree is needed for a 1-dimensional complex, namely a graph, to be an expander [3]. In particular, random Cayley graphs over 𝔽2n with degree Θ(n) (logarithmic in the number of vertices) are expanders with high probability. However, no abelian Cayley complex constructions with remotely close degree are known to have higher dimensional expansion, and a guiding question of this paper is to develop techniques for constructing and analyzing abliean Cayley HDXs of smallest possible degree.

In the rest of the introduction we will explain our constructions. In Section 1.1 we present our construction of local spectral Cayley complexes with arbitrarily good spectral expansion and a subpolynomial degree. In Section 1.2 we present our family of Cayley complexes that are both coboundary expanders and non-trivial local spectral expanders, with arbitrarily small polynomial degree. In Section 1.3 we discuss the common structure of our two constructions that relies on the Hadamard code. In Section 1.4 we present some open questions.

1.1 Local spectral expanders

We start with definitions and motivation, review past results and then state ours. The first notion of high dimensional expansion we consider is local spectral expansion. The spectral expansion of a graph G is the second largest eigenvalue of its random walk matrix in absolute value, denoted λ(G). Local spectral expansion of complexes is the spectral expansion of every link.

Definition 1 (Local spectral expansion).

Let λ0. A 2-dimensional simplicial complex X=(V,E,T) is a λ-local spectral expander if the underlying graph (V,E) is connected and for every uV, λ(Xu)λ.

Local spectral expansion is the most well-known definition of high dimensional expansion. It was first introduced implicitly by [47] for studying the real cohomology of simplicial complexes. A few decades later, a few other works observed that properties of specific local spectral expanders are of interest to the computer science community [79, 60, 62]. The definition above was given in [38], for the purpose of constructing agreement tests. These are strong property tests that are a staple in PCPs (see further discussion in Section 1.2). Since then they have found many more applications that we now discuss.

Applications of local spectral expanders

One important application of local spectral expansion is in approximate sampling and Glauber dynamics. Local spectral expansion implies optimal spectral bounds on random walks defined on the sets of the complex. These are known as the Glauber dynamics or the up-down walks. This property has lead to a lot of results in approximate sampling and counting. These include works on Matroid sampling [5], random graph coloring [20] and mixing of Glauber dynamics on the Ising model [4].

Local spectral expanders have also found applications in error correcting codes. Their sampling properties give rise to construction of good codes with efficient list-decoding algorithms [1, 37, 59]. One can also use the to construct locally testable codes that sparsify the Reed-Muller codes [39].

The list decoding algorithms in [1, 59] rely on their work on constraint satisfaction problems on local spectral expanders. These works generalize classical algorithms for solving CSPs on dense hypergraphs, to algorithms that solve CSPs on local spectral expanders. These works build on the “dense-like” properties of these complexes, and prove that CSPs on local spectral expanders are easy. It is interesting to note that local spectral expanders have rich enough structure so that one can also construct CSPs over them that are also hard for Sum-of-Squares semidefinite programs [35, 57]111In fact, [1] uses Sum-of-Squares to solve CSPs on local spectral expanders. It seems contradictory, but the hardness results in [35, 57] use CSPs where the variables are the edges of the HDX. The CSPs in [1] use its vertices as variables..

Some of the most important applications of local spectral expansion are constructions of derandomized agreement tests [38, 26, 51, 9, 31] and even PCPs [11]. Most of these works also involve coboundary expansion so we discuss these in Section 1.2.

Local spectral expanders have other applications in combinatorics as well. They are especially useful in sparsifying central objects like the complete uniform hypergraph and the boolean hypercube. The HDX based sparsifications maintain many of their important properties such as spectral gap, Chernoff bounds and hypercontractivity (see [62, 30, 67, 54, 8, 32] as a partial list).

Previous constructions

Attempts to construct bounded degree local spectral expanders with sufficient expansion for applications have limited success besides the algebraic constructions mentioned above [12, 16, 72, 79, 68, 86, 25]. Random complexes in the high dimensional Erdős–Rényi model defined by [73] are not local spectral expanders with overwhelming probability when the average degree is below N1/2 and no other bounded degree model is known. The current state of the art is the random geometric graphs on the sphere [74], that achieve non-trivial local spectral expansion and arbitrarily small polynomial degree (but their expansion is also bounded from below, see discussion in Section 1.2). Even allowing an unbounded degree, the only other known construction that is non-trivially sparse complexes is the one in [50] mentioned in the abstract.

Our result

The first construction we present is a family of Cayley local spectral expanders. Namely,

Theorem 2.

For every λ,ε>0 and integer d2 there exists an infinite family of d-dimensional Cayley λ-local spectral expanders over the vertices 𝔽2n with degree at most 2nε.

This construction builds on an ingenious construction by Golowich [50], which proved this theorem for ε=12. As far as we know, this is the sparsest construction that achieves an arbitrarily small λ-local spectral expansion other than the algebraic constructions.

Proof overview

Our construction is based on the well studied Grassmann poset, the partially ordered set of subspaces of 𝔽2n, ordered by containment. This object is the vector space equivalent of high dimensional expander, and was previously studied in [30, 69, 46, 50]. To understand our construction, we first describe the one in [50]. Golowich begins by sparsifying the Grassmann poset, to obtain a subposet. The generators of the Cayley complex in [50] are all (non-zero vectors in) the one-dimensional subspaces in the subposet. The analysis of expansion in [50] depends on the expansion properties of the subposet. The degree is just the number of one-dimensional vector spaces in the subposet, which is 2n1/2.

Our construction takes a modular approach to this idea. We modify the poset sparsification in [50] so that instead of the entire Grassmann poset, we can plug in any subposet Y of the Grassmann, and obtain a sparsification Y whose size depends on Y (not the complete Grassmann).

Having this flexible sparsification step, we iterate. We start with Y0, the complete Grassmann poset, we obtain a sequence Y1,Y2,,Ym of sparser and sparser subposets. The vectors in Yi are low-rank matrices whose rows and columns are vectors in subspaces of Yi+1.

We comment that while this is a powerful paradigm, it does have a drawback. The dimension of Yi is logarithmic in the dimension of Yi1 (the dimension of Y is the maximal dimension of a space inside Y). Thus for a given complex Y0 we can only perform this sparsification a constant number of steps keeping ε constant. Our infinite family is generated by taking an infinite family of Y0’s, and using our sparsification procedure on every one of them separately.

This construction of sparsified posets produces local spectral expanders of any constant dimension, as observed by [50]. The higher dimensional sets in the resulting simplicial complex correspond to the higher dimensional subspaces of the sparsification we obtain. We refer the reader to Section 3 for more details.

The analysis of the local spectral expansion is delicate, so we will not describe it here. One property that is necessary for it is the fact that every rank-r matrix has many decompositions into sums of rank-1 matrices. Therefore, to upper bound spectral expansion we study graphs that arise from decompositions of matrices.

In addition, we wish to highlight a local-to-global argument in our analysis that uses a theorem by [81]. Given a graph G=(V,E) that we wish to analyze, we find a set of expanding subgraphs {H1,H2,Hm} of G (that are allowed to overlap). We consider the decomposition graph whose vertices are V and whose edges are all {v,v} such that there exists an Hi such that v,vHi. If every Hi is an expander and the decomposition graph is also an expander, then G itself is an expander [81]. This decomposition is particularly useful in our setup. The graphs we need to analyze in order to prove the expansion of our complexes, can be decomposed into smaller subgraphs Hi. These Hi’s are isomorphic to graphs coming from the original construction of [50]. Using this decomposition we are able to reduce the expansion of the links to the expansion of some well studied containment graphs in the original Grassmann we sparsify.

 Remark 3 (Degree lower bounds for Cayley local spectral expanders).

The best known lower bound on the degree of Cayley λ-local spectral expanders over 𝔽2n is Ω(nλ2log(1/λ)) [2]. This bound is obtained simply because the underlying graph of a Cayley λ-local spectral expander is an O(λ)-spectral expander itself [87]. In Appendix I we investigate this question further, and provide some additional lower bounds on the degree of Cayley complexes based on their link structure. We prove that if the Cayley complex has a connected link then its degree is lower bounded by 2n1 (compared to n if the link is not connected). If the link mildly expands, we provide a bound that grows with the degree of a vertex inside the link. However, these bounds do not rule out Cayley λ-local spectral expanders whose generator set has size O(nλ2log(1/λ)). The best trade-off between local spectral expansion and the degree of the complex is still open.

1.2 Our coboundary expanders

Our next main result is an explicit construction of a family of 2-dimensional complexes with an arbitrarily small polynomial degree, that have both non-trivial local spectral expansion and coboundary expansion. To the best of our knowledge, this is the first such nontrivial construction. Again, these are Cayley complexes of 𝔽2n.

Coboundary expansion is a less understood notion compared to local spectral expansion. Therefore, before presenting our result we build intuition for it slowly by introducing a testing-based definition of coboundary expanders. After the definition, we will discuss the motivation behind coboundary expansion and applications of known coboundary expanders.

As mentioned before, there are several nonequivalent definitions of expansion for higher-dimensional complexes. In particular, coboundary expansion generalizes the notion of edge expansion in graphs to simplicial complexes. Coboundary expansion was defined independently by [73],[85] and [52]. The original motivation for this definition came from discrete topology; more connections to property testing were discovered later. We will expand on these connections after giving the definition. This definition we give is equivalent to the standard definition, but is described in the language of property testing rather than cohomology.

The more general and conventional definition for arbitrary groups Γ can be found in Section 5.1.

Definition 4.

Let X=(V,E,T) be a 2-dimensional simplicial complex. Consider the code B1𝔽2E whose generating matrix is the vertex-edge incidence matrix AX𝔽2E×V, and the local test 𝒯 of membership in this code for B1 given by first sampling a uniformly random triangle {u,v,w}T and then accepting f𝔽2E if and only if f({u,v})+f({v,w})+f({u,w})=0 over 𝔽2.

Let β>0. X is a β-coboundary expander over 𝔽2 if

f𝔽2E,[𝒯 rejects f]βdist(f,B1),

where dist(f,B1)=mincB1eUnif(E)[f(e)c(e)] is the relative distance from f to the closest codeword in B1.

Observe that the triangles are parity checks of B1, and so if the input f is a codeword, the test always accepts. A coboundary expander’s local test should reject inputs f which are “far” from the code with probability proportional to their distance from it. The proportionality constant β captures the quality of the tester (and coboundary expansion). We note that although the triangles are some parity checks of the code B1, they do not necessarily span all parity checks. In such cases, X is not a coboundary expander for any β>0.

Definition 5.

A set of 2-dimensional simplicial complexes {Xn} is a family of coboundary expanders if there exists some β>0 such that for all n, Xn is a β-coboundary expander.

Applications of coboundary expansion

We mention three different motivations to the study of coboundary expansion: from agreement testing, discrete geometry, and algebraic topology.

Coboundary expanders are useful for constructing derandomized agreement tests for the low-soundness (list-decoding) regime. As we mentioned before, agreement tests (also known as derandomized direct product tests) are a strong property test that arise naturally in many PCP constructions [33, 90, 48, 58] and low degree tests [94, 7, 91]. They were introduced by [48]. In these tests one gets oracle access to “local” partial functions on small subsets of a variable set, and is supposed to determine by as few queries as possible, whether these functions are correlated with a “global” function on the whole set of variables. The “small soundness regime”, is the regime of tests where one wants to argue about closeness to a “global” function even when the “local” partial functions pass the test with very small success probability (see [36] for a more formal definition). Works such as [36, 58, 40] studied this regime over complete simplicial complexes and Grassmanians, but until recently these were essentially the only known examples. Works by [51, 10, 27] reduced the agreement testing problems to unique games constraint satisfaction problems, and showed existence of a solution via coboundary expansion (over some symmetric groups), following an idea by [41]. This lead to derandomized tests that come from bounded degree complexes [31, 9].

In discrete geometry, a classical result asserts that for any n points in the plane, there exists a point that is contained in at least a constant fraction of the (n3) triangles spanned by the n points [13] 222This can also be generalized to any dimension by replacing triangles with simplices [15].. In the language of complexes, for every embedding of the vertices of the complete 2-dimensional complex to the plane, such a heavily covered point exists. One can ask whether such a point exists even when one allows the edges in the embedding to be arbitrary continuous curves. If for every embedding of a complex X to the plane (where the edges are continuous curves), there exists a point that lays inside a constant fraction of the triangles of X, we say X has the topological overlapping property. The celebrated result by Gromov states that the complete complex indeed has this property [52]. It is more challenging to prove this property for a given complex.

In [52], Gromov asked whether there exists a family of bounded-degree complexes with the topological overlapping property. Towards finding an answer, Gromov proved that every coboundary expander has this property. This question has been extremely difficult. An important progress is made in [43], where they defined cosystolic expansion, a relaxation of coboundary expansion, and proved that this weaker expansion also implies the topological overlapping property. The problem was eventually resolved in [60] for dimension 2 and in [44] for dimension >2 where the authors show that the [79] Ramanujan complexes are bounded-degree cosystolic expanders.

Coboundary expansion has other applications in algebraic topology as well. Linial, Meshulam, and Wallach defined coboundary expansion independently, initiating a study on high dimensional connectivity and cohomologies of random complexes [73, 85]. Lower bounding coboundary expansion turned out to be a powerful method to argue about the vanishing of cohomology in high dimensional random complexes [42, 55].

Known coboundary expanders

Most of the applications mentioned above call for complexes that are simultaneously coboundary expanders and non-trivial local spectral expanders. So far there are no known constructions of such complexes with arbitrarily small polynomial degree even in dimension 2 333By coboundary expanders, we are referring to complexes that have coboundary expansion over every group, not just 𝔽2.. Here we summarize some known results.

Spherical buildings of type Ad are dense complexes that appear as the links of the Ramanujan complexes in [79]. The vertex set of a spherical building consists of all proper subspaces of some ambient vector space 𝔽qd. [52] proved that spherical buildings are coboundary expanders (see also [77]). Geometric lattices are simplicial complexes that generalize spherical buildings. They were first defined in [71]. Most recently, [28] show that geometric lattices are coboundary expanders. [68] show that the 2-dimensional vertex links of the coset geometry complexes from [66] are coboundary expanders.

If we restrict our interest to coboundary expanders over a single finite group instead of all groups, bounded degree coboundary expanders that are local spectral expanders are known. [60] solved this for the 𝔽2 case conditioned on a conjecture by Serre. [19] constructed such complexes for the 𝔽2 unconditionally, and their idea was extended by [31, 9] to every fixed finite group, which lead to the aforementioned agreement soundness result. Unfortunately, their approach cannot be leveraged to constructing a coboundary expander with respect to all groups simultaneously.

We note that the coboundary expanders mentioned above are also local spectral expanders and that if we do not enforce the local spectral expansion property, coboundary expanders are trivial yet less useful.

To the best of our knowledge, all known constructions of 2-dimensional coboundary expanders (over all groups) that are also non-trivial local spectral expanders have vertex degree at least Nc for some fixed c>0, where N is the number of vertices (see e.g. [79, 66]).444To the best of our knowledge, this constant is c=0.5. The diameter of all of those complexes is at most a fixed constant, which implies this lower bound on the maximal degree. In this work, we give the first such construction with arbitrarily small polynomial degree.

Our result

We now state our main result in this subsection. For every integer k>0, and constant ε(0,12] we construct a family of k-dimensional simplicial complexes {Xε,n}n called the Johnson complexes. For any k-dimensional simplicial complex X, we use the notation (X)2 (the 2-skeleton of X) to denote the 2-dimensional simplicial complex consists of the vertex, edge, and triangle sets of X.

Theorem 6 (Informal version of Theorem 86, Lemma 59, and Lemma 91).

For any integer k2, ε(0,12], the 2-skeletons of the Johnson complexes Xε,n are (12ε2)-local spectral expanders and Ω(ε)-coboundary expanders (over every group Γ).

Moreover, if k3, the 2-skeletons of Xε,ns’ vertex links are 185-coboundary expanders .

Fix ε(0,12]. For every n satisfying 4|εn, we briefly describe the 2-skeletons of Xε,n. The underlying graph of Xε,n is simply the Cayley graph Cay(H;Sε) where H𝔽2n consists of vectors with even Hamming weight, and Sε is the set of vectors with Hamming weight εn. Thus the number of vertices in the graph is 2n1 while the vertex degree is (nεn)<2nh(ε) 555Here h is the binary entropy function.. The triangles are given by:

Xε,n(2)={{x,x+s1,x+s2}x𝔽2n,s1,s2,s1+s2Sε}.

Observe that the link of every vertex is isomorphic to the classically studied Johnson graph J(n,m,m/2) of m-subsets of [n], that are connected if their intersection is m/2 (for m=εn). We will use some of the known properties of this graph in our analysis.

We additionally show that when 2k|εn, we can extend the above construction to get k-dimensional simplicial complexes Xε,n with the exact same vertex set, edge set, and triangle set as defined above. Moreover we show that for every integer 0mk2, the link of an m-face in the complex is also a non-trivial local spectral expander (Lemma 59).

 Remark 7.

Let N=2n1. We note that all vertices in Xε,n are in poly(N) edges and all vertices in the links of Xε,n are in poly(N) edges. We remark that using a graph sparsification result due to [21], we can randomly subsample the triangles in Xε,n to obtain a random subcomplex which is still a local spectral expander with high probability but whose links have vertex degree polylog(N). A detailed discussion can be found in Appendix F.

Before giving a high-level overview of the proof for Theorem 6, we describe a general approach for showing coboundary expansion called the cone method. Appearing implicitly in [52], it was used in a variety of works (see [77, 71, 68] as a partial list). We also take this approach to show that the Johnson complexes are coboundary expanders.

Coboundary expansion for links of the [50] Cayley local spectral expanders

Even though most of our results on coboundary expansion are for the Johnson complexes, we can also use the methods in this paper to prove that the vertex links of the [50] Cayley local spectral expanders are coboundary expanders. This implies that these Cayley local spectral expanders are cosystolic expanders (see [60, 28]), the relaxation of coboundary expansion mentioned above. This makes them useful for constructing agreement tests and complexes with the topological overlapping property. We note that [50] observed that these complexes are not coboundary expanders so this relaxation is necessary. A definition of cosystolic expansion and a detailed proof can be found in Section 6.3.

Cones and isoperimetry

Recall first the definition of β-coboundary expansion above. We start with the code B1 of edge functions f which arise from vertex labelings by elements of some group Γ. This implies that composing (in order) the values of fB1 along the edges of any cycle will give the identity element idΓ. This holds in particular for triangles, which are our “parity checks”.

We digress to discuss an analogous situation in geometric group theory, of the word problem for finitely presented groups. In this context, we are given a word in the generators of a group and need to check if it simplifies to the identity under the given relations. In our context the given word is the labeling of f along some cycle, and a sequence of relations (here, triangles) is applied to successively “contract” this word to the identity. The tight upper bound on the number of such contractions in terms of the length of the word (called the Dehn function of the presentation), captures important properties of the group, e.g. whether or not it is hyperbolic. This ratio between the contraction size and the word length is key to the cone method.

One convenient way of capturing the number of contractions is the so-called “van Kampen diagram”, which simply “tiles” the cycle with triangles in the plane (all edges are consistently labeled by group elements). The van Kampen lemma ensures that if a given word can be tiled with t tiles, then there is a sequence of t contractions that reduce it to the identity [97]. The value in this viewpoint is that tiling is a static object, which can be drawn on the plane, and allows one to forget about the ordering of the contractions. We will make use of this in our arguments, and for completeness derive the van Kampen lemma in our context. Note that a bound on the minimum number of tiles (a notion of area) needed to cover any cycle of a given length (a notion of boundary length) can be easily seen as an isoperimetric inequality! The cone method will require such isoperimetric inequality, and the Dehn function gives an upper bound on it.

Back to β-coboundary expansion. Here the given f may not be in B1, and we need to prove that if it is “far” from B1, then the proportion of triangles which do not compose to the identity on f will be at least βdist(f,B1). The cone method localizes this task. To use this method, one needs to specify a family of cycles (also called a cone) in the underlying graph of the complex. Gromov observed that the complex’s coboundary expansion has a lower bound that is inverse proportional to the number of triangles (in the complex) needed to tile a cycle from this cone [52]. This number is also referred to as the cone area. Thus, bounding the coboundary expansion of the complex reduces to computing the cone area of some cone. Needless to say, an upper bound on the Dehn function, which gives the worst case area for all cycles, certainly suffices for bounding the cone area of any cone.666We note that in a sense the converse is also true - computing the cone area for cones with cycles of “minimal” length suffices for computing the Dehn function. We indeed give such a strong bound.

Proof overview

It remains to construct a cone in Xε,n and upper bound its cone area. We now provide a high level intuition for our approach. First observe that the diameter of the complex X=Xε,n is Θ(1/ε). The proof then proceeds as follows.

  1. 1.

    We move to a denser 2-dimensional complex X whose underlying graph is the Cayley graph Cay(H;Sε) where H𝔽2n consists of vectors with even Hamming weight, and Sε is the set of vectors with even Hamming weight εn. The triangle set consists of all 3-cliques in the Cayley graph. We note that X has the same vertex set as X but has more edges and triangles than the Johnson complex.

  2. 2.

    Then we carefully construct a cone 𝒜 in X with cone area Θ(1/ε).

  3. 3.

    We show that every edge in X translates to a length-2 path in X, and every 3-cycle (boundary of a triangle) in X translates to a 6-cycle in X which can be tiled by O(1) triangles from X.

  4. 4.

    We translate the cone 𝒜 in X into a cone 𝒜 in X by replacing every edge in the cycles of 𝒜 with a certain length-2 path in X. Thus every cycle C𝒜 can be tiled by first tiling its corresponding cycle C𝒜 with O(1/ε) X triangles and then tiling each of the X triangles with O(1) X triangles. Thereby we conclude that 𝒜 has cone area Θ(1/ε).

Local spectral expansion and comparison to random geometric complexes

These Johnson complexes also have non-trivial local spectral expansion. While they do not achieve arbitrarily small λ-local spectral expansion, they do pass the λ<12 barrier. From a combinatorial point of view, λ<12 is an important threshold. For λ12, there are elementary bounded-degree constructions of λ-local spectral expanders [22, 17, 23, 75, 49] but these fail to satisfy any of the local-to-global properties in HDXs. For λ<12 all these constructions break. For this regime, all bounded degree constructions rely on algebraic tools. This is not by accident; below 12 there are a number of high dimensional global properties suddenly begin to hold. For instance, a theorem by [47] implies that when λ<12 all real cohomologies of the complex vanish. Another example is the “Trickle-Down” theorem by [87] which says that the expansion of the skeleton (V,E) is non-trivial whenever λ<12. These are strong properties, and we do not know how produce them in elementary constructions. Therefore, when constructions of local spectral expanders are considered non-trivial only when λ<12.

To show local spectral expansion, we first note that the Johnson complex is symmetric for each vertex. Hence, it suffices to focus on the link of 0𝔽2n. Because the triangle set T is well-structured, we can show that the link graph of 0 is isomorphic to tensor products of Johnson graphs (Proposition 62). This allows us to use the theory of association schemes to bound their eigenvalues.

We also note that since all boolean vectors in {0,1}n lie on a sphere in n centered at [12,12,,12], the Johnson complex Xε,n can be viewed as a geometric complex whose vertices are associated with points over a sphere and two vertices form an edge if and only if their corresponding points’ L2 distance is εn. Previously [74] prove that randomized 2-dimensional geometric complexes are local spectral expanders. Comparing the two constructions, we conclude that Johnson complexes are sparser local spectral expanders than random geometric complexes.

1.3 The common structure between the two constructions

Taking a step back, we wish to highlight that the two constructions in our paper share a common structure. Both of these constructions can be described via “induced Hadamard encoding”. For a (not necessarily linear) function s:𝔽2d𝔽2n, the “induced” Hadamard encoding is the linear map s^:𝔽2d𝔽2n given by

s^(x)v𝔽2dx,vs(v),

where x,v=i=1dxivi and the sum is over 𝔽2. Our two constructions of Cayley HDXs take the generating set of the Cayley graph to be all bases of spaces Im(s^)𝔽2n, for carefully chosen functions s as above; the choice determines the construction. We note that the “orthogonality” of vectors of the Hadamard code manifests itself very differently in the two constructions: in the Johnson complexes it can be viewed via the Hamming weight metric, while in the other construction it may be viewed via the matrix rank metric. We connect the structure of links in our constructions, to the restrictions of these induced Hadamard encodings to affine subspaces of 𝔽2n. Using this connection we show that one can decompose the link into a tensor product of simpler graphs, which are amenable to our analysis. A special case of this observation was also used in the analysis of the complexes constructed by [50].

1.4 Open questions

Local spectral expanders

As mentioned above, we do not know how sparse a Cayley local spectral expander can be. To what extent can we close the gaps between the lower and upper bounds for various types of abelian Cayley HDXs? In particular, can we show that any nontrivial abelian Cayley expanders must have degree ω(n)? Conversely, can we construct Cayley HDXs where the degree is upper bounded by some polynomial in n? Limits of our iterated sparsification technique would also be of interest.

So far, the approach of constructing Cayley local spectral expanders over 𝔽2n by sparsifying Grassmann posets yields the sparsest known such complexes. In contrast to the success of this approach, we have limited understanding of its full power. To this end, we propose several questions: what codes can be used in place of the Hadamard codes so that the sparsification step preserves local spectral expansion? Could this approach be generalized to obtain local spectral expanders over other abelian groups? As mentioned above, we know that the approach we use can not give a complex of polynomial degree in n without introducing new ideas.

Coboundary expanders

Another fundamental question regards the isoperimetric inequalities we describe above. In this paper and many others, one uses the approach pioneered by Gromov [52] that applies isoperimetric inequalities to lower bounding coboundary expansion. A natural question is whether an isoperimetric inequality is also necessary to obtain coboundary expansion. An equivalence between coboundary expansion and isoperimetry will give us a simple alternative description for coboundary expansion. A counterexample to such a statement would motivate finding alternative approaches for showing coboundary expansion.

We call our family of 2-dimensional simplicial complexes that are both local spectral expanders and 1-dimensional coboundary expanders Johnson complexes. This construction can be generalized to yield families of k-dimensional Johnson complexes that are still local spectral expanders. However, it remains open whether they are also coboundary expanders in dimension >1.

1.5 Organization of this paper

In Section 2, we give preliminaries on simplicial complexes and local spectral expansion. We also define Grassmann posets–the vector space analogue for HDXs–which we use in our constructions. Other elementary backgrounds on graphs and expansion are given there as well.

In Section 3, we construct the subpolynomial degree Cayley complexes, proving Theorem 2. Most of this section discusses Grassmann posets instead of Cayley HDXs, but we describe the connection between the two given by [50] in this section too. We defer some of the more technical expansion upper bounds to Appendix D.

In Section 4 we construct the Johnson complexes which are both coboundary expanders and local spectral expanders. In this section we prove that they are local spectral expanders, leaving coboundary expansion to be the focus of the next two sections. We also give a detailed comparison of this construction to the one in [74], and discuss how to further sparsify our complexes by random subsampling.

In Section 5 we take a detour to formally define coboundary expansion and discuss its connection to isoperimetric inequalities. In this section we also give our version of the van-Kampen lemma, generalized to the setting of coboundary expansion. This may be of independent interest, as the van-Kampen lemma simplifies many proofs of coboundary expansion.

In Section 6 we prove that the Johnson complexes are coboundary expanders (Theorem 86), and local coboundary expanders (Theorem 89). We also prove that links in the construction of [50] are coboundary expanders.

In Section 7 we show that both the Johnson complex and the matrix complexes are special cases of a more general construction. In this section we show that the two complexes have a similar link structure, which is necessary for analyzing the local spectral expansion in both Cayley HDXs.

The appendices contain some of the more technical claims for ease of reading. In Appendix I we also give a lower bound on the degree of Cayley local spectral expanders, based on the degree of the link.

2 Preliminaries

We denote by [k]={1,2,,k}.

2.1 Graphs and expansion

Let G=(V,E,μ) be a weighted graph where μ:E0 are the weights. In this paper we assume that μ is a probability distribution μ:E(0,1] that gives every edge a positive measure. When μ is clear from context we do not specify it. We extend μ to a measure on vertices where μ(v)=uvμ(uv). When G is connected this is the stationary distribution of the graph. The adjacency operator of the graph A sends f:V to Af:V with Af(v)=𝔼uv[f(u)]=uvμ(u)μ(v)f(u). We denote by f,g=𝔼vμ[f(v)g(v)] the usual inner product, and recall the classic fact that A is self adjoint with respect to this inner product. We denote by λ(A) its second largest eigenvalue in absolute value. Sometimes we also write λ(G) instead of λ(A). It is well-known that λ(G)1.

Definition 8 (Expander graph).

Let λ0. A graph G is a λ-expander if λ(G)λ.

This definition is usually referred to as λ-two-sided spectral expansion. We note that the one-sided definition where one only gets an upper bound on the eigenvalues of G is also interesting, but is out of our paper’s scope (see e.g. [56]).

When G=(L,R,E) is a bipartite graph, we also have inner products on each side defined by f,g:L, f,g=𝔼vL[f(v)g(v)] with respect to μ restricted to L (and similarly to real valued functions on R). The left-to-right bipartite graph operator A that sends f:L to Af:R with Af(u)=𝔼vu[f(v)] (resp. right-to-left bipartite operator). It is well known that A|f𝟏 is equal to the second largest eigenvalue of the non bipartite adjacency operator A defined above (not in absolute value). We also denote this quantity λ(G)A|f𝟏 (it will be clear that whenever G is bipartite this is the expansion parameter in question).

Definition 9 (Bipartite expander graph).

Let λ0. A bipartite graph G is a λ-bipartite expander if λ(G)λ.

We use the following standard auxiliary statements.

Claim 10.

Let A,B be adjacency matrices of two graphs over the same vertex set and have the same stationary distribution. Let ε=maxvAvBv1=maxvuV|A(v,u)B(v,u)|. Then λ(A)λ(B)+ε.

We will usually instantiate this claim with B being the complete graph with self loops, i.e. the edge distribution is just two independent choices of vertices. This B has λ(B)=0 so we get this corollary.

Corollary 11.

Let A be an adjacency matrix of a weighted graph G=(V,E,μ).

  1. 1.

    λ(A)maxvVAvμ1=uV|A(v,u)μ(u)|.

  2. 2.

    In particular, if A is uniform over a set VV with μ(V)1p then λ(A)2p.

We also define a tensor product of graphs.

Definition 12.

Let G1=(V1,E1),G2=(V2,E2) be graphs. The tensor product G1G2 is a graph with vertices V1×V2 and edges (v1,v2)(u1,u2) if {v1,u1}E1 and {v2,u2}E2. The measure on G1G2 is the product of the original graphs’ measures.

We record the following well-known fact.

λ(G1G2)=max{λ(G1),λ(G2)}. (2.1)

In fact, if λ1λ2λn are the eigenvalues of G1 and η1η2ηm are the eigenvalues of G2, then the eigenvalues of G1G2 are the multiset {λiηj|i[n],j[m]}.

We also need the notion of a double cover.

Definition 13 (Double cover).

Let G=(V,E) be a graph and K1,1 be the graph that contains a single edge. The double cover of G is the graph GK1,1. Explicitly, its vertex set is V{0,1} and we connect {(v,i),(u,j)} if {v,u}E and ij.

The following observation is well known.

Observation 14.

A graph G is a λ-expander if and only if its double cover is a λ-bipartite expander.

2.1.1 A local to global lemma

We will use the following “local-to-global” proposition due to [81, Theorem 1.1]. We prove it in Appendix A to be self contained. This lemma is an application of the Garland method [47], which is quite common in the high dimensional expander literature (see e.g. [87]). Let us set it up as follows.

Let G=(V,E,μ) be a graph where μ is the distribution over edges. A local-decomposition of G is a pair τ=(T,νT) as follows. T={Gt=(Vt,Et,μt)}tT is a set such that (Vt,Et) are a subgraph of G and μt is a weight distribution over Et. νT is a distribution over T. Assume that {v,u}μ is sampled according to the following process:

  1. 1.

    Sample tνT.

  2. 2.

    Sample {v,u}μt.

The local-to-global graph τ is the bipartite graph on V and T whose edge distribution is

  1. 1.

    Sample tνT.

  2. 2.

    Sample a vertex vμt777i.e. v is sampled with probability μt(v)=12eμt[ve]..

  3. 3.

    Output {v,t}.

Note that the probability of vV under G and that under τ (conditioned on the V side) are the same.

Lemma 15 ([81, Theorem 1.1]).

Let G,τ,τ be as above. Let λ2=λ2(τ) and γ=max{λ(Gt)tT}. Then λ(G)γ+λ22(1γ).

We will also use the one-sided version of [81, Theorem 1.1]. For a formal proof see [26, Lemma 4.14]. We formalize it in our language.

Lemma 16.

Let G=(L,R,E) be a bipartite graph. Let τ=(T,νT) be a local decomposition. Let τ,L be the restriction of τ to the vertices of (L,T) (resp. τ,R). Then

λ2(G)max{λ2(Gt)tT}+λ2(τ,L)λ2(τ,R).

2.2 Vector spaces

Unless stated otherwise, all vector spaces are over 𝔽2. For a vector space V and subspaces u1,u2V we say their intersection is trivial if it is equal to {0}. We denote the sum u1+u2={x1+x2x1u1,x2u2}. If the sum is direct, that is the intersection of u1 and u2 is trivial, we write u1u2. We shall use this notation to refer both to the statement that u1u2={0} and to the object u1+u2. We need the following claim.

Claim 17.

Let V be a vector space. Let u1,u2,u3V be three subspaces such that (u1u2)u3={0}. Then u2(u1u3)={0}.

Proof.

Let x2=x1+x3u2(u1u3) where xiui. Thus x3=x2x1(u1u2)u3 which by assumption means that x3=0 and x2=x1. As u1u2={0} it follows that x2=x1=0 and the intersection is trivial.

2.3 Grassmann posets

In this paper all vector spaces are with respect to 𝔽2 unless otherwise stated. Let V be a vector space. The Grassmann partially ordered set (poset) 𝒢(V) is the poset of subspaces of V ordered by containment. When V is clear from the context we sometimes just write 𝒢.

Definition 18 (Grassman Subposet).

Let n>0, V be an n-dimensional vector space, and n. An -dimensional Grassmann subposet Y is a subposet of 𝒢(𝔽2n) such that

  1. 1.

    every maximal subspace in Y has dimension ,

  2. 2.

    if wY and ww, then wY.

We sometimes write dim(Y)=. The i-dimensional subspaces in Y are denoted Y(i). The vector space V is sometimes called the ambient space of Y.999formally there could be many such spaces, but in this paper we usually assume that V is spanned by the subspaces in Y.

A measured subposet is a pair (Y,μ) where Y is an -dimensional Grassmann subposet and μ is a probability distribution over -dimensional subspaces such that supp(μ)=Y(). We extend μ to a distribution on flags of subspaces by sampling vμ and then sampling a flag (v1v2v) uniformly at random. Sometimes we abuse notation and write viμ where viY(i) is the marginal over said flags. We sometimes say that Y is measured without specifying μ for brevity. When we write 𝒢 we mean that the distribution is uniform.

The containment graph is a bipartite graph with sides (Y(i),Y(j)) and whose edges {w,w} are such that ww. There is a natural distribution on the edges of this graph induced by the marginal of (vi,vj) of the flag above.

Let Y be an -dimensional Grassmann poset. For i< the Grassmann poset Yi=j=0iY(j) is the poset that contains every subspace in Y of dimension i.

A link of a subspace wY(i) is denoted Yw. It consists of all subspaces in the poset that contain w, namely Yw={wwwY}. If (Y,μ) is measured, the distribution over Yw is the distribution μ conditioned on the sampled flag having vi=w. We note that if V is the ambient space of Y then Yw is (isomorphic to) a Grassmann subposet with ambient space V/w by the usual quotient map.

For any -dimensional subposet Y, any i2, wY(i), and i<j, we denote Yw(j)={ww|wY(j)}. The underlying graph of the link is the following graph (which we also denote by Yw when there is no confusion). The vertices are

Uw={vV|span(v)+wY(i+1)}

and the edges are

Ew={{v,v}|span(v,v)+wY(i+2)}.

We note that sometimes the link graph is defined by taking the vertices to be Yw(i+1) and the edges to be all {w,w′′} such that w+w′′Y(i+2). These two graphs are closely related:

Claim 19.

Let Y be a Grassmann poset. Let wY(i) be a subspace and let Yw=(Uw,Ew) be the underlying graph of its link as defined above. Let G=(V,E) be the graph whose vertices are V=Yw(i+1) and whose edges are {w,w′′} such that w+w′′Y(i+2). Then λ(Yw)=λ(G).

Proof.

Let K2i be the complete graph over 2i vertices including self loops. We prove that GYwK2i. As λ(K2i)=0 it will follow by (2.1) that λ(G)=max{λ(Yw),0}=λ(Yw). For every wYw(i+1) we order the vectors in ww according to some arbitrary ordering ww={v1,v2,,v2i}. Our isomorphism from G to YwK2i sends vj(w,j) where w=w+span(vj) and the j in the subscript is according to the ordering of ww. It is direct to check that this is a bijection.

Moreover, vv in G if and only if w+span(v,v)Y(i+2). This span is equal to w+span(v,v)=(w+span(v))+(w+span(v)). Therefore vv if and only if the left coordinates of the images (w+span(v),j1) and (w+span(v),j2) are connected in Yw. As j1j2 is an edge in the complete graph with self loops, it follows that vv is in G if and only if the corresponding images are connected in YwK2i. The claim follows.

Thus we henceforth use our definition of a link.

We say that such a subposet is a λ-expander if for every i2 and wY(i) the graph Yw is a λ-two-sided spectral expander. We also state the following claim, whose proof is standard.

Claim 20.

The poset Y=𝒢(𝔽2n)d is a 12nd2-expander.

Sketch.

Let wY(i). By Claim 19, to analyze the expansion of the link of w, it suffices to consider the graph whose vertices are the subspaces wYw(i+1) and whose edges are ww′′ if w+w′′Yw(i+2). In this case, it is easy to see that this graph is just the complete graph (without self loops) with 2ni1 vertices. The claim follows by the expansion of the complete complex.

We also need the following claim.

Claim 21 ([30]).

Let Y be a Grassmann poset that is λ-expander. Then for every ij and wY, the containment graph between Yw(i) and Yw(j) is a (0.61+jλ)12(ji)-bipartite expander.

This claim was proven [30] without the explicit constant 0.61. Hence we reprove it in Appendix H with the constant.

2.4 The matrix domination poset

In this section we give preliminaries on the matrix domination posets. These posets are essential for proving that the HDX construction given in Section 3 sufficiently expands. They were a crucial component in the construction of abelian HDXs in [50]. We believe that the matrix domination posets are also interesting on their own right, being another important family of posets to be studied as those in [30, 69].

Let be n×n matrices over 𝔽2 for some fixed n. Let (i)={A|rank(A)=i}. The partial order on this set is the domination order.

Definition 22 (Matrix domination partial order).

Let A,B. We say that A dominates B if rank(A)=rank(B)+rank(AB). In this case we write BA.

Another important notion is the direct sum.

Definition 23 (Matrix direct sum).

We say that two matrices A and B have a direct sum if rank(A)+rank(B)=rank(A+B). In this case we write AB.

We note that this definition is equivalent to saying that A,BA+B. We also clarify that when we write AB, this refers both to the object A+B, and is a statement that rank(A)+rank(B)=rank(A+B). This is similar to the use of when describing a sum of subspaces U1,U2𝔽2n; the term U1U2 refers both to the sum of subspaces, and is a statement that U1U2={0}. We will see below that AB is equivalent to row(A)row(B)={0},col(A)col(B)={0}, so we view this notation as a natural analogue of what happens in subspaces.

In Section 3 we define and analyze expansion of graphs coming from Hasse diagrams of dominance orders. These graphs appear in the analysis of the construction in Section 3. Before doing so, let us state some preliminary properties of this partial order, all of which are proven in Appendix C. More specifically, we will show that this is a valid partial order (as already observed in [50]), discuss the properties of pairs of matrices that have a direct sum, and study structures of intervals in this poset (see definition below).

Claim 24.

The pair (,) is a partially ordered set.

We move on to characterize when AB, that is, when the sum of A and B is direct. This will be important in the subsequent analyses.

Claim 25.

For any matrices A,B the following are equivalent:

  1. 1.

    rank(A+B)=rank(A)+rank(B), i.e. AB.

  2. 2.

    The spaces row(A)row(B) and col(A)col(B) are trivial.

  3. 3.

    The spaces col(A+B)=col(A)col(B) and row(A+B)=row(A)row(B).

  4. 4.

    There exists a decomposition A=j=1rank(A)ejfj and B=j=1rank(B)hjkj such that the disjoint unions {ej}Γ{hj} and {fj}Γ{kj} are independent sets. Indeed, the two sets span row(A+B) and col(A+B) respectively.

We will also use this elementary (but important) observation throughout.

Claim 26 (Direct sum is associative).

Let A,B,C. If A and B have a direct sum, and C has a direct sum with AB, then A has a direct sum with CB. Stated differently, if AB and C(AB), then A(CB). The same holds for any other permutation of A,B and C.

Henceforth, we just write A1A2A3 to indicate that Ai(AjAk) for any three distinct i,j,k.

Finally, we will analyze subposets of that correspond to local components which are analogous to the links in simplicial complexes and Grassmann posets.

Definition 27 (Intervals).

Let M1M2 be two matrices. The interval between M1 and M2 is the subposet of induced by the set

M1M2={A|M1AM2}.

Similar to the above, we also denote by M1M2(i) the matrices in M1M2 of rank i. When M1=0 we just write M2.

The main observation we need on these intervals is this.

Proposition 28.

Let M1M2 be of ranks m1m2. The subposets M1M2 and M2M1 are isomorphic by A𝜓A=AM1. This isomorphism has the property that

rank(A)=rank(A)m1.

Another subposet we will be interested in is the subposet of matrices that are “disjoint” from some A. That is,

Definition 29.

Let A. The subposet A is the subposet of consisting of all {B|BA}.

We note that by Claim 25 A={B|row(B)row(A),col(B)col(A)={0}}.

Claim 30.

Let A(i). Then ϕ:AA,ϕ(B)=BA is an order preserving isomorphism.

2.5 Simplicial complexes and high dimensional expanders

A pure d-dimensional simplicial complex X is a hypergraph that consists of an arbitrary collection of sets of size (d+1) together with all their subsets. The i-faces are sets of size i+1 in X, denoted by X(i). We identify the vertices of X with its singletons X(0) and for good measure always think of X(1)={}. The k-skeleton of X is Xk=i=1kX(i). In particular the 1-skeleton of X is a graph. We denote by diam(X) the diameter of the graph underlying X.

2.5.1 Probability over simplicial complexes

Let X be a simplicial complex and let d:X(d)(0,1] be a density function on X(d) (that is, sX(d)d(s)=1). This density function induces densities on lower level faces k:X(k)(0,1] by k(t)=1(d+1k+1)sX(d),std(s). We omit the level of the faces When it is clear from the context, and just write [T] or tX(k)[T] for a set TX(k).

2.5.2 Links and local spectral expansion

Let X be a d-dimensional simplicial complex and let sX be a face. The link of s is the d=d|s|-dimensional complex

Xs={ts|tX,ts}.

For a simplicial complex X with a measure d:X(d)(0,1], the induced measure on d,Xs:Xs(d|s|)(0,1] is

d,Xs(ts)=d(t)tsd(t).
Definition 31 (Local spectral expander).

Let X be a d-dimensional simplicial complex and let λ0. We say that X is a λ-local spectral expander if for every sX, the link of s is connected, and for every sX(d2) it holds that λ(Xs)λ.

We stress that this definition includes connectivity of the underlying graph of X, because of the face s=. In addition, in some of the literature the definition of local spectral expanders includes a spectral bound λ(Xs)λ for all id2 and sX(i). Even though the definition we use only requires a spectral bound for links of faces sX(d2), it is well known that when λ is sufficiently small, this actually implies bounds on λ(Xs) for all id2 and sX(i) (see [87] for the theorem and more discussion).

Cayley Graphs and Cayley Local Spectral Expanders
Definition 32 (Cayley graph over 𝔽2n).

Let S𝔽2n. A Cayley graph over 𝔽2n with generating set S is a graph whose vertices are 𝔽2n and whose edges are E={{x,x+s}|x𝔽2n,sS}. We denote such a graph by Cay(𝔽2n,S).

Note that we can label every edge in E by its corresponding generator. A Cayley complex is a simplicial complex X such that X1 is a Cayley graph (as a set) and such that all edges with the same label have the same weight. We say that X is a λ-two-sided (one-sided) Cayley local spectral expander if it is a Cayley complex and a λ-two-sided (one-sided) local spectral expander.

3 Subpolynomial degree Cayley local spectral expanders

In this section we construct Cayley local spectral expander with a subpolynomial degree, improving a construction by [50].

Theorem 33.

For every λ,ε>0 and integer d2 there exists an infinite family {Xk}k=1 of d-dimensional λ-local spectral expanding Cayley complexes with X(0)=𝔽2nk. The degree is upper bounded by 2(nk)ε.

Golowich proved this theorem for ε=12.

As in Golowich’s construction, we proceed as follows. We first construct an expanding family of Grassmann posets {Yk}k=1 over 𝔽2 (see Section 2.3), and then we use a proposition by [50] (Proposition 37 below) to construct said Cayley local spectral expanders. The main novelty in this part of the paper is showing that this idea can be iterated, leading to a successive reduction of the degree.

The following notation will be useful later.

Definition 34.

Let d,n,D be integers and λ>0. We say a Grassmann poset is a [d,n,D,λ]-poset if Y is a d-dimensional λ-local spectral expander whose ambient space is 𝔽2n, with |Y(1)|2D.

[50] introduces a general approach that turns a Grassmann poset Y into a simplicial complex β(Y) called the basification of Y. The formal definition of this complex is as follows.

Definition 35.

Given a d-dimensional Grassmann poset Y. Its basification β(Y) is a (d1)-dimensional simplicial complex such that for every 0id1

β(Y)(i)={{v0,,vi}|span(v0,,vi)Y(i+1)}.

In [50] it is observed that the local spectral expansion of Y is identical to that of β(Y). Golowich constructs a Cayley complex whose vertex links are (copies of) the basification. The construction is given below.

Definition 36.

Given the basification β(Y) of a d-dimensional Grassmann complex Y over the ambient space 𝔽2n, define the d-dimensional abelian complex X=Cay(𝔽2n,β(Y)) such that X(0)=𝔽2n and for 0<id

X(i)={{x,x+v1,x+v2,,x+vi}|{v1,v2,,vi}β(Y)(i1)}.

We observe that the underlying graph is Cay(𝔽2n,Y(1)) and therefore its degree is 2D.

Proposition 37 ([50]).

Let Y be a d-dimensional Grassmann poset over 𝔽2n that is λ-expanding. Let X be the abelian complex given by its basification. Then X is a λ-local spectral expander. In addition, the underlying graph of X is a λ1λ-expander.

Thus our new goal is to prove the following theorem about expanding posets.

Theorem 38.

For every ε,λ>0, and d there exists infinite family of integers nk and of [d,nk,nkε,λ]-posets Yk.

This is sufficient to prove Theorem 33:

Proof of Theorem 33, assuming Theorem 38.

Let Yk be an infinite family of [d,nk,nkε,λ] in Theorem 38 for λ such that λ=λ1λ. Let Xk be their basifications. By Proposition 37. The complexes Xk have ambient subspace 𝔽2nk, degree |Y(1)|2(nk)ε, and expansion λ.

3.1 Expanding Grassmann posets from matrices

Let Y be a [d,n,D,λ]-poset. We now describe how to construct from it a [d,n,D,λ]-poset Y where d=Ω(logd), n=n2, D=dD and λ=2Ω(d) when λ14d. In other words, we describe a transformation

[d,n,D,λ]-poset Y[d,n,D,λ]poset Y.

After this, we will iterate this construction, this time taking Y to be the input, producing an even sparser poset Y′′ etc., as we illustrate further below.

Without loss of generality we identify the ambient space of Y with 𝔽2n and set the ambient space of Y to be n×n matrices (𝔽2n2). The 1-dimensional subspaces of Y are

Y(1)={M|rank(M)=d2androw(M),col(M)Y(d2)}. (3.1)

In words, these are all matrices whose rank is d/2 so that their row and column spaces are in Y. As we can see, n=n2 and |Y(1)||Y(1)|d and therefore D=log|Y(1)|dD. We postpone the construction higher dimensional faces (which determine the dimension d) and the intuition behind the expansion of Y for later. Let us first show how an iteration of this construction will construct sparser Grassmann posets.

This single step can be iterated any constant number of times, starting from a high enough initial dimension d0. Let us denote by 𝒮𝒫(Y) the operator that takes as input one Grassmann poset Y and outputs the sparser one Y as above. Fix m and fix a target dimension dm. Let d0dm and let n0 be sufficiently large. We set Y0,Y1,,Ym to be such that Y0=𝒢(𝔽2n0)d0 (which is a [d0,n0,D0,λ0]-poset for D0=n0 and λ0 that goes to 0 with n0) and Yi+1=𝒮𝒫(Yi). The final poset Ym is a

[dm,nm,Dm,λm]-poset.

Here dm=Ωm(logloglogm timesd0), nm=n2m, Dm=O~(d)n and λm=2Ω(dm) when λ0=2Ω(d0).

The above construction works for any large enough n0. This gives us an infinite family of Grassmann complexes whose ambient dimension is nm=n02m and whose degree is Dm=nmε (where m=log1ε). This infinite family proves Theorem 38.

3.1.1 The construction of the Grassmann poset 𝓢𝓟(𝒀)

We are ready to give the formal definition of the poset. We construct the top level subspaces, and then take their downward closure to be our Grassmann poset. Every top level face is going to be an image of a “non-standard” Hadamard encoding. The “standard” Hadamard could be described as follows. Let 𝔽2i be a vector space, and let 𝔽22i be indexed by the vectors in 𝔽2i. That is 𝔽22ispan({ev}v𝔽2i) where ev is the the standard basis vector that is 1 in the v-th coordinate and 0 elsewhere. With this notation the “standard” Hadamard encoding maps

xv𝔽2ix,vev

where x,v=i=1nxivi(mod 2) is the standard bilinear form. A “non-standard” Hadamard encoding in this context is the same as above, only replacing the standard vectors ev with another basis for a subspace, represented by 2i n×n matrices. It is defined by a set {s(v)}v𝔽2i satisfying some properties described formally below. The encoding is the linear map s^:𝔽2i𝔽2n×n,

s^(x)=v𝔽2ix,vs(v)

similar to the formula above. We continue with a formal definition.

We start with Y, a [d,n,D,λ]-poset (and assume without loss of generality that d is a power of 2) and let d=logd101010Although we define this poset to the highest dimension possible. Our construction will eventually take a lower dimensional skeleton of it..

Definition 39 (Admissible function).

Consider a [d,n,D,λ]-poset Y with d=logd. Let i>0, a (not necessarily linear) function s:𝔽2i{0}𝔽2n×n is admissible to Y if:

  1. 1.

    For every v𝔽2i{0}, rank(s(v))=2di.

  2. 2.

    The sum matrix Ms=v𝔽2i{0}s(v) is a direct sum of the s(v)’s, that is,

    rank(Ms)=v𝔽2i{0}rank(s(v))=2d2di.
  3. 3.

    The spaces col(Ms),row(Ms)Y(2d2di).

We remark that for the construction we only need to consider admissible functions for i=d, that is, functions s:𝔽2d{0}𝔽2n×n, where rank(s(v))=1, rank(Ms)=2d1 and col(Ms),row(Ms)Y(2d1). The other admissible functions will be used later in the analysis (see Section 7).

We denote by 𝒮i the set of admissible functions s:𝔽2i{0}𝔽2n×n. The Hadamard encoding of a function s:𝔽2i{0}𝔽2n×n is the linear function s^:𝔽2i𝔽2n×n given by

s^(x)=v𝔽2i{0}x,vs(v),

Observe that s^ is an isomorphism so the image of s^ is an i-dimensional subspace. This of course means that every subspace u𝔽2i is mapped isomorphically to a subspace of the same dimension Im(s^|u). Thus, the Grassmann poset 𝒢s{Im(s^|u)|u𝔽2i,u is a subspace} is isomorphic to the complete Grassmann 𝒢(𝔽2i).

Definition 40 (Matrix poset).

The poset Y=𝒮𝒫(Y) is a d-dimensional poset Y=s𝒮d𝒢s. We denote by 𝒮𝒫(Y) the operator that takes Y and produces Y as above.

In other words, Y is clearly a Grassmann poset and it is a union of 𝒢s for all admissible mappings s𝒮d.

The admissible functions on level i give us a natural description for Y(i):

Claim 41.

Let Y be as in Definition 40. Then

Y(i)={Im(s^)|s𝒮i}.

We prove this claim in Appendix B.

This poset also comes with a natural distribution over d-subspaces is the follows.

  1. 1.

    Sample two (d1)-dimensional subspaces w1,w2Y(d1) independently according to the distribution of Y.

  2. 2.

    Sample uniformly an admissible function s𝒮d such that the matrix Ms=v𝔽2d{0}s(v) has row(Ms)=w1 and col(Ms)=w2.

  3. 3.

    Output Im(s^).

We remark that we can generalize this construction by changing the definition of “admissible” to other settings. One such generalization that replaces the rank function with the hamming weight results in the Johnson poset which we describe in Section 4. We explore this more generally in Section 7.

We finally reach the main technical theorem of this section, Theorem 42. This theorem proves that if Y is an expanding poset, then so is a skeleton of 𝒮𝒫(Y). Using this theorem inductively is the key to proving Theorem 38.

Theorem 42.

There exists a constant K>0 such that the following holds. Let λ(0,1), D>0 and d>0 be an integer. Let d=max{22d,(Klog1λ)2} and let λ14d. If Y is a [d,n,D,λ]-poset then the d-skeleton of Y=𝒮𝒫(Y), namely Yd, is a [d,n,D,λ]-poset where n=n2 and D=dD.

Proof of Theorem 38, assuming Theorem 42.

Fix ε and without loss of generality ε=12m for some integer m0. Changing variables, it is enough to construct a family {Yk} of [d,nk2m,O(nk),λ]-posets for an infinite sequence of integers nk, such that the constant in the big O only depends on d,λ and m but not on nk. Then by setting nk=nk2m gives us the result 111111Technically this only gives a family [d,nk,O(nkε),λ]-posets. But ε>0 can be arbitrarily small. Thus for any ε>0, constructing [d,n,Cnε/2,λ]-posets is also a construction of [d,nk,nkε,λ]-posets, since eventually nkε>Cnkε/2 for any constant C independent of nk.

We prove this by induction on m for all d and λ simultaneously. For m=0 we take the complete Grassmanns, namely nk=k and the family Y=Yk=𝒢(𝔽2k)d that are [d,k,k,λ]-posets for sufficiently large k (the first three parameters are clear. By Claim 20 the links expansion of the complete Grassmann is 12(kd)1 which goes to 0 with k, hence for every λ>0 and large enough k they are λ-expanders).

Let us assume the induction hypothesis holds for m and prove it for m+1. Fix λ>0 and d. By Theorem 42, there exists some d and λ such that if we can find a family of [d,nk2m,O(nk),λ]-posets {Yk}k=1, then the posets Yk𝒮𝒫(Yk)d are [d,nk2m+1,O(nkd),λ]-posets. By the induction hypothesis (applied for d and λ) such a family {Yk}k=1 indeed exists. The theorem is proven.

3.2 A Proof Roadmap for a single iteration of 𝓢𝓟 - Theorem 42

The rest of this section is devoted to proving Theorem 42, and mainly to bounding the expansion of links in Y. Recall the notation to be the poset of matrices with the domination relation.

We fix the parameters λ and d. Without loss of generality we take d to be large enough so that d=22d (this requires that dlogK+loglog1λ for the constant K>0 in Theorem 42).

Recall the partial order defined in Section 2.4 on matrices where we write AM for two matrices A,M𝔽2n×n if rank(M)=rank(A)+rank(MA).

Fix Y, and let Y=𝒮𝒫(Y). Let WY() be a subspace (where d). In the next two subsections we describe the two steps of the proof: decomposition and upper bounding expansion.

3.2.1 Step I: decomposition

We will show that a link of a subspace WY() decomposes to a tensor product of simpler components.

For this we must define two types of graphs, relying on the domination relation of matrices and the direct sum.

Definition 43 (Subposet graph).

Let m>0 and let U(4m). The graph 𝒯U=(V,E) has vertices V=U(2m) and edges {A,B} such that there exists C(m) such that C(AC)(BC)U(3m).

For any two U1,U2(4m) of rank 4m, the graphs 𝒯U1𝒯U2 so we denote this graph by 𝒯m when we do not care about the specific matrix.

Definition 44 (Disjoint graph).

Let m,i>0 and let D(i). The graph D,m=(V,E) has vertices V=D(2m) and edges {A,B} such that there exists C(m) such that we have C(AC)(BC)D(3m).

For any n and two D1,D2(i), the graphs D1,mD2,m so we denote this graph by i,m when we do not care about the specific matrix.

The first component in the decomposition in the link of W is the subposet graph. The second component is the sparsified link graph. This graph depends on Y, unlike the previous component. In particular, the matrices in this component will have row and column spaces in Y. For the rest of this section we fix m=d2+2. Let ZW be any matrix whose row span and column span are row(ZW)=MWrow(M) and col(ZW)=MWcol(M). Note that both row(ZW) and col(ZW) have dimension (112)d (that is, d4m). The following definition will only depend on these row and column spaces, but it will be easier in the analysis to give the definition using this matrix ZW.

Definition 45 (Sparsified link graph).

The graph Y,W is the graph with vertex set

V={AZW(2m)|row(A)row(ZW),col(A)col(ZW)Y(d2m)}.

The edges are all {A1,A2} such that there exists a matrix UZW(4m) such that row(U)row(ZW),col(M)col(ZW)Y(d), and {A1,A2} are an edge in 𝒯U.

Formally, the distribution over edges in the sparsified link graph Y,W is the following.

  1. 1.

    Sample w1Yrow(ZW)(d) and w2Ycol(ZW)(d) according to their respective distributions.

  2. 2.

    Uniformly sample a matrix U such that row(ZW)row(U)=w1 and col(ZW)col(U)=w2 .

  3. 3.

    Sample an edge in 𝒯U.

We can now state our decomposition lemma:

Lemma 46.

YW(𝒯m𝒯m𝒯m)21 timesY,W.

This lemma is proven in Section 3.3.

3.2.2 Step II: upper bounding expansion

It remains to show that 𝒯m and Y,W are expander graphs. We prove the following two lemmas.

Lemma 47.

There exists an absolute constant γ(0,1) such that λ(𝒯m)γm for all md.

In particular, there is an absolute constant K1>0 such that the following holds: Let λ>0. If dK1+loglog1λ and d22d, then

λ(𝒯m)λ.
Lemma 48.

There exists a constant γ(0,1) such that the following holds. Let Y be a [d,n,D,λ]-poset for λ<14d, and let WY() where Y=𝒮𝒫(Y)d and d. Then λ(Y,W)γm.

In particular, there is an absolute constant K2>0 such that the following holds: Let λ>0. If dK2+loglog1λ, d22d and λ14d, then

λ(Y,W)λ.

The constant K in Theorem 42 is chosen to be 2max(K1,K2). We now give an high level explanation of the proofs of Lemma 47 and Lemma 48, and afterwards we use them to prove Theorem 42.

The graph 𝒯m does not depend on Y and the proof of Lemma 47 relies only on the properties of the matrix domination poset. Therefore it is deferred to Appendix D. In a bird’s-eye view, we use Lemma 16, the decomposition lemma, to decompose the graph into smaller subgraphs, and show that every subgraph is close to a uniform subgraph.

We prove Lemma 48 in Section 3.4. Its proof also revolves around Lemma 16, only this time the subgraphs in the decomposition come from (pairs of) subspaces in Y. Observe that in the first step in sampling an edge in Definition 45, one first samples a pair (w1,w2)Yrow(ZW)(d)×Ycol(ZW)(d). The subgraph induced by fixing w1 and w2 in the first step is isomorphic to a graph that contains all rank 2m matrices in 𝔽2n for some n, that are a direct sum with some matrix ZW (independent of Y). Thus every such subgraph is analyzed using the same tools and ideas as in the proof of Lemma 47.

In order to apply Lemma 16, we also need to show that the decomposition graph τ expands (see its definition in Section 2.1.1). This is the bipartite graph where one side is the vertices in Y,W, and the other side are the pairs of subspaces Yrow(ZW)(d)×Ycol(ZW)(d). A matrix AY,W is connected to (w1,w2) if row(A)w1 and col(A)w2.

To analyze this graph, we reduce its expansion to the expansion of containment graphs in Y. We make the observation that we only care about row(A) and col(A), since if A and A have the same rowspan and colspan, then they also have the same neighbors. To say this in more detail, τ𝒬 where 𝒬 is some complete bipartite graph, and replaces the matrices in τ with Yrow(ZW)(d2m)×Ycol(ZW)(d2m) (here every matrix A is projected to (row(A),col(A)) in ). The graph B itself is a tensor product of the containment graph of Yrow(ZW) and Ycol(ZW). Fortunately, as we discussed in Section 2.3, this graph is an excellent expander, which concludes the proof.

Given these components we prove Theorem 42.

Proof of Theorem 42.

Let us verify all parameters [d,n,D,λ]. The dimension d is clear from the construction.

The size |Y(1)||Y(1)|2d2 since it is enough to specify d vectors to construct a rank d2 matrix M=j=1d2ejfj (of course we have also double counted since many decompositions correspond to the same matrix). Thus log|Y(1)|dD=D.

Let us verify that the ambient space is n=n2 dimensional, or in other words that Y(1) really spans all n×n matrices (recall that we assumed without loss of generality that Y’s ambient space is 𝔽2n). For this it is enough to show that there are n2 linearly independent matrices inside Y(1). Let e1,e2,enY(1) be n linearly independent vectors. The ambient space of Y is 𝔽2n. Let us show that eiej is spanned by the matrices inside Y(1). Indeed, choose some subspaces wi,wjY(d) such that eiwi,ejwj. Then Y(1) contains all rank d2 matrices in 𝔽2n2 whose row and column spans are inside wi,wj. These matrices span all matrices whose row and column spans are in wi,wj and in particularly they span eiej.

Finally let us show that all links are λ-expanders. Fix WY(). By Lemma 46

YW(𝒯m)21Y,W

so λ(YW)max{λ(𝒯m),λ(Y,W)}. Both are λ-expanders by Lemma 47 and Lemma 48 when the conditions of the theorem are met.

To sum up, Y is a [d,n,D,λ]-expanding poset.

 Remark 49.

For the readers who are familiar with [50], we remark that contrary to that paper, we do not use the strong trickling down machinery developed in [69]. [69] show that expansion in the top-dimensional links trickles down to the links of lower dimension (with a worse constant, but still sufficient for our theorem). A priori, one may think that using [69] could simplify the proof. However, in our poset all links have the same abstract structure, so we might as well analyze all dimensions at once. Moreover, one observes that in many cases the bound on the expansion of these posets actually improves for lower dimensions.

3.3 Proof of the decomposition lemma - Lemma 46

The proof of Lemma 46 uses the following claim proven in [50].

Claim 50 ([50, Proposition 55]).

Let Yall=𝒮𝒫(𝒢)d and let WYall(). Then there exists matrices of Z1,Z2,,Z21 of rank d2, whose direct sum is denoted by ZW=i=121Zi, such that the link graph

YWall(j=121𝒯Zj)ZW,m.

This is not just an abstract isomorphism. The details are as follows. First, [50] observes that given W=Im(s^), for some admissible s, the set Im(s){Zj|x𝔽2{0},s(x)=Zj} does not depend on s, only on U. We denote it by QW={Zj}j=121.

Intuitively, the following proposition follows from the ’Hadamard-like’ construction of the Grassmann, and the intersection patterns of Hadamard code.

Proposition 51 ([50, Lemmas 59,61,62]).

Let Yall=𝒮𝒫(𝒢)d, let WYall(), let QU={Z1,Z2,,Z21} be as above, with ZW=j=121Zj. For every matrix N such that W+span(N)YUall(+1) there exists unique matrices A1,A2,,A2 such that

  1. 1.

    rank(Aj)=d2+1.

  2. 2.

    N=j=12Aj.

  3. 3.

    For j=1,2,,21 the matrices Aj𝒯Zj. That is, AjZj.

  4. 4.

    The matrix A2ZW,m. That is, row(A2) (resp. col(A2)) intersects trivially with row(ZW) (resp. col(ZW)).

  5. 5.

    The function N(A1,A2,,A2) is an isomorphism

    YWall(j=121𝒯Zj)ZW,m

We restate and reprove this proposition in Section 7. The proof our decomposition lemma is short given the one from [50]. For this (and this only) we need to slightly alter Definition 40 and Definition 45 so that we take into account two posets instead of one. Let Y1,Y2 be two posets of the same dimension d.

Definition 52 (Two-poset admissible function, generalizing Definition 39).

An admissible function with respect to Y1,Y2 to be a function s:𝔽2i{0}𝔽2n×n as in Definition 39 with the distinction that the row and column spaces of the matrix Ms=v𝔽2i{0}s(v) are

row(Ms)Y1(2d2di),col(Ms)Y2(2d2di).
Definition 53 (Two-poset matrix poset, generalizing Definition 40).

We denote by 𝒮𝒫(Y1,Y2) the matrix poset defined in Definition 40 such that the admissible functions are with respect to Y1 and Y2.

Definition 54 (Two-poset sparsified link graph, generalizing Definition 45).

For W𝒮𝒫(Y1,Y2) we denote by Y1,Y2,W the graph in Definition 45, with the distinction that all sums of row spaces are required to be in Y1 and all column spaces are required to be in Y2 (instead of them all being in the same poset Y).

Proof of Lemma 46.

Fix W and its corresponding QW={Z1,Z2,,Z21} and ZW. Conditioned on W, the first step of the sampling distribution in Definition 40 is the same as sampling w1row(ZW) and w2col(ZW) (where w1,w2Y(d)). Fixing the pair w1,w2 and conditioning on all three W,w1,w2, sampling an edge in the link YU is the same as sampling an edge in the link of W in the complex 𝒮𝒫(𝒢(w1),𝒢(w2)). As both 𝒢(w1) and 𝒢(w2) are isomorphic, 𝒮𝒫(𝒢(w1),𝒢(w2))𝒮𝒫(𝒢(w1),𝒢(w1))𝒮𝒫(𝒢(w1))121212Recall that 𝒢(wi) is the Grassmann poset containing all subspaces of wi.. We are back to the complete Grassmann case and are allowed to use Proposition 51. Let (W,w1,w2) be the subgraph obtained when fixing and conditioning on W,w1,w2. By Proposition 51, we can decompose this graph to a tensor product

(W,w1,w2)(j=121𝒯Zi)𝒢(w1),𝒢(w2),W.

The first 21 components are independent of w1 and w2; they are constant among all conditionals (and are all isomorphic to 𝒯m). Hence this is isomorphic to (𝒯m)21 where is the graph corresponding to a subgraph of Y,W obtained by conditioning the edge-sampling process of Y,W to sampling w1 and w2 in the first step. Thus the graph =𝒢(w1),𝒢(w2),W and the lemma is proven.

3.4 Expansion of the sparsified link graph

In this section we use the decomposition lemma to reduce the analysis of the sparsified link graph to the case of the complete Grassmann and prove Lemma 48.

We use the following claim on the complete Grassmann.

Claim 55.

Let Yall=𝒮𝒫(𝒢)d be the poset of rank d2 matrices for a sufficiently large d. Let WYall() and let w1,w2𝒢(d) be such that row(ZW)w1,col(ZW)w2. Then λ(𝒢(w1),𝒢(w2),W))γm for some universal constant γ(0,1).

We prove this claim in the next section.

Proof of Lemma 48.

Fix the subspace WY() and recall the notation wR=row(ZW),wC=col(ZW). We intend to use Lemma 15. The local decomposition we use is the following τ=(T,μT). For every pair (w1,w2)YwR(d)×YwC(d) we define the graph G(w1,w2) which is the subgraph obtained by conditioning on (w1,w2) being sampled in the first step of Definition 45. The distribution μT is the distribution that samples w1,w2YW(d) independently. By definition of Y,W this is indeed a local-decomposition.

We observe that the subgraph of Y,W obtained by fixing w1 and w2 in the first step is just Gw1,w2=𝒢(w1),𝒢(w2),W and hence by Claim 55 it is a γm-expander.

We describe the local-to-global graph τ in Lemma 15.

  1. 1.

    T=YwR(d)×YwC(d),

  2. 2.

    V={A|rank(A)=2m,row(A)row(ZW)Y,col(A)col(ZW)Y(d2m)},

and is an edge between (w1,w2)T and AV if row(A)row(ZW)w1 and col(A)col(ZW)w2.

Observe that we only care about τ(A)=(row(A)row(ZW),col(A)col(ZW)), and any two A1,A2 with τ(A1)=τ(A2), have the same neighbor set. In other words, this graph is isomorphic to the bipartite tensor product RC𝒬1,k where R is the containment graph between YwR(d) and YwR(d2m) (resp. C and wC), and 𝒬1,k is the complete bipartite graph with k vertices on one side and a single vertex on the other side. The number k is the number of matrices A such that (row(A)row(ZW),col(A)col(ZW))=(u1,u2), for any pair of fixed subspaces u1 and u2. By Claim 21 and the fact that Y is λ-expanding, the graph G is a (0.61+dλ)12(d2m)γm, where γ<1 is some constant and the last inequality is because λ14d.

By Lemma 15, λ(Y,U)λ(G)2+O(γm)=γm.

4 Johnson complexes and local spectral expansion

In this section we construct a family of simplicial complexes which we call Johnson complexes whose degree is polynomial in their size. The underlying 1-skeletons of Johnson complexes are abelian Cayley graphs Cay(𝔽2n,([n]εn)). We prove in this section that these complexes are local spectral expanders and in particular the links of all faces except for the trivial face have spectral expansion strictly smaller than 12. We then compare the Johnson complexes with the 2-dimensional local spectral expanders constructed from random geometric graphs [74] and show that the former complexes can be viewed as a derandomization of the latter random complexes. On the way we also define Johnson Grassmann posets {Yε,n}n, analogous to the matrix posets given in Section 3.1, and prove in Section 4.4 that Johnson complexes are exactly X(𝔽2n,β(Yε,n)), which are Cayley complexes whose vertex links are basifications of Yε,ns (Definition 36).

 Remark 56.

Later in Section 7, we shall define the induced Grassmann posets which generalize both the Johnson Grassmann posets and the matrix Grassmann posets, and we shall provide a unified approach to show local spectral expansion for induced Grassmann posets. However in this section, we will present a more direct proof of local expansion that is specific to Johnson complexes.

We name our construction Johnson complexes due to their connection to Johnson graphs. In particular, all the vertex links in a Johnson complex are generalization of Johnson graphs to simplicial complexes. So we start by giving the definition of Johnson graphs and then provide the construction of Johnson complexes.

Definition 57 (Johnson graph).

Let n>k> be integers. The adjacency matrix Johnson graph J(n,k,) is the (uniformly weighted) graph whose vertices are all sets of size k inside {1,2,,n} and two sets t1,t2 are connected if |t1t2|=.

Next we define Johnson complexes. We shall use wt(x) to denote the Hamming weight of a binary string x.

Definition 58 (Johnson complex Xε,n).

Let k and be any integer. Let n and let ε(0,12] be such that 2k|εn. Let Sε,n={x𝔽2n|wt(x)=εn} (abbreviate as Sε when n is clear from context). The ε-weight Johnson complex X=Xε,n is the k-dimensional simplicial complex defined as follows.

X(0)={x𝔽2n|wt(x) is even},
X(1)={{x,x+s}|xX(0),sSε},
X(k)={{x,x+s1,,x+sk}xX(0),i[k]siSε,T[k]wt(iTsi)=εn}.

For the rest of this work, we fix k,n,ε as above.

It turns out that the weight constraints on k-faces in a Johnson complex gives rise to a Hadamard-like intersection pattern for elements in the link faces. Any (k1)-face in the link of x can be written as {x+s1,,x+sk}. If we identify each si with the set of nonzero coordinates in it, these k sets always satisfy that any two distinct sets intersect at exactly εn/2 coordinates, and in general any k distinct sis intersect at εn/2i1 coordinates. We note that this is similar to the intersection pattern of k distinct codewords in a Hadamard code.

The main result of this section is proving that all links of this complex are good expanders.

Lemma 59 (Local spectral expansion of Johnson complexes).

For any 0mk2, the link graph of any m-face in the k-dimensional Johnson complex Xε,n is a two-sided (12ε2m+1)-spectral expander. In particular, Xε,n is a k-dimensional two-sided (12ε2k1)-local spectral expander.

The key observation (Proposition 62) towards showing this lemma is that the link graphs of m-faces are the tensor product of Johnson graphs.

Once this decomposition lemma is proven, we can use the second eigenvalue bounds for Johnson graphs to show that the links are (12ε2m+1)-spectral expanders. We note that this construction breaks the 12 link expansion barrier of known elementary constructions of local spectral HDXs (discussed in the introduction). Because our construction breaks this barrier, using the Oppenheim’s trickle down theorem [87], we directly get that the 1-skeleton of the Johnson complex is also a (12ε)-spectral expander.

We now outline the rest of this section. First, we prove the link decomposition lemma Proposition 62. Then using this lemma we show that Johnson complexes are basifications of Johnson Grassmann posets. Afterwards, we apply this lemma to prove the main result. Finally, we conclude this section by comparing the density parameters of the Johnson complexes with those of spectrally expanding random geometric complexes.

4.1 Link decomposition

In this part we prove the link decomposition result. Note that by construction the links of all vertices Xε,n are isomorphic. So it suffices to focus on the link of 𝟎𝔽2n (denoted by X𝟎) to show local spectral expansion for Xε,n. The link decomposition is a consequence of the Hadmard-like intersection patterns of the faces in X𝟎 as explained earlier.

For the rest of the section, we use Ci[n] to denote the set of nonzero coordinates in a vector xi and use M to denote 2m. We now state the face intersection pattern lemma.

Lemma 60.

Let m be an integer. Given a set {x1,,xm}𝔽2n and a subset B[m], define

CB=iBCijBCj¯ and cB=|CB|.

Then {x1,,xm}X𝟎(m1) if and only if for any subset B[m],

cB={2εnMBnM1M2εnotherwise.
Proof.

We first verify that every set {x1,,xm} satisfying the M cardinality constraints above is in X𝟎(m1). Recall that by definition {x1,,xm}X𝟎(m1) if and only if they satisfy the M1 weight equations

S[m],S,wt(iSxi)=εn.

Observe that the set of nonzero coordinates in iSxi are precisely j[n] that are nonzero in odd number of vectors in {xi|iS}

Set(iSxi)=iSCi=B[m],|BS| oddCB,

and that by definition the set {CB}B[m] is a partition of [n]. Therefore the weights can be rewritten as

S[m],S,wt(iSxi)=B[m],|BS| oddcB. (4.1)

Furthermore, for any nonempty subset S there are M/2 nonempty sets B[m] whose intersection with S has odd cardinality: let t=|S|, then the number of S’s subsets of odd cardinality is

i odd(ti)=12(it(ti)(i even(ti)i odd(ti)))=12((1+1)t(11)t)=2t1.

So the total number of such B is 2t12mt=M/2. Therefore if cB=2εnM when B, then wt(iSxi)=M/22εn/M=εn. Thus under this condition {x1,,xm}X𝟎(m1).

Next we prove by induction that any {x1,,xm}X𝟎(m1) satisfies the conditions on cB. The statement trivially holds when m=0. Suppose the same statement holds for all i-faces where im2.

By (4.1), we can deduce that every {x1,,xm1}X𝟎(m2) satisfies:

S[m1],S,B:|BS| oddcB=εn. (4.2)

Then by the induction hypothesis we know that cB=4εnM for B is the unique solution to the set of constraints above.

Now consider the set of constraints for the (m1)-face {x1,,xm}. There are in total M variables and we denote them {cB,cB{m}}B[m1] where cB=|CBCm¯| and cB{m}=|CBCm|. The new variables are related to variables in {cB}B[m1] via the identity cB=cB+cB{m} . So (4.2) can be expanded as:

S[m1],S,B:|BS| oddcB=B:|BS| oddcB+B:|BS| oddcB{m}=εn. (4.3)

Additionally, via (4.1) the weight constraints wt(xm+iSxi)=εn can be rewritten as:

S[m1],S,B:|BS| oddcB+B:|BS| evencB{m}=εn. (4.4)

Finally using the constraint wt(xm)=εn, we obtain equations:

S[m1],S,B:|BS| oddcB{m}+B:|BS| evencB{m}=|Cm|=εn. (4.5)

From (4.3),(4.4),and (4.3) we can deduce that

S[m1],S,B:|BS| oddcB{m}=εn/2. (4.6)

The M/21 constraints in (4.6) are exactly the same as the set of constraints in (4.2) except that the RHS values are εn/2 instead of εn. Therefore by the induction hypothesis, the unique solution is B,cB{m}=2εnM. As a result cB=cBcB{m}=2εnM. Finally we also have cm=εn(M/21)2εnM=2εnM and c=ccm=nM1M2εn. Thus we complete the induction step.

Corollary 61.

Let m be an integer and M=2m. For any {x1,,xm}X𝟎(m1), xm’s nonzero coordinate set Cm can be decomposed into the disjoint union of M/2 sets each of size 2εn/M as follows,

Cm=ΓB[m1]CB{m}, where CB{m}=iB{m}CijB{m}Cj¯.

Applying this coordinate decomposition to vertices and edges in the link graph of any face in X𝟎, we obtain the following characterization of the graphs.

Proposition 62.

Let 0mk2 be an integer and let M=2m. For any m-face in Xε,n, the underlying graph of its link is isomorphic to J(2εMn,εMn,ε2Mn)M1J(cn,εMn,ε2Mn) where c=1M1M2ε.

Proof.

Give an m-face {x,x+x1,,x+xm} in Xε,n, we note that by construction its link is isomorphic to the link of {0,x1,,xm}. So without loss of generality we only consider m-faces of the form above and we denote such a face by t. The by definition the vertex set in the link of t can be written as

Xt(0)={xm+1|S[m+1],wt(iSxi)=εn}.

By the decomposition lemma Corollary 61, we have the following isomorphism between the link vertices and collections of disjoints sets in (nεn/M). First recall the notation CB=iBCij[m]BCj¯. Then the isomorphism ϕ:Xt(0)B[m](CBεn/M) is given by

ϕ(xm+1)={Cm+1CB}B[m].

We use ϕ(xm+1)[B] to denote the set Cm+1CB.

Similarly, using Corollary 61 we can write the edge set as:

Xt(1)={{xm+1,xm+1}xm+1,xm+1X𝟎(0),B[m],|ϕ(xm+1)[B]ϕ(xm+1)[B]|=εn2M}.

Therefore the adjacency matrix of t’s link graph has entries:

At[xm+1,xm+1]=B[m]𝟏[|ϕ(xm+1)[B]ϕ(xm+1)[B]|=εn2M].

The product structure of At gives rise to a natural decomposition into tensor products of matrices HB{0,1}(CBεn/M)×(CBεn/M) where

U,V(CBεn/M),HB[U,V]=𝟏[|UV|=εn2M].

Furthermore since every nonempty B[m] has |CB|=cB=2εMn (Lemma 60), HB is the adjacency matrix of the Johnson graph J(2εMn,εMn,ε2Mn). In the case B=, |CB|=cn (Lemma 60), and so H is the adjacency matrix of J(cn,εMn,ε2Mn). In conclusion, the link graph of t is isomorphic to the tensor product J(2εMn,εMn,ε2Mn)M1J(cn,εMn,ε2Mn).

4.2 Local spectral expansion

We now finish the local spectral expansion proof for Johnson complexes using Proposition 62 together with the following Johnson graph eigenvalue bounds and the trickle-down theorem.

Theorem 63 ([24]).

Let A be the unnormalized adjacency matrix of J(n,k,). The eigenvalues of A are λ0,,λk where

λt=i=0t(1)ti(kii)(nk+itk+it)(ti).

We note that in the theorem above λi are unnormalized eigenvalues of the Johnson graphs. In the rest of the paper when we talk about spectral expansion, we consider normalized eigenvalues whose values are always in [1,1] .

We specifically care about the second eigenvalues of the Johnson graphs with n2k. The case of n=2k is proved in [70].

Lemma 64 ([70]).

The Johnson graph J(2k,k,k/2)’s eigenvalues satisfy maxt=1,,k|λt|λ0|λ2|λ0=12k2.

In other words, the graph J(2k,k,k/2) is a two-sided 12k2-spectral expander.

For the case n>(2+η)k, we show the following lemma (proof in Appendix E):

Lemma 65.

For any constant η>0, the Johnson graph J((2+η)k,k,k/2)’s eigenvalues satisfy that maxt=1,,k|λi|λ0η2(1+η). In other words the graph is a η2(1+η)-spectral expander.

The trickle-down theorem states that local spectral expansion implies expansion of all links.

Theorem 66 ([87]).

Let λ0. Let X be a 2-dimensional connected simplicial complex and assume that for any vertex vX(0), the link Xv is a two-sided λ-spectral expander, and that the 1-skeleton of X is connected. Then the 1-skeleton of X is a two-sided λ1λ-spectral expander. In particular, X is a two-sided λ1λ local spectral expander.

Now we are ready to prove the main result of this section.

Proof of Lemma 59.

Let t be any m-face in the complex. By Proposition 62, the link graph of t is Gt=J(2εMn,εMn,ε2Mn)M1J(cn,εMn,ε2Mn). Since eigenvalues of A1A2 are {λ1λ2|λ1𝖲𝗉𝖾𝖼(A1),λ2𝖲𝗉𝖾𝖼(A2)}, by Equation 2.1 the second largest eigenvalues satisfy λ(A1A2)=max(λ(A1),λ(A2)). Therefore the link graph Gt of t has |λ|2(Gt)max(12εn/M2,12ε2(1(2M1)ε))=1212ε1(2M1)ε12(1εM) (via Lemma 64 and Lemma 65). Therefore the k-dimensional Johnnson complex Xε,n is a two-sided (12ε2k1)-local spectral expander.

Furthermore, applying the trickle-down theorem to the 2-skeleton Xε,n2 we get that the underlying graph of the complex is a two-sided (12ε)/(22ε)1(12ε)/(22ε)=(12ε)-spectral expander.

4.3 Comparison to local spectral expanders from random geometric complexes

In this part, we compare the structure of the Johnson complexes to that of the random geometric complexes from [74]. We observe that the former can be viewed as a derandomization of the latter.

The random 2-dimensional geometric complex (RGC) Geod(N,p) is defined by sampling N i.i.d. points {xi}i[N] from the uniform distribution over the d-dimensional unit sphere, adding an edge between ij if xi,xjτ where τ is picked so that the marginal probability of an edge is p, and adding a 2-face if the three points are pairwise connected. In the following parameter regime the complexes have expanding vertex links.

Theorem 67 (Rephrase of Theorem 1.6 in [74]).

For every δ<12, there exists Cδ and c=Θ(1log(1/δ)) such that when HGeod(N,N1+c) for d=CδlogN, with high probability every vertex link of H is a two-sided (12δ)-local spectral expander whose vertex links are (12δ)-spectral expanders.

The Johnson complex X:=Xε,n with N=|X(0)| can be viewed as an approximate derandomization of the RGCs in n over N vertices. Note that the points in X(0) (which are boolean vectors) embed in the natural way to n. Furthermore, these points in n all lie on a sphere of radius n2 centered at [12,,12]. Two points are connected in X if the L2 distance between their images in n is exactly εn. The distinction from edges in RGCs is that in Johnson complexes points of distance <εn are not connected. Albeit the analysis in [74] shows that most neighbors of a vertex have distance εn so this is not a significant distinction. Similar to RGCs, three points in X form a 2-face if they are pairwise connected. By Lemma 59 the resulting 2-dimensional Johnson complex X has degree Nh(ε)131313h is the binary entropy function h(p)=plog1p+(1p)log11p. and its vertex links are (12ε2)-spectral expanders.

 Remark 68.

We further observe that while both constructions yield local spectral expanders with arbitrarily small polynomial vertex degree, the link graphs of the Johnson complexes are much denser. Use N to denote the number of vertices in the complexes. Then in the Johnson complexes the link graphs have vertex degree 𝗉𝗈𝗅𝗒(N) while in the RGCs the link graphs have average vertex degree 𝗉𝗈𝗅𝗒𝗅𝗈𝗀(N). We remark that one can use a graph sparsification result due to [21] to randomly subsample the 2-face in Xε,n while preserving their link expansion. As a result we obtain a family of random subcomplexes of the Johnson complexes that are local spectral expanders with similar vertex degree and link degree as the random geometric complexes. Detailed descriptions and proofs are given in Appendix F.

4.4 Johnson Grassmann posets

In this part, we take a small digression to define the Johnson Grassmann posets Yε,n and show that their basifications are exactly Johnson complexes Xε,n.

Definition 69 (Johnson Grassmann posets Yε,n).

Let d=log2εn. For every i[d], define the admissible function set as

𝒮i={s:𝔽2i{0}𝔽2n|v𝔽2iwt(s(v))=2di,wt(v𝔽2i{0}s(v))=2d2di}.

Define the Hadamard encoding s^:𝔽2i𝔽2n of s as

s^(y)=v𝔽2i{0}y,vs(v).

For each admissible function s𝒮i, use 𝒢s to denote the Grassmann poset {Im(s^|U)|U𝔽2i,U is a subspace}

Then the Johnson Grassmann poset is Yε,n=s𝒮d𝒢s.

We first verify that these posets are well-defined.

Claim 70.

For all 1id, Yε,n(i)={Im(s^)|s𝒮i} .

Proof.

The claim trivially holds for i=d. For i<d, we need to prove that (1) for every t𝒮i, there exist s𝒮d and i-dimensional subspace U𝔽2d such that Im(t^)=Im(s^|U) and (2) for every s𝒮d, any subspace WIm(s^) is in Yε,n.

We first prove (1). Given any admissible function t𝒮i, for every v𝔽2i{0} and u𝔽2di, use et(v),u𝔽2n to denote the vector that is nonzero only at the u-th nonzero coordinate of t(v). Here we identify the vector u in a natural way with a number in [2di]. Use z to denote the sum z=v𝔽2i{0}t(v). Set U to be the subspace that spans the first i coordinates in 𝔽2d, and set s:𝔽2d{0}𝔽2n as follows

v𝔽2i,u𝔽2di,s(v,u)={et(v),uv0,e1z,uo.w.

Then it is straightforward to verify that s𝒮d and that Im(t^)=Im(s^|U).

Next we check (2). Note that the codespace Im(s^) is a d-dimensional subspace in 𝔽2n whose nonzero elements have weight 2d/2=εn. Furthermore, consider any linear subspace WIm(s^) of dimension j<d. Since s^ is an isomorphism, there exists a j-dimensional linear subspace U𝔽2d such that W=Im(s^|U) which is the image of s^ restricted to the domain U. Let ψ𝔽2d×j be a linear map from 𝔽2j to U, and ϕ𝔽2j×d be such that ϕψ=Id. Define the function sU:𝔽2j{0}𝔽2n as follows

sU(v)=vUs(ψv+v).

By construction, sU is admissible and furthermore for every y𝔽2j

s^U(y)=v𝔽2j{0}y,vvUs(ψv+v)=v′′𝔽2d{0}y,ϕv′′s(v′′)=v′′𝔽2d{0}ϕy,v′′s(v′′)=s^(ϕy).

We derive that Im(s^U)=Im(s^|U)=W. Thus WYε,n(j) and so the claim is proven.

 Remark 71.

We observe that Yε,n is a subposet of the complete Grassmann poset 𝒢(𝔽2n), and is obtained by applying the sparsification operator 𝒮𝒫 to 𝒢(𝔽2n)εn.

We now prove that Xε,n is the basification of Yε,n using the link decomposition result.

Claim 72.

The k-dimensional Johnson complex Xε,n is the k-skeleton of the basification of Yε,n.

Proof.

To prove the claim it suffices to show that any span(x1,x2,,xk)Yε,n(k) if and only if all non-empty subset T[k] has wt(iTxi)=εn. In this proof we abuse the notation a bit and identify a vector in 𝔽2n with the set of its nonzero coordinates.

For the if direction, given {x1,x2,,xk}, construct s:𝔽2k{0}𝔽2n such that s(v)=i=1kxivi where xivi is the set of nonzero coordinates of xi if vi=1, and the set of zero coordinates of xi if vi=0. By Lemma 60, all such s(v)’s have weights exactly εn/2k1. By construction their nonzero coordinates are disjoint from each other’s. So s is an admissible function. Furthermore, let {e1,e2,,ek} be elementary vectors in 𝔽2k,

s^(ei) =v𝔽2k{0}ei,vs(v)
=v, s.t.vi=1xijixjvj
=xivi𝔽2k1jixjvj
=xi[n]=xi

Therefore span(x1,x2,,xk)=Im(s^)Yε,n(k).

For the only if direction, we can easily check that any Im(s^)Yε,n(k) contains only vectors of weight εn. So given any basis {x1,x2,,xk} of Im(s^), their nonzero linear combinations all have weight εn. Now the proof is complete.

5 Coboundary expansion and a van Kampen lemma

In this section we give the necessary preliminaries on coboundary expansion and also introduce a version of the famous van Kampen Lemma [97] that shall be used to prove coboundary expansion in the next section.

5.1 Preliminaries on coboundary expansion

We define coboundary expansion for general groups, closely following the definitions and notation in [28]. For a more thorough discussion on the connection between coboundary expansion and topology, we refer the reader to [28]. In the introduction we defined coboundary expansion as a notion of local testability of a code (which was a subspace of the functions on the edges). Instead of defining coboundary expansion for only 𝔽2-valued functions, we give the most general version of coboundary expansion, which uses arbitrary groups.

Let X be a d-dimensional simplicial complex for d2 and let Γ be any group. Let X(1) be the directed edges in X and X(2) be the directed 2-faces. For i=1,0 let Ci(X,Γ)={f:X(i)Γ}. We sometimes identify C1(X,Γ)Γ. For i=1,2 let

C1(X,Γ)={f:X(1)Γ|f(u,v)=f(v,u)1}

and

C2(X,Γ)={f:X(2)ΓπSym(3),(v0,v1,v2)X(2),f(vπ(0),vπ(1),vπ(2))=f(v0,v1,v2)sign(π)}.

be the spaces of so-called anti symmetric functions on edges and triangles. For i=1,0,1 we define operators δi:Ci(X,Γ)Ci+1(X,Γ) by

  1. 1.

    δ1:C1(X,Γ)C0(X,Γ) is δ1h(v)=h().

  2. 2.

    δ0:C0(X,Γ)C1(X,Γ) is δ0h(vu)=h(v)h(u)1.

  3. 3.

    δ1:C1(X,Γ)C2(X,Γ) is δ1h(vuw)=h(vu)h(uw)h(wv).

Let Id=IdiCi(X,Γ) be the function that always outputs the identity element. It is easy to check that δi+1δihIdi+2 for all i=1,0 and hCi(X,Γ). Thus we denote by

Zi(X,Γ)=kerδiCi(X,Γ),
Bi(X,Γ)=Imδi1Ci(X,Γ),

and have that Bi(X,Γ)Zi(X,Γ).

Henceforth, when the dimension i of the function f is clear from the context we denote δif by δf.

Coboundary expansion is a property testing notion so for this we need a notion of distance. Let f1,f2Ci(X,Γ). Then

dist(f1,f2)=sX(i)[f1(s)f2(s)]. (5.1)

We also denote the weight of the function wt(f)=dist(f,Id).

Definition 73 (1-dimensional coboundary expander).

Let X be a d-dimensional simplicial complex for d2. Let β>0. We say that X is a 1-dimensional β-coboundary expander if for every group Γ, and every fC1(X,Γ) there exists some gC0(X,Γ) such that

βdist(f,δg)wt(δf). (5.2)

In this case we denote h1(X)β.

This definition in particular implies that B1=Z1 for any coefficient group.

Coboundary expansion generalizes edge expansion

We note that 1-dimensional coboundary expanders are generalizations of edge expanders to simplicial complexes of dimension 2. A graph G=(V,E) is a 1-dimensional simplicial complex. For Γ=𝔽2 we can analogously define function spaces C1(G,𝔽2),C0(G,𝔽2), C1(G,𝔽2), and operators δ1 and δ0 over G.

Observe that B0(G,𝔽2) consists of constant functions over the vertices. Using the notations above we can write the definition of a 0-dimensional coboundary expander as follows.

Definition 74 (0-dimensional coboundary expander in 𝔽2 ).

A 1-dimensional simplicial complex G=(V,E) is a 0-dimensional β-coboundary expander in 𝔽2 if for every fC0(G,𝔽2) there exists some gC1(G,𝔽2) such that

βdist(f,δ1g)wt(δ0f). (5.3)

Let us check that this is equivalent to the definition of β-edge expanders in terms of graph conductance. Viewing every function f as a partition of V into two sets Vf and Vf¯ and viewing δ0f as the indicator function of whether an edge is in the cut between Vf and Vf¯, we derive that

mingC1(G,𝔽2)dist(f,δ1g)=min(|Vf||V|,|Vf¯||V|),wt(δ0f)=|E(Vf,Vf¯)||E|.

Then the condition Equation 5.3 is equivalent to the statement that for every vertex partition (Vf,Vf¯) of the graph G=(V,E),

βmin(|Vf||V|,|Vf¯||V|)|E(Vf,Vf¯)||E|.

This is the standard definition of a β-edge expander.

Coboundary Expansion and Local Testability

One should view coboundary expansion as a property testing notion. We call B1(X,Γ)C1(X,Γ) a code (as a subset, no linearity is assumed in the general case). Given a function in the ambient space fC1(X,Γ) one cares about its Hamming distance to the code, that is, how many edges of f need to be changed in order to get a word in B1(X,Γ). Denote this quantity dist(f,B1(X,Γ)). Coboundary expansion relates this quantity to another quantity, the fraction of triangles {u,v,w} such that δf(uvw)Id, namely wt(δf).

We note that if f=δgB1(X,Γ), namely f satisfies the property of being in the function space, then one can verify that δδg=Id, or in other words, that wt(δf)=0. In a β-coboundary expander we get a robust inverse of this fact. That is, that if f is ε-far from any function in B1(X,Γ), then its coboundary is not equal to the identity on at least a βε-fraction of the triangles.

This suggests the following natural test for this property.

  1. 1.

    Sample a random triangle {u,v,w}X(2).

  2. 2.

    Accept if and only if f(uv)=f(uw)f(wv) (or equivalently δf(uvw)=Id).

Note that wt(δf(uvw)) is the probability that f fails the test. Saying that a complex is a coboundary expander is saying that this test is sound, namely X is a β-coboundary expander if and only if for every f:X(1)Γ

dist(f,B1(X,Γ))1βuvw[f fails the test]. (5.4)

Over 𝔽2, this view of coboundary expansion was first observed by [61], who used it for testing whether matrices over 𝔽2 have low rank. This view also appeared in [41] for a topological property testing notion called cover-stability. In later works, this test was as a component in the analysis of agreement tests [51, 27, 10]. We also refer the reader to [10, 29] for additional connections of coboundary expansion and local testing in the context of unique games problems and to [18] for its connection to group (te)stability.

5.2 Contractions, cycles and cones

One general approach to proving coboundary expansion is the cone method invented by [52] and used in many subsequent works to bound coboundary expansion of various complexes [77, 63, 71, 68, 28]. The following adaptation of the cone method to functions over non-abelian groups is due to [29]. We adopt their definition of cones, and after presenting the definition, we will explain the motivation behind it as well as its connection to isoperimetric inequalities of the complex.

We use ordered sequences of vertices to denote paths in X, and to denote the concatenation operator 161616If P=(v0,v1,,vm) and Q=(u0=vm,u1,,un) then their concatenation is PQ=(v0,v1,,vm,u1,,un)., and for any path P, we use P1 to denote the reverse path. Fixing a simplicial complex X, we define two symmetric relations on paths in X.

(BT)

We say that P0(BT)P1 if Pi=Q(u,v,u)Q and P1i=Q(u)Q where i{0,1}.

(TR)

We say that P0(TR)P1 if Pi=Q(u,v)Q and P1i=Q(u,w,v)Q for some triangle uwvX(2) and i=0,1.

Let be the smallest equivalence relation that contains the above relations (i.e. the transitive closure of two relations). We comment that these are also the relations defining the fundamental group π1(X,v0) of the complex X (see e.g. [95]).

We also want to keep track of the number of (TR) equivalences used to get from one path to another. Towards this we denote by P1P if there is a sequence of paths (P=P0,P1,,Pm=P) and j[m1] such that:

  1. 1.

    Pj(TR)Pj+1 and

  2. 2.

    For every jj, Pj(BT)Pj+1.

I.e. we can get from P to P by a sequence of equivalences, where exactly one equivalence is by (TR).

Similarly, for i>1 we denote by PiP if we get from P to P using i triangles.

A contraction is a sequence of equivalent cycles that ends with a single point. More formally,

Definition 75.

Let C=(v0,v1,,vt,v0) be a cycle around v0. A contraction S is a sequence of cycles S=(C0=C,C1,,Cm=(v0)) such that Ci1Ci+1 for every i=0,1,,m1. If the contraction contains m cycles, we say it uses m-triangles, or simply that it is an m-contraction.

A m-contraction can be viewed as a witness to C0m(v0).

Before giving the definition of cones which are used to prove coboundary expansion, we provide some intuition behind the connection between coboundary expansion and cones. In order to prove Equation 5.4 for a complex X, we need to upper bound the distance from any function fC1(X,Γ) to the codespace B1(X,Γ) (with δ0 being the encoding function). This is done by constructing a message gC0(X,Γ) from f and 𝒫 a family of paths from one vertex v0 to every other vertex. Note that every edge together with the two paths in 𝒫 from v0 to the edge’s endpoints form a cycle. The ratio between the probability that f fails the test and the distance from f to the codespac is bounded by these cycles’ length of contraction. The vertex v0, the family of paths, and the contractions of the induced cycles constitutes a cone. The connection between the cone and coboundary expansion of X is captured by Theorem 78 and a detailed proof can be found in [29].

Definition 76 (cone).

A cone is a triple 𝒜=(v0,{Pu}uX(0),{Suw}uwX(1)) such that

  1. 1.

    v0X(0).

  2. 2.

    For every uX(0){v0}, Pu is a walk from v0 to u. For u=v0, we take Pv0=(v0) to be the cycle with no edges from v0 to itself.

  3. 3.

    For every uwX(1), Suw is a contraction of Pu(u,w)Pw1.

The sequence Suw depends on the direction of the edge uw. We take as a convention that Swu just reverses all cycles of Suw (which is also a contraction Of the reverse cycle). Thus for each edge it is enough to define one of Suw,Swu.

The maximum length of contraction of Suw among all edges uw is called the cone area.

Definition 77 (Cone area).

Let 𝒜 be a cone. The area of the cone is

Area(𝒜)=maxuwX(1)|Suw|1.

We note that in previous works this was known as the diameter or radius of a cone [68, 29]. We chose the term “area” here since it aligns with the geometric intuition behind triangulation.

Gromov is the first to use the area of the cone to prove coboundary expansion for abelian groups. The following theorem which generalizes Gromov’s approach to general groups is by [29].

Theorem 78 ([29, Lemma 1.6]).

Let X be a simplicial complex such that Aut(X) is transitive on k-faces. Suppose that there exists a cone 𝒜 with area R. Then X is a 1(k+13)R-coboundary expander for any coefficient group Γ.

5.3 Contraction via van Kampen diagrams

In this subsection we prove a version of van Kampen’s lemma for our “robust” context. Previously, we defined the area of a cycle in the cone to be the length of its contraction sequence. The van Kampen lemma reduces the problem of bounding the contraction length of a cycle to counting the number of faces in a planar graph.

The van Kampen diagrams are an essential tool in geometric group theorem [80, Chapter V]. They were introduced by van Kampen in 1933 in the context of the word problem in groups defined by presentations [97], and are a powerful visual tool for exhibiting equivalences of words of some given group presentation. They are also used to bound the number of relations required to prove that a word is equal to identity (such a bound is called the Dehn function of a presentation). The van Kampen diagrams are plane graphs that embed into the presentation complex of a group. The van Kampen lemma states that a word is equivalent to the identity if and only if it forms a cycle in the presentation complex which can be tiled by faces in a van Kampen diagram. Furthermore the number of inner faces of the diagram provides an upper bound on the relations needed to prove that the word equals to identity. The advantage of these diagrams is that they bound the length of a sequential process by the size of static objects.

We need a similar tool in the context of abstract complexes, which is a simple generalization of the above setup. Our main motivation for this statement is give a simple and intuitive way to bound the area of cones. Previous works that use the cones, give sequences of contractions, explaining which triangle goes after another (see e.g. [29]). This is sufficient for the proof. However, in all known examples, the ordering is just a formality, and the proofs were really describing a tiling (i.e. the contraction was really just a set of faces that formed a disk whose boundary is the cycle we needed to contract). So in this section we give justification to just drawing out the tiling via a van Kampen diagram instead of giving the full sequence of contraction.

A plane graph H=(V,E) is a planar graph together with an embedding. We will denote by H both the abstract graph and the embedding.

The van Kampen lemma has a few components. First we have our simplicial complex X and a cycle C0 in X. In addition, we have a diagram. This diagram contains:

  1. 1.

    A plane graph H=(V,E) that is 2-vertex connected.

  2. 2.

    A labeling ψ:VX(0) such that for every edge {u,v}E, either ψ(u)=ψ(v), or {ψ(u),ψ(v)}X(1).

It is easy to see that a walk in H is mapped by ψ to a walk in X (possibly with repeated vertices).

Let F={f0,f1,,f} be the set of faces of H with f0 being the outer face. For every face let C~i be the cycle bounding fi, and let Ci=ψ(C~i). To be completely formal one needs to choose a starting point and an orientation to the cycle, but we ignore this point since the choice is not important to our purposes.

Refer to caption
(a) A 2-dimensional complex X.
Refer to caption
(b) A van Kampen diagram H,F of X.
Figure 1: A van Kampen diagram for X,C0.

We are now ready to state our van Kampen lemma.

Lemma 79.

Let X,C0,H, and F be as above. Assume that for every i=1,2,, the cycle Ci has an mi-triangle contraction. Then there exists an m0-triangle contraction for C0 where m0=i=1mi.

A proof of the lemma can be found in Appendix G. Here we give a simply example to demonstrate how to use this lemma. Consider the 2-dimensional complex X in Figure 1(a) with 9 vertices and 10 2-faces (all triangles in the underlying graph are 2-faces in X). Let C0=(x1,x2,x6,x5,x7,x9,x4,x1) be a cycle in X.

A van Kampen diagram H,F for X,C0 is given in Figure 1(b). H has 9 vertices and 4 faces F={f0,f1,f2,f3}. We can easily check that H is 2-vertex connected and has the natural labeling ψ(vi)=xi for i[9]{8} and ψ(v8)=x4. The labeling satisfies that ψ(C~i)=Ci for i=0,1,2,3.

Furthermore, its clear from the figure that C1, C2, and C3 have 2-triangle, 3-triangle, and 2-triangle contractions respectively. So by the van Kampen lemma, C0 has a 2+3+2=7-triangle contraction.

5.4 Cone areas and isoperimetric inequalities

In this subsection we explain the connection between cone areas and isoperimetric inequality. In a 2-dimensional simplicial complex, an isoperimetric inequality is an upper bound on the area of a cycle in terms of its length. In our context this is the following.

Definition 80 (Isoperimetric inequality).

Let X be a 2-dimensional simplicial complex and let R>0. We say that X admits an R-isoperimetric inequality if for every cycle C with edges there exists an R-triangle contraction

Area(C)RLen(C).

Isoperimetric inequalities are particularly useful in presentation complexes of Cayley graphs in geometric and combinatorial group theory [80]. Cones are closely related to isoperimetric inequalities as was already observed by [52].

We formalize the connection with this proposition.

Proposition 81.

Let X be a simplicial complex with diameter D and let R>0. Then

  1. 1.

    If X admits an R-isoperimetric inequality, then X has a cone whose area is at most (2D+1)R.

  2. 2.

    If X has a cone with area a then X admits an a-isoperimetric inequality.

Here the diameter of a complex is the diameter of the underlying graph.

Sketch.

For the first item, we construct a cone as follows. We fix an arbitrary vertex v0X(0), and as for the paths Pu, we take arbitrary shortest paths from v0 to u. Any cycle of the form Pu(u,w)Pw1 (where {u,w}X(1)) has at most 2D+1 edges. We take the smallest contraction of this cycle as Suw. By the isoperimetric inequality, Suw uses at most (2D+1)R triangles.

As for the second item, let 𝒜 be a cone with area a and let C be a cycle with m+1 edges (w0,w1,,wm,w0). Let P0,P1,,Pm be the corresponding paths from v0 to each of the vertices in w0,w1,,wm. By Lemma 79, we can contract C via the van Kampen diagram in Figure 2. We note that the boundary cycle of every inner face in the diagram corresponds to Pwi(wi,wi+1)Pwi+1 (where i/(m+1)) therefore its area is at most a. We deduce the isoperimetric inequality Area(C)a(m+1)=aLen(C).

Refer to caption
Figure 2: The second item of Proposition 81

5.5 Substitution and composition

Later in Section 6.1, we will reduce the question of bounding the cone area of some complex X to bounding that of X which contains X as a subcomplex. The relevant definitions and auxiliary proposition for this approach are given below.

Definition 82.

Let X be any complex and let X be a subcomplex of X with X(0)=X(0). A substitution is a set 𝒫={Puv|uvX(1)} of paths Puv from u to v in X such that Puv=Pvu1 (so it suffices to give one path for each pair of vertices). We say that 𝒫 is an m-substitution if all paths have length at most m.

We note that the underlying complexes X,X of a substitution are implicit in the notation, but they will always be clear in context. Via the substitution, every path in X has a corresponding path in X:

Definition 83.

Let X,X be as above and let 𝒫={Puv|uvX(1)} be a substitution. Let Q=(v0,v1,,vm) be a path in X. The composition Q~ is the path

Q~=Pv0v1Pv1v2Pvm1vm in X.

The following proposition captures the key property of this substitution.

Proposition 84.

Let X be any complex and let X be a subcomplex of X containing all vertices of X. Let 𝒫 be a substitution. Assume that for every triangle t=(u,v,w)X(2), the composition Ct~ of the 3-cycle Ct=(u,v,w,u) has an m-triangle contraction in X. Then for every cycle C in X that has an -triangle contraction in X, the composition cycle C~ in X has an m-triangle contraction .

To prove this proposition, we need the following claim about the contraction property of two cycles with shared vertices.

Claim 85.

Let Cs=P1Q1 and Ct=P2Q1 be two cycles in X such that Q is nonempty. If their difference cycle CΔ=P1P21 has an m-contraction, then there is an m-contraction from Cs to Ct.

We delay the proof of this claim and prove the proposition assuming this claim.

Proof of Proposition 84.

Let S=(C0=C,C1,,C) be the contraction in X. Let C~0,C~1,,C~k be their compositions in X. If Ci1Ci+1 via a TR relation (u,v)(u,w,v) and some BT relations in X, by Claim 85 C~imC~i+1 via the m-triangle contraction of PuvPuwPwv in X. Since there are (TR) steps in the contraction of C, we have C~mC~. Lastly, since C is a point, by definition of composition so is C~. So the proposition is proven.

Proof of Claim 85.

We first contract Cs to the intermediate cycle P1P21P2Q1=CΔCt via (BT) relations. Then we contract CΔ to a point without touching the part Ct. This procedure gives a m-contraction from Cs to Ct.

6 Coboundary expansion

Our main result in this section is proving that the Johnson complexes Xε,n and their vertex links are coboundary expanders via Theorem 78. In addition, in Section 6.3, we also show that the vertex links of the complexes constructed by [50] are coboundary expanders.

Theorem 86.

Let n and ε>0 satisfy that 4|εn. Then the 2-dimensional Johnson complex Xε is a 1-dimensional Ω(ε)-coboundary expander.

To show the statement via Theorem 78, it boils down to show that Aut(Xε) is transitive on 2-faces and that there exists a cone 𝒜 with area Θ(1ε). The first claim is straightforward. The automorphism group Aut(Xε) contains all permutations of coordinates and all translations by even-weight vectors. In particular, it is transitive on all triangles. So it is enough to bound the cone area of Xε using the following lemma.

Lemma 87.

The Johnson complex Xε has a cone 𝒜 with area Θ(1ε).

We note that by Proposition 81, this immediately implies the following corollary.

Corollary 88.

The complex Xε admits an Θ(1ε)-isoperimetric inequality.

In addition, we also show that every vertex link of Xε is a coboundary expander.

Theorem 89.

Let n and 14ε>0 satisfies that 8|εn. In the 3-dimensional Johnson complex Xε, every vertex link (Xε)v is a 1-dimensional 185-coboundary expander.

 Remark 90.

Experts may recall the local-to-global theorem in [44] which states that if a complex is both a good local-spectral expander and its vertex links are 1-dim coboundary expanders then the complex is also a 1-dim coboundary expander. So one may suspect that the coboundary expansion theorem Theorem 86 can be derived from coboundary expansion of links (Theorem 89) and local-spectral expansion of Xε (Lemma 59). However, this approach fails since the local-spectral expansion of Xε is not good enough for applying the local-to-global theorem. So instead, we prove coboundary expansion of Xε by directly using the cone method.

By link isomorphism, we can focus on the link of 𝟎 without loss of generality. Then the automorphism group Aut(X𝟎) contains all permutations of coordinates and so is transitive over X𝟎(2) (Lemma 60). By Theorem 78 it is enough to show that there exists a cone with area 85.

Lemma 91.

Let 0<ε14. Any vertex link (Xε)v has a cone with area at most 85.

As above, by Proposition 81, this implies:

Corollary 92.

A link of a vertex vXε admits an 85-isoperimetric inequality.

6.1 Constructing a bounded area cone for 𝑿𝜺

In this subsection we give a proof of Lemma 87. We take a two-step approach to showing that Xε has a cone of bounded area. First we define a related complex Xε which contains Xε as a subcomplex, and construct a cone for Xε with bounded area. Next, we replace every edge in Xε with a path in Xε between the same two endpoints. Then effectively the edges forming a triangle in Xε become a cycle in Xε. The second step is then to find a bounded-size tiling for every such cycle inside Xε.

The key proposition used in this approach is as follows.

Proposition 93 (Restatement of Proposition 84 ).

Let X be any complex and let X be a subcomplex of X containing all vertices. Let 𝒫 be a substitution. Assume that for every triangle t={u,v,w}X(2), the composition Ct~ of the 3-cycle Ct=(u,v,w) has an m-triangle contraction in X. Then for every cycle C in X that has an -triangle contraction in X, the composition cycle C~ in X has an m-triangle contraction.

This proposition implies that if for the boundary cycle Ct of every triangle tX(2), its composition Ct~ has a Θ(1)-triangle contraction in X, then the cone area of X is asymptotically the same as that of X. This lemma suggests a two-step strategy towards showing Lemma 87. First we construct a Xε which has a cone of area Θ(1/ε) (Claim 94 is proved in Section 6.1.2), and then we show that the boundary of 2-faces in Xε has Θ(1)-contraction in Xε (Claim 95 is proved in Section 6.1.3).

Claim 94.

Xε has a cone of area 16/ε.

Claim 95.

For every triangle t={u,v,w}Xε(2) whose corresponding boundary cycle is Ct=(u,v,w,u), we can contract the composition C~t in Xε using O(1) triangles.

Postponing the proofs of these lemma and claims till later subsections, we are ready to derive Lemma 87.

Proof of Lemma 87.

Claim 94 implies that the complex Xε has cone area O(1ε), while Claim 95 implies that for every triangle boundary C in Xε, its composition C~ has a O(1)-triangle contraction in Xε. By Proposition 93 we conclude that he cone area of Xε is O(1ε).

Before moving on, we consider two “patterns” of contractions shown in Figure 3(a) and Figure 3(b). They are going to be used extensively in the later proofs.

Definition 96 (Middle vertex contraction.).

A cycle C has a middle vertex contraction in a simplicial complex X if there is a vertex z so that for every edge {u,w}C, {z,u,w}X(2).

Claim 97 (Middle vertex pattern).

Let C be a length m cycle in a simplicial complex X. If C has a middle vertex contraction, then C has an m-triangle contraction.

Proof.

Given such a cycle C and a center vertex z, we can construct a van-Kampen diagram (H,ψ) for the triangles between z and edges in C, where H is the plane graph given by Figure 3(a) and ψ is the identity map. Note that H has m inner faces each corresponding to a triangle and an outer face whose boundary is C. Then by Lemma 79, C has an m-triangle contraction.

Definition 98 (Middle path contraction.).

A 4-cycle C=(v,u,w,u) has a length m middle path contraction in a simplicial complex X if there is a length m walk (u=u1,u2,,um=u) so that for every edge {ui,ui+1}, the triangles {ui,ui+1,v},{ui,ui+1,w}X(2).

Claim 99 (Middle path pattern).

Let C=(v,u,w,u) be a 4-cycle in a simplicial complex X. If C has a length m middle path contraction, then C has a 2m-contraction.

Proof.

We again construct a van-Kampen diagram (H,ψ) for the set of triangles {ui,ui+1,v},{ui,ui+1,w}X(2), where H is the plane graph given by Figure 3(b) and ψ is the identity map. Note that H has 2m inner faces each corresponding to a triangle and an outer face whose boundary is C. Then by Lemma 79, C has an 2m-triangle contraction.

Refer to caption
(a) Middle vertex contraction.
Refer to caption
(b) Middle path contraction.
Figure 3: Two contraction patterns.

6.1.1 𝑿𝜺 and its cone 𝓐

In this part, we construct a 2-dimensional simplicial complex Xε such that Xε has a 2-substitution in Xε.

Definition 100.

Let Sε={x𝔽2n|wt(x)εn,wt(x) is even}. The 2-dimensional complex Xε is given by

Xε(0)=X(0),
Xε(1)={{x,x+s}|xX(0),sSε},
Xε(2)={{x,x+s1,x+s2}|xX(0),s1,s2,s1+s2Sε}.
Claim 101.

Xε has a 2-substitution in Xε.

Proof.

For any edge (x,x+s)Xε (where sSε), find s1,s2Sε such that s=s1+s2. Such s1 and s2 can be constructed as follows: first split s=t1+t2 into two vectors of equal weight. Then take any vector r of weight εn|s|2 with disjoint support from s, and set si=r+ti. Now by setting Px,x+s=(x,x+s1,x+s1+s2=x+s), we obtain a 2-substitution for Xε(1) in Xε.

To bound the cone area of Xε, we start by constructing a cone 𝒜 for Xε. In the rest of the section we drop the subscript ε and simply write X and X. Now we introduce a few definitions in order to describe 𝒜 concisely.

Definition 102 (Monotone path).

A path P=(v0,v1,v2,,vm) in X is called monotone if vivi+1, where we identify the string with the set of coordinates that are equal to 1.

Analogously we can define monotone cycles.

Definition 103 (Monotone cycle).

A cycle C is monotone if it can be decomposed to C=P1P21 where P1,P2 are monotone paths of equal length.

Definition 104 (Lexicographic path).

Fix an ordering on the coordinates of vectors in X(0). A path P=(v0,v1,v2,,vm) in X is called lexicographic if the path is monotone and every element in vi+1vi is larger than all elements in vi under the given ordering.

We also define half-step lexicographic path.

Definition 105 (Half-step lexicographic path).

A path P=(v0,v1,v2,,vm) in X is called a half-step lexicographic path if it is a lexicographic path from v0 to vm such that all but the last edge {vi,vi+1} in the path satisfy that |vi+1vi|=εn2, while the last edge satisfies |vmvm1|εn2.

Note that if v0 and vm are connected then there is a unique half-step lexicographic path between them.

Analogously we can define half-step lexicographic cycles.

Definition 106 (Half-step lexicographic cycle).

A cycle C in X is half-step lexicographic if it can be decomposed to C=P1(x,a)(a,y)P21 where P1,P2 are half-step lexicographic paths of equal length, and that axy.

This is saying that in the half-step lexicographic cycle C, every edge {vi,vi+1} in P1 and P2 satisfies that |vi+1vi|=εn2, while the endpoints of the two paths satisfy that |ax|εn and |ay|εn.

We consider the following cone 𝒜:

Definition 107 (Cone of X).

Fix an ordering on the coordinates of vectors in X(0). Set the base vertex v0=0. For every vX(0){v0} we take Pv to be the half-step lexicographic path from v0 to v in X.

6.1.2 Bounding the area of 𝓐: proof of Claim 94

We prove that for every uvX(1), the cycle C=PuuvPv has a Θ(1ε)-triangle contraction. The strategy is to decompose C into a set of cycles in X and compose these cycles’ contractions together to obtain a contraction for C. The cycle decomposition is done by a recursive use of Lemma 79.

In the rest of the section, we will use both +, and set operations ,,,¯ (exclusion, union, intersection, and complement) over boolean strings in X(0){0,1}n. +, are entry-wise XOR for the boolean strings, while set operations are applied to the support of a string (i.e. the set of nonzero entries in the string).

The base case in the recursive argument is a monotone four-cycle, and we first show that all such cycles have Θ(1)-contraction.

Claim 108.

Let C=(v0,v1,v2,v1,v0) be any monotone four-cycle in X. Then C has a 4-triangle contraction.

Proof.

By definition of monotone cycles, v2 has size 2εn and that v1,v1v2. If |v2|εn we can contract C since {v0,v1,v2},{v0,v1,v2}X(2).

Otherwise εn<|v2|2εn, we intend to show that C has a length 2 middle path contraction. For these vertices we need to find a path between v1,v1 so that for every edge e in that path e{v0},e{v2}X(2). Let a=v1+v1. We split to cases:

  1. 1.

    If |a|εn then we just take the path to be (v1,v1).

  2. 2.

    Otherwise εn<|a|2εn. Then we split v1v1=b1Γb2 and v1v1=c1Γc2 both into equal-size parts as illustrated in Figure 4. So both a1=b1+c1 and a2=b2+c2 have size at most εn. We take the path (v1,v1+a1,v1=v1+a1+a2). Since the middle vertex v1+a1 is contained in v2 and has size between that of v1 and v1, it is connected to v2 and to 0.

By Claim 99 there is a 4-triangle contraction of the cycle.

Refer to caption
Figure 4: Partition of v1v1 in the proof of Claim 108.

The general statement for all half-step lexicographic cycles is as follows.

Lemma 109.

Let m2 and let C=(0,b1,,bm,a,cm,,c1,0) be a half-step lexicographic cycle of length 2(m+1). Then C has an (8m2)-contraction.

Refer to caption
Figure 5: Half-step lexicographic cycle decomposition in Lemma 109.
Proof.

We shall decompose C into 2m1 monotone four-cycle and 2 triangles in X as illustrated in Figure 5. Then applying Claim 108, we deduce that C has a 4(2m1)+2=8m2-contraction. To describe the decomposition, we define auxiliary vertices ai=bici for i=1,,m and am+1=a. We next argue that ai is connected to bi,ci and ai+1 in X.

First to show that for all i[m] ai is connected to bi and ci, note that |bi|=|ci|=iεn/2. Thus if |bi+ci|2εn, then |bici|=|cibi|εn and ai=bici would be connected to both bi and ci. To show |bi+ci|2εn, we observe that |cmbm||abm|εn and analogously |bmcm|εn. Now, assume for contradiction that for some i<m, |bi+ci|>2εn. Similarly we deduce that |cibi|,|bici|>εn. Suppose without loss of generality the largest element in ai comes from bi then cibi is a subset of cmbm because any element added to bm after the i-th step is larger than all elements in ci. Thus |cmbm|>εn. We arrive at a contradiction. So indeed |bi+ci|2εn, and bi and ci are both connected to ai for i[m].

To show that for all i[m1] ai is connected to ai+1, note that ai+1ai and |ai+1ai||bi+1bi|+|ci+1ci|εn. To see that am is connected to a, note that aambm and so |aam||abm|εn.

Let H be the plane graph in Figure 5 whose vertices are {0,a1,,am,b1,,bm,c1,,cm}. By construction H is a van-Kampen diagram for X with 2m+2 inner faces.

Furthermore, we note that the cycle boundaries C0=(0,b1,a1,c1,0), Cb,i=(bi,bi+1,ai+1,ai,bi) and Cc,i=(ci,ci+1,ai+1,ai,ci) for i[m1] are all monotone four cycles. Cb,m=(bm,a,am,bm) and Cc,m=(cm,a,am,cm) are two triangles. Applying Lemma 79 we deduce that C has a 4(1+2(m1))+2=8m2-triangle contraction. Thus we conclude the proof.

Refer to caption
(a) C, P1, and P2.
Refer to caption
(b) Minimal monotone cycle Cm.
Figure 6: Van-Kampen diagrams used in the proof of Claim 94.
Proof of Claim 94.

Let {u,v} be an edge in X(1) and Cuv=Pu(u,v)Pv1 be the decoding cycle. Since {u,v}X(1) it holds that |u+v|εn. Thereby |u+v|=|uv||uv||uv||v| and similarly |u+v||uv||u|. Thus the triangle {v,u,uv} is in X(2). Define the cycle C=Pu(u,uv,v)Pv1, and the monotone paths P1=Pu(u,uv) and P2=Pv(v,vu) (and C=P1P21). If both paths have equal length, then we can contract the cycle C using (16/ε2)-triangles by Lemma 109 as follows. We begin by constructing the following van-Kampen diagram Figure 6(a) to decompose Cuv into C and C′′=(u,uv,v,u): let H be the graph with vertices V(Pu)V(Pv){u,v,uv} and edges E(Pu)ΓE(Pv)Γ{{u,v},{u,uv},{v,uv}}, where V(P) denote P’s vertex set and E(P) its edge set. By definition, the plane graph H given in Figure 6(a) is a van-Kampen diagram with 3 plane graph faces. H embeds into X as illustrated by Figure 6(a). In particular, the edge boundaries of the 3 faces in H are mapped to Cuv,C, and C′′ in X. Therefore by Lemma 79, Cuv has a (16/ε1) contraction.

If P1 and P2 are of different length, we do as follows (Figure 6(b)). Assume that P1 is longer. Since |u+v|εn, the length of Pu and the length of Pv differ by at most 2. By construction, the crefix Pu that is obtained by removing the last |Pu||Pv| vertices and ends with a vertex x has |x||v|. Thus |uvx||uvv|εn. In this case, the triangle {x,u,vu}X(2) can be used to decompose Cuv. Denote the monotone cycle Cm=Pu(x,uv)(uv,y)Pv1. Again by Lemma 109, Cm has a 8(2/ε1)2-triangle contraction. Now we add (x,uv) (and also (x,u) if it is not in Pu) to the graph H. Now the van-Kampen diagram (H,Id) has 3 faces (or 4 if (x,u) is not in Pu) whose face boundaries are mapped to Cuv,Cm,(x,u,uv,x) (and potentially (x,x,u,x)). Since the last 1 (or 2) cycle has a 1-triangle contraction, Cuv has a 8(2/ε1)-triangle contraction by Lemma 79.

6.1.3 Contracting 𝑿(𝟐) with 𝑿: proof of Claim 95

We move back to consider the Johnson complex X which is a subcomplex of X.

Claim 110.

Let C=(v0,v1,v2,v1,v0) be any four-cycle in X. Then C has an 8-triangle contraction.

Note that in contrast to Claim 108 we do not assume monotonicity.

Proof.

Without loss of generality v0=0. In this case v2 has |v2|=t for some even 2t2εn. We intend to find a path between v1 and v1 and then apply the middle path contraction from Claim 99. For this we define the following graph G=(V,E).

V=N(0)N(v2)
E={{u,w}|{u,w,0},{u,w,v2}X(2)}.

We note that v1,v1V, and that if there is a length- path from v1 to v1 in this graph, then the four-cycle has a 2-triangle contraction by Claim 99.

To find such paths, we define two functions mapping tensor products of Johnson graphs to G.

ψc:Gc:=J(t,t2,t4)J(nt,εnt2,ε2nt4)G,
ψf:Gf:=J(t,t2,t4)J(nt,εnt2,ε2nt4)G,

where every vertex (u,w) in the two tensor graphs where u(v2t/2) and w([n]v2εnt/2) is mapped to ψc((u,w))=ψf((u,w))=uw. Here we implicitly identify the t elements in J(t,t2,) with the set v2, and the nt elements in J(nt,εnt2,) with [n]v2. Note that the two tensor product graphs have the same vertex space. Furthermore when t4 is an integer, the two functions are identical.

We first show that the functions give two bijections between the vertex sets: for any distinct vertices (u,w),(u,w) in the tensor product graphs, the unions uw and uw are also distinct in V. Furthermore, for any vV, v and v2v both have weight εn. This implies that |vv2|=t2 and |vv2|=εnt2. Therefore v has the preimage (vv2,vv2) under ψc. Vertex bijectivity follows.

We next show that ψc is actually a graph homomorphism. That is to say every edge in Gc is mapped to an edge in G. For every edge {(u1,w1),(u2,w2)} in Gc, we have |u1u2|=t4 and |w1w2|=ε2nt4. Subsequently

ψc((u1,w1))+ψc((u2,w2))=(u1w1)+(u2w2)=(u1+u2)(w1+w2)

has weight 2(t2t4)+2(εnt2(ε2nt4))εn=εn. Therefore {ψc((u1,w1)),ψc((u2,w2)} is an edge in G. Thus ψc is a vertex bijective graph homomorphism. A similar argument shows that the same is true for ψf.

We next use the following claim to find length-4 paths between any pair of vertices in GcGf and then transfer this property to G via ψc,ψf.

Claim 111.

Let Gc=(Vc,Ec) and Gf=(Vf=Vc,Ef) be defined as above. For any two vertices v1=(u,w) and β=(u,w) in V such that uu and ww, there is a length two path (v1,(x,y),β) in Gcf=(Vc,EcEf) such that {v1,(x,y)}Ec and {(x,y),β}Ef.

The claim immediately implies that for any pair of vertices v1,v1 in the union graph Gcf, we can find an intermediate vertex β such that the two components in β are distinct from the components in v1 and v1, and then find a length-4 path of the form (v1,α,β,α,v1) in Gcf.

We postpone the proof of the claim and conclude that using the vertex bijective graph homomorphisms ψc and ψf, such paths also exist in G. Therefore there exists a length-4 path between any two vertices v1,v1 in G. So the four-cycle has an 8-triangle contraction.

Proof of Claim 111.

When t4 is an integer, Gc=Gf. The existence of the intermediate vertex (x,y) is derived from the fact that there is a length two path between any two vertices in the Johnson graphs J(t,t2,t4) and J(nt,εnt2,ε2nt4).

Now we focus on the case when t2 is odd. Construct x as illustrated in Figure 7(a). Take axuu s.t. |ax|=|uu|2, bxuu s.t. |bx|=|uu|2, cxuu s.t. |cx|=|uu|21, and dxuu¯ s.t. |dx|=|uu¯|2171717Since uu, the sizes on the right-hand side of the size constraints are nonnegative. So these size constraints are satisfiable.. Then set x=axbxcxdx. We can verify that |ux|=t4, |xu|=t41=t4, and |x|=t4+t4=t2.

Similarly, construct y as illustrated in Figure 7(b). Take ayww s.t. |ay|=|ww|2, byww s.t. |by|=|ww|2, cyww s.t. |cy|=|ww|2+1, and dyww¯ s.t. |dy|=|ww|2. Then set y=aybycydy. We can verify that |wy|=εn2t4, |yw|=εn2t4+1=εn2t4, and |y|=|w|2+|w|2=εnt2.

Now by construction {(u,w),(x,y)}Ec and {(x,y),(u,w)}Ef, and thus we conclude the proof.

Refer to caption
(a) x=axbxcxdx.
Refer to caption
(b) y=aybycydy.
Figure 7: Construction of the intermediate vertex (x,y).

We are ready to prove the main result of this subsection

Proof of Claim 95.

Recall that by Claim 101 for every edge in {x,x+s}X(1) we can find some s1,s2Sε such that path Px,x+s=(x,x+s1,x+s1+s2=x+s). So we focus on six-cycles in X of the form C=(u,a,v,b,w,c,u) such that (u,v,w) is a triangle in X (i.e. vu,wu,vw all have weight at most εn). Let us further assume without loss of generality that u=0. Thus, C=(0,a,v,b,w,c,0) where v,w,vw all have weight at most εn.

Our plan is as follows:

  1. 1.

    We find vertices a,b,c such that (0,a,v,b,w,c,0) is a cycle in X, and such that a,b,c are neighbors of 0.

  2. 2.

    We decompose C to five four-cycles Ca,Cb,Cc,C1,C2 as illustrated in Figure 8(a). Then by Claim 110 each of the four-cycle has a 8-triangle contraction. Furthermore, the figure gives a van-Kampen diagram with C being the outer face boundary, and the four-cycles being the inner face boundaries. So applying Lemma 79, we can conclude that C has a 40-triangle contraction.

Refer to caption
(a) Decomposition of C.
Refer to caption
(b) Partition of the support of vw.
Figure 8: Decomposition and partition in the proof of Claim 95.

Now we construct a,b,c. The construction is easy when vw has even weight. In this case vw and wv also have even weight. We construct the auxiliary vertices by first evenly partitioning vw=laΓlc, vw=maΓmc and wv=raΓrc, then finding a set xvw¯ s.t. |x|=εn|vw|/2, and setting a=la+ma+ra+x, b=la+ma+rc+x, and c=lc+mc+rc+x. By construction the three vertices are adjacent to 0 and form the cycle (0,a,v,b,w,c,0) in X.

The construction becomes complicated when vw, vw, and wv have odd weights. In this case, we partially partition the supports of vw,vw, and wv as follows (Figure 8(b)):

vw =laΓlcΓsl s.t. {|la|=|vw|/2|lc|=|vw|/2
vw =maΓmcΓsm s.t. {|ma|=|vw|/2|mc|=|vw|/2
wv =raΓrcΓsr s.t. {|ra|=|wv|/2|rc|=|wv|/2

where |sl|=|sm|=|sr|=1.

Then we pick a=la+ma+ra+sm+x and c=lc+mc+rc+sm+x where x is supported over vw¯ and |x|=εn|vw|/2. Note that since |vw|=|v|+|wv||v|+|wv|2εn, the cardinality εn|vw|/20 is well defined. Define b=la+ma+rc+sm+x . We note that |va|=|lc+mc+ra+sl+x|=εn. Similarly |wc|=|lc+ma+ra+sr+x|=εn, so a and c have edges to v and w respectively. Furthermore |vb|=|lc+mc+rc+sl+x|=εn and |wb|=|la+mc+ra+sr+x|=εn. So b is connected to v and w. By construction a,b,c are all connected to 0 therefore the cycles Ca,Cb,Cc,C1,C2 all exist. Thus we complete the proof.

6.2 Cone diameter of the vertex links: proof of Lemma 91

Recall that the links of every vertex in the complex are isomorphic to one another. Therefore it is enough to prove the lemma for the link of 0. By Lemma 60, the underlying graph of the link complex is J(n,εn,ε2n), and the 2-faces are

X0(2)={{v0,v1,v2}|{v0,v1},{v1,v2},{v0,v2}X0(1) and |v0v1v2|=ε4n}.

Let us begin with the following claim.

Claim 112.

Let C=(v,u,w,u,v) be a 4-cycle in J(n,εn,ε2n) such that vw=, then C has a contraction using 4 triangles.

Proof.

We intend to use the middle path pattern from Claim 99. So let us show that there exists a path (u,z,u) such that both edges in the path form triangles with v and with w. To find z, we find separately z1=zv and z2=zw and set z=z1Γz2. To find z1 we set x1=uv,x2=uv and note that both of these have size ε2n while v has size εn. We note that |x1x2|=|x2x1| and we take z1 by taking t=min{|x1x2|,ε4} coordinates from each of x1x2,x2x1, an additional ε4nt coordinates from each of x1x2,v(x1x2). This is possible since:

  1. 1.

    |x1x2|=ε2nt and

  2. 2.

    |v(x1x2)|εn|x1x2|=εn|x2||x1x2|ε2nt .

Find z2 analogously in w. Then by construction {u,v,z},{u,v,z},{u,w,z},{u,w,z} are all in X0(2). So Claim 99 implies that C has a 4-triangle contraction.

Proof of Lemma 91.

Without loss of generality consider the link of 0. Let v0X0 be the base vertex. Since the diameter of the Johnson graph is 2, for any uX0(0){v0} we arbitrarily choose a path of length 2 from v0 to u as Pu (the existence of triangles ensures that we can do this for neighboring vertices as well). To bound the cone diameter, we consider any edge {u,u}X0(1) and its corresponding cone cycle C=Pu(u,u)Pu1. Let us re-annotate C=(v0,v1,v2,v3,v4,v0).

Let us begin by reducing to the case where v0 is disjoint from v2v3. Observe that |vi|=εn and that |vij=0i1vj||vivi1|ε2n. Thus |j=04vj|3εn and by assumption that ε14 there exists a vertex z such that z is disjoint from j=04vj.

Since the diameter of the Johnson graph is 2, we can decompose C into 5 five-cycles C0,C1,C2,C3,C4 via the van-Kampen diagram given in Figure 9(a). Then by Lemma 79, if every Ci can be contracted by m triangles, the original cycle C has a 5m-triangle contraction. So we will show next that every Ci has a contraction of 17 triangles.

Refer to caption
(a) van-Kampen diagram of C.
Refer to caption
(b) van-Kampen diagram of Ci.
Figure 9: Van-Kampen diagrams used in the proof of Lemma 91.

Re-annotate Ci=(v0,v1,v2,v3,v4,v0) such that v0 is disjoint from v2v3. We can find some v1 and v4 such that the following holds:

  1. 1.

    v1 is disjoint from v3v4.

  2. 2.

    v4 is disjoint from v1v2.

  3. 3.

    The path P=(v0,v1,v2,v3,v4,v0) is a closed walk in X0.

If such vertices exists, then Ci can be decomposed into two four-cycles Ca,Cc and a five-cycle Cb via the van-Kampen diagram in Figure 9(b). Furthermore since v0v2=v0v3=, each of the four-cycles can by contracted by 4 triangles (Claim 112). Furthermore, we will soon show that Cb has a 9-triangle contraction using the following claim.

Claim 113.

If a five-cycle C=(v0,v1,v2,v3,v4,v0) in X0 satisfies that every vertex vC is disjoint from the cycle vertices that are not neighbors of v in C, then C has a 9-triangle contraction in X0.

Before proving this claim let us complete the proof of the lemma. Applying Lemma 79 again, we can conclude that Ci has a 9+24=17-triangle contraction.

We now find such v1 and v4. Partition v0 into s1Γs2 of equal size ε2n. Then define v1=s1(v2v3) and v4=s2(v3v2). The two sets both have size εn since |s1|=|s2|=|v2v3|=|v3v2|=ε2n. It is straightforward to verify that the three properties above are satisfied. We thus complete the proof.

Refer to caption
(a) van-Kampen diagram of C.
Refer to caption
(b) Decomposition of the set v0v1v2v3v4.
Figure 10: Decomposition of C in Claim 113.
Proof of Claim 113.

Define sets a,b,c,d,e[n] to be a=v4v0,b=v0v1,c=v1v2,d=v2v3 and e=v3v4. By the assumption on the vertices, the 5 sets all have size εn2 and satisfy that v0=aΓb,v1=bΓc,v2=cΓd,v3=dΓe, and v4=eΓa. Furthermore, for each x{a,b,c,d,e} we partition it into two disjoint sets x1,x2 of size εn4 as illustrated in Figure 10(b).

Now we can decompose C into 9 triangles as illustrated in Figure 10(a) by defining v5,v6, and v7 as follows: v5=b1c1d1e1, v6=a1b1c2e1, v7=a1b1d1e2. We can verify that each of the 9 inner face in the figure has its boundary being a triangle in X0(2). Thus C has a 9-triangle contraction.

6.3 Coboundary expansion of links in the complexes of [50]

Even though most of this Section 6 is devoted to the Johnson complex, our techniques also extend to the complexes constructed by [50] that were described in Section 3. In this section we prove that the link of every vertex in these complexes are coboundary expanders.

Lemma 114.

Let Y=𝒮𝒫(𝒢(𝔽2n)d) for n>2d. Let X=β(Y) be the basification of Y. Then X has a cone with area 459 and is therefore a 1-dimensional 1459-coboundary expander.

The proof of this lemma is just a more complicated version of the proof of Lemma 91. Before proving the lemma, we give an explicit description of the link structure. The vertices are X(0)=(d2), i.e. all matrices of a certain rank d2. The edges are

X(1)={{A1,A2}|B(d4),B(A1B)(A2B)}.

Finally, the triangles X(2) are all {A1,A2,A3} such that there exist B1,B2,,B7(d8) such that the sum j=17Bj is direct, and

A1=B1B2B3B4,
A2=B1B2B5B6,
A3=B1B3B5B7.

This description is a direct consequence of the definition of admissible functions in Section 3.

We follow the footsteps of the proof of Lemma 91. Towards this we need two claims. The first proves that there exist length 4 paths between any two vertices in X, so that we can construct a cone where the cycles have constant length. This was immediate in the Johnson case but needs to be argued here. This claim also constructs length-2 paths between any two matrices that form a direct sum. we will need this later on.

Claim 115.
  1. 1.

    For any two matrices A,BX(0) there is a path of length 4 between A and B.

  2. 2.

    If AB then there is a path (A,C,B). Moreover, there exists such a path where the middle vertex C=A1B1 such that the components of this sum have equal rank and satisfy A1A and B1B181818Not all paths from A to B have this property. For instance, let e1,e2,e3,e4 be four independent vectors. Let A=e1e1+e2e2, C=e2e2+e3e3 and B=(e2+e3)e3+e4e4. One can verify that because C=(e2+e3)e3+e2(e2+e3) then (A,C,D) is indeed a path. However, we can directly check that there are no A1A,B1B such that C=A1B1..

The second claim is a a variant of Claim 112. Claim 112 bounds 4-cycles in the Johnson complex provided that two non-neighbor vertices in the cycle are disjoint. This claim is the analog for X:

Claim 116.

Let (Z,C,A,D,Z) be a 4-cycle with the following properties.

  1. 1.

    The matrices ZA are a direct sum.

  2. 2.

    We can decompose C=C1C2 and D=D1D2 such that C1,D1Z and C2,D2A.191919We note that there is no analogue to second property of the cycle in the statement 112. The analogue is that C=(C1A)(CZ) (and similarly for D). This follows from the first property in the Johnson case but we require it explicitly in this case.

Then the cycle has a tiling with O(1)-triangles.

Both of these claims are proven after the lemma itself.

Proof of Lemma 114.

It is easy to see that the complex X has a transitive action on the triangles. Therefore by Theorem 78, it suffices to find a cone whose area is 459 to prove coboundary expansion.

Let M0 be an arbitrary matrix we take as the root of our cone. We take arbitrary length 4 paths PA from M0 to every matrix AX(0). This is possible by Claim 115.

For every edge {A,A}, we need to find a contraction for the cycle PA(A,A)PA1. We note that this cycle has length 9. Therefore it suffices to show that every 9 cycle (M0,A1,A2,,A8,M0) has a tiling with 459 triangles. We begin by reducing the problem into tilings of 5 cycles instead. Indeed, observe that for every edge {Ai,Ai+1} in the cycle, dim(row(Ai)+row(Ai+1))=dim(col(Ai)+col(Ai+1))=3d4. Therefore there exists some ZX(0) such that row(Z) and col(Z) are a direct sum with row(Ai)+row(Ai+1) and col(Ai)+col(Ai+1) respectively (In fact, a random matrix Z will satisfy this with high probability for all edges in the cycle because n2d).

Refer to caption
(a) From a 9-cycle to 5-cycles.
Refer to caption
(b) Middle vertex D.
Figure 11: Decomposition of the cycles.

By Claim 115 there exists a length two path from Z to every vertex Ai in the cycle as in Figure 11(a). Therefore, by drawing these paths we can decompose our cycle into 9 cycles of length 5 of the form (Z,Ci,Ai,Ai+1,Ci+1,Z) such that the row/column spaces of Z are a direct sum with row(A1)+row(A2) and col(A1)+col(A2). This is a similar step as the one we do in Figure 9(a) in the Johnson case.

Fix a cycle as above let us denote by B the matrix such that B(A1B)(A2B). Let Z1,Z2 be of equal rank such that Z=Z1Z2. Denote by D=Z1B. We observe that {Z,D},{A1,D} and {A2,D} are all edges and therefore we can decompose this cycle into a 3-cycle (D,A1,A2,D) and two 4-cycles (Z,Ci,Ai,D,Z) that we need to tile (see Figure 11(b)).

The tiling of (D,A1,A2,D) is simple. We decompose Z1,B,A1B and A2B into a direct sum of matrices of equal rank Z1=K1K2,B=L1L2,A1B=M1M2 and A2B=N1N2. Then the matrix E=K1L1M1N1 is connected in a triangle with all three edges. so we can triangulate this three cycle using three triangles.

As for the cycles (Z,Ci,Ai,D,Z), we tile them with the claim Claim 116 using 24-triangles. Thus we can triangulate every 5-cycle using of 51 triangles. As every 9-cycle is decomposed into 9 such 5-cycles we get a total of 459 triangles, so the cone area is 459.

Proof of Claim 115.

First note that the first statement follows from the second, because for any A,B there exists some DX(0) such that AD and BD (this is because of the assumption that n>2d). Thus we can take a 2-path from A to D and then another 2-path from D to B.

Let us thus show that assuming that AB there is a 2-path from A to B. Decompose A=A1A2 of equal rank, and similarly for B=B1B2. Let C=A1B1 and take the path (A,C,B). The claim follows.

Up until now, this was largely similar to Lemma 91. Surprisingly, the proof of Claim 116 is more complicated then its Johnson analogue Claim 112. This stems from the fact the matrix domination poset is different from the matrix Johnson Grassmann poset, and in particular there isn’t a perfect analogue to set intersection in the matrix poset (this is called a meet in poset theory).

Proof of Claim 116.

We will use the middle path pattern Claim 99. We observe that C1,D1Z and D2,D2A, and we can view them as vertices in 𝒯Z and 𝒯A respectively. We will use a similar strategy as in Claim 112, and use the fact that the graph 𝒯Z has short paths between every two matrices. That is,

Claim 117.

For every m and two matrices C,D𝒯m there is a path of length 12 between C and D.

This claim is proven in the end of Section D.4.

Using this claim, we find a pair of 12-paths from Ci to Di in 𝒯Z and 𝒯A respectively: (C1,M1,M2,,M11,D1) and (C2,N1,N2,,N11,D2). Then we observe that the matrices Ki=MiNi form a path (C,K1,K2,,K11,D) from C to D in X. Moreover, every edge in this path is in a triangle with A and with Z. The claim is proven.

6.3.1 Coboundary expansion in the links and cosystolic expansion

In [50] it is proven that the Cayley complex whose link is X is not a coboundary expander for any constant β>0. It is done by proving that Z1(X,Γ)B1(X,Γ).

However, we can still prove that these complexes are cosystolic expanders. This notion is a weakening of coboundary expansion that allows the existence of cohomology, i.e. for Z1(X,Γ)B1(X,Γ):

Definition 118 (1-dimensional cosystolic expander).

Let X be a d-dimensional simplicial complex for d2. Let β>0. We say that X is a 1-dimensional β-cosystolic expander if for every group Γ, and every fC1(X,Γ) there exists some hZ1(X,Γ) such that

βdist(f,h)wt(δf). (6.1)

The difference between this definition and the definition of coboundary expansion, is that in the definition of coboundary expansion we require h=δg, or equivalently hB1(X,Γ) whereas here we only require hZ1(X,Γ) which is less restrictive.

We note that cosystolic expansion is still an important property and can sometimes be used in applications such as topological overlapping property [43] or to get some form of agreement testing guarantee [27].

Kaufman, Kazhdan and Lubotzky were the first to prove that in local spectral expanders, cosystolic expansion follows from coboundary expansion of the links [60] (together with local spectral expansion). Later on their seminal result was extended to all groups and higher dimensions [44, 63, 64, 65, 28]. In particular, we can use the quantitatively stronger theorem in [28, Theorem 1.2], to get cosystolic expansion from Lemma 114 and the local spectral expansion.

Corollary 119.

Let Y=𝒮𝒫(𝒢(𝔽2n)d) for n>2d. Let X=β(Y) be the basification of Y. Let Cay(𝔽2n,S) be the complexes whose links are isomorphic to X, as constructed in Section 3. Assume that n is sufficiently large such that Cay(𝔽2n,S) is a 104-local spectral expander. Then Cay(𝔽2n,S) is also a 1-dimensional 104-cosystolic expander.

We omit the details.

7 Induced Grassmann posets

In this subsection we will present a generalization of our Johnson and Matrix Grassmann posets. After a few preliminaries, we will present a way to construct Grassmann posets based on the Hadamard encoding. We will see that such complexes have a simple description of their links. Afterwards, we will show that on some of these complexes we can decompose the links into a tensor product of simple graphs, generalizing some of the previous results in this paper. We start with some classical facts about quotient spaces and bilinear forms.

7.1 Preliminaries on quotient spaces and bilinear forms

Quotient spaces

Let UV be a subspace. The quotient space is a vector space V/U whose vectors are the sets v+U={v+y|yU} for every vector vV. It is standard that addition (and scalar multiplication) is well defined on these sets. Addition is defined as (v+U)+(x+U)(v+x)+U and the sum of the two sets does not depend on the representatives vv+U and xx+U.

Bilinear forms

Let V1,V2 be two vector spaces. A bilinear form is a function :V1×V2𝔽2 such that

x1+x2,y1+y2=x1,y1+x1,y2+x2,y1+x2,y2

for every x1,x2V1 and y1,y2V2. A bilinear form is non-degenerate if for every 0xV1 there exists yV2 such that x,y=1, and for every 0yV2 there exists xV1 such that x,y=1.

When possible, we will work with the standard bilinear form std:𝔽2n×𝔽2n𝔽2 given by x,ystd=j=1nxjyj instead of arbitrary bilinear forms. The next claim allows us to move to this standard bilinear form.

Claim 120.

Let :V1×V2𝔽2 be a non-degenerate bilinear form. Then dim(V1)=dim(V2)=:m and there exists isomorphisms ψi:Vi𝔽2m such that x,y=ψ1(x),ψ2(y)std.

From now on, we write instead of std when it is clear from context; Claim 120 justifies the abuse of notation.

Proof sketch of Claim 120.

To see that dim(V1)dim(V2), note that from non-degeneracy the function π:V1V2 that sends x𝜋x, is an injective linear function. Swapping V1 and V2 shows that the dimensions are equal.

We observe that for every basis f1,,fm of V1 there exists a dual basis h1,,hm of V2 such that fi,hj={1i=j0ij. As for the isomorphisms, we fix some basis f1,,fm of V1 and its dual basis h1,,hmV2. Let e1,,em𝔽2m be the standard basis. It is easy to verify that the pair of isomorphisms ψ1 that sends fi to ei, and ψ2 that sends hi to ei satisfy x,y=ψ1(x),ψ2(y).

For a fixed bilinear form and a subspace UV1 the orthogonal subspace is the subspace

U={yV2|xU,x,y=0}V2,

and for a subspace UV2, one can analogously define UV1.

Definition 121 (Derived bilinear form).

Let :V1×V2𝔽2 be a non-degenerate bilinear form and let UV1 be a subspace. The derived bilinear form U:V1/U×U𝔽2 is a bilinear form given by

x+U,vU=x,v

for any x+UV1/U and vU.

It is easy to verify that x+U,vU is well defined. That is, it does not depend on the representative xx+U. It is also straightforward to verify that this derived bilinear form is non-degenerate.

Most of the time we will abuse notation and write x+U,v instead of x+U,vU when U is clear from the context.

7.2 The induced Grassmann poset - definition and running examples

In this subsection we construct a type of Grassmann posets called induced Grassmann posets. This construction generalizes the matrix Grassmann poset [50], its sparsified version in Definition 40 and the Johnson Grassmann poset in Definition 58.

Let s:𝔽2d{0}𝔽2n be a function, not necessarily linear. The induced Hadamard encoding of s is the linear map s^:𝔽2d𝔽2n where

s^(x)v𝔽2dx,vs(v)=v𝔽2d:x,v=1s(v).

We note that the inner product between any x and the 0 vector is always 0. Thus we just need to define these functions over s:𝔽2d{0}𝔽2n.

We call s^ the induced Hadamard encoding, because if n=2d1, we index the coordinates of 𝔽2n by the non-zero vectors of 𝔽2d, and set s:𝔽2d{0}𝔽2n to be the function that sends v𝔽2d{0} to the standard basis vector that is 1 on the v-th coordinate and zero elsewhere. Then s^ is the (usual) Hadamard encoding and its image is the Hadamard code.

Definition 122 (Induced Grassmann poset).

Let d,n0 be two integers such that n2d1. Let 𝒮 be a set of (non-linear) functions such that every s𝒮 is injective and the set Im(s){s(v)|v𝔽2d{0}} is independent. The 𝒮-induced Grassmann poset is the d-dimensional Grassmann poset Y𝒮 such that Y𝒮(d)={Im(s^)|s𝒮}.

To be explicit, for i<d, an i-dimensional subspace W is in Y𝒮(i) if there exists some WY𝒮(d) containing W. Equivalently, this is if and only if there exist a s𝒮 and a subspace U𝔽2d such that s^|U=W. For i=1 this says that vY𝒮(1) if and only if v=s^(x) for some s𝒮 and non-zero x𝔽2d.

We note that if the vectors in the image of s are independent, then dim(Im(s^))=d. We also note that different s,s may still result in the same spaces Im(s^)=Im(s^).

Although this definition seems abstract, hopefully, the following examples, which were already introduced in the previous sections, will convince the reader that this definition is natural.

Example 123 (The complete Grassmann).

Let d and n2d1 be positive integers. Let 𝒮 be all injective functions whose image is independent. Then Y𝒮=𝒢(F2n)d is the d-skeleton of the complete Grassmann of 𝔽2n. To see this let us show that every d-dimensional subspace W has some s𝒮 such that Im(s^)=W. Let s𝒮 be an arbitrary function and let W=Im(s^). Find some AGLn(𝔽2) that maps W to W and set s(x)A(s(x)). It is easy to verify that indeed s𝒮 and that Im(s^)=W.

Example 124 (Johnson Grassmann poset).

Let d and n2d1 be positive integers. Let E={ei}i=1n be the standard basis for 𝔽2n. Let 𝒮J be the set of injective functions from 𝔽2d to E. For this 𝒮J, the poset Y𝒮J is the Johnson Grassmann poset.

First note that a vector from 𝔽2n is in Y𝒮J(1) if and only if its Hamming weight is 2d1: every such vector w is equal to w=s^(x)=v𝔽2dx,vs(v) for some s𝒮J and x0. The s(v)’s are distinct standard basis vectors, and there are exactly 2d1 non-zero x,v in the sum. Therefore the weight of w is 2d1.

The d-dimensional subspaces are the Hadamard encoding on 2d1 coordinates inside n. Let us be more precise. Fix a map s and for simplicity assume that Im(s)={e1,e2,,e2d1}. Let W=span(Im(s)). By indexing W with the coordinates of v𝔽2d{0}, then s^(x)=(x,v)v𝔽2d{0}W, which is the Hadamard encoding of x.

The basification of this poset is an alternative description of the links of Johnson complexes.

Example 125 (Matrix poset [50]).

Let d and n2d1. Recall that (1) is the set of all rank one n×n matrices over 𝔽2. Let 𝒮 be the set of functions s:𝔽2d(1) such that the matrix Ms=(v𝔽2d{0}s(v)) is a direct sum, or in other words rank(Ms)=2d1. One can see directly that such s’s are the admissible functions of Definition 39 for the special case where the ambient poset is complete Grassmann 𝒢(𝔽2n). In this case, Y𝒮=𝒮𝒫(𝒢(𝔽2n)).202020There is a slight technical difference between this complex and the one in [50], that follows from Golowich’s use of larger fields. See [50] for more details.

To draw the analogy to the Johnson, let us illustrate that indeed a matrix A is a 1-dimensional subspace in the 𝒮-induced Grassmann poset Y𝒮 if and only if rank(A)=2d1. This follows the same logic as in the Johnson case. If AY𝒮(1) then A=s^(x) for some s𝒮 and x0. This means that A is the sum of 2d1 distinct s(v)’s. As the matrix Ms is a direct sum, the sum of the s(v)’s is also a direct sum. This implies that rank(A)=x:v,x=1rank(s(v))=2d1. On the other hand, suppose A has rank 2d1 and decomposition A=j=12d1ejfj. Take an arbitrary x𝔽2d{0} and let R={v𝔽2d|v,x=1}. As R also has size 2d1, we can find some s𝒮 that maps the elements in R to the ejfj in the decomposition of A. For such an s, we have s^(x)=vRs(v)=A, thus concluding AY𝒮(1).

The construction in [50] used matrices over a larger field of characteristic 2 instead of 𝔽2 itself. See [50] for the details.

The next example is the one given in Definition 40.

Example 126 (Sparsified matrix poset).

Let d>0 and let Y0 be any 2d1-dimensional Grassmann poset over 𝔽2n. We define a sparsification 𝒮Y0𝒮.

𝒮Y0={s𝒮|row(Ms),col(Ms)Y0(2d1)}

where Ms=(v𝔽2d{0}s(v)). The one dimensional spaces MY𝒮Y0(1) are 2d1-rank matrices such that row(M),col(M)Y0(2d1). The top-level spaces are WY𝒮(d), such that the sum of row spaces (resp. column spaces) is in Y0(2d1).

Finally, we end this subsection with the comment that if one has a distribution μ over 𝒮, this also defines a distribution over Y𝒮(d) in a natural way. That is, sampling sμ and then outputting Im(s^)Y𝒮(d). Unless otherwise stated, we will always take the uniform distribution over Y𝒮(d).

7.2.1 Subspaces of an induced Grassmann poset

Fix i<d. The subspaces Y𝒮(i) are defined by downward closure, but we can give an alternative description of Y𝒮(i) via an induced Grassmann poset with some 𝒮i that is derived from 𝒮. We begin by looking at our examples for intuition and then generalize.

In the examples above, the lower dimensional subspaces have some structure to them. For instance, one can verify that the i-dimensional subspaces in the Johnson Grassmann poset could be described as images of Hadamard encodings s^ where the image of s:𝔽2i{0}𝔽2n consists of vectors of Hamming weight 2di such that the supports of every pair s(v) and s(v) are disjoint. This generalizes the case where i=d, and the image of s𝒮J are distinct vectors of weight 1.

In a similar manner, we saw in Claim 41 that i-dimensional subspaces of the Matrix Grassmann poset are images of induced Hadamard encodings

Im(s^)={v𝔽2ix,vs(v)|x𝔽2i},

where every s(v) has rank 2di  and Ms=v𝔽2i{0}s(v) has rank 2d2di. Again, this is a natural generalization of the case where i=d.

Back to the more general setup. Recall that every WY𝒮(d) is the image of s^ for some s𝒮. The map s^ is always injective, therefore every i-dimensional subspace WW is also the image W=Im(s^|U) of some i-dimensional subspace U𝔽2d.

Let V𝔽2d be the (di)-dimensional space such that U=V, that is, U={x𝔽2d|yV,x,y=0}. Let sV:(𝔽2d/V){0+V}𝔽2n be sV(v+V)=vv+Vs(v). We use the bilinear form V to define the function sV^:U𝔽2n as the induced Hadamard encoding, i.e.

sV^(x)=v+V𝔽2d/Vv+V,xVsV(v+V).

Here we recall that v+V,xVx,v for xU (and we recall that this is independent of the choice of representative v).

Let

𝒮i={sV|s𝒮,V𝔽2d,dim(V)=di}.

We will show that for every s𝒮, Im(s^|U)=Im(sV^) and hence 𝒮i induces Y𝒮(i).

Claim 127.

For every subspace U𝔽2d, V=U, function s:𝔽2d𝔽2n, and xU, sV^(x)=s^(x). As a result, (Y𝒮)i=Y𝒮i.

Here there is some abuse of notation since the domain of sV^ is not 𝔽2i, but some arbitrary i-dimensional space U𝔽2d. However, this does not matter since we are taking the image space of sV^.

Before proving this claim, let us review our previous examples in light of this.

Example 128 (Johnson Grassmann poset).

For the Johnson Grassmann poset, fix a (di)-dimensional subspace V𝔽2d. Then a function sV𝒮J,i if and only if every value sV(v+V) has Hamming weight 2di and for every v+Vu+V the supports of sV(v+V) and sV(u+V) are mutually disjoint.

By Claim 120 we replace the functions in 𝒮i, with similar functions whose domain is 𝔽2i, without changing the resulting poset. Thus another set of functions 𝒮i such that the induced Grassmann on 𝒮i is also equal to (Y𝒮J)i is the set of all functions s:𝔽2i{0}𝔽2n such that the Hamming weight of every s(v) is 2di, and such that if vu then the supports of s(v) and s(u) are disjoint. These are exactly the admissible functions in Definition 69.

Example 129 (Matrix poset and sparsified matrix poset).

For the matrix example above let us fix some s𝒮 and (di)-dimensional subspace V𝔽2d. The matrix sV(v+V) is a direct sum of 2di rank 1 matrices. Thus rank(sV(v+V))=2di. The matrices {sV(v+V)}v+V have the property that their sum MsV=v+V0+VsV(v+V) is a direct sum, or equivalently that rank(MsV)=2d2di.222222Note that this is not the matrix Ms in Example 125, since the matrices s(v) do not participate in this sum when vV{0}.

Again by Claim 120, we can give an equivalent set of functions 𝒮i – the level i admissible functions in Section 3. These are all functions s:𝔽2i{0}𝔽2n such that rank(s(v))=2di and rank(Ms)=2d2di where Ms=v𝔽2i{0}s(v).

We remark that the sparsified matrix induced Grassmann poset 𝒮Y0 also admit a similar description of the i-spaces which was explained in Section 3.

Proof of Claim 127.

Fix s and an i dimensional subspace U. Let V=U be some di-dimensional subspace in 𝔽2d. Let xU. Note that while s^(x)=v0x,vs(v), we can remove all elements vV from the sum since x is orthogonal to them. We also recall that for every v1,v2v+V, x,v1=x,v2x,v+V so

s^(x) =vVx,vs(v)
=v+V0+Vx,v+V(vv+Vs(v))
=v+V0+Vx,v+VsV(v+V)=sV^(x).

Thus in particular for every s, Im(s^|U)=Im(s^V). As s^ is injective, every subspace WY𝒮i(i) is the image Im(s^|U) of some i-dimensional subspace U𝔽2d. The claim follows.

7.3 A decomposition for the links

Our goal is to prove that links of some induced Grassmann posets decompose into tensor products of simple graphs, reproving and extending both Proposition 51 for the matrix Grassmann poset, Lemma 46 for the sparsified matrix poset, and Proposition 62 for the Johnson Grassmann poset.

For this we need to zoom in to a less general class of induced Grassmann posets, which we call rank-based induced Grassmann posets with the direct-meet property. Let us define these.

7.3.1 Rank-based posets

Let G𝔽2n be a spanning set that does not contain 0. The rank of a vector v with respect to G, rankG(v), is the minimum number of elements in G necessary to write v as their sum.

Definition 130 (k-admissible spanning set).

We say G is k-admissible if for every v with rankG(v)k there exists some u such that rankG(v+u)=rankG(v)+rankG(u)=k.

Example 131.
  1. 1.

    For example in Johnson Grassmann posets, take G𝒥{e1,e2,,en} to be the standard basis. Then rankG𝒥(v)=wt(v) is just its Hamming weight. This set is n-admissible.

  2. 2.

    For matrix Grassmann posets, taking G(1) to be the set of rank one matrices inside 𝔽2n×n, then rankG(M)=rank(M) is its usual matrix rank. This set is also n-admissible. This second example can be extended to G being the rank one k-tensors for k>2 in 𝔽2n×n×n as well.

The following notation of a direct sum generalizes the matrix poset direct sum.

Definition 132 (Abstract direct sum).

We say that w1+w2++wj is a direct sum and write w1w2wj, if rankG(w1+w2++wj)==1jrankG(w). We also write w1w2 if w1(w2w1).

For G𝒥 we have w1w2 if and only if they are disjoint (as sets) and w1w2 if and only if w1w2. For G the definitions of M1M2 and M1M2 coincide with the direct sum and matrix domination order defined in Section 2.4. It is easy to show that for any G the relation is always a partial order.

Definition 133 (Rank r-admissible functions).

Let d be an integer. Let G be a (r(2d1))-admissible set. A rank r admissible function is s:𝔽2d{0}𝔽2n such that every s(v) has rankG(s(v))=r, and such that v𝔽2d{0}s(v) is a direct sum. The rank r admissible set of functions 𝒮G is the set containing all rank r admissible functions.

We comment that this set 𝒮 indeed gives rise to an induced Grassmann poset, because if the sum of the vectors in {s(v)}v𝔽2d{0} is a direct sum, then this set is independent. The reason is that if there is a nonempty subset A{s(v)}v𝔽2d{0} such that vAs(v)=0, then

rankG(v𝔽2d{0}s(v))=rankG(v𝔽2d(A{0})s(v))v𝔽2d(A{0})rankG(s(v))<v𝔽2d{0}rankG(s(v)),

which shows that in such a case the sum was not a direct sum in the first place.

For the rest of this section we will always assume there is some ambient (r(2d1))-admissible set G, and that 𝒮=𝒮G with respect to this set.

Definition 134 (Rank-based induced Grassmann poset).

If 𝒮 is the rank r admissible set with respect to some G, then Y𝒮 is called a rank-based induced Grassmann poset.

Example 135.

Both the Johnson Grassmann poset and the matrix Grassmann posets are rank-based induced Grassmann posets for G𝒥 and 𝒢 respectively.

Example 136 (Non example).

The d-skeleton of the complete Grassmann is not a rank-based induced Grassmann for any d2. To see this we observe that in a rank-based induced Grassmann poset Y𝒮, every wY𝒮(1) has rankG(w)=r2d12. This is because s^(x) is always a direct sum of 2d1 vectors of rank r. However, in the complete Grassmann Y(1) contains all non-zero vectors, including the vectors in G which have rank one.

7.3.2 The direct-meet property

Unfortunately, this is still too general for a meaningful decomposition lemma. For this we also need to define another property of G which we will call the direct-meet property.

Definition 137 (Meet).

The Meet of a set of elements T𝔽2n is an element Meet(T)𝔽2n such that

  1. 1.

    For every tT, Meet(T)t (in the abstract direct sum sense).

  2. 2.

    For every v𝔽2n, if vt for every tT, then vMeet(T).

This is a standard definition in poset theory. We note that Meet(T) does not necessarily exist, but if it exists it is always unique.

Definition 138 (Direct-meet property).

We say that G has the direct-meet property if for every three elements, w1,w2,w3 such that w1w2w3, the meet of {w1w2,w1w3} exists and is equal to w1.

We say Y𝒮 has the direct-meet property if it is a rank-based induced complex, where the generating set G has the direct-meet property.

We note that this definition is not satisfied by all spanning sets G.

Example 139 (Non example).

Let G={e1,e2,e3,e1+e4,e2+e4,e3+e4}𝔽24 where e1,e2,e3,e4 are the standard basis. Then G does not have the direct-meet property. To see this let w1=e1,w2=e2,w3=e3. The triple w1w2w3 is a direct sum. However, e1+e4w1+w2=e1+e2=(e1+e4)+(e2+e4) and e1+e4w1+w3=e1+e3=(e1+e4)+(e3+e4), but e1+e4⩽̸e1=w1. Hence w1 is not the meet of w1w2 and w1w3.

However, both the Johnson and the matrix sets have this property.

Example 140.

For the set G𝒥={e1,e2,,en} which defines Y𝒥, the direct-meet property holds. Indeed, the meet of any set T is the intersection Meet(T)=tTt, where we treat the vectors as sets. In particular, the meet of w1w2 and w1w3 is w1.

Example 141.

A more interesting example is the low-rank decomposition case. Let G be the set of rank 1 matrices which defines Y𝒮. Contrary to the Johnson case, there exists a set {M1,M2} with no meet. For example let e1,e2 be independent, let M1=e1e1+e2e2 and let M2=e1e1+e2(e1+e2). Both A=e1e1 and B=e2(e1+e2) are under M1 and M2 in the matrix domination order. However, A⩽̸B and B⩽̸A and therefore there is no meet for {M1,M2}. Nevertheless, the rank 1 matrices have the direct-meet property.

Claim 142.

The set G has the direct-meet property.

This claim essentially abstracts the observation in [50, Lemma 57]. We prove it in Section C.3.

Finally we state an elementary claim about the meet which we will use later on, extending the property from three elements to any finite number of elements.

Claim 143.

Let G be a set with the direct-meet property. Let T={w1,w2,,wm} be such that j=1mwj (with respect to G). Let T^={v1,v2,,vr} be linear combinations of T, i.e. vj=Ijw for some subsets Ij[m]. Then

Meet(T^)=j=1rIjw.

The proof is just an induction on the size of T^. We omit it.

7.3.3 The general decomposition lemma

We move towards our decomposition lemma for links of a rank-based Y𝒮 with the direct-meet property. Our components for the decomposition lemma are the following.

Definition 144 (z-domination graph).

Let z𝔽2n be of rank 4m. The graph 𝒯z has vertices

V={yz|rank(y)=2m},
E={{w1w2,w1w3}|rank(wi)=m,w1w2w3z}.

To sample an edge we sample a uniformly random decomposition w1w2w3w4=z, such that rank(wi)=m and output {y,y} such that y=w1w2,y=w1w3. The set of edges is the support of the the above distribution.

For 𝒢, this graph coincides with the subposet graphs introduced in Definition 43. For the Johnson Grassmann poset, this graph turns out to be the Johnson graph 𝒯zJ(4m,2m,m). This is because every vector in the graph has weight 2m and is contained in a z of weight 4m. Having y=w1w2 and y=w1w3 in this definition is equivalent to y and y intersecting on half their coordinates.

We continue with our second component.

Definition 145 (z-link graph).

Let z𝔽2n be a vector whose rank is r(2d2i) and let mr2i2. The graph z,m has vertices

V={y𝔽2n|rank(y)=2m,yz},
E={{w1w2,w1w3}|rank(wi)=m,zw1w2w3}.

We define the (weighted) edges according to the following sampling process. To sample an edge we sample a random s𝒮 such that v𝔽2ds(v)tz. Then we uniformly sample ztz such that rank(z)=4m and output a random edge in 𝒯z.

For 𝒢, this graph coincides with the disjoint graph introduced in Definition 44. For the Johnson Grassmann poset, this graph is also a Johnson graph, z,mJ(n|z|,2m,m). This is because every vector in the graph has weight 2m whose support is disjoint from z. The sampling process in this graph amounts to uniformly sampling a 4m-weighted set z that is disjoint from z, and then taking a step inside its 𝒯z. This is the same as sampling (uniformly) two subsets y,y disjoint from z that intersect on half their coordinates.

The final component we need to state the decomposition lemma is this following claim.

Claim 146.

Let Y𝒮 be a rank-based induced poset with the direct-meet property. Then for every WY𝒮(i), and s1,s2𝒮i such that Im(s1^)=Im(s2^)=W, it holds that Im(s1)=Im(s2).

We will hence denote by QW={z1,z2,,z2i1} the image set of a given W. We also denote by zW=j=12i1zj the direct sum.

This claim is a consequence of the direct-meet property. We prove it later and for now, let us proceed to the decomposition lemma.

Lemma 147 (The decomposition lemma).

Let WY𝒮(i) with QW={zj}j=12i1 and zw=j=12izj as above. Then YW𝒯z1𝒯z2𝒯z2i1zW,2i2.

We observe that this lemma applied to Y𝒮𝒥 implies Proposition 62. Applied to Y𝒮 this lemma proves Proposition 51. We can even generalize this lemma slightly more to capture the sparsified matrix case in Lemma 46. See Section 7.4 for details.

In order to prove Lemma 147, we need to define the isomorphism. To do so, we give a combinatorial criterion for a vector y being in YW𝒮(1) in terms of its meets with the elements in QW.

Claim 148.

Let WY𝒮(i) with QW={z1,z2,,z2i1} as above. Let y𝔽2n. Then y is in the link of W if and only if there exists unique y1,y2,,y2i with the following properties:

  1. 1.

    y=j=12iyj (that is, y is equal to the sum of all yj’s and this sum is direct).

  2. 2.

    All yj’s have equal rank.

  3. 3.

    yizi.

In this case the subspace W=W+span(y), has QW={zj}j=12i1{zjyj}j=12i.

Note that items 1 and 3 imply that the rank of yj is half the rank of zj.

Given Claim 148, we can define the isomorphism ψ:YW𝒯z1𝒯z2𝒯z2i1zW,2i2 by

ψ(y)=(y1,y2,,y2i), (7.1)

where the image consists of the unique yj’s promised by the claim. This function is also a bijection by Claim 148.

To conclude the proof, we need to argue that an edge {y,y} is sampled by sampling the different components yj,yj independently from one another. For this part, we basically need the following independence claim for the distribution we used when sampling s𝒮. Let P be the random variable obtained by sampling a function from 𝒮. For a set R𝔽2d, let P|R be the random variable obtained by restricting the function only to the vectors of R. Let z0𝔽2n. Then P|R and P|𝔽2dR are independent, if we condition on the event vRP|R(v)=z0.

Claim 149.

Let 𝒮 be a rank-based poset. Let R1,R2,,Rm𝔽2d{0} be a partition. Let z1,z2,,zm1𝔽2n be such that rank(zi)=|Ri|r and z1z2zm1.

Consider the joint random variables {Pi=s|Ri}i=1m. Then conditioned on the event that for every i=1,2,,m1

vRiPi(v)=zi,

these random variables are independent.

We prove the lemma first, then go back to show the sub-claims.

Proof of Lemma 147.

Let us denote by 𝒢=𝒯z1𝒯z2𝒯z2i1zW,r2i2. We define a map ψ:YW𝒮(1)𝒢 mapping y(y1,y2,,y2i) as in (7.1). That is, the yj’s are as in Claim 148. By Claim 148, this map is well defined for every y and sends link vertices into the vertices of 𝒢. Moreover, by Claim 148 this is also a bijection, since the map

ψ1(y1,y2,,y2i)j=12iyj

is indeed onto Y¯W𝒮(1) according to the claim.

Next we prove that a pair {y,y} is an edge in YW𝒮 if and only if {ψ(y),ψ(y)} is an edge in 𝒢 (ignoring any edge weights for now). Recall that {y,y} is an edge in YW𝒮 if and only if yYW𝒮J(1) where W=W+span(y). By Claim 148, QW={yj}j=12i{zjyj}j=12i1. Let us re-index tjQW’s with

tj,b={yjb=0zjyjb=1.

for (j,b)([2i1]×{0,1}){(2i,0)}. Moreover, by applying Claim 148 to W we have that yYW𝒮(1) if and only if:

  1. 1.

    We can decompose y=(j,b)[2i]×{0,1}yj,b such that the rank of every summand is equal.

  2. 2.

    For every (j,b)(2i,1), yj,btj,b.

  3. 3.

    The final y2i,1 is a direct sum with zW (the sum of all elements in QW).

So on the one hand, if ψ(y),ψ(y) are neighbors in the tensor product 𝒢, we can take yj,0=Meet(yj,yj) and yj,1=Meet(yj,zjyj) which will satisfy the above property (and is well defined by the properties of 𝒯zj and the direct-meet property). This shows that being an edge in 𝒢 implies being an edge in YW𝒮.

For the reverse direction, suppose there exists such a decomposition of y. Then for every zj the vectors w1=yj,0,w2=yj,1,w3=tj,0yj,0 and w4=tj,1yj,1 have that w1w2=yj and w1w3=yj. In addition they have equal rank and their direct sum is equal to zj. Thus {yj,yj} is an edge in 𝒯zj. For the final component, a similar argument applies: We decompose w1=y2i,0, w2=y2iy2i,0 and w3=y2i,1. All three vectors have rank 2i2 and have a direct sum. Furthermore, y2i=w1w2 and y2i=w1w3. As a result {y2i,y2i} is an edge in zW,r2i2. Thus {ψ(y),ψ(y)} is an edge in 𝒢.

Finally, we note that we can sample {y,y} by sampling every pair {yj,yj} independently. Indeed, when sampling an edge in the link of W, we are conditioning on sampling some s𝒮 so that for a fixed (di)-dimensional subspace V0, the image of sV0:𝔽2d/V0{0}𝔽2n is fixed. For every j2i1, there exists some v+V0 such that {yj,yj} depend only on the values of vV0 (this is the v+V0 such that yj,yjsV0(v+V0)). For the final component {y2i,y2i}, this edge only depends on s restricted to (0+V0){0}. By Claim 149, the values of s on the respective parts in each coset v+V0 are independent once all values of sV0 have been fixed. We conclude that indeed ψ is an isomorphism.

We conclude this subsection with the proofs of Claim 146, Claim 148 and Claim 149.

Proof of Claim 146.

We will prove something even stronger. With the notation in the claim, we show that there exists some AGLi(𝔽2) such that s2(x)=s1(Ax)232323Note that a priori s1 and s2 could have different domains, so technically A is an isomorphism between the domain of s1 and that of s2.. Let s1,s2𝒮i be such that Im(s1^)=Im(s2^)=W and such that without loss of generality the domain of s1 and s2 is 𝔽2i{0}. Observe that by Claim 143, Meet({s^(y)|y𝔽2i,x,y=1})=s(x), since the subset on the left consists of direct sums of a bunch of s(x), and s(x) is the only common component in these sums of s^(y).

Now assume that Im(s2^)=Im(s1^). This implies that there is an isomorphism B such that s1^(x)=s2^(Bx). On the other hand, by the above

s1(x) =Meet({s1^(y)|y𝔽2i,x,y=1})
=Meet({s2^(By)|y𝔽2i,x,y=1})
=Meet({s2^(By)|By𝔽2i,x,B1By=1})
=y=ByMeet({s2^(y)|y𝔽2i,x,B1y=1})
=Meet({s2^(y)|y𝔽2i,(B1)x,y=1})
=s2((B1)x).

Set A=(B1) and we got s1(x)=s2(Ax). We note that the above proof used the intersection patterns of the Hadamard code.

Proof of Claim 148.

Let s𝒮 and U𝔽2d be such that Im(s^|U)=W and let UU be such that Im(s^|U)=W. Write V=Vspan{b} such that U=V and U=V. We recall that every v+V𝔽2d/V can be partitioned into two cosets of V, v+V=v+VΓ(v+b)+V and therefore sV(v+V)=sV(v+V)+sV((v+b)+V). By the fact that sV𝒮i this sum is also direct.

We first prove the only if direction. Let xUU be such that s^(x)=y. By Claim 127, it also holds that sV^(x)=y. By the fact that xUU, the inner product x,b=1 and therefore, x,v+Vx,(v+b)+V. This implies that for every v0+V0+V, exactly one of yj{sV(v0+V),sV((v0+b)+V)} satisfies yjy. Indeed:

y =sV^(x)
=v+V0+Vx,v+VsV(v+V)
=v0v0+V0+V(x,v0+VsV(v0+V)+x,(v0+b)+VsV(v0+b+V)).

Assume that x,v0+V=1 and thus x,(v0+b)+V=0 (the other case is similar). In this case, because this whole sum is a direct sum every non-zero component in the sum is dominated by y. In particular sV(v0+V)y. Moreover, any component that does not appear in this sum is a direct sum with y, and in particular sV(v0+b+V)⩽̸y.

Thus we re-index zj=sV(v+V) (arbitrarily) and set yj to be the component where yjy and yjsV(v+V)=zj. We also set y2i=sV(b) and note that y2i also participates in the linear combination of sV^(x) because x,b=1. All yj’s have rank 2di1 and by the discussion above, we have that y=j=12iyj. Moreover, yjzj for every j2i1 and y2i is a direct sum with the sum of zj’s. Thus, QW={sV(v+V)|v+VV}={yj}j=12i{zjyj}j=12i1 by construction. Finally, we note that the when the admissible functions come from a rank-based construction that has the direct-meet property, then yj=Meet(y,sV(v0+V)) for some v0+V. Thus, the yj’s are unique.

Conversely, let us assume that the three items hold and prove that WY(i+1). Let s𝒮i be such that Im(s^)=W. Recall that 𝒮i+1 consists of all functions s whose image contains vectors of rank 2di whose sum is a direct sum. Therefore, let us construct such a function s:𝔽2i+1𝔽2n satisfying Im(s^)=W. First, we re-index the elements yj as yv’s for every v𝔽2i{0} (but keep the notation y2i as before) so that yvs(v). For an input (b,v)(𝔽2×𝔽2i){0},

s(b,v)={s(v)yvb=0,v0yvb=1,v0y2ib=1,v=0.

It is easy to see that the image of s is {yj}j=12i{zjyj}j=12i1, and these vectors form a direct sum and they all have rank 2di1. Thus we successfully construct a s𝒮i+1. Moreover, one readily verifies that s^(1,0)=v𝔽2is(1,v)=j=12iyj=y and that for U′′={(0,v)|v𝔽2i} we have that Im(s^|U′′)=W. Thus Im(s^)=W.

Proof of Claim 149.

It suffices to prove that Pi is independent of P[m]{i} where P[m]{i} denotes the rest of the random variables. For any i=1,2,,m1, the distribution for Pi is uniform over all partial functions s0:Ri𝔽2d satisfying (1) vRi rank(s0(v))=r, and (2) vRis0(vi)=zi. This follows from the fact that for any fixed conditioning of the form Pj=s|(𝔽2d{0})Ri where the image of Pj sum up to zj for all ji, all such functions s0 have equal probability density.

For i=m, a similar argument applies. Conditioned on P1=s|R1,P2=s|R2,,Pm1=s|Rm1 (where the sum of each s|Ri’s values equals zi), the last partial function s|Rm is sampled by picking a uniformly random (ordered) set of rank r elements t1,t2,,t|Rm| satisfying that (j=1m1zj)(j=1|Rm|tj). It is obvious that the distribution of Pm is independent of the specific functions assigned to P1,P2,,Pm1.

7.4 The distribution over admissible functions

We can extend the decomposition lemma above to a slightly more general setup. In this setup we sample s𝒮 according to a specified distribution instead of sampling it uniformly. Let 𝒮 be a set of admissible functions. Let μ be a probability density function of 𝒮. We say that μ is permutation invariant if for every s𝒮 and every permutation π of 𝔽2d{0}, μ(s)=μ(sπ). Such a μ induces the following measure over the d-dimensional subspaces Y𝒮(d) in the rank-based induced poset: first sample sμ, and then outputs Im(s^). We call posets obtained by this process measured rank-based posets.

The sparsified matrix poset is an example of a measured rank-based posets, where the distribution μ of admissible functions is given by the following:

  1. 1.

    Sample W1,W2Y0(2d1) independently.

  2. 2.

    Sample s uniformly at random such that row(v𝔽2d{0}s(v))=W1 and col(v𝔽2d{0}s(v))=W2.

For general Y0, this distribution μ is nonuniform, and the resulting poset is a measured rank-based poset. Hence this more generalized definition captures the sparsified matrix poset in Definition 40.

For such posets we can prove a version of the decomposition lemma using the following variants of the graphs from Definition 145.

Definition 150 ((z,μ)-link graph).

Let z𝔽2n be of rank 2d2i and let m2i2. The graph zμ has vertices

V={y𝔽2|rank(y)=2m,yz},
E={{w1w2,w1w3}𝔽2|rank(wi)=m,zw1w2w3}.

The edge distribution is given by: first sample a random vector sμ conditioned on t:=v𝔽2d{0}s(v)z. Then uniformly sample a zt of rank 4m and finally output an edge in 𝒯z according to the distribution in that graph.

Lemma 151.

Let Y𝒮 be a measured rank-based poset with the direct-meet property. Then for every WY𝒮(i) with QW={z1,z2,,z2i1} and zW=j=12i1zj defined as before,

YW𝒮𝒯z1𝒯z2𝒯z2i1zW,r2i2μ.

The proof of this lemma follows the exact same argument in the proof of the decomposition lemma Lemma 147. Therefore we omit the proof for brevity.

References

  • [1] Vedat Alev, Fernando Jeronimo, and Madhur Tulsiani. Approximating constraint satisfaction problems on high-dimensional expanders. In Proc. 59th IEEE Symp. on Foundations of Computer Science, pages 180–201, November 2019. doi:10.1109/FOCS.2019.00021.
  • [2] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289–304, 1992. doi:10.1002/RSA.3240030308.
  • [3] Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Structures & Algorithms, 5(2):271–284, 1994. doi:10.1002/RSA.3240050203.
  • [4] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence i: Modified log-sobolev inequalities for fractionally log-concave distributions and high-temperature ising models. arXiv preprint, 2021. arXiv:2106.04105.
  • [5] 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. doi:10.1145/3313276.3316385.
  • [6] Anurag Anshu, Nikolas P Breuckmann, and Chinmay Nirkhe. Nlts hamiltonians from good quantum codes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1090–1096, 2023. doi:10.1145/3564246.3585114.
  • [7] Sanjeev Arora and Madhu Sudan. Improved low degree testing and its applications. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 485–495, El Paso, Texas, 1997. doi:10.1145/258533.258642.
  • [8] Mitali Bafna, Max Hopkins, Tali Kaufman, and Shachar Lovett. Hypercontractivity on high dimensional expanders. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 185–194, 2022. doi:10.1145/3519935.3520040.
  • [9] Mitali Bafna, Noam Lifshitz, and Dor Minzer. Constant degree direct product testers with small soundness, 2024. arXiv:2402.00850.
  • [10] Mitali Bafna and Dor Minzer. Characterizing direct product testing via coboundary expansion. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1978–1989, 2024. doi:10.1145/3618260.3649714.
  • [11] Mitali Bafna, Dor Minzer, and Nikhil Vyas. Quasi-linear size pcps with small soundness from hdx. arXiv preprint, 2024. doi:10.48550/arXiv.2407.12762.
  • [12] Cristina M Ballantine. Ramanujan type buildings. Canadian Journal of Mathematics, 52(6):1121–1148, 2000.
  • [13] Imre Bárány. A generalization of carathéodory’s theorem. Discrete Mathematics, 40(2-3):141–152, 1982. doi:10.1016/0012-365X(82)90115-7.
  • [14] Yonatan Bilu and Nathan Linial. Constructing expander graphs by 2-lifts and discrepancy vs. spectral gap. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 404–412. IEEE, 2004. doi:10.1109/FOCS.2004.19.
  • [15] Endre Boros and Zoltán Füredi. The number of triangles covering the center of an n-set. Geometriae Dedicata, 17:69–77, 1984.
  • [16] Donald I Cartwright, Patrick Solé, and Andrzej Żuk. Ramanujan geometries of type an. Discrete mathematics, 269(1-3):35–43, 2003.
  • [17] Michael Chapman, Nathan Linial, and Peled Yuval. Expander graphs — both local and global. Combinatorica, 40:473–509, 2020. doi:10.1007/s00493-019-4127-8.
  • [18] Michael Chapman and Alexander Lubotzky. Stability of homomorphisms, coverings and cocycles i: Equivalence, 2023. arXiv:2310.17474.
  • [19] Michael Chapman and Alexander Lubotzky. Stability of homomorphisms, coverings and cocycles ii: Examples, applications and open problems, 2023. arXiv:2311.06706.
  • [20] 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, 2021.
  • [21] Fan Chung and Paul Horn. The spectral gap of a random subgraph of a graph. Internet Mathematics, 4(2-3):225–244, 2007. doi:10.1080/15427951.2007.10129296.
  • [22] David Conlon. Hypergraph expanders from cayley graphs. Israel Journal of Mathematics, 233(1):49–65, 2019.
  • [23] David Conlon, Jonathan Tidor, and Yufei Zhao. Hypergraph expanders of all uniformities from cayley graphs. Proceedings of the London Mathematical Society, 121(5):1311–1336, 2020.
  • [24] Philippe Delsarte and Vladimir I. Levenshtein. Association schemes and coding theory. IEEE Transactions on Information Theory, 44(6):2477–2504, 1998. doi:10.1109/18.720545.
  • [25] Yotam Dikstein. New high dimensional expanders from covers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 826–838, 2023. doi:10.1145/3564246.3585183.
  • [26] Yotam Dikstein and Irit Dinur. Agreement testing theorems on layered set systems. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science, 2019.
  • [27] Yotam Dikstein and Irit Dinur. Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers. CoRR, abs/2308.09582, 2023. doi:10.48550/arXiv.2308.09582.
  • [28] Yotam Dikstein and Irit Dinur. Coboundary and cosystolic expansion without dependence on dimension or degree. CoRR, abs/2304.01608, 2023. doi:10.48550/arXiv.2304.01608.
  • [29] Yotam Dikstein and Irit Dinur. Swap cosystolic expansion. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1956–1966, 2024. doi:10.1145/3618260.3649780.
  • [30] Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean functions on high-dimensional expanders. arXiv preprint arXiv:1804.08155, 2018. arXiv:1804.08155.
  • [31] Yotam Dikstein, Irit Dinur, and Alexander Lubotzky. Low acceptance agreement tests via bounded-degree symplectic hdxs, 2024. URL: https://eccc.weizmann.ac.il/report/2024/019/.
  • [32] Yotam Dikstein and Max Hopkins. Chernoff bounds and reverse hypercontractivity on hdx. arXiv preprint arXiv:2404.10961, 2024. doi:10.48550/arXiv.2404.10961.
  • [33] Irit Dinur. The pcp theorem by gap amplification. Journal of the ACM (JACM), 54(3):12–es, 2007.
  • [34] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Good locally testable codes. arXiv preprint arXiv:2207.11929, 2022. doi:10.48550/arXiv.2207.11929.
  • [35] Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani. Explicit sos lower bounds from high-dimensional expanders. In 12th Innovations in Theoretical Computer Science (ITCS 2021), 2021. arXiv:2009.05218.
  • [36] Irit Dinur and Elazar Goldenberg. Locally testing direct products in the low error range. In Proc. 49th IEEE Symp. on Foundations of Computer Science, 2008.
  • [37] Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma. List-decoding with double samplers. SIAM journal on computing, 50(2):301–349, 2021. doi:10.1137/19M1276650.
  • [38] 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. doi:10.1109/FOCS.2017.94.
  • [39] Irit Dinur, Siqi Liu, and Rachel Yun Zhang. New codes on high dimensional expanders. arXiv preprint arXiv:2308.15563, 2023. doi:10.48550/arXiv.2308.15563.
  • [40] Irit Dinur and Inbal Livni Navon. Exponentially small soundness for the direct product z-test. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pages 29:1–29:50, 2017. doi:10.4230/LIPICS.CCC.2017.29.
  • [41] Irit Dinur and Roy Meshulam. Near coverings and cosystolic expansion. Archiv der Mathematik, 118(5):549–561, May 2022. doi:10.1007/s00013-022-01720-6.
  • [42] Dominic Dotterrer and Matthew Kahle. Coboundary expanders. Journal of Topology and Analysis, 4(04):499–514, 2012.
  • [43] Dominic Dotterrer, Tali Kaufman, and Uli Wagner. On expansion and topological overlap. Geometriae Dedicata, 195:307–317, 2018.
  • [44] Shai Evra and Tali Kaufman. Bounded degree cosystolic expanders of every dimension. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 36–48, 2016. doi:10.1145/2897518.2897543.
  • [45] Ofer Gabber and Zvi Galil. Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407–420, 1981. doi:10.1016/0022-0000(81)90040-4.
  • [46] Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang. Eigenstripping, spectral decay, and edge-expansion on posets. arXiv preprint arXiv:2205.00644, 2022. doi:10.48550/arXiv.2205.00644.
  • [47] Howard Garland. p-adic curvature and the cohomology of discrete subgroups of p-adic groups. Ann. of Math., 97(3):375–423, 1973. doi:10.2307/1970829.
  • [48] Oded Goldreich and Shmuel Safra. A combinatorial consistency lemma with application to proving the PCP theorem. In RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science. LNCS, 1997.
  • [49] Louis Golowich. Improved Product-Based High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.38.
  • [50] Louis Golowich. From grassmannian to simplicial high-dimensional expanders. arXiv preprint arXiv:2305.02512, 2023. doi:10.48550/arXiv.2305.02512.
  • [51] Roy Gotlib and Tali Kaufman. List agreement expansion from coboundary expansion, 2022. arXiv:2210.15714.
  • [52] M. Gromov. Singularities, expanders and topology of maps. part 2: from combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal., 20:416–526, 2010. doi:10.1007/s00039-010-0073-8.
  • [53] Anna Gundert and Uli Wagner. On eigenvalues of random complexes. Israel Journal of Mathematics, 216:545–582, 2016.
  • [54] Tom Gur, Noam Lifshitz, and Siqi Liu. Hypercontractivity on high dimensional expanders. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 176–184, 2022. doi:10.1145/3519935.3520004.
  • [55] Christopher Hoffman, Matthew Kahle, and Elliot Paquette. The threshold for integer homology in random d-complexes. Discrete & Computational Geometry, 57:810–823, 2017. doi:10.1007/S00454-017-9863-1.
  • [56] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006.
  • [57] Max Hopkins and Ting-Chun Lin. Explicit lower bounds against ω(n)-rounds of sum-of-squares. arXiv preprint arXiv:2204.11469, 2022. doi:10.48550/arXiv.2204.11469.
  • [58] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. New direct-product testers and 2-query PCPs. SIAM J. Comput., 41(6):1722–1768, 2012. doi:10.1137/09077299X.
  • [59] 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. doi:10.1145/3406325.3451126.
  • [60] Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Isoperimetric inequalities for ramanujan complexes and topological expanders. Geometric and Functional Analysis, 26(1):250–287, 2016.
  • [61] Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. In Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 501–506, 2014. doi:10.1145/2554797.2554842.
  • [62] Tali Kaufman and David Mass. High dimensional random walks and colorful expansion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017.
  • [63] Tali Kaufman and David Mass. Good distance lattices from high dimensional expanders. (manuscript), 2018. arXiv:1803.02849.
  • [64] Tali Kaufman and David Mass. Unique-neighbor-like expansion and group-independent cosystolic expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.
  • [65] Tali Kaufman and David Mass. Double balanced sets in high dimensional expanders. arXiv preprint arXiv:2211.09485, 2022. doi:10.48550/arXiv.2211.09485.
  • [66] Tali Kaufman and Izhar Oppenheim. Construction of new local spectral high dimensional expanders. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 773–786, 2018. doi:10.1145/3188745.3188782.
  • [67] Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap. Combinatorica, 40:245–281, 2020. doi:10.1007/S00493-019-3847-0.
  • [68] Tali Kaufman and Izhar Oppenheim. Coboundary and cosystolic expansion from strong symmetry. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 84:1–84:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.84.
  • [69] Tali Kaufman and Ran J Tessler. Garland’s technique for posets and high dimensional grassmannian expanders. arXiv preprint, 2021. arXiv:2101.12621.
  • [70] Mikhail Koshelev. Spectrum of johnson graphs. Discrete Mathematics, 346(3):113262, 2023. doi:10.1016/J.DISC.2022.113262.
  • [71] Dmitry N Kozlov and Roy Meshulam. Quantitative aspects of acyclicity. Research in the Mathematical Sciences, 6(4):1–32, 2019.
  • [72] Wen-Ching Winnie Li. Ramanujan hypergraphs. Geometric & Functional Analysis GAFA, 14:380–399, 2004.
  • [73] Nathan Linial and Roy Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475–487, 2006. doi:10.1007/S00493-006-0027-9.
  • [74] Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang. Local and global expansion in random geometric graphs. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 817–825, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3564246.3585106.
  • [75] Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang. High-dimensional expanders from expanders. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, page 12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
  • [76] Alexander Lubotzky. Expander graphs in pure and applied mathematics. Bulletin of the American Mathematical Society, 49(1):113–162, 2012.
  • [77] Alexander Lubotzky, Roy Meshulam, and Shahar Mozes. Expansion of building-like complexes. Groups, Geometry, and Dynamics, 10(1):155–175, 2016.
  • [78] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. doi:10.1007/BF02126799.
  • [79] Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Explicit constructions of ramanujan complexes of type ad. European Journal of Combinatorics, 26(6):965–993, 2005. doi:10.1016/J.EJC.2004.06.007.
  • [80] Roger C Lyndon, Paul E Schupp, RC Lyndon, and PE Schupp. Combinatorial group theory, volume 89. Springer, 1977.
  • [81] Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, pages 581–606, 2002.
  • [82] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families i: Bipartite ramanujan graphs of all degrees. Annals of Mathematics, 182:307–325, 2015. doi:10.4007/annals.2015.182.1.7.
  • [83] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families ii: Mixed characteristic polynomials and the Kadison-Singer problem. Annals of Mathematics, pages 327–350, 2015.
  • [84] Grigorii Aleksandrovich Margulis. Explicit constructions of concentrators. Problemy Peredachi Informatsii, 9(4):71–80, 1973.
  • [85] Roy Meshulam and Nathan Wallach. Homological connectivity of random k-dimensional complexes. Random Structures & Algorithms, 34(3):408–417, 2009. doi:10.1002/RSA.20238.
  • [86] Ryan O’Donnell and Kevin Pratt. High-dimensional expanders from chevalley groups. In Shachar Lovett, editor, 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 of LIPIcs, pages 18:1–18:26. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CCC.2022.18.
  • [87] Izhar Oppenheim. Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps. Discrete & Computational Geometry, 59(2):293–330, 2018. doi:10.1007/S00454-017-9948-X.
  • [88] Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 375–388. ACM, 2022. doi:10.1145/3519935.3520017.
  • [89] Mark S Pinsker. On the complexity of a concentrator. In 7th International Telegraffic Conference, volume 4, pages 1–318, 1973.
  • [90] Ran Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763–803, June 1998. doi:10.1137/S0097539795280895.
  • [91] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 475–484, New York, NY, USA, 1997. ACM. doi:10.1145/258533.258641.
  • [92] Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. doi:10.1145/1391289.1391291.
  • [93] Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 3–13. IEEE, 2000. doi:10.1109/SFCS.2000.892006.
  • [94] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. doi:10.1137/S0097539793255151.
  • [95] David Surowski. Covers of simplicial complexes and applications to geometry. Geometriae Dedicata, 16:35–62, April 1984. doi:10.1007/BF00147420.
  • [96] Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 238–251, 2017. doi:10.1145/3055399.3055408.
  • [97] Egbert R Van Kampen. On some lemmas in the theory of groups. American Journal of Mathematics, 55(1):268–273, 1933.

Appendix A The decomposition lemma

Proof of Lemma 15.

Let us denote by AG,At the adjacency operators of G,Gt respectively. We also denote by A the bipartite adjacency operator of Bτ. That is, for a function f:V, Af:T is the function Af(t)=𝔼vμt[f(v)]. We note that by assumption, for every f:V such that 𝔼v[f(v)]=0, Af2λ22f2.

Let f:V be an eigenvector of AG of norm 1 and denote its eigenvalue by μ. Then

|μ| =|f,AGf|=𝔼{u,v}μG[f(u)f(v)]
=|𝔼tμT[𝔼{u,v}μt[f(u)f(v)]]|
=|𝔼tμT[ft,Atft]|

where ft is the restriction of f to the vertices of Vt. Let us denote ft=ft0𝟏+ft such that ft0𝟏 is a constant and ftft0𝟏. Then by expansion,

|𝔼tμT[(ft0)2+γft,ft]|
=|𝔼tμT[(1γ)(ft0)2+γft,ft]|
=(1γ)|𝔼tμT[(ft0)2]|+γ|𝔼vV[f(v)2]|
=(1γ)|𝔼tμT[(ft0)2]|+γ.

Here first equality is algebra, the second is because μG(v)f(v)2=vtμT(t)μt(v)f(v)2 and the last equality is due to the fact that f has norm 1. Finally, we note that the constant ft0=𝔼vμt[f(v)]=Af(t). That is

=(1γ)Af2+γ(Af2λ22)γ+(1γ)λ22.

Appendix B Intermediate subspaces of the expanding matrix Grassmann poset

In this appendix we prove that the intermediate subspaces in the Grassmann matrix poset come from level i-admissible functions.

Claim (Restatement of Claim 41).

Let Y be as in Definition 40. Then

Y(i)={Im(s^)|s𝒮i}.

For this proof we recall the preliminaries in Section 7 on quotient spaces and bilinear forms.

Proof of Claim 41.

Fix d and d=logd. It is enough to prove that W{Im(s^)|s𝒮i} if and only if there exists WY(d) such that WW (i.e. if and only if WY(i)). We start with some WY(i) and prove that W{Im(s^)|s𝒮i}. Let WY(d) be such that ww. Let s𝒮d be such that Im(s^)=W. The matrices in the image of s are linearly independent 242424Here we say matrices are linearly independent if they are linear indpendent as vectors in 𝔽2n2. since their sum has maximal rank. Hence s^:𝔽2dW is an isomorphism. From this there exists some i-dimensional subspace U𝔽2d so that W=Im(s^|U). We write U=V for some (di)-dimensional subspace V (with respect to the standard bilinear form). Let us define s:(𝔽2d/V){[0]}𝔽2n×n as

s(v+V)=vv+Vs(v).

It is direct to check that s is admissible, since every vv+Vs(v) is a disjoint sum of 2di rank one matrices, and the sum Ms=v+V0+Vs(v+V) is also equal to

Ms=vVs(v)

which has rank 2d2di and whose row and column spaces are in Y1 and Y2 respectively, since it is contained in the row and column space of Ms=v0s(v). We can also define s^:U𝔽2n×n as

s^(x)=v+V𝔽2d/V{[0]}x,v+Vs(v+V).

Here the inner product is the derived inner product as in Section 2.2. We note that s^(x)=s^(x) because

s^(x) =v+V(𝔽2d/V){[0]}x,v+Vs(v)
=v+V(𝔽2d/V){[0]}x,v+Vvv+Vs(v)
=()v+V(𝔽2d/V){[0]}vv+Vx,vs(v)
=v𝔽2d{0}x,vs(v)=s^(x)

where () is because the derived inner product x,v+V is equal to (the standard) inner product x,v for every vv+V. Even though the function s is defined over U which is not equal to 𝔽2i, and s^ is defined through the derived bilinear form (not the standard one), by Claim 120 we can find an admissible s′′ so that Im(s′′^)=Im(s^). This proves that w{Im(s^)|s𝒮i}.

As for the converse direction, “reverse engineer” the proof above. Let W{Im(s^)|s𝒮i}, and we show that WY(i). Let s𝒮i be such that Im(s^)=W. Let Ms=v𝔽2i{0}s(v) and let W1(Y1)row(Ms)(d1),W2(Y2)col(Ms)(d1). These spaces exist from the purity of Y1 and Y2. We define s𝒮d as follows. For every v𝔽2i{0} we (arbitrarily) find a decomposition of s(v) into rank one matrices, and index them by x𝔽2di. That is, s(v)=x𝔽2diexfx. We set s(v,x)=exfx. For v=0𝔽2i we define s using W1 and W2. We find space W1 and W2 such that row(S)Wj=Wj and ordered bases e1,e2,,e2di1 to W1 and f1,f2,,f2di1 to W2. We (arbitrarily) re-index these bases as {ex|x𝔽2di0} and {fx|x𝔽2di0} and set s(0,x)=exfx. It is a direct definition chase to verify that s is admissible, i.e. that Ms=(v,x)𝔽2d{0}s(v,x) has rank 2d1 and its row and column spaces are equal to W1 and W2 respectively. Finally, the image of s^ restricted to U={(x,0)|x𝔽2i} is w since

s^(x,0) =(v,v)𝔽2i×𝔽2di{(0,0)}(x,0),(v,v)s(v,v)
=v𝔽2i{0}x,vv𝔽2dis(v,v)
=v𝔽2i{0}x,vs(v)=s^(x).

Thus W=Im(s^)Y(d) and it contains W=Im(s^|U), so WY(i).

Appendix C Elementary properties of matrix poset

C.1 Domination is a partial order

Let us begin by showing that this relation is a partial order. We do so using this claim.

Proof of Claim 25.

The implications of (4)(2) and (3)(2) are a direct consequence of the definitions. Let us see that (1)(2).

rank(A+B) =dim(row(A+B))
dim(row(A)+row(B))
=dim(row(A))+dim(row(B))dim(row(A)row(B))
=rank(A)+rank(B)dim(row(A)row(B)).

This shows that if rank(A+B)=rank(A)+rank(B) then row(A)row(B)={0} (and similarly for the column space).

Finally, let us see that (2)(1),(3),(4). Assume that row(A)row(B),col(A)col(B) are trivial. Let us write r1=rank(A),r2=rank(B). Then we can write A=i=1r1eifi and B=i=1r2gihi and because the row and column spaces intersect trivially, we have that {ei}Γ{gi} and {fi}Γ{hi} are r1+r2 sized sets that are independent, thus proving (4) (which implies (3)). This also shows that rank(A+B)=dim(col(A+B))=rank(A)+rank(B), thus proving (1).

Proof of Claim 26.

By Claim 25, XY if and only if col(X)col(Y) and row(X)row(Y) are {0}. So first of all note that if C(BA) then row(C)row(BA)={0} (and the same for the column space). By Claim 25 row(BA)=row(B)row(A), so in particular row(C)row(B)={0} (resp. col(C)col(B)={0}). Thus, CB.

Now let us show that A(BC). By Claim 17, if row(A)row(B) and row(C)(row(A)row(B)) then row(A)(row(B)row(C)) (resp. column spaces). Thus by Claim 25 A(BC).

Proof of Claim 24.

We need to verify reflexivity, anti-symmetry and transitivity. Let A,B,C be matrices.

  1. 1.

    Reflexivity is clear.

  2. 2.

    Anti-symmetry: assume that AB and BA this implies that rank(BA)=rank(A)rank(B)=rank(B)rank(A)=0 so A=B.

  3. 3.

    Transitivity: CB and BA. Then by Claim 25, row(A)=row(B)row(AB). In addition this claim shows that row(BC)row(B). Together this implies that row(BC) intersects trivially with row(AB). The same holds also for the column spaces. Thus by Claim 25 this implies that rank(AC)=rank(AB)+rank(BC), i.e. ACAB. Thus,

    rank(A) =(BA)rank(B)+rank(AB)
    =(CB)(rank(C)+rank(CB))+rank(AB)
    =(ABAC)(rank(C)+rank(CB))+(rank(AC)rank(BC))
    =rank(C)+rank(AC).

 Remark 152.

Recall the following definition from partially ordered set theory.

Definition 153 (Rank function).

Let (A,) be a poset. A rank function ρ: is a function with the following properties.

  1. 1.

    If A>B then ρ(A)>ρ(B).

  2. 2.

    For every A>B there exists AC>B so that ρ(C)=ρ(B)+1.

A poset is called a graded poset if there exists a rank function for that poset.

The order of matrices is also a graded poset, where the matrix rank is the rank function. To see this, we note that if AB, then rank(A)=rank(B)+rank(AB) so in particular rank(A)rank(B) and if AB, rank(A)>rank(B). Moreover, if A>B then by the fourth item of Claim 25, we can write A=B(j=1tejfj) for some t>0. Taking C=B(ejfj) concludes that the rank function (of matrices) is a rank function (of the graded poset).

C.2 Isomorphism of intervals

We begin with this claim.

Claim 154.
  1. 1.

    Let AB,C. Then BC if and only if BACA.

  2. 2.

    Let B,C be such that BA and CA. Then BC if and only if BACA.

Proof.

For the first item,

B C
rank(C)=rank(B)+rank(CB)
rank(C)rank(A)=rank(B)rank(A)+rank(CB)
(AB,C)rank(CA)=rank(BA)+rank((CA)(BA))
BACA.

For the second item,

B C
rank(C)=rank(B)+rank(CB)
rank(C)+rank(A)=rank(B)+rank(A)+rank(CB)
rank(CA)=rank(BA)+rank((CA)(BA))
BACA.

Proof of Proposition 28.

By Claim 154 the bijection ψ maps A such that AM2 to A=AM1 such that AM2M1. Therefore ψ is well defined as a function from I(M1,M2) to I(0,M2M1). Obviously ψ is injective (since it is injective over the set of all matrices). Moreover, if M1A1A2M2 then by Claim 154 the order is maintained, i.e. A1=A1M1A2M1=A2. The fact that rank(A)=rank(A)rank(M1) follows from M1A. Thus to conclude we need to show that ψ is surjective, or in other words, if AM2M1 then A+M1M2. Let AM2M1. Then by Claim 25 row(A)+row(M2M1A)=row(M2M1) and in particular row(A)row(M2M1) and similarly col(A)col(M2M1). By M1M2, we have that rank(M2)=rank(M1)+rank(M2M1) and by Claim 25 this implies that row(M2M1)row(M1)={0} and similarly for the columns spaces. We conclude that row(A)row(M1) and col(A)col(M1) are trivial. By using Claim 25 we have that for A=ψ1(A)=A+M1,

rank(A)=rank(A)+rank(M1)

or equivalently that AM1. Finally, we also have that AM2 by Claim 154 (as A,M2M1 and A=AM1M2M1). Thus ψ is surjective since A is a preimage of A inside {A|M1AM2}.

Proof of Claim 30.

Fix A and note that BA if and only if AA+B. Thus ϕ is a bijection. The order preservation follows from the second item of Claim 154.

C.3 The matrices have the direct-meet property

In this subsection we prove Claim 142.

Proof of Claim 142.

The technical statement we shall use in the proof is the following: For any matrices A,BC such that row(A)row(B) and col(A)col(B), it holds that AB.

Let us first show that this statement implies the direct meet property. Let M1,M2,M3 be three matrices whose sum is direct. We observe that row(M1)=row(M1M2)row(M1M3)252525It is clear that row(M1)row(M1M2)row(M1M3). The other direction follows from a dimension count. and similarly col(M1)=col(M1M2)col(M1M3). Consider any A such that AM1M2 and AM1M3. Observe that row(A)row(M1M2)row(M1M3). Thus row(A)row(M1). The same argument applies to the respective column spaces, and so by the technical statement above AM1. This implies that the set G has the direct meet property.

Now we prove the statement itself. Observe that row(BA)row(B) and col(BA)col(B). Moreover, (CB)B which means that row(CB) (respectively col(CB)) intersects trivially with row(B) (respectively col(B)). Thus (CB)(BA). So we get

rank(CA)=rank((CB)+(BA))=rank(CB)+rank(BA).

On the other hand, because A,BC, the equality above can be rewritten as

rank(C)rank(A)=rank(C)rank(B)+rank(BA)

or equivalently rank(B)=rank(A)+rank(BA) i.e. AB.

Appendix D Properties of the graphs induced by the matrix poset

In this appendix we prove Lemma 47 and Claim 55 necessary to prove the expansion of the complexes constructed in Section 3. We also prove Claim 117 necessary for the coboundary expansion proven in Section 6. To do so, we need to take a technical detour and provide some further definitions that generalize the graphs in said statements. In Section 3 we defined some graphs that naturally arise from the relations and . To analyze them, we need to generalize these definitions.

Definition 155 (Relation graph).

Let i<jn. The relation graph (i,j)=(L,R,E) is the bipartite graph whose vertices are L=(i),R=(j) and {A,B}E if AB.

This is the analogous graph to the “down-up” graph in simplicial complexes, i.e. the graph whose vertices are X(i) and X(j) (for some simplicial complex X) and whose edges are all pairs {s,t} such that st (see e.g. [38]).

Another important graph is the following “sum graph”.

Definition 156 (Sum graph).

Let i,j,k be integers such that ki,j and i+jkn. The Sum graph 𝒮(i,j,k)=(L,R,E) is the bipartite graph whose vertices are L=(i),R=(j) and {A,B}E if there exists C(k) such that C(AC)(BC) are a direct sum.

When k=0 we denote this graph by 𝒟𝒮(i,j)𝒮(i,j,0). In this case its definition simplifies: AB if and only if AB.

All the aforementioned graphs turn up when one analyzes the Grassmann graph defined in Section 3. However, the bulk of the analysis in Section 3 is on links of the Grassmann complex. There the graphs that appear are actually subgraphs of these graphs. Hence, we also make the following definitions of the graphs where we take U or D as our underlying posets instead of all .

Definition 157 (Upper bounded relation graph).

Let i<jn. Let U(). The graph U(i,j)=(L,R,E) is the bipartite graph whose vertices are L=U(i),R=U(j) and {A,B}E if AB.

Note that for every U1,U2(), the graphs U1(i,j),U2(i,j) are isomorphic. So when we do not care about the matrix we write (i,j) instead of U(i,j).

The graphs 𝒟𝒮U(i,j) and 𝒮U(i,j,k) are defined analogously as the subgraphs of matrices in U:

Definition 158 (Upper bounded sum graph).

Let i,j,k, be integers such that ki,j and i+jk. Let U(). The Sum graph 𝒮U(i,j,k)=(L,R,E) is the bipartite graph whose vertices are L=U(i),R=U(j) and {A,B}E if there exists C(k) such that C(AC)(BC)U.

In these cases we also write 𝒟𝒮(i,j),𝒮(i,j,k) when we do not care about U.

The second type of localization is with respect to subspaces.

Definition 159 (Lower bounded local relation graph).

Let i,j, be integers such that i<jn. Let D(). The graph D(i,j) is the subgraph of (i,j) whose vertices are in D.

Definition 160 (Lower bounded sum graph).

Let i,j,k, be integers such that ki,j and i+jkn. Let D(). The Sum graph 𝒮D(i,j,k)=(L,R,E) is the bipartite graph whose vertices are L=D(i),R=D(j) and {A,B}E if there exists C(k) such that DC(AC)(BC) (is a direct sum).

In the next section we prove upper bounds on the expansion of some of these graphs. In all the following claims γ(0,1) stands for universal constants which we don’t calculate (and may change between claims). The main lemmas we need are these.

Lemma 161.

λ2(𝒮(i,j,k))γ(jmax(k,ik)).

Lemma 162.

Let i,j,k, be such that ij and 2in. Let D(). Then λ2(𝒮D(i,j,k))γ(njmax(k,ik)).

In order to prove these lemmas we need to analyze the other graphs as well. More specifically, we will use Lemma 15 to reduce the analysis of the 𝒮 graphs to the expansion of the and 𝒟𝒮 graphs. The bounds we need for Lemma 161 are these.

Claim 163.

Let i,j. Then λ2(𝒟𝒮(i,j))ijγ(ij).

Claim 164.

Let U(). The graph U(i,j) is isomorphic to 𝒟𝒮(i,j). Consequently by Claim 163 λ2((i,j))γ(ji).

For Lemma 162 we will also need this claim.

Claim 165.

Let i,j, be such that ij2 and nj. Let D(). Then λ2(D(i,j))γj.

The proofs of all these claims are all quite technical, and while most of the proof ideas repeat themselves among claims, we did not find one proof from which to deduce all claims. More details are given in the next subsections. We conclude this sub section with the short proofs of Lemma 47 and Claim 55, that were necessary to prove the main theorem in Section 3. They follow directly from Lemma 161 and Lemma 162.

Proof of Lemma 47.

The double cover of 𝒯m is 𝒮4m(2m,2m,m). Thus by Lemma 161 and Observation 14 λ(𝒯m)=λ2(𝒮4m(2m,2m,m))=γm.

Proof of Claim 55.

Careful definition chasing reveals that the double cover of (𝒢(w1),𝒢(w2),W) is (isomorphic to) 𝒮ZW(2m,2m,m). Indeed, assume for simplicity that w1=w2=𝔽2n. Thus the vertices in the double cover of (𝒢(w1),𝒢(w2),W) are two copies of ZW(2m). This is because by Claim 25, ASW if and only if row(A)row(ZW),col(A)col(ZW) are a direct sum. Hence by Observation 14 it is enough to argue about the bipartite expansion of 𝒮ZW(2m,2m,m).

We observe that AA in 𝒮ZW(2m,2m,m) if and only if AA in (𝒢(W1),𝒢(W2),W). Matrices A and A are connected in (𝒢(w1),𝒢(w2),U) when there exists UZW(4m) such that AA𝒮U(2m,2m,m). This is equivalent to existence of B1,B2,B3,B4(m) such that B1B2B3B4ZW(4m) with A=B1B2 and A=B1B3 (the sum of Bi’s is U). Observe that B4 is redundant in this definition, that is, it is enough to require that there exists B1,B2,B3(m) such that B1B2B3ZW(3m) with A=B1B2 and A=B1B3. This is because if we are given these B1,B2,B3 as so, we can always find a suitable B4. By writing B2=AB1 and B3=AB1, we get that A,A are connected in (𝒢(w1),𝒢(w2),W), if and only if ZWB1(AB1)(AB1). This is exactly the definition of the edges in 𝒮ZW(2m,2m,m).

Thus by Lemma 162 λ((𝒢(w1),𝒢(w2),W))=λ2(𝒮ZW(2m,2m,m))γ(d0dim(W)3m)=γm.

D.1 Expansion of the upper bound local graphs

We begin by showing how Lemma 161 and Lemma 162 reduce to the other claims by Lemma 16.

Proof of Lemma 161.

Fix U() and i,j,k. We intend to use Lemma 16. We index our components by (k), where every component GC will be the graph containing edges {A,B} such that C(AC)(BC)U. We claim that GC𝒟𝒮UC(ik,jk), by the map AAC. Indeed, by Proposition 28 the vertices in GC, which are CU(i)ΓCU(j) map isomorphically to the vertices of 𝒟𝒮UC(ik,jk). Moreover, by Claim 154 C(AC)(BC)U if and only if (AC)(BC)UC.

Thus GC𝒟𝒮UC(ik,jk) and by Claim 163 we conclude that λ2(GC)γ(k(jk)(ik))=γ(j(ik)).

The corresponding bipartite decomposition graph of (say) the right-side is the graph τ,R=(V,T,E) given by:

  1. 1.

    V=U(j).

  2. 2.

    T=U(k).

  3. 3.

    E={(A,C)|AC}.

This is precisely U(j,k). By Claim 164 this graph is an γ(jk)-spectral expander. Therefore by Lemma 16, λ2(𝒮U(i,j,k))γ(jmax(k,ik)).

Proof of Lemma 162.

We use Lemma 16. Our components will be GU=𝒮U(i,j,k) for all UD(n). We observe that sampling an edge by sampling UD(n) and then sampling an edge in 𝒮U(i,j,k), results in a uniform distribution over the edges of D(i,j,k). By Lemma 161 every such component has λ2(GU)γ(njmax(k,ik)).

We note that the (say) left side of the bipartite decomposition graph is the bipartite graph τ,L=(V,T,E) with:

  1. 1.

    V=D(i).

  2. 2.

    T=D(n).

  3. 3.

    E={(B,U)|BU}.

This is precisely D(i,n). By Claim 165, λ2(D(i,n))γ(ni)γ(njmax(k,ik)) so by Lemma 16,

λ2(𝒮D(i,j,k))γ(njmax(k,ik)).

Let us also give a short proof for Claim 164.

Proof of Claim 164.

Fix i,j, and U(). For notational convenience let U(i,j)=(L,R,E) and 𝒟𝒮U(i,j)=(L,R,E). We define ϕ:LΓRLΓR to be

BL,ϕ(B)=BandAR,ϕ(A)=UA.

Let us first show that indeed ϕ bijectively maps the vertices L,R to L,R respectively. For L this is clear. Moreover, AU if and only if UAU, and in this case rank(A)=j if and only if rank(UA)=rank(U)rank(A)=j. Thus ϕ is a bijection of the vertex sets in every side.

Next we verify that {A,B}E if and only if {UA,B}E. Indeed, {A,B}E if and only if BAU. By definition of , this is if and only if A=B(AB) and U=A(UA), or more compactly, B(AB)(UA)=U. On the other hand, B(UA)U if and only if B(UA)(AB)=U, and thus {A,B}E if and only if {UA,B}E. The isomorphism is proven.

In the next subsections we give proofs to Claim 163 and Claim 165, are more technical.

D.2 Bounding the expansion of the direct sum graphs

The proof of Claim 163 is by induction on the sum of matrix ranks, i+j. We begin with the base case.

Claim 166.

λ2(𝒟𝒮U(1,1))O(212).

The base case follows from the fact that the walk in 𝒟𝒮U(1,1) is close to the uniform random walk as in Corollary 11.

Proof of Claim 166.

Without loss of generality let us assume that U=I, the identity matrix whose rank is . For vectors x,y𝔽2 x,y=j=1xjyj the standard bilinear form over 𝔽2, which we sometimes abuse notation and call an “inner product”. Golowich observes the following

Claim 167 ([50, Lemma 66]).

Let I the identity matrix of rank . A matrix AI if and only if A=i=1′′eifi for some ′′ and {ei}i=1′′,{fi}i=1′′ such that

ei,fj={1i=j0ij.

Thus 𝒟𝒮U(1,1) is (isomorphic to) the bipartite graph where L={(e,f)𝔽22|e,f=1}, R is a disjoint copy of L, and we connect (e,f)(e,f) if and only if e,f=e,f=0 (i.e. we move from ef to (e,f)). We will use Corollary 11 and show that the two step walk in this graph is O(2)-close to the uniform graph, thus proving that λ2(𝒟𝒮U(1,1))O(212). For concreteness we will use the two step walk from L to L.

Let us fix an initial vertex (e0,f0) and let μ be the distribution over vertices in the two step walk. Let J be the uniform distribution over vertices. We want to show that μJ=vV|μ(v)1|V||O(2).

The basic idea is this: we prove below that the probability that we traverse from (e0,f0) to (e2,f2) essentially only depends on whether e0=e2, and whether f0=f2 (and not on e2 or f2 themselves). While this is not true per se, it is true up to some negligible probability. Then we use the large regularity to bound the probability that (e2,f2) has e0=e2 or f0=f2 by O(2). This asserts that μ is (almost) uniform on a set that contains all but a negligible fraction of the vertices, which is enough to show closeness to J. Details follow.

We record for later the following observations.

Observation 168.
  1. 1.

    If (e,f)L then e,f0.

  2. 2.

    |L|=(21)21.

  3. 3.

    The graph is D=(211)22-regular.

The first two observations are immediate, but we explain the third: fixing (e,f), we count its neighbors (e,f). There are 211 choices for e since it is perpendicular to f and non-zero. Given e, the vector f satisfies

e,f=1ande,f=0.

Note that e,e are linearly independent since both are non-zero and e,fe,f. There are 22 solutions to these linear equations hence the graph is (211)22-regular.

Let (e2,f2) be any vertex. The first crude bound we give on the is just by regularity. For any (x,y)V, μ(x,y)1D=1(211)22. This bound is tight when (e0,f0)=(e2,f2). Similarly, if either e0=e2 or f0=f2 then we also just bound μ(e0,f0)1(211)22; there are at most 2 such pairs.

Now let us assume e2e0,f2f0 and calculate more accurate upper and lower bounds on μ(e2,f2) by counting how many two paths there are from (e0,f0) to (e2,f2), or equivalently, how many (e1,f1)R are common neighbors of (e0,f0),(e2,f2).

Given e0,e2, the vector e1 needs to satisfy f0,e1=f2,e1=0. The two vectors f0,f2 are linearly independent by assumption that they are both distinct and non-zero. Thus there are 221 non-zero e1-s that satisfy f0,e1=f2,e1=0.

Fixing e1 the vector f1 needs to satisfy e0,f1=e2,f1=0 and e1,f1=1. If e0,e1,e2 are linearly independent then there are exactly 2m3 solutions to these equations, all of them are non-zero, and every such solution corresponds to a common neighbor (e1,f1). If they are not linearly independent we claim that there is no solution. We note that every pair must be linearly independent: All three are non-zero vectors. Moreover, e0,e2 are distinct vectors by assumption, and similarly e1e0 (resp. e1e2) because f0,e0f0,e1 (resp. f2,e2f2,e1). Every pair of distinct non-zero vectors are independent. Thus, if there is a dependency then e1=e0+e2, and so the first two equations imply that e1,f1=0, so there is no solution.

We conclude that the number of paths from (e0,f0) to (e2,f2) is one of the following.

  1. 1.

    (221)23=22523 - if e0+e2 is not a valid solution in the first step, i.e. either f0,e0+e20 or f2,e0+e20.

  2. 2.

    (222)23=22522 otherwise.

We have that for every such pair,

μ(e2,f2)=225((211)22)22b((211)22)2,

for b{2,3}. This implies that μ(e2,f2)=1|V|+ε1+ε2 for

|ε2|=|2b((211)22)2|263

and

|ε1| |224((211)22)21|V||
=2(325)(22)2(21)2263

Thus in particular,

μJ(e0,e2)1 =e2=e0f2=f0|μ(e2,f2)1|V||+e2e0andf2f0|μ(e2,f2)1|V||
2(211)22+22(ε1+ε2)
2(24+27)282.

The claim now follows from Corollary 11.

Now we prove Claim 163. As mentioned before, the proof is by induction on i+j. A similar induction was done in [26] when analyzing the so-called swap walk, a generalization of the Kneser graph to high dimensional expanders. In the inductive step, one uses Lemma 16 to reduce the analysis of (i,j) to that of (i1,j) (which holds true by the inductive assignment). Details follow.

Proof of Claim 163.

We show that if i>1 then

λ2(𝒟𝒮(i,j))λ2(𝒟𝒮1(i1,j))+λ2(𝒟𝒮(1,j)). (D.1)

By using this inequality we eventually get that

λ2(𝒟𝒮(i,j))(ij)λ2(𝒟𝒮ij(1,1))=O((ij)212(ij)),

where the final equality holds by Claim 166.

To prove (D.1) we use Lemma 16. In this case our local decomposition is T={GB|BU(1)}. The graph GB=(LB,RB) is the induced bipartite subgraph where LB={AL|BAU} and RB={AR|(A,B)𝒟𝒮U(1,j)}. We claim that GB𝒟𝒮UB(i1,j): the isomorphism ϕ:GB𝒟𝒮UB(i1,j) maps

ARBϕ(A)=AandALBϕ(A)=AB.

For the right sides, we note that (A,B)𝒟𝒮U(1,j) if and only if AUB so this isomorphism maps the right side of GB to that of 𝒟𝒮UB(i1,j). For the left sides, Proposition 28 gives us that BAU if and only if ABUB. Thus ϕ maps matrices ARB isomorphically to matrices on the left side of Gm10(UB,a1,a21). Checking that A1A2 in 𝒟𝒮UB(i1,j) if and only if ϕ(A1)ϕ(A2) in GB is direct. Therefore for every B, the second largest eigenvalue λ2(GB)=λ2(𝒟𝒮1(i1,j)).

We note that by definition the graph τ,L=𝒟𝒮(1,j). Thus (D.1) follows from Lemma 16.

D.3 Bounding the expansion of the relation graphs

We start by proving the claim in the following special case.

Claim 169.

Let D() and let i,j be such that ij3, then λ2(D(i,j))γj.

After proving Claim 169, we prove Claim 165 by using Lemma 16 again.

Proof of Claim 169.

Fix D,i,j. For this case we intend to use Corollary 11 on the two step walk on D(i). We prove that

maxB1VμB1J1γ′′j (D.2)

where μB1 is the distribution of the two step walk starting from B1, and the distribution J is the uniform distribution over D(i). Fix B1D(i) and from now on we just write μ instead of μB1 for short.

We will show that there exists a set VD(i) such that both B2μ[B2V],B2J[B2V]1p for a sufficiently small p(γ)j. Then we will also prove that the distribution μ conditioned on this event V is uniform, and this will give us (D.2). Here

V={B2D(i)row(B2)(row(B1)row(D))={0},col(B2)(col(B1)col(D))={0}}.

A quick calculation will show that in this case μJ12pγj for some γ(0,1).

First we show that B2J[V]1O(22ij): Let us show that the probability of choosing a uniform B2D(i) such that row(B2)(row(B1)row(D)){0} is at most i22ij (the same also holds for the column spaces). The row span of B2 is sampled uniformly as an i dimensional subspace inside a n dimensional space, conditioned on row(B2)row(D)={0}. So this probability is

row(B2)[(row(B1)row(D))row(B2){0}|row(B2)row(D)={0}]row(B2)[(row(B1)row(D))row(B2){0}]row(B2)[row(B2)row(D)={0}].

The ratio is bounded by i22i+n11i2nO(i22i+(n)) via standard calculations. The same probability holds for the columns spaces, therefore B2J[V]1O(i2i+(n))=1O(γ(2ij)). The last equality is by jn.

Next we claim that B2μ[V]1O(22ij). Indeed, the two step walk from B1 traverses to some UD(j) (whose row space intersects trivially with row(D)), and from U we independently choose a matrix B2U. As row(U)row(D)={0}, it follows that row(B2)row(B1)row(D){0} if and only if row(B1)row(B2){0}. For any fixed UD(j), the probability that row(B1)row(B2){0} is at most O(i22ij) (repeating the calculation above).

Now let us show that conditioned on V, for any two neighbors B2,B2V of B1 in the two step walk, the probability of sampling B2 is the same as sampling B2. To show this it is enough to show that there exists a graph isomorphism of the original “one-step graph”, that fixes B1 and sends B2 to B2. Let us denote by GL(𝔽2n) the general linear group, or equivalently the group of n×n invertible matrices. We will find E1GL(w1),E2GL(w2) such that:

  1. 1.

    E2A=AE1=A.

  2. 2.

    E2B1E1=B1.

  3. 3.

    E2B2E1=B2.

Assume we found such E1,E2. We claim that XE2XE1 is an isomorphism of the one-step graph. Indeed, note that if AB then as multiplying by an invertible matrix maintains rank, it follows that E2AE1E2BE1=AE2BE1. Therefore, XE2XE1 is a bijection on the vertices of the graph. It is easy to check that this multiplication also maintains the relation so this is indeed an isomorphism. Finally, it is also easy to see that (B1,M,B2) is mapped to a path (B1,E2ME1,B2), so in particular such an isomorphism implies that the probability of sampling B2,B2V is the same.

To find such E1,E2 recall that E2(ef)E1=(E2e)(E1f). Thus we can decompose A=t=1etft, B1=t=1ietft, B2=t=1ihtkt and B2=t=1ihtkt. By assumption on the intersections of the row (and column) spaces, the sets {et}t=1Γ{et}t=1iΓ{ht}t=1i and {et}t=1Γ{et}t=1iΓ{ht}t=1i are independent and have the same size. The same holds for the corresponding sets of column vectors (replacing e,h with f,k). Thus we just find any E1,E2 such that

E1et=et,E1et=et,E1ht=ht
E2ft=ft,E1ft=ft,E1kt=kt.

These will have the desired properties. By the arguments above, the claim is proven. We comment that the above proof is one place where an analogous argument fails to hold for higher dimensional tensors. We heavily relied on the fact that for any fixed matrix U, the row span and column span of an i rank matrix BU is uniformly distributed over i dimensional subspaces inside row(U) and col(U), even if these marginals are not independent.

We move on to the general case.

Proof of Claim 165.

Fix i,j, and D(). The case where ij3 is by Claim 169 so assume that j3<ij2. Towards using Lemma 16, we decompose D(i,j) to components {GB}BD(j3) where GB is the graph induced by all edges {M,C} such that BCM. We claim that GB is isomorphic to (DB)(ij3,2j3). The isomorphism ϕ:GB(DB)(ij3,2j3) is ϕ(M)=MB. Let us start by showing that this maps vertices to vertices.

Indeed, fix any BD(j3) and let GB=(LB,RB,EB). Explicitly,

LB={MD(i)|MB},RB={CD(j)|CB}.

Note that every MLB is a direct sum MD, and as BM this implies that (B(MB))D. As we saw before, this implies that (BD)(MB), therefore ϕ(M)=MB(DB)(ij3). Conversely, if M(DB)(ij3) then ϕ1(M)=MB has rank(ϕ1(M))=i. Moreover, as M(DB) then (MB)D, i.e. ϕ1(M)D(j). It is also clear that Bϕ1(M) hence ϕ1(M)LB. Of course, a similar argument holds for the right side RB, then ϕ is a bijection of the vertex set. Finally, by Claim 154, CM if and only if CBMB, so this is indeed an isomorphism of graphs.

We note that if ij2 then ij3122j3 and therefore we can use Claim 169 and deduce that for every BD(j3), λ2(GB)γj. Moreover, we observe that the bipartite local to global graph for the left side, τ,L is D(j3,j), thus by Claim 169 this also has λ2(τ,L)γj and so by Lemma 16 the lemma is proven. We comment that the requirement that ij2 is just for convenience. Multiple uses of the same decomposition with Lemma 16, would yield a similar bound whenever i(1ε)j for any fixed constant ε>0. As we only need the claim for i=j2, we merely mention this without proof.

D.4 Short paths in 𝒯m

This subsection of the appendix is devoted to the proof of Claim 117 which is necessary to analyze the coboundary expansion of the complexes in [50].

We begin with the following auxiliary claim proven in the end of the subsection.

Claim 170.

Let Z1 be a rank 4m matrix and let Z2 be a rank 3m matrix.

  1. 1.

    Let A,BZ1 be such that rank(A)=rank(B)=m. Then there exists a matrix T with rank(T)=m such that AT,TBZ1.

  2. 2.

    Let A,BZ2 be such that rank(A)=rank(B)=m then there exists M1,M2,M3 such that

    AM1,M1M2,M2M3,M3BZ2.

Phrasing this claim differently, the first item claims that any two matrices in one side of 𝒟𝒮4m(m,m) have a length 2 path between them. The first item claims that any two matrices in one side of 𝒟𝒮3m(m,m) have a length 4 path between them.

Proof of Claim 117.

We proceed as follows. We first decompose C,D𝒯Z into m ranked matrices such that C=C1C2 and D=D1D2. Then we find some T of rank m such that TC1,TD1Z. This is possible due to the first item in Claim 170.

Then we will prove that there exists a 12-path composed of three paths of length 4: one from C1C2 to C1T, one from C1T to D1T and one from D1T to D1D2.

Let us show how to construct the first path, the other two are constructed similarly. Note that C1C1C2,C1T and that they are both Z. Thus if we find M1,M2,M3ZC1 such that

C2M1,M1M2,M2M3,M3TZC1,

Then by Proposition 28, adding C1 to all three M1,M2,M3 will give us the desired path in 𝒯Z:

(C1C2,C1M1,C1M2,C1M3,C1T).

But observe that ZC1 has rank 3m, and thus existence of such matrices M1,M2,M3 is promised by Claim 170 so we can conclude.

Proof of Claim 170.

Without loss of generality let us assume that Z1 is the identity matrix of rank 4m and that Z2 is the identity matrix of rank 3m. We wish to use the criterion for AI given in Claim 167.

For this proof we also require the following observation which follows from elementary linear algebra. We leave its proof to the reader.

Observation 171.

Let W𝔽2n be a subspace of dimension j. Let E={e1,e2,,ek} be k independent vectors. Assume that Wspan(E)={0}. Then for every b1,b2,,bk𝔽2 there exists a solution x to the set of linear equations:

  1. 1.

    For every wW, x,w=0, and

  2. 2.

    For every i=1,2,,k, x,ei=bi.

Let us begin with the first item. Given A,B of rank m we need to find some T of tank m such that AT,BTZ1. Equivalently, we will find T such that AT and BT satisfies the criterion in Claim 167.

Let us write A=j=1mej(A)fj(A),B=j=1mej(B)fj(B) where these decompositions satisfy the property in Claim 167. Let W={w𝔽24m|j=1,2,,mw,fj(A)=w,fj(B)=0}. As W is a solution space of 2m linear equations over 𝔽24m, it is a subspace of dimension 2m. We will select the rows of T from W.

However, it is not enough to just select arbitrary rows from W, since we need to satisfy the condition that if ei,fj participates in the decomposition of T then ei,fj=1 if and only if i=j. In addition, we will also require that fj will be perpendicular to all the ei(A),ei(B)’s. This will define a set of linear equations which we will solve using Observation 171. To do this we will find an m-dimensional subspace in WW that intersects trivially with the span of the ej(A),ej(B)’s (the sum of row spaces of A and B).

We note that Wrow(A)=Wrow(B)={0}. Let us show this for row(A): any non-zero vector xrow(A) is a sum of j=1mbjej(A) where at least on of the bj’s are not zero. On the other hand, x,fj(A)=bj, so there is at least one x,fj(A)0, implying that xW. Thus we conclude that dim(W(row(A)+row(B)))m, and in particular there exists some m dimensional subspace WW such that W intersects trivially with row(A)+row(B). Let E={e1(T),,em(T)} be a basis of W.

Thus by Observation 171, for every i=1,2,,m there exists some fi(T) such that

  1. 1.

    For every j=1,2,,m, ej(A),fi(T)=ej(B),fi(T)=0 for all j=1,2,,m, and

  2. 2.

    In addition

    ej(T),fi(T)={1i=j0ij.

By taking T=j=1mej(T)fj(T) we observe that both AT and BT satisfy Claim 167, and therefore AT,BTZ1.

Let us turn to the second item. We continue with the notation A=j=1mej(A)fj(A),B=j=1mej(B)fj(B). The strategy here will be similar. Let W1={w𝔽23m|j=1,2,,kw,fj(A)=w,fj(B)=0}. We observe that this is the solution set of 2m linear equations and therefore its dimension is m. Let e1(M1),e2(M1),,em(M1)W1 be m independent vectors, and set ej(M3)=ej(M1). We observe that as before W1row(A)={0} so by Observation 171, for every j=1,2,,m there exists some fj(T) such that

  1. 1.

    For every ei(A), ei(A),fj(M1)=0.

  2. 2.

    For every i,j,

    ei(M1),fj(M1)={1i=j0ij.

We note that the linear equations for fj(M1)’s do not consider the ej(B)’s.

Similarly, we find fj(M3) ignoring the ej(A)’s. That is, for every j=1,2,,m we find fj(M3) such that

  1. 1.

    For every ei(B), ei(B),fj(M3)=0.

  2. 2.

    For every i,j,

    ei(M3),fj(M3)={1i=j0ij.

Then we set M1=j=1mej(M1)fj(M1) and M1=j=1mej(M3)fj(M3). It is easy to verify that as before AM1,BM3Z2.

Now we find M2 such that M1M2,M2M3Z2. The upshot of the previous step is that now M1 and M3 have the same row space span({e1(M1),e2(M1),,em(M1)}). Thus we find M2 as follows. Let W2={w𝔽23m|j=1,2,mw,fj(A)=w,fj(B)=0}. This subspace also has dimension m so let e1(M2),e2(M2),,em(M2)W2 be a set of independent vectors from W2.

As before, we observe that W2row(M1)={0} but this time row(M1)+row(M3)=row(M1). Thus by Observation 171 for every j=1,2,,m, we can find fj(M2) such that

  1. 1.

    For every i=1,2,,m, ei(M1),fj(M2)=ei(M3),fj(M2)=0, and

  2. 2.

    In addition,

    ei(M2),fj(M2)={1i=j0ij.

Then we set M2=j=1mej(M2)fj(M2). It is direct to verify that M1M2,M2M3Z2 by Claim 167.

Appendix E Second largest eigenvalue of 𝑱(𝒏,𝒌,𝒌/𝟐)

Proof of Lemma 65.

Let n=(2+η)k. For the Johnson graph J(n,k,k/2), its largest unnormalized eigenvalue λ0=(kk/2)(nkk/2). Therefore by Theorem 63 the absolute values of the normalized eigenvalues are

|λt|λ0 =|i=0t(1)ti(kik/2i)(nk+itk/2+it)(ti)|(kk/2)(nkk/2)
=|i=max(0,tk/2)min(t,k/2)(1)ti(ti)k/2××(k/2i+1)k××(ki+1)
k/2××(k/2+it+1)(nk)××(nk+it+1)|.

Here the convention is that when we write (ab) for b>a or b<0, then the term is equal to 0. Thus, the terms corresponding to i<tk/2 or i>min{t,k/2} vanish since the product of the three binomial coefficients is 0 for these choices of i. We first show the statement for odd t[k]. In this case, we group terms (ti) and (tti) together to get

i=max(0,tk/2)t/2(ti)|j=0i1(k/2j)(kj)j=0ti1k/2jnkjj=0ti1k/2jkjj=0i1k/2jnkj|
=i=max(0,tk/2)t/2(ti)j=0i1k/2jkjj=0i1k/2jnkj|j=iti1k/2jnkjj=iti1k/2jkj|.

To simplify the products we first observe that for any 0j<k/2, k/2jkjk/2k=12 and k/2jnkjk/2nk=12(1+η).

i=max(0,tk/2)t/2(ti)(12)i(12(1+η))i|j=iti1k/2jnkjj=iti1k/2jkj|. (E.1)

Furthermore we use the following claim to bound the term in absolute value:

Claim 172.

For any constant η>0 and any integers 1m<C and 0sm,

j=smCj2Cjj=smCj2(1+η)Cj(Cs2Cs)ms+1(Cs2(1+η)Cs)ms+1.

A proof is given later in the appendix. By the claim the expression in Equation E.1 can be bounded by a binomial sum:

i=max(0,tk/2)t/2(ti)(12)i(12(1+η))i((12)t2i(12(1+η))t2i)
=i=max(0,tk/2)t/2|(1)i(ti)(12)i(12(1+η))ti
+(1)ti(tti)(12)ti(12(1+η))i|
|i=0t(1)i(ti)(12)i(12(1+η))ti|
(1212(1+η))t
=(η2(1+η))tη2(1+η).

Next consider the case of even t[k]. First use the binomial identity (ti)=(t1i)+(t1i1) to obtain the following bound

|i=max(0,tk/2)min(t,k/2)((1)t1(i1)(t1i1)(1)t1i(t1i))
j=0i1(k/2j)(kj)j=0ti1k/2jnkj|
=|i=max(0,t1k/2)min(t1,k/2)(1)t1i(t1i)j=0i(k/2j)(kj)j=0ti2k/2jnkj
𝟏[t1>k/2](1)t1k/2(t1k/2)j=0k/2(k/2j)(kj)j=0tk/22k/2jnkj
+i=max(0,t1k/2)min(t1,k/2)(1)t1i(t1i)j=0i1(k/2j)(kj)j=0ti1k/2jnkj
𝟏[t1k/2](1)k/2(t1k/2)j=0t2k/2(k/2j)(kj)j=0k/2k/2jnkj|.

First note that the second term and the fourth term always evaluate to 0. Thus we can simplify the expression as

|i=max(0,t1k/2)min(t1,k/2)(1)t1i(t1i)(k/2i)(ki)j=0i1(k/2j)(kj)
j=0(t1)i1k/2jnkj|+|i=max(0,t1k/2)min(t1,k/2)(1)t1i(t1i)
k/2(ti1)nk(ti1)j=0i1(k/2j)(kj)j=0(t1)i1k/2jnkj|.

These two terms resembles the expression of |λt1|λ0 and can be bounded by grouping terms (t1i) and (t1t1i).

i=max(0,t1k/2)(t1)/2(t1i)j=0ik/2jkjj=0i1k/2jnkj
|j=i(t1)i1k/2jnkjj=i(t1)i1k/2j1kj1|
+i=max(0,t1k/2)(t1)/2(t1i)j=0i1k/2jkjj=0ik/2jnkj
|j=i(t1)i1k/2j1nkj1j=i(t1)i1k/2jkj|

Using Claim 172 again yields

i=max(0,t1k/2)(t1)/2(t1i)(12)i+1(12(1+η))i
((12)(t1)2i(12(1+η))(t1)2i)
+i=max(0,t1k/2)(t1)/2(t1i)(12)i(12(1+η))i+1
((12)(t1)2i(12(1+η))(t1)2i)
(12+12(1+η))(1212(1+η))t1η2(1+η).

We thus conclude that for all t[k], |λt|λ0η2(1+η).

Proof of Claim 172.

We prove the statement by induction on s. The case of s=m holds trivially. Suppose the statement holds for all s>s, then we are going to show that the inequality also holds for s=s. Note that by the induction hypothesis

j=s+1mCj2Cjj=s+1mCj2(1+η)Cj(C(s+1)2C(s+1))ms(C(s+1)2(1+η)C(s+1))ms. (E.2)

To simplify the expressions we define

X(s)=j=smCj2Cjx(s)=Cs2Cs

and also

Y(s)=j=smCj2(1+η)Cjy(s)=Cs2(1+η)Cs.

Using this notation, (E.2) can be rewritten as

X(s+1)Y(s+1)x(s+1)msy(s+1)ms.

Rearranging the inequality we get that

x(s+1)msX(s+1) y(s+1)msY(s+1)
x(s)(x(s+1)msX(s+1)) y(s)(y(s+1)ms1Y(s+1))
x(s)x(s+1)msX(s) y(s)y(s+1)msY(s)
X(s)Y(S) x(s)x(s+1)msy(s)y(s+1)ms (E.3)

Now we bound this difference

(x(s)ms+1y(s)ms+1)(x(s)x(s+1)msy(s)y(s+1)ms)
= x(s)(x(s)msx(s+1)ms)y(s)(y(s)msy(s+1)ms) (E.4)

We note that for fixed constants α,β>1, and γ>0, the function p(x)=(αβ(1+x))γ(α1β(1+x)1)γ is decreasing when x0. If we set α=Cs,β=2Cs, and γ=ms, then

x(s)msx(s+1)ms=p(0), while y(s)msy(s+1)ms=p(2ηC2Cs).

Therefore

x(s)msx(s+1)msy(s)msy(s+1)ms,

and together with the fact that x(s)y(s) we can deduce that (E.4)0. Equivalently,

x(s)ms+1y(s)ms+1x(s)x(s+1)msy(s)y(s+1)msX(s)Y(s),

where the second inequality holds by (E.3). Note that this inequality is exactly the claim statement for s=s. Thus we finish the induction step and conclude the proof.

Appendix F Sparsifying the Johnson complexes

While both the Johnson complexes and the RGCs over N=2n1 vertices have vertex degree 𝖭, the Johnson complexes have much denser vertex links, or equivalently more 2-faces. The degree of the Johnson complex Xε,n’s vertex links is

dlink=(εnεn/2)((1ε)nεn/2)Nε/2,

while that of the RGCs is polylog(N). In fact we can sparsify the links and reduce the number of 2-faces in Johnson complexes by keeping each 2-face with probability p, and set p so that the link degree becomes polylog(N). Then we shall use the following theorem to show that the link expansion is preserved after subsampling.

Theorem 173 (Theorem 1.1 [21]).

Suppose G is a graph on n vertices with second largest eigenvalue in absolute value λ2(G) and minimum degree dmin. A random subgraph H of G with edge-selection probability p has a second eigenvalue λ2(H) satisfying

λ2(H)λ2(G)+O(lognpdmin+(logn)3/2pdmin(loglogn)3/2)

with probability >1f(n) where f(n) tends to 0 faster than any polynomial in 1n.

From this eigenvalue preservation result we can get the following sparsification.

Corollary 174.

Consider a random subcomplex X of a 2-dimensional Johnson complex Xε,n constructed by selecting each 2-face i.i.d. with probability p(h(ε)logN)3/2dlink where N=2n1, and dlink is the degree of Xε,n’s vertex links. Then with high probability every vertex link of X is a 12(1ε)(1+on(1))-spectral expander.

Here we recall that h(x) is the binary entropy function.

Proof.

We first argue that almost surely X(1)=Xε,n(1) so that for every vX(0) the vertex link Xv has the same vertex set as (Xε,n)v. From the subsampling process we know that for any edge {v,v+s}Xε,n(1), the degree of v+s in the link of v follows a binomial distribution with

𝔼[degree of v+s in Xv]=pdlink=(h(ε)logN)3/2.

By the Chernoff bound for binomial distributions we know that

[degree of v+s in Xv0.1(h(ε)logN)3/2]e0.45(h(ε)logN)3/2=NΘ(logN).

So by a simply union bound over all pairs of {v,v+s} we get that with probability 1N1+h(ε)NΘ(logN)=1o(1) every link in Xv has the same vertex set as (Xε,n)v.

Next, recall by Lemma 59 Xε,n’s vertex links have second eigenvalue <12(1ε). Since the choice of p ensures that logNh(ε)pdlink+(logh(ε))3/2pdlink(loglogh(ε)N)3/2=o(1), each link of X is a 12(1ε)(1+o(1)) expander. Finally, applying an union bound over all links of X completes the proofs.

Appendix G Proof of the van Kampen lemma

To prove this lemma, we would like to contract C0 using the contractions of {Ci}i>0 so the proof should give us an order in which Ci-s are contracted. This order is given by the order in which the set {fi}i>0 are contracted to reduce 2f0 to a point. Therefore, for every such diagram, it suffices to find a single face fj such that we can contract to obtain a diagram of a cycle with one less interior face. The property we need from fj is that the shared boundary of fj and f0 is a contiguous path. This requirement is captured in the following definition.

Definition 175 (valid face and path).

Let H be a van Kampen diagram. We say that an interior face fj is valid if we can write its boundary cycle C~j=PjQ such that the exterior cycle can be written as C~0=PjQ where Pj contains at least one edge and the vertices of Q,Q are disjoint (except for the endpoints). In this case we call Pj a valid path.

Lemma 79 will easily follow from the following three claims.

Claim 176.

Every 2-connected plane graph H has at least one valid face.

Claim 177.

Let Pj=(v0,v1,,vm) be a valid path in H. Then for every 1im1, deg(vi)=2.

Claim 178.

Let H=(V,E) be a van Kampen diagram, let Pj=(v0,v1,,vm) and let Hj=(V,E) be the induced subgraph on V=V{v1,v2,,vm1}. Then Hj is 2-vertex connected.

Given the three claims, we can prove the van Kampen lemma as follows.

Refer to caption
Figure 12: Contracting a face in H to obtain Hj in Lemma 79.
Proof of Lemma 79.

Fix X,C0,H,F,ψ be as defined in Section 5.3. We prove this lemma by induction on the number of inner faces of H. If H has exactly one inner face f1, then its boundary C~1 is also the boundary C~0 of the outer face f0. Then we can deduce that C0=ψ(C~0)=ψ(C~1)=C1. So indeed there is a contraction of C0 using m0=m1-triangles.

Assuming the lemma is true for all van Kampen diagrams with at most inner faces, we shall prove it for van Kampen diagrams H,F with +1 inner faces. By Claim 176, we can always find a valid face fj in H such that C~0=PjQ and C~j=PjP where Pj is the corresponding valid path. The decompositions are illustrated in Figure 12.

Using Claim 85, we can contract C0 (the image of the outer boundary of H under ψ) to ψ(QP) using mj triangles. Correspondingly, we can construct an induced subgraph Hj of H by removing all edges and intermediate vertices in Pj.

Note that the the outer boundary of Hj is C~0=QP. Furthermore, since the intermediate vertices in Pj all have degree 2 in H (by Claim 177), removing these vertices only removes the inner face fj. Therefore, Hj has inner faces. Finally by Claim 178, Hj is still a 2-connected plane graph.

Thereby Hj,F{fj} is a van Kampen diagram of the cycle ψ(C~0) in X with inner faces, and so the induction hypothesis applies. Thus we complete the inductive step and the lemma is proven.

Next we shall prove the three supporting claims. Before doing so, we define the cyclic ordering of vertices in a cycle which will later be used in the proofs.

Definition 179 (Cyclic ordering).

Let H=(V,E) be a graph. For a given cycle C in H, a cyclic ordering of the vertices in C is such that two consecutive vertices in the ordering share an edge in C.

Proof of Claim 176.

We will show that either there exists a valid face, or that there exists two inner faces fifj and four vertices v1,v2,v3,v4 in the cycle C0 such that v1,v3fi, v2,v4fj (that is, on the boundaries of the respective faces), and such that in the cyclic ordering of C0, v1v2v3v4. Then we will show that the latter case implies there is an embedding of a 5-clique on the plane, reaching a contradiction. We mention that these points do not need to be vertices in H, only points on the plane.

Indeed, take a face fi that shares an edge with f0. If it is not valid, it partitions C0fi into disconnected segments (and this partition is not empty since otherwise fi was valid). If there exists some fj that touches two distinct segments, we can take v1,v3fi and v2,v4fj as above. Otherwise, we take some SC0fi, that contains an edge. We now search for a valid face whose path is contained in S, and continue as before. That is, take some fi that shares an edge in S with the outer face. If it is valid we take fi and if not we consider the partition of Sfi as before. We note that this process stops because the number of edges in the segment in every step strictly decreases - and when we stop we either find a valid face or four points as above.

Now let us embed the 5-clique. Indeed, we fix a point on the outer face v0 in the interior of f0, and take {v0,v1,v2,v3,v4} to be the vertices of the clique. The edges are drawn as follows.

  1. 1.

    From v0 to every other vertex we can find four non intersecting curves that only go through f0.272727For this one can use the Riemann mapping theorem to isomorphically map the outer face to the unit disc and C0 to its boundary. Without loss of generality we can choose v0 so that it is mapped to the center. Then we draw straight lines from the image of v0 to the rest of the points in the boundary (and use the inverse to map this diagram back to our graph).

  2. 2.

    The edges {v1,v2},{v2,v3},{v3,v4},{v4,v1} are the curves induced by the cycle C0. These curves do not intersect the previous ones (other than in v1,v2,v3,v4) since the curves in the first item lie in the interior of f0.

  3. 3.

    By assumption, the pairs v1,v3fi and v2,v4fj so we can connect these pairs by curves that lie in the interiors of fi and fj respectively, and in particular they do not intersect any of the other curves.

Proof of Claim 177.

Let fj be the valid face. Let us denote by e0,e2 the edges adjacent to v in P0 which is not an endpoint. Assume towards contradiction that there is another edge e1 adjacent to v. Thus e1 either lies in the interior or the exterior of fj.

If it lies in the interior, then by 2-vertex connectivity there exists a path starting at e1 connecting to another point in the boundary of fj, and other than v and the end point, the path lies in the interior of fj. This is a contradiction, since any such path disconnects fj to two faces. Otherwise it lies in the exterior, but the argument is the same only with f0 instead of fj.

Proof of Claim 178.

Let v0,v1 the end points in P1, and notice that v0,v1 participate in a cycle in H- the cycle bounding the outer face. In particular Hj is connected. Remove any vertex z from Hj. Let Px,y be a path that connects two vertices x,y in H{z} (that may contain some vertices in Pj). Let us show that we can modify Px,y to some P in Hj{z}. By Claim 177 every vertex in Pj which we removed had degree 2. Therefore any path containing a vertex in Pj, contains all of Pj (or its reverse). Thus to mend Px,y we just need to show that and v0,v1 are in a simple cycle in Hj. Indeed, this is true from the definition of a valid path: Cj=PjQ and C0=PjQ such that all vertices in Q,Q are disjoint besides the end points. The paths Q,Q participate in simple cycles therefore QQ1 is a simple cycle and we conclude.

Appendix H Expansion of containment walks in the Grassmann poset

To stay self contained we reprove Claim 21 in a similar manner as in [30].

Proof of Claim 21.

Although all the claims below apply for Yw for any wY, for a simple presentation let us assume that w={0} (the same idea works for arbitrary w). Let us denote by Ui,j the bipartite graph operator from Y(i) to Y(j). We note that Ui,j=Uj1,jUi+1,i+2Ui,i+1, and therefore it is sufficient to prove that λ2(Ui,i+1)(0.61+iλ)12. We do so by induction on i.

In fact, we prove a slightly stronger statement, that λ2(Ui,i+1)=(=1i12+11+iλ)12. This suffices because =1i12+11=112+110.61. Let Di+1,i be the adjoint operator to Ui,i+1, and denote by λi=λ(Di+1,iUi,i+1) be the second largest eigenvalue of the two step walk from Y(i) to Y(i). To show that λ2(Ui,i+1)=(=1i12+11+iλ)12 it suffices to prove that λi=(=1i12+11+iλ).

The base case for the induction is for U1,2. In this case

λ1=λ(D2,1U1,2)=13I+23M+

where M+ is the non-lazy version of the walk (namely, where we traverse from w1 to w2 if w1+w2Y(2)). The adjacency operator M+ is the link of {0}, and thus by λ-expansion we have that λ113+23λ1221+λ.

Assume that λ2(Ui,i+1)(=1i12+11+iλ)12 and consider the two step walk on Y(i+1). As above, we note that

λi+1=λ(Di+2,i+1Ui+1,i+2)=12i+21I+(112i+21)Mi+1+

where M+ is the non-lazy version of the walk. We note that the laziness probability 12i+21 is because every subspace wY(i+2) has exactly 2i+21 subspaces of codimension 1 (so this is the regularity of the vertex). Thus we will prove below that λ(Mi+1+)λ+λi(=1i12+11+(i+1)λ) and this will complete the induction.

Let us decompose the non-lazy walk M+ via Lemma 15. Our components are T={YW}WY(i). To be more explicit, note that W1W2 in the two step walk if and only if W1+W2Y(i+2). We can choose such a pair by first choosing WY(i) and then choosing an {W1,W2} in the link YW. The distribution of the link if the conditional distribution, hence taking μ to be the Y(i)-marginal of the distribution over flags in Y, we have that T is a local-to-global decomposition. The local-to-global graph τ connects WY(i) to WY(i+1) - so this is just the containment graph (Y(i),Y(i+1)) which by induction is a λi-expander. By Lemma 15, λ(Mi+1+)λ+λi(=1i12+11+(i+1)λ) and we can conclude.

Appendix I A degree lower bound

A classical result in graph theory says that a connected Cayley graph over 𝔽2n has degree at least n. Moreover, if the Cayley graph is a λ-expander then it has degree at least Ω(nλ2log(1/λ)) [2]. Are there sharper lower bounds on the degree if the Cayley graph is also a Cayley local spectral expander?

In this section we consider the “inverse” point of view on this question. Given a graph G with m vertices, what is the maximal n such that there exists a connected Cayley complex over 𝔽2n whose link is isomorphic to G. Using this point of view, we prove new lower bounds for Cayley local spectral expanders, that depend on properties of G. Specifically, we prove that if G has no isolated vertices then m>1.5(n1); if G is connected we prove that m>2n1. Finally, if the link is a d-regular edge expander, we prove a bound of Ω(d1/2n). For all these bounds, we use the code theoretic interpretation of the links given in [50].

We begin by describing the link of a Cayley complex, and using this description we give a lower bound on the degree of the Cayley complex in terms of the rank of some matrix. This linear algebraic characterization of a degree lower bound is already implicit in [50, Section 6].

After that, we will lower bound the rank of the matrix, and through this we will get lower bounds on the degree of such Cayley complexes.

A link in a Cayley complex X naturally comes with labels on the edges which are induced by the generating set (i.e. an edge between x+s1 and x+s2 in the link of x will be labeled s1+s2 which by assumption is a generator in the generating set). Note that if x+s1,x+s2 is labeled s1+s2 then there is a 3-cycle in the link between x+s1,x+s2 and x+s1+s2 where every edge whose endpoints correspond to two generators is labeled by the third generator.

Let G=(V,E) be a graph with vertex set V={v1,v2,,vm} and a labeling :EV. The graph G is nice if for every {vi,vj} that is labeled vk there is a three cycle vi,vj,vk in the graph where {vi,vk} is labeled vj and {vj,vk} is labeled vi. We would like to understand for which n does there exist a Cayley complex X over 𝔽2n so that the vertex links of X are isomorphic to G. That is, for which n can we find generators s1,s2,,sm𝔽2n such that the map ϕ(si)=vi is a graph isomorphism between the vertex link and G. Observe that for this to hold, whenever there is an edge {vi,vj}E labeled by vk, we require that si+sj+sk=0. Thus we can define the matrix HG𝔽2|E|×|V| to have in every row the indicator vector of i,j,k for every {vi,vj}E labeled by vk. Let us show that this is a sufficient condition.

Claim 180.

Let G be a nice graph with m vertices. Let S={s1,s2,,sm}𝔽2n and let Ms be the matrix whose rows are the si’s. Then the following is equivalent.

  1. 1.

    The columns of Ms are in the kernel of HG.

  2. 2.

    There exists a Cayley complex X over 𝔽2n and whose link is isomorphic to G whose underlying graph is Cay(𝔽2n,S).

In particular, if X is connected then mn+rank(HG).

This equivalence is essentially what was proven in [50, Lemma 77]. The degree bound is a direct consequence of it. Nevertheless, we prove it in our language for clarity.

Proof.

If the first item occurs, this means that for every {vi,vj}E labeled by vk, si+sj+sk=0 and therefore the 3-cycles (x,x+si,x+si+sj=x+sk,x) are in Cay(𝔽2n,S) so add {x+si,x+sj,x+sk} into the triangle set of X. Then it is straightforward to verify that the link of X is isomorphic to G.

On the other hand, from the discussion above, the isomorphism to G implies that for every edge {vi,vj} in G with label, their corresponding generators satisfy si+sj+sk=0. Hence the columns of Ms are in Ker(HG).

In particular, this implies that rank(Ms)dim(Ker(HG))=mrank(HG). On the other hand, if the complex is connected then rank(Ms)n. Combining the two we get that the degree of X is lower bounded by mn+rank(HG).

Corollary 181.

Let X be a connected Cayley complex over 𝔽2n with degree m such that the link of X contains no isolated vertices. Then m1.5(n1). Moreover, if the link is connected then m2n1.

Proof.

The corollary follows from the inequality mn+rank(HG), together with the observation that rank(HG)m3 which we now explain. We can greedily select independent rows from HG such that whenever a generator si has not appeared in any selected rows, we take an row where si appears. As every newly selected row contains at most 3 new generators, we can find at least m3 such equations. Thus, mn+m3 and the bound follows.

If the link is connected, we can improve on this argument. At every step when we select a row, we denote by DV the set of vertices that have appeared in the selected rows. Since the link is connected, therefore while DV we can always choose a new row containing vertices from both D and its complement, in which case the new row (besides the first one) introduces at most 2 new vertices. Thus rank(HG)1+m32=m212. The bound follows.

I.1 Improved bound from expansion

If the graph G is an (edge) expander, we can improve the naive bounds above. Let m be the degree of the Cayley complex and d be the degree of a vertex in the link. We get a degree bound of m=Ω(d1/2)n. In particular, if the degree goes to infinity (which is also a necessary condition to get better and better spectral expansion), this lower bound tends to infinity as well.

Lemma 182.

Let X be a simple Cayley HDX over 𝔽2n with m generators.282828Simple, means that there are no loops or multi-edges. This also implies that every two labels of edges that share a vertex are distinct. Assume that the link is d-regular and denote it by G=(V,E). Let c(0,1) be such that for every subset of vertices DV in the link ,

(x,y)E[xD,yD]cxV[xD]yV[yVD]

where the probability is over sampling an edge (oriented) in the link. Then

m=Ω(cd1/2n).

A few remarks are in order.

 Remark 183.
  1. 1.

    We note that the edge expansion condition in the lemma is equivalent to one-sided λ-spectral expansion for some λ<1 by Cheeger’s inequality. Thus whenever λ is bounded away from 1 we can treat c as some constant absorbed in the Ω notation, and write m=Ω(d1/2n).

  2. 2.

    Moreover, the well-known Alon-Boppana bound implies that d-regular λ-one sided spectral expanders have d=Ω(λ2). Therefore, this bound also implies

    m=Ω(λ1n).

    However, this is not as sharp as the bound given in [2].

  3. 3.

    We prove this lemma for regular graphs for simplicity. The argument could be extended for more general edge expanders.

Proof of Lemma 182.

We will assume without loss of generality that d36 since otherwise the claim is trivial from the bound mn. By Claim 180, mn+rank(HG) therefore it suffices to prove that

rank(HG)(1O(1cd1/2))m (I.1)

to prove the lemma.

This lower bound follows from the same greedy row selection process we conducted above. We start by greedily selecting rows from HG such that the selected rows are independent. We keep track of the vertices/variables that appear in the selected rows, and select new rows such that every new row introduces the least number of new vertices possible. We will prove that there is a way to select rows so that only O(1d1/2c) fraction of the rows selected will introduce more than one new vertex (and the number of newly introduced vertices in one step is always 3). Since the process terminates after rank(HG) steps, the argument above implies that rank(HG)(1+O(1d1/2c))m which in turn implies (I.1).

For i=1,2,,rank(HG) we denote by Di the set of variables that are contained in one of the first i rows selected. By assumption, (x,y)E[xDi,yDi]c[xDi][yVDi]. Equivalently,

(x,y)E[xDi|yDi]c[xDi].

In particular, for every Di there exists a vertex yiVDi such that at least c[xDi]d of its outgoing edges go into Di. In particular, once [xDi]1cd1/2 every yi has at least d1/2 edges into Di.

Hence, we select rows as follows. If [Di]<1cd1/2 we select new rows arbitrarily that introduce as few new vertices as possible. After [xDi]1cd1/2, if in the i-th step every new row introduces at least two new vertices, we select a row that contains yi (as defined above) and a vertex in Di (such a row exists by our choice of yi). We observe that if every new row introduces at least two new vertices, this implies that the edges connecting yi to Di are labeled by distinct generators in VDi. In particular, after selecting yi which adds yi and another new vertex to Di+1, there are at least d1/2113d1/2 edges from yi to Di+1 that are labeled by distinct vertices in VDi+1 (since these edge labels were not in Di when we inserted yi). So the next 13d1/2 steps of the process add at most 1 new vertex per step. In particular, for every such step where 2 vertices are inserted to Di to get Di+1, there is a sequence of 13d1/2 steps each of which adds 1 new vertex. In conclusion, there are at most O(3md1/2+m2cd1/2) steps that introduce more than one new vertex to Di (out of at least m212 steps) and the lemma follows.