Authors Prahladh Harsha, Ramprasad Saptharishi,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22
www.theoryofcomputing.org
RESEARCH EXPOSITION
On the Elementary Construction of
High-Dimensional Expanders by
Kaufman and Oppenheim
Prahladh Harsha∗ Ramprasad Saptharishi∗
Received June 9, 2020; Revised November 26, 2022; Published October 26, 2024
Abstract. At STOC 2018, Kaufman and Oppenheim presented an elementary
construction of high-dimensional spectral expanders using elementary matrices. We
give a short, self-contained elementary proof of the correctness of their construction.
As a bonus, this also yields a simple construction and analysis of standard expanders
of bounded degree.
ACM Classification: F.2.2, G.2.2
AMS Classification: 68R10
Key words and phrases: high-dimensional expanders, groups, cosets
1 Introduction
In the last few years, there has been a surge of activity related to high-dimensional expanders
(HDXs). High-dimensional expanders are high-dimensional generalizations of classical graph
This work was done while the authors were visiting the Simons Institute for the Theory of Computing, Berkeley
to participate in the summer cluster on Error-Correcting Codes and High Dimensional Expanders, 2019.
∗ Research of the authors supported by the Department of Atomic Energy, Government of India, under project
no. 12-R&D-TFR-5.01-0500. Research of the first and second authors supported in part by the Swarnajayanti and
Ramanujan Fellowships, respectively.
© 2024 Prahladh Harsha and Ramprasad Saptharishi
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2024.v020a005
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
expanders. Depending on which definition of graph expansion is generalized, there are several
different (and unfortunately, often inequivalent) definitions of HDXs. For the purposes of
this note, we will restrict ourselves to the spectral definition of HDXs (see Definition 2.4).
Ramanujan graphs are families of expander graphs which have optimal spectral expansion (see
Definition 2.3). Lubotzky, Phillips and Sarnak [5] and Margulis [8] independently gave explicit
constructions of Ramanujan graphs. Ramanujan complexes are high-dimensional generalizations
of Ramanujan graphs. Lubotzky, Samuels and Vishne [6, 7] and Sarveniazi [12] gave explicit
constructions of Ramanujan complexes, which are the high-dimensional analgoues of the
construction of Lubotzky, Phillips and Sarnak [5]. These constructions were the first construction
of constant-degree spectral HDXs. The Ramanujan graphs constructed by Lubotzky, Phillips and
Sarnak [5] and Margulis [8] have the nice property that they are simple to describe, however the
proof of the optimality of their expansion is involved. The Ramanujan complexes constructed
by Lubotzky, Samuels and Vishne [6, 7] and Sarveniazi [12], on the other hand, are non-trivial to
describe and it is difficult to prove their high-dimensional expansion property. Subsequently
Kaufman and Oppenheim [4, See STOC version] gave an elegant elementary construction
of bounded-degree spectral HDXs using elementary matrices. While their HDXs are not
Ramanujan, their construction gives rise to new families of expander graphs whose spectral gap
is close to the optimal Ramanujan bound.
Despite the Kaufman–Oppenheim construction being elementary and simple, the proof of
expansion is not elementary. The purpose of this exposition is to give an elementary proof of
the expansion of the Kaufman–Oppenheim HDX construction. In particular, we obtain the same
eigenvalue bound as their proof.
The 1-skeleton (see Def. 2.1) of a HDX (even of a one-sided spectral HDX) is a two-sided
spectral expander (see Def. 2.3). Thus, this construction has the added advantage that it yields
an elementary construction (accompanied by a simple proof) of a standard two-sided spectral
expander (though not an optimal one).
2 Preliminaries
We begin by recalling what a simplicial complex is.
Definition 2.1 (Simplicial complex). A simplicial complex 𝑋 over a finite set 𝑈 is a collection of
subsets of 𝑈 with the property that if 𝑆 ∈ 𝑋 then any 𝑇 ⊆ 𝑆 is also in 𝑋.
• For all 𝑖 ≥ −1, define 𝑋(𝑖) := {𝑆 ∈ 𝑋 : |𝑆| = 𝑖 + 1}. Thus, if 𝑋 is non-empty, then
𝑋(−1) = {∅}.
• The elements of 𝑋 are called simplices or faces. The elements of 𝑋(0), 𝑋(1) and 𝑋(2) are
usually referred to as vertices, edges and triangles, respectively.
• For any 1 ≤ 𝑘 ≤ 𝑑, the 𝑘-skeleton of the complex 𝑋 is the subcomplex 𝑋(−1) ∪ 𝑋(0) ∪ 𝑋(1) ∪
· · · ∪ 𝑋(𝑘). We identify the 1-skeleton with the graph defined by 𝑋(0) and 𝑋(1).
• The dimension of the simplicial complex 𝑋 is defined as the largest 𝑑 such that 𝑋(𝑑) (which
consists of faces of size 𝑑 + 1) is non-empty.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 2
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
• The simplicial complex is said to be pure if every face is contained in some face in 𝑋(𝑑),
where 𝑑 = dim(𝑋).
• For a face 𝑆 ∈ 𝑋, the link of 𝑆, denoted by 𝑋𝑆 , is the simplicial complex defined as
𝑋𝑆 := {𝑇 \ 𝑆 : 𝑇 ∈ 𝑋 , 𝑆 ⊆ 𝑇} .
Thus, a graph 𝐺 = (𝑉 , 𝐸) is just a simplicial complex 𝐺 of dimension one with 𝐺(0) = 𝑉
and 𝐺(1) = 𝐸. We will deal with weighted pure simplicial complexes where the weight function
satisfies a certain balance condition.
Definition 2.2 (weighted pure simplicial complexes). Given a 𝑑-dimensional pure simplicial
complex 𝑋 and an associated weight function 𝑤 : 𝑋 → ℝ≥0 , we say the weight function is
balanced if the following two conditions are satisfied.
Õ 1 Õ
𝑤(𝑆) = 1 ; 𝑤(𝑆) = 𝑤(𝑇), for all 𝑖 < 𝑑 and 𝑆 ∈ 𝑋(𝑖). (2.1)
𝑖+2
𝑆∈𝑋(𝑑) 𝑇∈𝑋(𝑖+1),𝑇⊃𝑆
A weighted simplicial complex (𝑋 , 𝑤) is a pure simplical complex accompanied with a balanced
weight function 𝑤. If no weight function is specified, then we work with the balanced weight
function 𝑤 induced by the uniform distribution on the set 𝑋(𝑑) of maximal faces.
For a face 𝑆 ∈ 𝑋, the balanced weight function 𝑤 𝑆 associated with the link 𝑋𝑆 is the restricted
weight function, suitably normalized, more precisely 𝑤 𝑆 := 𝑤| 𝑋 /𝑤(𝑆). 𝑆
Condition (2.1) states that the weight function can be interpreted as a family of joint distri-
butions (𝑤| 𝑋(−1) , . . . , 𝑤| 𝑋(𝑑) ) where 𝑤| 𝑋(𝑖) is a probability distribution on 𝑋(𝑖). The distribution
𝑤| 𝑋(𝑑) is specified by the first condition in (2.1) while the second condition implies that the
weight distribution 𝑤| 𝑋(𝑖) is the distribution on 𝑋(𝑖) obtained by picking a random 𝜏 ∈ 𝑋(𝑑)
according to 𝑤| 𝑋(𝑑) and then removing (𝑑 − 𝑖) elements uniformly at random.
We now recall the classical definition of what it means for a graph to be a spectral expander.
We will be exclusively discussing only undirected graphs.
Definition 2.3 (spectral expander). Given a weighted graph 𝐺 = (𝑉 , 𝐸, 𝑤) on 𝑛 vertices, let 𝐴𝐺
be its normalized adjacency matrix given as follows:
𝑤(𝑢,𝑣)
(
𝑤(𝑢)
if {𝑢, 𝑣} ∈ 𝐸,
𝐴𝐺 (𝑢, 𝑣) :=
0 otherwise.
Let 1 = 𝜆1 ≥ 𝜆2 ≥ · · · ≥ 𝜆𝑛 ≥ −1 be the 𝑛 eigenvalues1 of 𝐴𝐺 . We denote the second largest
eigenvalue of 𝐺 by 𝜆(𝐺).
𝐺 is said to be a 𝜆-spectral expander if max{𝜆2 , |𝜆𝑛 |} ≤ 𝜆. This is sometimes also referred to
as a 𝜆-two-sided spectral expander.
𝐺 is said to be a 𝜆-one-sided spectral expander if 𝜆2 ≤ 𝜆.
1By the balance condition, 𝑤 satisfies 𝑤(𝑣) = {𝑢,𝑣}∈𝐸 𝑤(𝑢, 𝑣). The matrix 𝐴𝐺 is self-adjoint with respect to the
Í
inner product h 𝑓 , 𝑔i 𝑤 := 𝔼𝑣∼𝑤 [ 𝑓 (𝑣)𝑔(𝑣)] since h 𝑓 , 𝐴𝑔i 𝑤 = h𝐴 𝑓 , 𝑔i 𝑤 = 𝔼{𝑢,𝑣}∼𝑤 [ 𝑓 (𝑢)𝑔(𝑣)]. Hence, 𝐴𝐺 has 𝑛 real
eigenvalues which can be obtained using the Courant–Fischer Theorem (Theorem A.1).
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 3
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
This spectral definition of expanders is generalized to higher-dimensional simplicial com-
plexes as follows.
Definition 2.4 (𝜆-spectral HDX). A weighted simplicial complex (𝑋 , 𝑤) of dimension 𝑑 ≥ 1
is said to be a 𝜆-spectral HDX (or a 𝜆-two-sided spectral HDX)2 if for every −1 ≤ 𝑖 ≤ 𝑑 − 2 and
𝑠 ∈ 𝑋(𝑖), the weighted 1-skeleton of the link (𝑋𝑠 , 𝑤 𝑠 ) is a 𝜆-spectral expander.
A weighted simplicial complex (𝑋 , 𝑤) of dimension 𝑑 ≥ 1 is said to be a 𝜆-one-sided spectral
HDX if for every −1 ≤ 𝑖 ≤ 𝑑 − 2 and 𝑠 ∈ 𝑋(𝑖), the weighted 1-skeleton of the link (𝑋𝑠 , 𝑤 𝑠 ) is a
𝜆-one-sided spectral expander.
Using Garland’s technique [2], Oppenheim [10] showed that if the 1-skeletons of all the links
are connected, then a spectral gap at dimension (𝑑 − 2) descends to all lower levels.
Descent Theorem 2.5 (Oppenheim, 2018). Let (𝑋 , 𝑤) be a 𝑑-dimensional weighted simplicial complex
with the following properties.
• For all 𝑠 ∈ 𝑋(𝑑 − 2), the link (𝑋𝑠 , 𝑤 𝑠 ) is a 𝜆-one-sided spectral expander for some 𝜆 < 𝑑−1
1
.
• The 1-skeleton of every link is connected.
𝜆
Then, (𝑋 , 𝑤) is a 1−(𝑑−1)𝜆
-one-sided spectral HDX.
Thus to prove that a given simplicial complex is a spectral HDX, it suffices to show that the
1-skeleton of every link is connected and to show a spectral gap at the top level. For the sake of
completeness, we give a proof of the Descent Theorem in Appendix A which includes a descent
theorem for the least eigenvalue as well.
3 Coset complexes
The HDX construction of Kaufmann and Oppenheim is a particular instantiation of a certain
type of simplicial complex called a coset complex based on a group and its subgroups. In this
section, we give an exposition of these objects. For a basic primer on group theory, see Section B.
Definition 3.1 (coset complex). Let 𝐺 be a group and let 𝐾1 , . . . , 𝐾 𝑑 be 𝑑 subgroups of 𝐺. The
coset complex 𝒳(𝐺, {𝐾 1 , . . . , 𝐾 𝑑 }) is a (𝑑 − 1)-dimensional simplicial complex defined as follows:
• The set of vertices, 𝒳(0), consists of the left cosets of 𝐾1 , . . . , 𝐾 𝑑 and we shall say the left
cosets of 𝐾 𝑖 are of type 𝑖.
• The set of maximal faces, 𝒳(𝑑 − 1), consists of the 𝑑-sets of cosets of different types with a
non-empty intersection. That is,
{𝑔1 𝐾 1 , . . . , 𝑔 𝑑 𝐾 𝑑 } ∈ 𝒳(𝑑 − 1) ⇐⇒ 𝑔1 𝐾1 ∩ · · · ∩ 𝑔 𝑑 𝐾 𝑑 ≠ ∅.
2These are sometimes also referred to as 𝜆-link HDXs or 𝜆-local-expanders to distinguish from an alternative
global definition of high-dimensional expansion.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 4
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
An equivalent way of stating this is that {𝑔1 𝐾 1 , . . . , 𝑔 𝑑 𝐾 𝑑 } ∈ 𝒳(𝑑 − 1) if and only if there is
some 𝑔 ∈ 𝐺 such that 𝑔 𝑖 𝐾 𝑖 = 𝑔𝐾 𝑖 for all 𝑖, since
𝑔 𝑖 𝐾 𝑖 = 𝑔𝐾 𝑖 ⇐⇒ 𝐾 𝑖 = 𝑔 𝑖−1 𝑔𝐾 𝑖 ⇐⇒ 𝑔 𝑖−1 𝑔 ∈ 𝐾 𝑖 ⇐⇒ 𝑔 ∈ 𝑔 𝑖 𝐾 𝑖 .
• The lower-dimensional faces are obtained by down-closing the maximal faces. Hence, for
0 ≤ 𝑟 ≤ 𝑑, {𝑔 𝑖1 𝐾 𝑖1 , . . . , 𝑔 𝑖 𝑟 𝐾 𝑖 𝑟 } ∈ 𝒳(𝑟 − 1) if and only if 𝑖 𝑗 ≠ 𝑖 𝑘 for all 𝑗 ≠ 𝑘 and
𝑔 𝑖1 𝐾 𝑖1 ∩ · · · ∩ 𝑔 𝑖 𝑟 𝐾 𝑖 𝑟 ≠ ∅.
We shall call the set {𝑖1 , . . . , 𝑖 𝑟 } the type of this face.
• The dimension of this complex is 𝑑 − 1.
• The weight function we will use is the one induced by the uniform distribution on the set
𝒳(𝑑 − 1) of maximal faces.
A simplicial complex constructed this way is partite in the sense that each maximal face
consists of vertices of distinct types.
It follows from the definition, that 𝒳(𝑖) is precisely the set of cosets of the form 𝑔𝐾 𝑆 where
𝐾 𝑆 = 𝑗∈𝑆 𝐾 𝑗 for sets 𝑆 ⊆ [𝑑] of size exactly 𝑖 + 1. In particular, 𝒳(𝑑 − 1), the set of maximal
Ñ
faces, is in 1-1 correspondence with the group 𝐺 if 𝑗∈[𝑑] 𝐾 𝑗 = {id} where “id” is the identity
Ñ
element of the group 𝐺.
Connectivity
Observation 3.2. 𝑔1 𝐾1 ∩ 𝑔2 𝐾 2 ≠ ∅ if and only if 𝑔1−1 𝑔2 ∈ 𝐾 1 𝐾 2 .
Proof. (⇒) Say 𝑥 = 𝑔1 𝑘 1 = 𝑔2 𝑘 2 for 𝑘 1 ∈ 𝐾 1 and 𝑘 2 ∈ 𝐾2 . Then 𝑔1−1 𝑔2 = 𝑔1−1 𝑥 · 𝑥 −1 𝑔2 = 𝑘1 𝑘 2−1 ∈
𝐾1 𝐾2 .
(⇐) If 𝑔1−1 𝑔2 = 𝑘 1 𝑘 2 for some 𝑘 1 ∈ 𝐾 1 and 𝑘 2 ∈ 𝐾2 , then 𝑔1 𝑘 1 = 𝑔2 𝑘 2−1 ∈ 𝑔1 𝐾1 ∩ 𝑔2 𝐾 2 .
Lemma 3.3 (Criterion for connected 1-skeletons). The 1-skeleton of 𝒳(𝐺, {𝐾 1 , . . . , 𝐾 𝑑 }) is connected
if and only if 𝐺 = h𝐾1 , . . . , 𝐾 𝑑 i.
Proof. (⇐) Since there is always an edge between 𝑔𝐾 𝑖 and 𝑔𝐾 𝑗 for 𝑖 ≠ 𝑗, it suffices to show that
𝐾 1 is connected to 𝑔𝐾1 for an arbitrary 𝑔 ∈ 𝐺. Suppose, for an arbitrary element 𝑔 ∈ 𝐺, we have
𝑔 = 𝑔1 . . . 𝑔 𝑟 where 𝑔 𝑗 ∈ 𝐾 𝑖 𝑗 and 𝑖 𝑗 ≠ 𝑖 𝑗+1 for each 𝑗. We might, without loss of generality, assume
that (a) 𝑔1 ∈ 𝐾 1 (otherwise set 𝑔 = 1 · 𝑔1 · · · 𝑔 𝑟 ) and (b) if 𝑟 ≥ 2, then 𝑖 𝑟 ≠ 1 (since otherwise we
might then have worked with 𝑔 0 = 𝑔1 𝑔2 . . . 𝑔 𝑟−1 as 𝑔𝐾 1 = 𝑔 0𝑔 𝑟 𝐾 1 = 𝑔 0 𝐾1 ).
Then, we get the following path connecting 𝐾1 and 𝑔𝐾 𝑖 𝑟
𝐾 1 = 𝑔1 𝐾 𝑖1 → (𝑔1 𝑔2 )𝐾 𝑖2 → (𝑔1 𝑔2 𝑔3 )𝐾 𝑖3 → . . . → (𝑔1 · · · 𝑔 𝑟 )𝐾 𝑖 𝑟 = 𝑔𝐾 𝑖 𝑟 .
Note that, due to Observation 3.2, each successive pair of cosets are connected by an edge in the
simplicial complex. Now, since 𝑔𝐾 𝑖 𝑟 is adjacent to 𝑔𝐾 1 (as 𝑖 𝑟 ≠ 1), we have that 𝐾 1 is connected
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 5
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
to 𝑔𝐾 1 .
(⇒) For an arbitrary 𝑔 ∈ 𝐺, since the 1-skeleton is connected we have a path
𝐾 1 = 𝑔0 𝐾 𝑖0 → 𝑔1 𝐾 𝑖1 → · · · → 𝑔 𝑟 𝐾 𝑖 𝑟 = 𝑔𝐾1 .
By Observation 3.2, for every 𝑗 = 0, . . . , 𝑟 − 1, we have 𝑔 −1 𝑗
𝑔 𝑗+1 ∈ 𝐾 𝑖 𝑗 𝐾 𝑖 𝑗+1 ∈ h𝐾 1 , . . . , 𝐾 𝑑 i.
Therefore,
𝑔 = (𝑔0−1 𝑔1 ) · (𝑔1−1 𝑔2 ) · · · (𝑔 𝑟−1
−1
𝑔 𝑟 ) ∈ h𝐾 1 , . . . , 𝐾 𝑑 i .
Structure of links of the coset complex
For any set 𝑆 ⊆ [𝑑], define the group 𝐾 𝑆 := 𝑖∈𝑆 𝐾 𝑖 ; let 𝐾 ∅ := h𝐾 1 , . . . , 𝐾 𝑑 i. The following lemma
Ñ
shows that the links of a coset complex are themselves coset complexes.
Lemma 3.4. For any 𝑣 ∈ 𝒳(𝑘) of type 𝑆 ⊆ [𝑑], the link 𝑋𝑣 is isomorphic to the simplicial complex
defined by 𝒳(𝐾 𝑆 , {𝐾 𝑆 ∩ 𝐾 𝑖 : 𝑖 ∉ 𝑆}).
Proof. It suffices to prove this lemma for 𝑣 ∈ 𝒳(0) as links of higher levels can be obtained by
inductive applications of this case.
Observe that if 𝑔 is any element of 𝐺, then (𝑔 𝑖1 𝐾 𝑖1 , . . . , 𝑔 𝑖 𝑟 𝐾 𝑖 𝑟 ) ∈ 𝒳(𝑟 − 1) if and only if
(𝑔𝑔 𝑖1 𝐾 𝑖1 , . . . , 𝑔𝑔 𝑖 𝑟 𝐾 𝑖 𝑟 ) ∈ 𝒳(𝑟 − 1). Therefore, the link of a coset 𝑔𝐾 𝑖 is isomorphic to the link of
the coset 𝐾 𝑖 . Thus, it suffices to prove the lemma for links of the type 𝑋𝐾 𝑖 for some 𝑖 ∈ [𝑑].
Let 𝑣 be the coset 𝐾1 , without loss of generality. The vertices of the link, 𝑋𝑣 (0), are cosets of
𝐾 2 , . . . , 𝐾 𝑑 that have a non-empty intersection with 𝐾 1 . Note that any non-empty intersection
𝑔 𝑗 𝐾 𝑗 ∩ 𝐾1 of a coset with 𝐾1 is itself a coset 𝑔˜ 𝑗 (𝐾 𝑗 ∩ 𝐾 1 ) of the intersection subgroup 𝐾 𝑗 ∩ 𝐾1 in
𝐾 1 . Indeed, suppose that 𝑔 𝑗 ℎ 𝑗 ∈ 𝐾1 for some ℎ 𝑗 ∈ 𝐾 𝑗 . Then, 𝑔 𝑗 ℎ 𝑗 𝐾 𝑗 = 𝑔 𝑗 𝐾 𝑗 and 𝑔 𝑗 ℎ 𝑗 𝐾1 = 𝐾 1 and
hence
𝑔 𝑗 𝐾 𝑗 ∩ 𝐾 1 = 𝑔 𝑗 ℎ 𝑗 𝐾 𝑗 ∩ 𝑔 𝑗 ℎ 𝑗 𝐾1 = 𝑔 𝑗 ℎ 𝑗 (𝐾 𝑗 ∩ 𝐾 1 ).
vertices of the link 𝑋𝑣 (0) are in bijective correspondence with the cosets of the
Therefore, the
subgroups 𝐾 𝑗 ∩ 𝐾 1 : 𝑗 ∈ {2, . . . , 𝑑} .
The maximal faces in 𝑋 that contain the coset 𝐾 1 are precisely the 𝑑-sets {𝐾 1 , 𝑔2 𝐾2 , . . . , 𝑔 𝑑 𝐾 𝑑 }
of cosets with a non-empty intersection and hence
∅ ≠ 𝐾 1 ∩ 𝑔2 𝐾2 ∩ · · · ∩ 𝑔 𝑑 𝐾 𝑑 = (𝑔2 𝐾2 ∩ 𝐾1 ) ∩ · · · ∩ (𝑔 𝑑 𝐾 𝑑 ∩ 𝐾 1 ) = 𝑔˜ 2 (𝐾2 ∩ 𝐾1 ) ∩ · · · ∩ 𝑔˜ 𝑑 (𝐾 𝑑 ∩ 𝐾1 ),
which are precisely the maximal faces of the coset complex 𝒳 𝐾1 , 𝐾 𝑗 ∩ 𝐾 1 : 𝑗 ∈ {2, . . . , 𝑑} .
This establishes the isomorphism between 𝑋𝑣 and 𝒳 𝐾 1 , 𝐾 𝑗 ∩ 𝐾 1 : 𝑗 ∈ {2, . . . , 𝑑} .
4 A concrete instantiation
The simplicial complex of Kaufman and Oppenheim [4, See STOC version] is a specific
instantiation of the above coset complex construction. This section is devoted to an exposition of
this instantiation of Kaufman and Oppenheim. We will need some notation to describe their
group.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 6
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
Notation
• Let 𝑝 be a prime power and consider the ring 𝔽 𝑝 [𝑡] of polynomials over the finite field
𝔽 𝑝 . Let 𝑅 denote the quotient ring 𝔽 𝑝 [𝑡]/h𝑡 𝑠 i where h𝑡 𝑠 i denotes the ideal generated by
𝑡 𝑠 . This is a ring whose elements can be identified with polynomials in 𝔽 𝑝 [𝑡] of degree
less than 𝑠 (where addition and multiplication are performed modulo 𝑡 𝑠 ), with 𝑡 being a
formal variable and 𝑠 a positive integer3. By increasing the value of 𝑠, the construction
will provide a family of complexes on a growing number of vertices.
• For any 𝑑 ≥ 3, and 1 ≤ 𝑖, 𝑗 ≤ 𝑑 with 𝑖 ≠ 𝑗 and an element 𝑟 ∈ 𝑅, we define 𝑒 𝑖,𝑗 (𝑟) to be the
𝑑 × 𝑑 elementary matrix with 1’s on the diagonal and 𝑟 on the (𝑖, 𝑗)-th entry.
For the sake of notational convenience, we shall extend this notation and write 𝑒 𝑘,ℓ (𝑟) :=
𝑒 𝑖,𝑗 (𝑟) for all 𝑘, ℓ ∈ ℤ such that 𝑘 ≡ 𝑖 (mod 𝑑) and ℓ ≡ 𝑗 (mod 𝑑) (1 ≤ 𝑖, 𝑗 ≤ 𝑑). For
example, 𝑒 𝑑,𝑑+1 (𝑟) refers to 𝑒 𝑑,1 (𝑟).
We will extend further and use {𝑖, 𝑖 + 1, . . . , 𝑗 − 1} mod 𝑑 to denote the set 𝑖, 𝑖 + 1, · · · 𝑗 − 1
when 𝑖 < 𝑗, and the set {𝑖, 𝑖 + 1, . . . 𝑑, 1, 2, . . . , 𝑗 − 1} when 𝑗 ≤ 𝑖.
We are now ready to describe the groups in the construction.
For 𝑖 ∈ {1, . . . , 𝑑}, 𝐾 𝑖 = 𝑒 𝑗,𝑗+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 , 𝑗 ∈ [𝑑] \ {𝑖} .
𝐺 = h𝐾 1 , . . . , 𝐾 𝑑 i
Each 𝐾 𝑖 is generated by elementary matrices that have 1’s on the diagonal and an arbitrary
linear polynomial in one entry of the generalised diagonal {(𝑖, 𝑗) : 𝑖 + 1 ≡ 𝑗 (mod 𝑑)}.
It so happens that the group 𝐺 generated by the subgroups 𝐾 1 , . . . , 𝐾 𝑑 is SL𝑑 (𝑅), the group
of 𝑑 × 𝑑 matrices with entries in 𝑅 whose determinant is 1 (in 𝑅). This is a non-trivial fact (see
[3, Theorem 4.3.9]). All we will need is the simpler fact that |𝐺| grows exponentially with 𝑠 (for
fixed 𝑝 and 𝑑) while the size of the groups 𝐾 𝑖 are functions of 𝑝 and 𝑑 (and independent of 𝑠).
This will follow from the sequence of observations and lemmas developed in the following
section.
Given the above definition, there are two “different” subgroups we can define.
Ù
𝐾𝑆 = 𝐾𝑖 ,
𝑖∈𝑆
𝐾
f𝑆 := 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 , 𝑖 ∉ 𝑆 .
That is, 𝐾 𝑆 is the intersection of the groups {𝐾 𝑖 : 𝑖 ∈ 𝑆}, and 𝐾
f𝑆 is the group generated by the
intersection of the sets of generators of the 𝐾 𝑖 . Thus, clearly, 𝐾
f𝑆 ⊆ 𝐾 𝑆 . The following lemma
shows that in fact the two groups are identical.
3In the subsequent journal version [4], the authors generalise the ring 𝑅 to any unital commutative ring. For the
purposes of this exposition, we focus exclusively on finite rings of the form described above.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 7
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
Lemma 4.1 (Intersections of 𝐾 𝑖 ’s). For any 𝑆 ⊆ [𝑑],
Ù
𝐾
f𝑆 = 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 , 𝑖 ∉ 𝑆 = 𝐾 𝑖 = 𝐾𝑆
𝑖∈𝑆
In other words, the group generated by the intersection of generators equals the group intersection.
We will prove this lemma in the following section by giving an explicit description of the
groups that makes the above lemma evident. An immediate consequence of this lemma is that
𝐾 [𝑑] = {id} and hence 𝒳(𝑑 − 1), the set of maximal faces, is in 1-1 correspondence with the
group 𝐺.
4.1 Explicit description of the groups
The following is an easy consequence of the definition of 𝑒 𝑖,𝑗 (𝑟). Note that 𝑒 𝑖,𝑗 (𝑟) is defined only
if 𝑖 ≠ 𝑗.
Observation 4.2. (a) Sum: 𝑒 𝑖,𝑗 (𝑟1 ) · 𝑒 𝑖,𝑗 (𝑟2 ) = 𝑒 𝑖,𝑗 (𝑟1 + 𝑟2 ).
As a corollary, 𝑒 𝑖,𝑗 (𝑟)−1 = 𝑒 𝑖,𝑗 (−𝑟).
(b) Product: If 𝑖 ≠ ℓ , the commutator4 [𝑒 𝑖,𝑗 (𝑟1 ), 𝑒 𝑘,ℓ (𝑟2 )] behaves as follows.
(
𝑒 𝑖,ℓ (𝑟1 𝑟2 ) if 𝑗 = 𝑘,
[𝑒 𝑖,𝑗 (𝑟1 ), 𝑒 𝑘,ℓ (𝑟2 )] =
id if 𝑗 ≠ 𝑘.
Proof. Let 𝜇𝑖,𝑗 denote the matrix that has a 1 at the (𝑖, 𝑗)-th entry, and 0 everywhere. Then, (a)
follows as
𝑒 𝑖,𝑗 (𝑟1 )𝑒 𝑖,𝑗 (𝑟2 ) = (𝐼 + 𝜇𝑖,𝑗 𝑟1 ) · (𝐼 + 𝜇𝑖,𝑗 (𝑟2 ))
= 𝐼 + 𝜇𝑖,𝑗 · (𝑟1 + 𝑟2 ) (since 𝜇2𝑖,𝑗 = 0 when 𝑖 ≠ 𝑗).
As for (b), we follow along a similar calculation. Note that
(
0 if 𝑗 ≠ 𝑘
𝜇𝑖,𝑗 · 𝜇 𝑘,ℓ =
𝜇𝑖,ℓ if 𝑗 = 𝑘.
Therefore,
[𝑒 𝑖,𝑗 (𝑟1 ), 𝑒 𝑘,ℓ (𝑟2 )] = (𝐼 − 𝜇𝑖,𝑗 𝑟1 ) · (𝐼 − 𝜇 𝑘,ℓ 𝑟2 ) · (𝐼 + 𝜇𝑖,𝑗 𝑟1 ) · (𝐼 + 𝜇 𝑘,ℓ 𝑟2 ).
When 𝑗 = 𝑘 (along with the assumption that 𝑖 ≠ 𝑗, 𝑘 ≠ ℓ ), this simplifies to
[𝑒 𝑖,𝑗 (𝑟1 ), 𝑒 𝑘,ℓ (𝑟2 )] = (𝐼 − 𝜇𝑖,𝑗 𝑟1 − 𝜇 𝑘,ℓ 𝑟2 + 𝜇𝑖,ℓ · 𝑟1 𝑟2 ) · (𝐼 + 𝜇𝑖,𝑗 𝑟1 + 𝜇 𝑘,ℓ 𝑟2 + 𝜇𝑖,ℓ · 𝑟1 𝑟2 )
= 𝐼 + 𝜇𝑖,𝑗 (𝑟1 − 𝑟1 ) + 𝜇 𝑘,ℓ (𝑟2 − 𝑟2 ) + 𝜇𝑖,ℓ (𝑟1 𝑟2 + 𝑟1 𝑟2 − 𝑟1 𝑟2 )
= 𝐼 + 𝑟1 𝑟2 𝜇𝑖,ℓ .
4The commutator of two elements 𝑔, ℎ, denoted by [𝑔, ℎ], is defined as 𝑔 −1 ℎ −1 𝑔 ℎ. (Definition B.3)
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 8
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
If 𝑗 ≠ 𝑘, then we get
[𝑒 𝑖,𝑗 (𝑟1 ), 𝑒 𝑘,ℓ (𝑟2 )] = (𝐼 − 𝜇𝑖,𝑗 𝑟1 ) · (𝐼 − 𝜇 𝑘,ℓ 𝑟2 ) · (𝐼 + 𝜇𝑖,𝑗 𝑟1 ) · (𝐼 + 𝜇 𝑘,ℓ 𝑟2 ).
= 𝐼 + 𝜇𝑖,𝑗 (𝑟1 − 𝑟1 ) + 𝜇 𝑘,ℓ (𝑟2 − 𝑟2 ) = 𝐼
Therefore, for distinct 𝑖, 𝑗, 𝑘 ∈ [𝑑] (which exist when 𝑑 ≥ 3), we have
𝑒 𝑖,𝑗 (𝑟1 ), 𝑒 𝑗,𝑖 (𝑟2 ), 𝑒 𝑖,𝑘 (𝑟3 ) = 𝑒 𝑖,𝑘 (𝑟1 𝑟2 𝑟3 )
Thus, for all 𝑑 ≥ 3, using the above observation along with Observation 4.2(a), we get that
𝑒 𝑖,𝑗 (𝑟) for any 𝑟 ∈ 𝑅 can be generated by 𝑒 𝑘,ℓ (𝑎𝑡 + 𝑏) : 𝑘, ℓ ∈ [𝑑] , 𝑎, 𝑏 ∈ 𝔽 𝑝 . This in particular
implies that |𝐺| is at least 𝑝 𝑠 . On the other hand, the size of 𝐾 𝑖 depends only on 𝑑, 𝑝 and is
independent of 𝑠. The lemma below describes 𝐾 𝑑 ; the other 𝐾 𝑖 are just rearrangements of rows
and columns in 𝐾 𝑑 .
Lemma 4.3 (Explicit description of 𝐾 𝑑 ). The group 𝐾 𝑑 = 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 , 𝑖 ≠ 𝑑 consists
of the matrices 𝐴 = (𝐴 𝑖,𝑗 ) of the following form:
if 𝑖 = 𝑗,
1
𝐴 𝑖,𝑗 = a polynomial of degree ≤ 𝑗 − 𝑖 if 𝑖 < 𝑗,
if 𝑖 > 𝑗.
0
Stating the above differently, for any 𝑛 ∈ [𝑑], the group 𝐾 𝑛 = 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 , 𝑖 ≠ 𝑛
consists of the matrices 𝐴 = (𝐴 𝑖,𝑗 ) of the following form:
if 𝑖 = 𝑗,
1
𝐴 𝑖,𝑗 = a polynomial of degree (𝑗 − 𝑖) mod 𝑑 if 𝑗 ≠ 𝑖 and 𝑛 ∉ {𝑖, 𝑖 + 1, . . . , 𝑗 − 1} mod 𝑑 ,
otherwise.
0
Proof. Follows by repeated application of Observation 4.2.
Therefore, we can obtain a crude bound of |𝐾 𝑖 | ≤ 𝑝 𝑂(𝑑 ) for any 𝑖. Also, the above lemma also
3
gives an explicit description of the groups 𝐾 𝑆 .
Corollary 4.4 (Explicit description of 𝐾 𝑆 ). For any subset 𝑆 ⊆ [𝑑], the group 𝐾 𝑆 = 𝑖∈𝑆 𝐾 𝑖 consists
Ñ
of matrices 𝐴 = (𝐴 𝑖,𝑗 ) of the following form:
if 𝑖 = 𝑗,
1
𝐴 𝑖,𝑗 = a polynomial of degree (𝑗 − 𝑖) mod 𝑑 if 𝑗 ≠ 𝑖 and {𝑖, 𝑖 + 1, . . . , 𝑗 − 1} mod 𝑑 ∩ 𝑆 = ∅,
otherwise.
0
Recall the other set of subgroups defined for each 𝑆 ⊆ [𝑑]:
𝐾
f𝑆 := 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 , 𝑖 ∉ 𝑆 .
These groups can also be explicitly described.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 9
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
f𝑆 ). For any ∅ ≠ 𝑆 ⊆ [𝑑], the group 𝐾
Lemma 4.5 (Explicit description of 𝐾 f𝑆 is the set of all 𝑑 × 𝑑
matrices 𝐴 = (𝑎 𝑖𝑗 ) of the form
if 𝑖 = 𝑗,
1
𝑎 𝑖,𝑗 = a polynomial of degree ≤ 𝑗 − 𝑖 if 𝑗 ≠ 𝑖 and {𝑖, 𝑖 + 1, . . . , 𝑗 − 1} mod 𝑑 ∩ 𝑆 = ∅,
otherwise.
0
Proof. Any 𝐴 ∈ 𝐾 f𝑆 can be expressed as 𝐴 = 𝐵1 · · · 𝐵𝑚 where each 𝐵𝑟 = 𝑒 𝑖 𝑟 ,𝑖 𝑟 +1 (ℓ 𝑟 ), for some linear
polynomial ℓ 𝑟 , with 𝑖 𝑟 ∉ 𝑆. Then,
Õ
𝐴 𝑖,𝑗 = (𝐵1 )𝑖1 ,𝑖2 (𝐵2 )𝑖2 ,𝑖3 · · · (𝐵𝑚 )𝑖 𝑚 ,𝑖 𝑚+1 .
𝑖 1 ,...,𝑖 𝑚+1
𝑖 1 =𝑖 , 𝑖 𝑚+1 =𝑗
From the structure of each 𝐵𝑟 , any nonzero contribution from the RHS must involve either
𝑖 𝑟+1 = 𝑖 𝑟 , or 𝑖 𝑟+1 = 𝑖 𝑟 + 1 if 𝑟 ∉ 𝑆. This forces that the only entries of 𝐴 that are nonzero, besides
the diagonal, are at (𝑖, 𝑗) with none of {𝑖, 𝑖 + 1, . . . , 𝑗 − 1} in 𝑆.
In the case when {𝑖, 𝑖 + 1, . . . , 𝑗 − 1} ∩ 𝑆 = ∅, the above argument also shows that the entry
𝐴 𝑖,𝑗 has degree at most 𝑗 − 𝑖. Furthermore, using Observation 4.2, we can easily see that
𝑒 𝑖,𝑗 ( 𝑓 ) ∈ 𝐾
f𝑆 for an arbitrary polynomial 𝑓 (𝑡) of degree at most 𝑗 − 𝑖. From this, we can deduce
that the structure of 𝐾 f𝑆 is exactly as claimed.
Proof of Lemma 4.1. Follows immediately from Corollary 4.4 and Lemma 4.5.
From this point on, since the groups 𝐾 𝑆 and 𝐾
f𝑆 are identical, we drop the tilde notation and use
𝐾 𝑆 for 𝐾
f𝑆 .
4.2 Connectivity of the coset complex
Lemma 4.6. Let 𝑆 ⊂ [𝑑] with |𝑆| ≤ 𝑑 − 2. Then,
𝐾 𝑆 = h𝐾 𝑆 ∩ 𝐾 𝑖 : 𝑖 ∈ [𝑑] \ 𝑆i .
Proof. It is clear that 𝐾 𝑆 is a superset of the RHS. It only remains to show that the other
containment also holds. To see this, consider an arbitrary generator 𝑒 𝑗,𝑗+1 (𝑟) of 𝐾 𝑆 . Since 𝑗 ∉ 𝑆
and |𝑆| ≤ 𝑑 − 2, there is some 𝑖 ∈ [𝑑] \ (𝑆 ∪ {𝑗}). Therefore, 𝑒 𝑗,𝑗+1 (𝑟) ∈ 𝐾 𝑆 ∩ 𝐾 𝑖 and hence is
generated by the RHS.
Combining the above lemma with Lemma 3.3 and Lemma 3.4, we have the following corollary.
Corollary 4.7. For the coset complex 𝒳(𝐺, {𝐾 1 , . . . , 𝐾 𝑑 }) defined by the above groups, the 1-skeleton of
every link is connected.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 10
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
5 Spectral expansion of the complex
In this section we prove that the coset complex 𝒳(𝐺, {𝐾1 , . . . , 𝐾 𝑑 }) is a good spectral HDX. The
Descent Theorem (Theorem 2.5) states that it suffices to show that the 1-dimensional links of
faces in 𝒳(𝑑 − 3) are good spectral expanders.
5.1 Structure of 1-dimensional links
One-dimensional links of the coset complex constructed are links of 𝑣 ∈ 𝒳(𝐺, {𝐾1 , . . . , 𝐾 𝑑 }) of
exactly 𝑑 − 2 (which are elements of 𝒳(𝑑 − 3)). Any such 𝑣 can be written as {𝑔𝐾1 , . . . , 𝑔𝐾 𝑑 } \
size
𝑔𝐾 𝑖 , 𝑔𝐾 𝑗 for 𝑖, 𝑗 ∈ [𝑑] with 𝑖 ≠ 𝑗 and 𝑔 ∈ 𝐺. Since the link of 𝑣 is isomorphic to the link of
{𝐾1 , . . . , 𝐾 𝑑 } \ 𝐾 𝑖 , 𝐾 𝑗 , we might as well assume that 𝑔 = id. These happen to be of two types
depending on whether 𝑖 and 𝑗 are consecutive or not.
Observation 5.1. Consider 𝑣 = {𝐾1 , . . . , 𝐾 𝑑 } \ 𝐾 𝑖 , 𝐾 𝑗 where 𝑖 and 𝑗 are not consecutive (i. e.,
(𝑖 − 𝑗) ≠ ±1 mod 𝑑). Then the 1-dimensional link of 𝑣 is a complete bipartite graph.
Proof. Note that since 𝑗 ≠ 𝑖 ± 1, we have [𝑒 𝑖,𝑖+1 (𝑟1 ), 𝑒 𝑗,𝑗+1 (𝑟2 )] = id by Observation 4.2. Hence,
these two elements commute.
The link of 𝑣 corresponds to the coset complex 𝒳(𝐻, {𝐻1 , 𝐻2 }) where
𝐻 = 𝐾 [𝑑]\{𝑖,𝑗} = 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏), 𝑒 𝑗,𝑗+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 ,
𝐻1 = 𝐾 [𝑑]\{𝑖} = 𝑒 𝑖,𝑖+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 ,
𝐻2 = 𝐾 [𝑑]\{𝑗} = 𝑒 𝑗,𝑗+1 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 .
Thus, the groups 𝐻1 and 𝐻2 commute with each other and hence any element of ℎ ∈ 𝐻 can be
written as ℎ = 𝑔1 · 𝑔2 where 𝑔1 ∈ 𝐻1 and 𝑔2 ∈ 𝐻2 . Observation 3.2 implies that the resulting
graph is the complete bipartite graph.
The interesting case is when 𝑣 = {𝐾1 , . . . , 𝐾 𝑑 } \ {𝐾 𝑖 , 𝐾 𝑖+1 }. Without loss of generality, we may
focus on the link of 𝑣 = {𝐾 3 , 𝐾4 , . . . , 𝐾 𝑑 }. This corresponds to the coset complex 𝒳(𝐻, {𝐻1 , 𝐻2 })
where
𝐻 = 𝐾3,4,...,𝑑 = 𝑒1,2 (𝑎𝑡 + 𝑏), 𝑒2,3 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 ,
𝐻1 = 𝐾2,3,4,...,𝑑 = 𝑒1,2 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 ,
𝐻2 = 𝐾1,3,4,...,𝑑 = 𝑒2,3 (𝑎𝑡 + 𝑏) : 𝑎, 𝑏 ∈ 𝔽 𝑝 .
Hence, it suffices to focus on the first three rows and columns of these matrices as the rest of
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 11
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
them are constant. Written down explicitly,
1
ℓ 1 𝑄
ℓ 1 , ℓ2 are linear polynomials in 𝔽 𝑝 [𝑡]
𝐻 = 0 1 ℓ2 : ,
and 𝑄 is a quadratic polynomial in 𝔽 𝑝 [𝑡]
0
0 1
1
ℓ 0
𝐻1 = 0 1 0 : ℓ is a linear polynomial in 𝔽 𝑝 [𝑡] ,
0
0 1
1 0 0
𝐻2 = 0 1 ℓ : ℓ is a linear polynomial in 𝔽 𝑝 [𝑡] .
0
0 1
Multiplication of an arbitrary element of 𝐻 with an arbitrary element of 𝐻1 is of the form
1 ℓ 1 𝑄 1 ℓ 0 1 ℓ 1 + ℓ 𝑄
0 1 ℓ 2 · 0 1 0 = 0 ℓ .
1 2
0 0 1 0 0 1 0 0 1
Note that the a unique choice of ℓ that makes the (1, 2)-th entry of the RHS zero is ℓ = −ℓ1 . Thus,
each coset of 𝐻1 in 𝐻 has a unique representative of the form 𝑀1 (ℓ , 𝑄) described below, and
similarly, each coset of 𝐻2 in 𝐻 has a unique representative of the form 𝑀2 (ℓ , 𝑄):
1 0 𝑄 1 ℓ 𝑄
𝑀1 (ℓ , 𝑄) := 0 1 ℓ , 𝑀2 (ℓ , 𝑄) := 0 1 0
0 0 1 0 0 1
respectively, where ℓ is a linear polynomial and 𝑄 is a quadratic polynomial in 𝔽 𝑝 [𝑡]. This is
because any element of 𝐻 can be uniquely written as
1 ℓ 1 𝑄 1 ℓ 1 𝑄 − ℓ 1ℓ 2 1 0 0
0 1 ℓ 2 = 0 0 1 ℓ 2
1 0
0 0 1 0 0 1 0 0 1
1 0 𝑄 − ℓ1ℓ 2 1 ℓ1 0
ℓ 2 0 1 0 .
= 0 1
0 0 1 0 0 1
Lemma 5.2. For linear polynomials ℓ 1 , ℓ2 ∈ 𝔽 𝑝 [𝑡] and quadratic polynomials 𝑄 1 , 𝑄2 ∈ 𝔽 𝑝 [𝑡], we have
that
𝑀1 (ℓ 1 , 𝑄1 )𝐻1 ∩ 𝑀2 (ℓ 2 , 𝑄2 )𝐻2 ≠ ∅ ⇐⇒ ℓ 1ℓ2 = 𝑄 1 − 𝑄2 .
Proof. Note that matrices in 𝐻1 𝐻2 are of the form
1 ℓ 1 0 1 0 0 1 ℓ 1 ℓ 1 ℓ 2
0 1 0 0 1 ℓ 2 = 0 1 ℓ 2 .
0 0 1 0 0 1 0 0 1
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 12
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
By Observation 3.2, the cosets have a non-empty intersection if and only if
1 0 −𝑄1 1 ℓ2 𝑄2 1 ℓ2 𝑄2 − 𝑄1
−1
𝐻1 𝐻2 3 𝑀1 (ℓ 1 , 𝑄1 ) 𝑀2 (ℓ 2 , 𝑄2 ) = 0 1 −ℓ1 0 1 0 = 0 1
−ℓ 1
0 0 1 0 0 1 0 0 1
which happens if and only if (ℓ 2 )(−ℓ1 ) = 𝑄2 − 𝑄 1 which is the same as 𝑄1 − 𝑄 2 = ℓ 1ℓ 2 .
Therefore, the 1-dimensional link is the bipartite graph 𝐴 = (𝑈 , 𝑉 , 𝐸) with left and right
vertices identified by pairs (ℓ , 𝑄) where ℓ and 𝑄 are linear and quadratic polynomials in 𝔽 𝑝 [𝑡],
respectively, with (ℓ 1 , 𝑄1 ) ∼ (ℓ 2 , 𝑄2 ) ⇔ ℓ1ℓ 2 = 𝑄1 + 𝑄2 (by associating 𝑀1 (ℓ , 𝑄) with the tuple
(ℓ , 𝑄) on the left, and 𝑀2 (ℓ , 𝑄) with the tuple (ℓ , −𝑄) on the right).
Note that 𝐴 is a 𝑝 2 -regular bipartite graph with 𝑝 5 vertices on each side. It suffices to show
that 𝐴 is a good expander.
Kaufman and Oppenheim [4] prove the expansion properties of this graph using the
representation theory of the associated groups, while we directly analyse the spectral gap of
the adjacency matrix associated with this graph. O’Donnell and Pratt [9, Case 2 in the Proof of
Theorem 3.23] give yet another proof of the spectral gap using the Polynomial Identity Lemma
(also referred to as the Schwartz–Zippel lemma).
5.2 A related graph
The following graph is the “lines-points” or the “affine plane” graph used by Reingold, Vadhan
and Wigderson [11] (as the base graph in their construction of constant-degree expanders, using
the zig-zag product). Let 𝔽 𝑞 be a finite field. Consider the bipartite graph 𝐵 𝑞 = (𝑈 0 , 𝑉 0 , 𝐸0)
defined as follows:
𝑈0 = 𝑉0 = 𝔽𝑞 × 𝔽𝑞 𝐸0 = {((𝑎, 𝑏), (𝑐, 𝑑)) : 𝑎𝑐 = 𝑏 + 𝑑} .
Note that the graph 𝐵 𝑞 is 𝑞-regular as for any 𝑎, 𝑏, 𝑐 ∈ 𝔽 𝑞 , there is a unique 𝑑 ∈ 𝔽 𝑞 such that
𝑎𝑐 = 𝑏 + 𝑑 and thus the vertex (𝑎, 𝑏) has exactly 𝑞 neighbours in 𝐵 𝑞 .
Lemma 5.3 ([11, Lemma 5.1]). The 𝑞-regular bipartite graph 𝐵 𝑞 is a √1𝑞 -one-sided spectral expander.
Proof. Let 𝐵2𝑞 denote the multigraph whose adjacency matrix is the square of the adjacency
matrix of 𝐵 𝑞 . Note that 𝐵2𝑞 is a multigraph as each edge in 𝐵2𝑞 corresponds to a length-two path
in 𝐵 𝑞 and there may be more than one such path between a pair of vertices. It is easy to see that
if 𝑎 ≠ 𝑐,
1
Number of edges between (𝑎, 𝑏) and (𝑐, 𝑑) in 𝐵2𝑞 = 𝑞 if 𝑎 = 𝑐 and 𝑏 = 𝑑,
0 otherwise.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 13
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
Therefore, the adjacency matrix of 𝐵2𝑞 can be written5 (under a suitable order of listing vertices)
as
𝑞𝐼 𝑞 2 + (𝐽𝑞 − 𝐼 𝑞 ) ⊗ 𝐽𝑞 (where 𝐽𝑞 is the 𝑞 × 𝑞 matrix of 1𝑠).
By observing that 𝐽𝑞 has eigenvalue of 𝑞 with multiplicity 1, and eigenvalue 0 with multiplicity
(𝑞 − 1), a simple calculation shows that 𝐵2𝑞 has eigenvalue of 𝑞 2 with multiplicity 1, eigenvalue 𝑞
with multiplicity 𝑞(𝑞 − 1) and eigenvalue 0 with multiplicity 𝑞 − 1. Hence the unnormalized
second largest eigenvalue of 𝐵2𝑞 is 𝑞 and hence we have that the normalized second largest
√
eigenvalue of 𝐵 𝑞 is 1/ 𝑞.
5.3 Relating the graph 𝐵 𝑞 with 𝐴
Set 𝑞 = 𝑝 3 so that 𝔽 𝑞 = 𝔽 𝑝 [𝑦]/h𝜇(𝑦)i for some irreducible polynomial 𝜇(𝑦) of degree 3. Therefore,
each element in 𝔽 𝑞 is expressible as 𝑎 0 + 𝑎 1 𝑦 + 𝑎 2 𝑦 2 for some 𝑎 0 , 𝑎1 , 𝑎2 ∈ 𝔽 𝑝 . Thus, the graph
𝐵 𝑞 = (𝑈 0 , 𝑉 0 , 𝐸0) defined above, for 𝑞 = 𝑝 3 , is a 𝑝 3 -regular bipartite graph with 𝑝 6 vertices on
either side.
Let 𝑈 00 = 𝑉 00 = (𝑎 0 + 𝑎 1 𝑦, 𝑏0 + 𝑏1 𝑦 + 𝑏2 𝑦 2 ) : 𝑎 0 , 𝑎1 , 𝑏0 , 𝑏1 , 𝑏2 ∈ 𝔽 𝑝 , which is a subset of 𝑈 0
and 𝑉 0, respectively, of size 𝑝 5 each.
Observation 5.4. The induced subgraph of 𝐵 𝑞 on 𝑈 00 , 𝑉 00 is exactly the graph 𝐴 = (𝑈 , 𝑉 , 𝐸)
described earlier.
Proof. Note that ((ℓ 1 (𝑦), 𝑄1 (𝑦)), (ℓ 2 (𝑦), 𝑄2 (𝑦))) ∈ 𝐸0 if and only if
ℓ1 (𝑦) · ℓ2 (𝑦) = 𝑄1 (𝑦) + 𝑄2 (𝑦) mod 𝜇(𝑦).
However, since the above equation has degree at most 2, we have
ℓ 1 (𝑦) · ℓ 2 (𝑦) = 𝑄 1 (𝑦) + 𝑄 2 (𝑦) ⇔ ℓ 1 (𝑦) · ℓ 2 (𝑦) = 𝑄 1 (𝑦) + 𝑄2 (𝑦) (mod 𝜇(𝑦)),
and the first equation is exactly the adjacency condition of the graph 𝐴. Hence, the induced
subgraph of 𝐵 𝑞 on 𝑈 00 , 𝑉 00 is indeed the graph 𝐴.
Normally, induced subgraphs of expanders need not even be connected. However, the
following lemma shows that there are some instances where we may be able to give non-trivial
bounds on 𝜆.
Lemma 5.5. Let 𝑋 be a 𝑑-regular graph that is an induced subgraph of a 𝐷-regular graph 𝑌. Then,
𝐷𝜆(𝑌)
𝜆(𝑋) ≤ .
𝑑
5In the equation, the notation ⊗ refers to the Kronecker product, or tensor product of matrices. It is well known
that, for square matrices 𝐴 and 𝐵, the multiset of eigenvalues of 𝐴 ⊗ 𝐵 is all products of the form 𝜆 𝑖 · 𝜈 𝑗 where 𝜆 𝑖 is
an eigenvalue of 𝐴 and 𝜈 𝑗 is an eigenvalue of 𝐵.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 14
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
Proof. The Courant–Fischer characterization of the second largest eigenvalue (Theorem A.1)
𝑎 𝑇 𝐺𝑎
tells us that 𝜆(𝑋) = max𝑎⊥1|𝑋 | 𝑑·𝑎 𝑇 𝑎 where 𝐺 is the adjacency matrix of 𝑋. Consider an arbitrary
𝑎 ∈ ℝ such that 𝑎 ⊥ 1|𝑋 | = 0. Since 𝑋 is an induced subgraph of 𝑌, the vector 𝑎 can be padded
|𝑋 |
with zeroes to obtain a vector 𝑏 𝑎 ∈ ℝ |𝑌| such that 𝑏 𝑎 ⊥ 1|𝑌| . Therefore, if 𝐴𝑋 and 𝐴𝑌 are the
normalised adjacency matrices of 𝑋 and 𝑌, we have
𝑎 𝑇 𝐴𝑋 𝑎 𝐷 𝑏 𝑇𝑎 𝐴𝑌 𝑏 𝑎 𝐷 𝑏 𝑇 𝐴𝑌 𝑏 𝐷𝜆(𝑌)
𝜆(𝑋) = max = · max ≤ · max = .
𝑎⊥1 |𝑋 | 𝑎 𝑎𝑇 𝑑 𝑎⊥1|𝑋 | 𝑏 𝑎 𝑏 𝑎
𝑇 𝑑 𝑏⊥1|𝑌| 𝑏 𝑏𝑇 𝑑
Corollary 5.6. The graph 𝐴(𝑈 , 𝑉 , 𝐸) corresponding to the 1-dimensional links of 𝒳(𝐺, {𝐾 1 , . . . , 𝐾 𝑑 })
is a √1𝑝 -one-sided spectral expander.
Proof. The graph 𝐵 𝑝 3 is a bipartite, 𝑝 3 -regular graph with 𝜆(𝐵 𝑝 3 ) ≤ 𝑝 3/2
1
and 𝐴(𝑈 , 𝑉 , 𝐸) is a
𝑝 2 -regular graph that is an induced subgraph of 𝐵 𝑝 3 . Hence, by Lemma 5.5,
𝑝 3 · (1/𝑝 3/2 ) 1
𝜆(𝐴) ≤ = √ .
𝑝2 𝑝
The final expansion bounds
From the corollary above, we obtain the following theorem of Kaufman and Oppenheim.
Theorem 5.7 ([4]). For 𝑝 > (𝑑 − 2)2 , the (𝑑 − 1)-dimensional coset complex 𝒳(𝐺, {𝐾1 , . . . , 𝐾 𝑑 }) is a
√ 1
𝑝−(𝑑−2)
-one-sided spectral HDX.
Proof. It follows directly from Theorem 2.5 that 𝒳(𝐺, {𝐾1 , . . . , 𝐾 𝑑 }) is a 𝛾-one-sided spectral
HDX for
1/√𝑝 1
𝛾≤ =√ .
√
1 − (𝑑 − 2)( / 𝑝 )
1 𝑝 − (𝑑 − 2)
Constructing two-sided spectral HDXs and standard expanders: The (𝑑 − 1)-dimensional
coset complex 𝒳(𝐺, {𝐾 1 , . . . , 𝐾 𝑑 }) is not a two-sided spectral HDX as the 1-skeletons of the links
of the faces in 𝒳(𝑑 − 3) are bipartite. However, if we restrict attention to the 𝑘-skeleton of 𝒳 for
some 𝑘 < 𝑑 − 1 then we can bound the least eigenvalue by applying the Descent Theorem to the
least eigenvalue (Theorem A.2(2)). This is summarized in the following corollary.
Corollary 5.8. For 𝑝 > (𝑑 − 2)2 and nany 1 ≤ 𝑘 < 𝑑 othe 𝑘-skeleton of the (𝑑 − 1)-dimensional coset
complex 𝒳(𝐺, {𝐾1 , . . . , 𝐾 𝑑 }) is a max √ 1
𝑝−(𝑑−2)
, 𝑑−𝑘
1
-two-sided spectral HDX.
n o
In particular, if we set 𝑘 = 1 in the above corollary, we get a standard max √ 1
𝑝−(𝑑−2)
, 𝑑−1
1
-
two-sided spectral expander. This graph is a 𝑑-partite graph and hence its least eigenvalue is at
most − 1/(𝑑 − 1), while the above argument shows that it is least (and hence equal to) − 1/(𝑑 − 1).
Thus, this not only yields an elementary construction and proof of one-sided spectral HDXs
(Theorem 5.7), but also one of standard spectral expander (Corollary 5.8).
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 15
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
A Proof of the Descent Theorem
For the sake of completeness, we present the proof of Theorem 2.5 that asserts that proving
spectral expansion for the maximal faces is sufficient to obtain expansion of any link. This
exposition is essentially from the lecture notes by Dikstein [1].
Let (𝑋 , 𝑤) be a weighted 𝑑-dimensional simplicial complex. Let 𝜇𝑑 = 𝑤| 𝑋(𝑑) be the distribu-
tion on the set 𝑋(𝑑) of (𝑑 + 1)-sized faces. This distribution induces distributions 𝜇𝑖 on 𝑋(𝑖) in
the natural way.
For two functions 𝑓 , 𝑔 : 𝑋(0) → ℝ, define their inner product h 𝑓 , 𝑔i 𝑋 = 𝔼𝑢∼𝜇0 [ 𝑓 (𝑢)𝑔(𝑢)]. We
will drop the subscript 𝑋 if it is clear from context. Note that, by the definition of 𝜇1 , sampling
𝑢 according to 𝜇0 can be equivalently achieved by sampling an edge (𝑢, 𝑣) according to 𝜇1 and
returning one of the points uniformly at random. Therefore,
h 𝑓 , 𝑔i 𝑋 = 𝔼𝑢∼𝜇0 [ 𝑓 (𝑢)𝑔(𝑢)] = 𝔼{𝑢,𝑣}∼𝜇1 [ 𝑓 (𝑢)𝑔(𝑢)] = 𝔼𝑣∼𝜇0 𝔼𝑢∼𝑋𝑣 (0) [ 𝑓 (𝑢)𝑔(𝑢)] = 𝔼𝑣∼𝜇0 [h 𝑓𝑣 , 𝑔𝑣 i 𝑋𝑣 ],
(A.1)
where 𝑓𝑣 , 𝑔𝑣 : 𝑋𝑣 (0) → ℝ are the restrictions to the link of 𝑣.
Define the adjacency operator 𝐴 that, on a function 𝑓 : 𝑋(0) → ℝ on vertices returns another
function 𝐴 𝑓 on vertices defined via
𝐴 𝑓 (𝑣) = 𝔼𝑢∼𝑣 [ 𝑓 (𝑢)],
where 𝑢 ∼ 𝑣 refers to a random neighbour of 𝑣 according to the distribution 𝑢 ∼ 𝜇0 (𝑋𝑣 ). In
other words, 𝐴 averages 𝑓 over neighbours. Furthermore, 𝐴 is self-adjoint with respect to the
above inner product, i.e, h𝐴 𝑓 , 𝑔i = h 𝑓 , 𝐴𝑔i. Hence, it has 𝑛 real eigenvalues and an orthonormal
set of eigenvectors. Clearly 𝐴1 = 1; the constant 1 function is an eigenvector for this operator (in
fact, it is an eigenvector corresponding to the largest eigenvalue 1). The remaining eigenvalues
are characterized by the Courant–Fischer Theorem, stated below.
Theorem A.1 (Courant–Fischer). Let 𝐴 ∈ ℝ 𝑛×𝑛 be an 𝑛 × 𝑛 matrix over the reals that is self-adjoint
with respect to some inner product h·, ·i : ℝ 𝑛 × ℝ 𝑛 → ℝ. Then 𝐴 has 𝑛 real eigenvalues 𝜆1 ≥ · · · ≥ 𝜆𝑛
which have the following characterization.
h𝑥, 𝐴𝑥i h𝑥, 𝐴𝑥i
𝜆𝑖 = max min = min max .
𝑉 : dim 𝑉=𝑖 0≠𝑥∈𝑉 h𝑥, 𝑥i 𝑉 : dim 𝑉=𝑛−𝑖+1 0≠𝑥∈𝑉 h𝑥, 𝑥i
Similar to (A.1), we have
h𝐴 𝑓 , 𝑔i 𝑋 = 𝔼{𝑢,𝑤}∼𝜇1 [ 𝑓 (𝑢)𝑔(𝑤)] = 𝔼{𝑢,𝑣,𝑤}∼𝜇2 [ 𝑓 (𝑢)𝑔(𝑤)]
= 𝔼𝑣∼𝜇0 𝔼{𝑢,𝑤}∼𝜇1 (𝑋𝑣 ) [ 𝑓 (𝑢)𝑔(𝑤)]
= 𝔼𝑣∼𝜇0 h𝐴𝑣 𝑓𝑣 , 𝑔𝑣 i 𝑋𝑣
(A.2)
where 𝐴𝑣 denotes the adjacency operator restricted to the link 𝑋𝑣 .
With the above notation, we can now state the theorem we wish to prove. It suffices to prove
the theorem in the case of 𝑑 = 3 as we can obtain Theorem 2.5 by induction.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 16
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
Theorem A.2. Suppose (𝑋 , 𝑤) is weighted 2-dimensional simplicial complex. Then, we have the
following two implications:
1. Suppose the 1-skeleton of 𝑋 is connected and for every vertex 𝑣 ∈ 𝑋(0), h𝐴𝑣 𝑓 , 𝑓 i ≤ 𝜆 h 𝑓 , 𝑓 i for
all 𝑓 : 𝑋𝑣 (0) → ℝ with 𝑓 ⊥ 1𝑋𝑣 for some 𝜆 ∈ [0, 1). Then, for any 𝑔 : 𝑋(0) → ℝ with 𝑔 ⊥ 1𝑋 ,
𝜆
we have h𝐴𝑔, 𝑔i ≤ 𝛾 h𝑔, 𝑔i where 𝛾 ≤ 1−𝜆 .
2. Suppose the 1-skeleton of 𝑋 is non-empty and for every vertex 𝑣 ∈ 𝑋(0), we have h𝐴𝑣 𝑓 , 𝑓 i ≥
𝜂 h 𝑓 , 𝑓 i for all 𝑓 : 𝑋𝑣 (0) → ℝ for some 𝜂 ∈ [−1, 1). Then, for any 𝑔 : 𝑋(0) → ℝ, we have
𝜂
h𝐴𝑔, 𝑔i ≥ 𝛾 h𝑔, 𝑔i where 𝛾 ≥ 1−𝜂 .
Before we see a proof of this, let us see how Theorem 2.5 follows from this.
Descent Theorem A.3 (Theorem 2.5 restated). Suppose (𝑋 , 𝑤) is a non-empty 𝑑-dimensional
weighted simplicial complex with the following properties.
• The 1-skeleton of every link is connected.
• For all 𝑣 ∈ 𝑋(𝑑 − 2), the link (𝑋𝑣 , 𝑤 𝑣 ) is a 𝜆-one-sided spectral expander for some 𝜆 < 𝑑−1
1
. I. e.,
there is a 𝜆 > 0 such that, for every 𝑣 ∈ 𝑋(𝑑 − 2) and every 𝑔 : 𝑋𝑣 (0) → ℝ with 𝑔 ⊥ 1, we have
h𝐴𝑣 𝑔, 𝑔i ≤ 𝜆 h𝑔, 𝑔i .
𝜆
Then, (𝑋 , 𝑤) is a 𝛾-one-sided spectral HDX for 𝛾 ≤ 1−(𝑑−1)𝜆 . That is, for any 𝑣 ∈ 𝑋(−1) ∪ · · · ∪ 𝑋(𝑑 − 2)
and every 𝑔 : 𝑋𝑣 (0) → ℝ with 𝑔 ⊥ 1, we have h𝐴𝑣 𝑔, 𝑔i ≤ 𝛾 h𝑔, 𝑔i.
Furthermore, suppose we also know that there is a 𝜂 ∈ [−1, 0) such that, for every 𝑣 ∈ 𝑋(𝑑 − 2) and
every 𝑔 : 𝑋𝑣 (0) → ℝ, we have h𝐴𝑣 𝑔, 𝑔i ≥ 𝜂 h𝑔, 𝑔i. Then, 𝑋 is a 𝛾-two-sided spectral HDX with
𝜆 𝜂
𝛾 ≤ max , .
1 − (𝑑 − 1)𝜆 1 − (𝑑 − 1)𝜂
That is, for every 𝑔 : 𝑋𝑣 (0) → ℝ with 𝑔 ⊥ 1, we have | h𝐴𝑣 𝑔, 𝑔i | ≤ 𝛾 h𝑔, 𝑔i.
Proof. For any 𝑖 ≤ 𝑑 − 2, let
h𝐴𝑣 𝑔, 𝑔i
𝜆 𝑖 = min max ,
𝑣∈𝑋(𝑖) 𝑔:𝑋𝑣 (0)→ℝ h𝑔, 𝑔i
𝑔⊥1
the smallest one-sided spectral expansion with respect to 𝑋(𝑖). From repeated applications of
Theorem A.2,
𝜆0 𝜆1 /(1 − 𝜆1 ) 𝜆1 𝜆 𝑑−2
𝜆−1 ≤ ≤ = ≤ ··· ≤
1 − 𝜆0 1 − (𝜆1 /(1 − 𝜆1 )) 1 − 2𝜆1 1 − (𝑑 − 1)𝜆 𝑑−2
which eventually completes the proof for one-sided spectral expansion.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 17
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
For two-sided spectral expansion, we also have to show that all the eigenvalues are bounded
away from −1. One again, let 𝜂 𝑖 be such that
h𝐴𝑣 𝑔, 𝑔i
𝜂 𝑖 = max min .
𝑣∈𝑋(𝑖) 𝑔 : 𝑋𝑣 (0)→ℝ h𝑔, 𝑔i
𝑔⊥1
By repeated applications of Theorem A.2 (2), we obtain
𝜂0 𝜂1 /(1 − 𝜂1 ) 𝜂1 𝜂 𝑑−2
𝜂−1 ≥ ≥ = ≥ ··· ≥
1 − 𝜂0 1 − (𝜂1 /(1 − 𝜂1 )) 1 − 2𝜂1 1 − (𝑑 − 1)𝜂 𝑑−2
Together, we have that 𝑋 is a 𝛾-two-sided spectral HDX for
𝜆 𝜂
𝛾 = max , .
1 − (𝑑 − 1)𝜆 1 − (𝑑 − 1)𝜂
Proof of Theorem A.2. Let 𝑔 be an eigenvector that satisfies h𝑔, 𝑔i = 1 and 𝑔 ⊥ 1𝑋 that maximises
(or minimises) h𝐴𝑔, 𝑔i, and 𝛾 = h𝐴𝑔, 𝑔i be the extremal value. In particular, 𝐴𝑔 = 𝛾 · 𝑔. From
(A.2) we have 𝛾 = h𝐴𝑔, 𝑔i = 𝔼𝑣 [h𝐴𝑣 𝑔𝑣 , 𝑔𝑣 i].
Even though 𝑔 ⊥ 1𝑋 , the local component 𝑔𝑣 need not be perpendicular to 1𝑋𝑣 . Hence,
let us write 𝑔𝑣 = 𝛼 𝑣 1𝑋𝑣 + 𝑔𝑣⊥ where 𝑔𝑣⊥ ⊥ 1𝑋𝑣 ; we shall drop the subscript from 1𝑋𝑣 for the
sake of brevity as the length of the vector will be clear from context. Note that 𝛼 𝑣 = h𝑔𝑣 , 1i =
𝔼𝑤∈𝑋𝑣 (0) [𝑔𝑣 ] = 𝐴𝑔(𝑣). Therefore, 𝔼𝑣 [𝛼2𝑣 ] = h𝐴𝑔, 𝐴𝑔i = 𝛾2 . Hence,
𝛾 = h𝐴𝑔, 𝑔i = 𝔼𝑣 [h𝐴𝑣 𝑔𝑣 , 𝑔𝑣 i] = 𝔼𝑣 𝛼2𝑣 + 𝐴𝑣 𝑔𝑣⊥ , 𝑔𝑣⊥
(A.3)
We shall now focus on the proof of Theorem A.2 (1). The other direction is exactly identical
with the inequality flipped.
In the case of Theorem A.2 (1), where we are given h𝐴𝑣 𝑔𝑣⊥ , 𝑔𝑣⊥ i ≤ 𝜆 h𝑔𝑣⊥ , 𝑔𝑣⊥ i for all 𝑣 ∈ 𝑋(0),
we have
𝛾 = 𝔼𝑣 𝛼2𝑣 + 𝐴𝑣 𝑔𝑣⊥ , 𝑔𝑣⊥ ≤ 𝔼𝑣 𝛼2𝑣 + 𝜆 𝑔𝑣⊥ , 𝑔𝑣⊥
= 𝔼𝑣 (1 − 𝜆)𝛼2𝑣 + 𝜆 h𝑔𝑣 , 𝑔𝑣 i
= (1 − 𝜆)𝛾 2 + 𝜆.
=⇒ 𝛾(1 − 𝛾) ≤ 𝜆(1 − 𝛾2 )
=⇒ 𝛾 ≤ 𝜆(1 + 𝛾) (connected, thus 𝛾 < 1)
𝜆
=⇒ 𝛾 ≤ .
1−𝜆
In the case of Theorem A.2 (2), where we are given h𝐴𝑣 𝑔𝑣⊥ , 𝑔𝑣⊥ i ≥ 𝜂 h𝑔𝑣⊥ , 𝑔𝑣⊥ i for all 𝑣 ∈ 𝑋(0),
the same argument yields
𝛾 = 𝔼𝑣 𝛼 2𝑣 + 𝐴𝑣 𝑔𝑣⊥ , 𝑔𝑣⊥ ≥ 𝔼𝑣 𝛼2𝑣 + 𝜂 𝑔𝑣⊥ , 𝑔𝑣⊥ = (1 − 𝜂)𝛾2 + 𝜂
𝜂
=⇒ 𝛾 ≥
1−𝜂
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 18
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
B Primer on group theory
In this section, for completeness, we shall note the basic definitions and properties of groups
that are used in this exposition.
Definition B.1 (Groups and subgroups). A set of elements 𝐺 equipped with a binary operation
★ : 𝐺 × 𝐺 → 𝐺 is said to be a group if it satisfies the following properties:
Associativity: For all 𝑔1 , 𝑔2 , 𝑔3 ∈ 𝐺, we have (𝑔1 ★ 𝑔2 ) ★ 𝑔3 = 𝑔1 ★ (𝑔2 ★ 𝑔3 ).
Identity: There exists an identity element id ∈ 𝐺 such that, for all 𝑔 ∈ 𝐺, we have 𝑔 ★ id =
id ★ 𝑔 = 𝑔.
Inverses: For every element 𝑔 ∈ 𝐺, there is an element 𝑔 −1 ∈ 𝐺 such that 𝑔 ★ 𝑔 −1 = 𝑔 −1 ★ 𝑔 = id.
A subset 𝐻 ⊆ 𝐺 is said to be a subgroup of 𝐺 if 𝐻 the binary operation ★ restricted to 𝐻
satisfies the above three properties (including the fact that ℎ1 ★ ℎ 2 ∈ 𝐻 for all ℎ 1 , ℎ2 ∈ 𝐻).
Often the binary operation ★ is omitted and products just expressed as concatenation of
elements.
Definition B.2 (Cosets). Given a subgroup 𝐻 of a group 𝐺, if 𝑥 ∈ 𝐺 is an arbitrary element, the
left coset of 𝐻 containing 𝑥, denoted by 𝑥𝐻, is defined as the set
𝑥𝐻 = {𝑥 ℎ : ℎ ∈ 𝐻} .
Two cosets 𝑥𝐻 and 𝑦𝐻 are identical if and only if 𝑥 −1 𝑦 ∈ 𝐻. Hence, any element 𝑥 0 ∈ 𝑥𝐻 is also
referred to as a coset representative of 𝑥𝐻 as 𝑥 0 𝐻 = 𝑥𝐻.
Right cosets are defined similarly. A subgroup 𝐻 is said to be normal if the right cosets and
the left cosets agree for all 𝑥, i. e., 𝑥𝐻 = 𝐻𝑥, ∀𝑥 ∈ 𝐺.
Since two cosets of a subgroup 𝐻 of 𝐺 are either identical or disjoint, the set of distinct cosets
of a subgroup 𝐻 of 𝐺 partition the elements of 𝐺. If a subgroup 𝐻 is normal, this set of cosets
forms a group 𝐺/𝐻, called the quotient group of 𝐻 in 𝐺.
For subgroups 𝐻, 𝐾 of 𝐺, we will often consider the product 𝐻𝐾 (or 𝐻 ★ 𝐾) which refers
to the set {ℎ 𝑘 : ℎ ∈ 𝐻 , 𝑘 ∈ 𝐾}. It is worth stressing that 𝐻𝐾 need not be a subgroup of 𝐺 and
the above just refers to a set of elements that can be expressed as an (ordered) product of an
element in 𝐻 and an element in 𝐾.
For an arbitrary subset 𝑆 of 𝐺, we will define h𝑆i as the smallest subgroup of 𝐺 that contains
the set 𝑆. This is also referred to as the group generated by 𝑆.
In general, the binary operation ★ is order dependent. Groups where 𝑔1 𝑔2 = 𝑔2 𝑔1 for all
𝑔1 , 𝑔2 ∈ 𝐺 are said to be commutative or abelian groups. The following notion of commutators (and
commutator subgroups) is a way to measure how non-commutative a group 𝐺 is.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 19
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
Definition B.3 (Commutators). For a pair of elements 𝑔, ℎ ∈ 𝐺, we shall define the commutator
of 𝑔, ℎ (denoted by [𝑔, ℎ]) as
[𝑔, ℎ] := 𝑔 −1 ℎ −1 𝑔 ℎ.
The commutator subgroup of 𝐺, denoted by [𝐺, 𝐺] is the group generated by all commutators. That is,
[𝐺, 𝐺] := h{[𝑔, ℎ] : 𝑔, ℎ ∈ 𝐺}i .
Note that if 𝐺 is abelian, then [𝐺, 𝐺] = {id}. As mentioned earlier, the commutator subgroup
can be thought of as a way of describing how non-abelian a group is. In fact, the commutator
subgroup of 𝐺 is the smallest normal subgroup 𝐻 of 𝐺 such that the quotient 𝐺/𝐻 is abelian
(although these are concepts that are not necessary to follow this exposition).
References
[1] Yotam Dikstein: Oppenheim’s Trickling Down Theorem, 2019. Lecture
notes from the Error-Correcting Codes and High-Dimensional Expansion Boot
Camp at Simons Institute for the Theory of Computing, Available at
https://simons.berkeley.edu/sites/default/files/docs/14119/ecctalkii.pdf. 16
[2] Howard Garland: 𝑝-adic curvature and the cohomology of discrete subgroups of 𝑝-adic
groups. Ann. Math., 97(3):375–423, 1973. [doi:10.2307/1970829] 4
[3] Alexander J. Hahn and O. Timothy O’Meara: The Classical Groups and K-Theory. Springer,
1989. [doi:10.1007/978-3-662-13152-7] 7
[4] Tali Kaufman and Izhar Oppenheim: High dimensional expanders and coset ge-
ometries. Europ. J. Combinat., 111(103696), 2023. Preliminary version in STOC’18.
[doi:10.1016/j.ejc.2023.103696, arXiv:1710.05304] 2, 6, 7, 13, 15
[5] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak: Ramanujan graphs. Combinatorica,
8(3):261–277, 1988. Preliminary version in STOC’86. [doi:10.1007/BF02126799] 2
[6] Alexander Lubotzky, Beth Samuels, and Uzi Vishne: Explicit constructions of Ramanujan
complexes of type 𝐴˜𝑑 . Europ. J. Combinat., 26(6):965–993, 2005. [doi:10.1016/j.ejc.2004.06.007,
arXiv:math/0406217] 2
[7] Alexander Lubotzky, Beth Samuels, and Uzi Vishne: Ramanujan complexes of type 𝐴˜𝑑 .
Israel J. Math., 149(1):267–299, 2005. [doi:10.1007/BF02772543, arXiv:math/0406208] 2
[8] Grigorii Aleksandrovich Margulis (Григорий Александрович Маргулис): Явные
теоретико-групповые конструкции комбинаторных схем и их применения в постро-
ении расширителей и концентраторов (Russian) [Explicit group-theoretical construc-
tions of combinatorial schemes and their application to the design of expanders
and concentrators]. Problemy Peredachi Informatsii, 24(1):51–60, 1988. Available at
https://www.mathnet.ru/eng/ppi686, (English translation in Problems Inform. Transmission,
24(1):39–46, 1988). 2
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 20
O N THE H IGH -D IMENSIONAL E XPANDERS BY K AUFMAN AND O PPENHEIM
[9] Ryan O’Donnell and Kevin Pratt: High-dimensional expanders from Chevalley groups.
In Proc. 37th Comput. Complexity Conf. (CCC’22), pp. 18:1–26. Schloss Dagstuhl–Leibniz-
Zentrum fuer Informatik, 2022. [doi:10.4230/LIPIcs.CCC.2022.18, arXiv:2203.03705] 13
[10] Izhar Oppenheim: Local spectral expansion approach to high dimensional expanders Part
I: Descent of spectral gaps. Discr. Comput. Geom., 59(2):293–330, 2018. [doi:10.1007/s00454-
017-9948-x, arXiv:1709.04431] 4
[11] Omer Reingold, Salil Vadhan, and Avi Wigderson: Entropy waves, the zig-zag graph
product, and new constant-degree expanders. Ann. Math., 155(1):157–187, 2005. Preliminary
version in FOCS’00. [doi:10.2307/3062153, arXiv:math.CO/0406038, ECCC:TR01-018] 13
[12] Alireza Sarveniazi: Explicit construction of a Ramanujan (𝑛1 , 𝑛2 , . . . , 𝑛 𝑑−1 ) -regular hyper-
graph. Duke Math. J., 136(1):141–171, 2007. [doi:10.1215/S0012-7094-07-13913-9] 2
AUTHORS
Prahladh Harsha
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
prahladh tifr res in
http://www.tifr.res.in/~prahladh/
Ramprasad Saptharishi
School of Technology and Computer Science
Tata Institute of Fundamental Research
Mumbai, India
ramprasad tifr res in
http://www.tifr.res.in/~ramprasad.saptharishi/
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 21
P RAHLADH H ARSHA AND R AMPRASAD S APTHARISHI
ABOUT THE AUTHORS
Prahladh Harsha is a theoretical computer scientist at the Tata Institute of Funda-
mental Research (TIFR). He received his B. Tech. degree in Computer Science and
Engineering from the IIT Madras in 1998. He then obtained his S. M. and Ph. D.
degrees in Computer Science from MIT in 2000 and 2004, respectively, advised
by Madhu Sudan. Prior to joining TIFR in 2010, he was at Microsoft Research,
Silicon Valley and at the Toyota Technological Institute at Chicago. His areas of
interest include computational complexity, hardness of approximation, coding
theory and information theory. Prahladh credits his mother for his interest in
mathematics and dance. He is also deeply indebted to U Koteswara Rao, his high
school mentor, for exposing him to both the beauty and rigour in mathematics.
Ramprasad Saptharishi is a theoretical computer scientist at the School of Technology
and Computer Science at the Tata Institute of Fundamental Research, Mumbai,
and is generally interested in most questions of an algebraic nature. He did his
Ph. D. at Chennai Mathematical Institute, advised by Manindra Agrawal, and
spent a couple of years at Microsoft Research, India and Tel Aviv University for
his postdoc. His other interests include board games, reading ridiculously long
web-series and writing software code. However, writing reasonable biographies
continues to remain outside his area of expertise.
T HEORY OF C OMPUTING, Volume 20 (5), 2024, pp. 1–22 22