# New High Dimensional Expanders from Covers

Yotam Dikstein Weizmann Institute of Science, ISRAEL. email:
<EMAIL_ADDRESS>Supported by Irit Dinur’s ERC grant 772839.

###### Abstract

We present a new construction of high dimensional expanders based on covering
spaces of simplicial complexes. High dimensional expanders (HDXs) are
hypergraph analogues of expander graphs. They have many uses in theoretical
computer science, but unfortunately only few constructions are known which
have arbitrarily small local spectral expansion.

We give a randomized algorithm that takes as input a high dimensional expander
$X$ (satisfying some mild assumptions). It outputs a sub-complex $Y\subseteq
X$ that is a high dimensional expander and has infinitely many simplicial
covers. These covers form new families of bounded-degree high dimensional
expanders. The sub-complex $Y$ inherits $X$’s underlying graph and its links
are sparsifications of the links of $X$. When the size of the links of $X$ is
$O(\log|X|)$, this algorithm can be made deterministic.

Our algorithm is based on the groups and generating sets discovered by
Lubotzky, Samuels and Vishne (2005), that were used to construct the first
discovered high dimensional expanders. We show these groups give rise to many
more “randomized” high dimensional expanders.

In addition, our techniques also give a random sparsification algorithm for
high dimensional expanders, that maintains its local spectral properties. This
may be of independent interest.

##  1 Introduction

Expanders are graphs that are highly connected. It is a known fact that there
exist families of expander graphs that are bounded-degree. These graphs play a
key role in theoretical computer science, combinatorics and many other areas
in mathematics [HLW06]. High dimensional expanders (HDXs) are a hypergraph
analogue of expander graphs. Loosely speaking, high dimensional expanders have
the property that neighborhoods of faces are themselves expanding graphs.
Lubotzky surveys the different definitions of high dimensional expanders
[Lub17].

High dimensional expanders are promising objects in theoretical computer
science. They have been used for efficiently solving CSPs [AJT19], for
constructing agreement testers [DK17, DD19] and for sampling and counting
matroids and other combinatorial objects (e.g. [Ana+19], [CLV21]).

There are only two constructions of high dimensional expanders that achieve
arbitrarily good expansion, [LSV05a] and [KO18]. Both constructions rely on
group theory. This is contrary to expander graphs, where in addition to group-
theoretic constructions, elementary combinatorial constructions and random
constructions are known [HLW06].

The goal of this work is to construct new high dimensional expanders by using
random simplicial covers. Graph covers (or lifts) are a key ingredient in many
random expander constructions. A graph $G^{\prime}$ covers a graph $G$ if
there is a surjective graph homomorphism $\psi:G^{\prime}\to G$ so that for
every vertex $v\in G^{\prime}$, $deg(v)=deg(\psi(v))$. There is a simple
algorithm (described below) that given a graph $G$, outputs a random cover
$G^{\prime}$ of $G$. In many cases the covers will also be expander graphs,
and indeed this is exploited to construct infinite families of expanders (see
e.g. [BL06] and [MSS15]). In this work, we manage to extend this technique to
high dimensional expanders.

###  1.1 High dimensional expanders

A pure $d$-dimensional simplicial complex $X$ is a set system (or hypergraph)
consisting of an arbitrary collection of sets of size $d+1$ together with all
their subsets. The sets of size $i+1$ in $X$ are denoted by $X(i)$, and in
particular, the vertices of $X$ are denoted by $X(0)$. The $1$-skeleton of $X$
is the graph whose vertices are $X(0)$ and edges are $X(1)$. The sets in a
simplicial complex are called faces. We say that $X$ is _connected_ if its
$1$-skeleton is connected.

Let $s\in X(i)$. The link of $s$ is a simplicial complex denoted by $X_{s}$
whose sets are all $t\in X$ so that $s\cap t=\emptyset$ and $s\cup t\in X$.
For $\lambda\geqslant 0$, a $\lambda$-two-sided high dimensional expander is a
simplicial complex so that its $1$-skeleton, and all the $1$-skeletons of its
links are $\lambda$-two-sided spectral expanders.

This definition is due to [DK17]; it concentrates on spectral properties. High
dimensional expanders by this definition are useful in many applications as
discussed above. However, there are other non-equivalent definitions for high
dimensional expansion. We recommend [Lub17] for a comparison between the main
definitions that interest the community.

###  1.2 Graph covers and simplicial covers

Let $X,Y$ be pure $d$-dimensional simplicial complexes. A simplicial
homomorphism is a function $\psi:X(0)\to Y(0)$ so that every $s\in X(d)$ is
mapped to $\psi(s)\in Y(d)$. A homomorphism is a _cover_ if it is surjective,
and locally it behaves like an isomorphism. That is, for every face $t\in
Y(i)$ and preimage $s\in X(i)$ so that $\psi(s)=t$, the restriction of $\psi$
to $X_{s}$ is an isomorphism between $X_{s}$ and $Y_{t}$. For graphs, this
definition coincides with the previous definition discussed above.

Given a graph on $n$ vertices $G=(V=\\{v_{1},v_{2},...,v_{n}\\},E)$, we can
construct a cover $G^{\prime}=(V^{\prime},E^{\prime})$ of $G$ as follows. Let
$\Gamma$ be any finite group and let $f:E\to\Gamma$ be a labeling. The
vertices of $G^{\prime}$ are set to be $V^{\prime}=V\times\Gamma$. For every
$i<j$, the vertices $(v_{i},g),(v_{j},h)$ are adjacent in $G^{\prime}$ if
$v_{i}v_{j}\in E$ and $h=g\cdot f(ij)$. The covering map is the map that
projects $(i,g)$ to its left coordinate $i$. In fact, every graph cover
corresponds to some group and some edge labeling $f:E\to\Gamma$ [Sur84].

This method has proven to be useful in constructing new expander graphs from
initial expanders. Amit and Linial initiated the study of random graph covers
[AL02]. Bilu and Linial showed that if $G$ is a bounded-degree expander,
$\Gamma=\mathbb{F}_{2}$ and $f$ is chosen at random, then $G^{\prime}$ is an
expander with positive probability [BL06]. A breakthrough paper by Marcus,
Spielman and Srivastava [MSS15] used graph covers to create optimal
(Ramanujan) bipartite expander graphs. It is tempting to try and generalize
this simple construction to high dimensional expanders.

Unfortunately, in simplicial complexes this method does not work as is. Given
a $d$-dimensional simplicial complex $X$ and a labeling of the $1$-skeleton
$f:X(1)\to\Gamma$, the resulting covering graph $G^{\prime}$ is not
necessarily a ($1$-skeleton of a) $d$-dimensional simplicial complex at all.
It turns out that connected covers of a simplicial complex correspond to
subgroups of its fundamental group (as a topological space) [Sur84]. This
group may be trivial so complexes may have no non-trivial connected covers.

###  1.3 Our contribution

Not all is lost. In this paper we show that even if a high dimensional
expander $X$ has no covers, with the help of certain groups $\Gamma$ we can
find a non-trivial sub-complex $Y\subseteq X$ that is a high dimensional
expander _and has infinitely many covers_. In more detail, we start with:

  1. 1.

An initial high dimensional expander $X$. The links of $X$ need to be (almost)
regular and relatively dense, but $X$ itself may have bounded degree.

  2. 2.

An infinite group $\Gamma$ that has infinitely many normal subgroups of finite
index, together with a generating set $S\subseteq\Gamma$. Links of the clique
complex of the Cayley graph $Cay(\Gamma,S)$ should be themselves expanding
graphs. 111A clique complex of a graph is a simplicial complex whose vertices
and edges are those of the graph $Cay(\Gamma,S)$. The high-dimensional faces
of the complex are all cliques in the graph.

######  Theorem 1.1 (Informal, for the formal theorem see Theorem 3.2).

There is a randomized algorithm that takes as input a high-dimensional
expander $X$ satisfying Item 1, and a group and generating set $(\Gamma,S)$
satisfying Item 2. The algorithm outputs a subcomplex $Y\subseteq X$ and a
labeling $f:X(1)\to S$ so that:

  1. 1.

$Y$ has infinitely many covers $\\{Y_{n}\\}_{n=1}^{\infty}$ which can be
constructed in polynomial time using $f$.

  2. 2.

$Y$ is a high dimensional expander.

  3. 3.

$Y$ contains a constant fraction of the faces of $X$, proportional to
$\frac{1}{poly(|S|)}$.

We note that the cover $\\{Y_{n}\\}_{n=1}^{\infty}$ are the new family of high
dimensional expanders we seek. Their vertices are
$Y(0)\times(\Gamma/\Gamma_{n})$ where $\\{\Gamma_{n}\\}_{n=1}^{\infty}$ are
normal subgroups of $\Gamma$ of finite index. Their links are isomorphic to
links of faces in the original subcomplex $Y$. Hence links of these covers are
sparsifications of links in the original complex $X$.

Groups and generating sets $(\Gamma,S)$ as required in the input appeared in
[LSV05, LSV05a], where they were used to construct the first known high
dimensional expanders. The resulting simplicial complexes we construct are
however, are different and depend on the input $X$ we give the algorithm.

Interestingly, we show that this new simplicial complex $Y$ inherits
properties both from $X$ and from $Cay(\Gamma,S)$. Globally, the $1$-skeleton
of $Y$ is identical to the $1$-skeleton of $X$ (i.e it has the same vertex set
and edge set). For every $\sigma\in Y$, the link $Y_{\sigma}\subseteq
X_{\sigma}$ is a sparsification that has a constant fraction of the faces in
$X_{\sigma}$. The algorithm sparsifies the higher-dimensional faces so that
locally its links are homomorphic to links of faces in the clique complex of
$Cay(\Gamma,S)$.

There are many starting points $X$ that satisfies the requirements in Theorem
1.1. The simplest is the complete complex. We could also use a random model to
sample our initial simplicial complex, such as the model suggested by [LM06]:
its vertices are $\\{1,2,...,m\\}$, every $d$-face is sampled independently
with some probability $p\in(0,1)$. Although we don’t usually think about the
complete complex or the model in [LM06] as “bounded-degree”, recall that $X$
is just a single complex (and thus always has bounded degree). Albeit, we can
initialize our construction by taking $X$ out of a family of bounded-degree of
high dimensional expanders as long as they are regular. A work by Friedgut and
Iluz shows how to construct strongly regular high dimensional expanders from
existing ones [FI20], which we can use.

The algorithm in Theorem 1.1 can also be derandomized when $X$ has logarithmic
sized links.

Though our main result deals with covers, our random sparsification technique
has another application of independent interest. We show that we can sparsify
a high dimensional expander $X$, so that it will be homomorphic to some fixed
smaller high dimensional expander $C_{0}$, while maintaining its high
dimensional expansion.

######  Theorem 1.2 (Informal, for the formal theorem see Theorem 4.1).

There is a randomized algorithm that takes as input a simplicial complex
$C_{0}$, and simplicial complex $X$ that satisfies Item 1, and outputs a sub-
complex $Y\subseteq X$ so that:

  1. 1.

$Y$ is homomorphic to $C_{0}$.

  2. 2.

$Y$ has a constant fraction of the faces of $X$ (the constant depends on
$C_{0}$).

  3. 3.

If $X$ and $C_{0}$ are high dimensional expanders then $Y$ is also a high
dimensional expander.

Note that $Y\subseteq X$ could be viewed also as a sparsifying algorithm for
$X$, that produces a sparser simplicial complex that still has high
dimensional expansion properties. We also show that when $X$ has small enough
links, then we can derandomize the algorithm in Theorem 1.2.

###  1.4 Constructing covers in higher dimension

Let us understand how to generalize the graph cover construction to higher
dimensional simplicial complexes.

Let $X$ be a $d$-dimensional high dimensional expander where $d\geqslant 2$
with vertex set $X(0)=\\{v_{1},v_{2},...,v_{n}\\}$ (we order of the vertices
arbitrarily). Let $f:X(1)\to\Gamma$ be a labeling to some group $\Gamma$. Let
$G^{\prime}$ be the _graph cover_ of the $1$-skeleton of $X$, generated by
$f$. In order to extend $G^{\prime}$ to a _simplicial cover_ of $f$ to have
the property that for every triangle $v_{i}v_{j}v_{k}\in X$ where $i<j<k$

$f(v_{i}v_{j})f(v_{j}v_{k})=f(v_{i}v_{k}).$ (1.1)

Labelings $f$ with this property are called $\Gamma$-cosystols. If $f$ is a
$\Gamma$-cosystol, then whenever $(v_{i},g)\sim(v_{j},gf(v_{i}v_{j}))$ and
$(v_{i},g)\sim(v_{k},gf(v_{i}v_{k}))$, it also holds that

$(v_{j},gf(v_{i}v_{j}))\sim(v_{k},gf(v_{i}v_{j})f(v_{j}v_{k})=gf(v_{i}v_{k})),$

I.e. all edges of the triangle
$\\{(v_{i},g),(v_{j},gf(v_{i}v_{j})),(v_{k},gf(v_{i}v_{k}))\\}$ are in
$G^{\prime}$. We can then extend $G^{\prime}$ to a simplicial complex
$X^{\prime}$ with

$X^{\prime}(2)=\left\\{\\{(v_{i},g),(v_{j},gf(v_{i}v_{j})),(v_{k},gf(v_{i}v_{k}))\\}\left|\;\vphantom{\\{(v_{i},g),(v_{j},gf(v_{i}v_{j})),(v_{k},gf(v_{i}v_{k}))\\}v_{i}v_{j}v_{k}\in
X(2),i<j<k<,g\in\Gamma}\right.v_{i}v_{j}v_{k}\in
X(2),i<j<k<,g\in\Gamma\right\\}$

and similarly for $\ell>2$,

$X^{\prime}(\ell)=\left\\{\\{(v_{i_{0}},g),(v_{i_{1}},gf(v_{i_{0}}v_{i_{1}})),...,(v_{i_{\ell}},gf(v_{i_{0}}v_{i_{\ell}}))\\}\left|\;\vphantom{\\{(v_{i_{0}},g),(v_{i_{1}},gf(v_{i_{0}}v_{i_{1}})),...,(v_{i_{\ell}},gf(v_{i_{0}}v_{i_{\ell}}))\\}i_{0}i_{1}...i_{\ell}\in
X(\ell),i_{0}<i_{1}<...<i_{\ell},g\in\Gamma}\right.i_{0}i_{1}...i_{\ell}\in
X(\ell),i_{0}<i_{1}<...<i_{\ell},g\in\Gamma\right\\}).$

###  1.5 Overview of our construction

The cover constructed from a labeling $f:X(1)\to\Gamma$ may be trivial, that
is, that $X^{\prime}$ may consist of $|\Gamma|$ disjoint copies of $X$. Recall
that connected covers are determined by the fundamental group of $X$, and it
could be the case that all covers $X^{\prime}$ of $X$ are trivial.

To overcome this in our construction, we “go the other way around”. We sample
a labeling $f:X(1)\to\Gamma$ by sampling the label of each edge independently.
We then wish to remove from $X$ all faces that contain triangles
$v_{i}v_{j}v_{k}\in X(2)$ where $i<j<k$ and $f(v_{i}v_{j})f(v_{j}v_{k})\neq
f(v_{i}v_{k})$. If we do so, we get a sub-complex $Y\subseteq X$ so that $f$
is one of its $\Gamma$-cosystols.

The main problem with this naive triangle removal, is that with high
probability some links of faces in $Y$ will not be expanders anymore. It could
be, for example, that all triangles adjacent to some vertex are removed (and
its link becomes disconnected). Denote by $B_{\sigma}$ the event that the link
of $\sigma$ is not an expander graph.

Fortunately, Lovasz’s Local Lemma [EL74] guarantees us that if the probability
of each $B_{\sigma}$ is small, and that every event $B_{\sigma}$ is
independent of all but a few of the $B_{\sigma^{\prime}}$, then the event
where no $B_{\sigma}$ occurs has positive probability (i.e. $Y$ is a high
dimensional expander with positive probability). The heart of our analysis is
to properly define these “local bad events”, and to show that we can indeed
apply Lovasz’s Local Lemma to them. We use similar techniques to also promise
that the $f$-cover of $Y$ is indeed connected.

Moser and Tardos proved that there is a procedure to turn the existential
proof based on Lovasz’s Local Lemma to a randomized algorithm that finds $Y$
in polynomial time [MT10]. When the links of $X$ are not too small, we can
derandomize this algorithm using the work of [CGH13].

As $Y$ is obtained by removing faces from $X$, it is not surprising that
$1$-skeletons of links of faces in $Y$ are obtained by removing vertices and
edges from links of faces in $X$. To show that these links still expand with
high probability, we analyze random sparsifications of expander graphs with
logarithmic degree, and show that with high enough probability a graph remains
an expander after such a sparsification. To do so we use the Inverse Expander
Mixing Lemma proven by Bilu and Linial [BL06]. This analysis is quite general
and may be of independent interest.

###  1.6 Related works

Properties of high dimensional expanders were first used in the work of
Garland [Gar73], even before they were explicitly defined. Local spectral
properties of links were used there to show that the real cohomology of a
simplicial complex vanishes. Later on, a strong notion of coboundary expansion
was discovered by Gromov [Gro10], and also by Linial, Meshulam and Wallach
[LM06], [MW09]. The definition we use of high dimensional expanders is due to
Dinur and Kaufman [DK17], who also defined the one-sided version of high-
dimensional expansion (before their work, a weaker notion of expansion in the
links was used in e.g. [EK16, KKL14]). The first construction of bounded-
degree high dimensional expanders was done before the definition we use today,
by Lubotzky, Samuels and Vishne [LSV05]. A second algebraic construction was
discovered by Kaufman and Oppenheim [KO18, KO21]. Recently, [OP22] construct
new high dimensional expanders using the method of [KO18] with Chevalley
groups. Friedgut and Iluz modified existing constructions for creating hyper-
regular high dimensional expanders [FI20]. There have been combinatorial
constructions of high dimensional expanders by Chapman, Linial and Peled
[CLY20], Liu, Mohanty and Yang [LMY20] and Golowich [Gol21]. However, the
combinatorial constructions currently produce $\lambda$-HDXs for
$\lambda\geqslant\frac{1}{2}$.

As mentioned above, there is a long line of works on random graph covers and
their properties e.g. [AL02, Ami+01, Fri03, BL06, Pud15, MSS15]. This work
lead to the breakthrough construction of bipartite Ramanujan graphs of all
degrees by Marcus, Spielman and Srivastava. The works that study expansion
usually focused on analysis of the eigenvalues of the covering graph. In
higher dimension however, every connected cover is also a high dimensional
expander. This fact is a corollary of a work of Oppenheim [Opp18], which we
discuss more precisely in Section 2. However, to analyze the links in our
construction, we use the techniques developed by Bilu and Linial [BL06]
towards analyzing random graph covers.

Dinur and Meshulam also studied on simplicial covers from a TCS perspective
[DM19]. They study a topological property test on a class of simplicial
complexes called _cosystolic expanders_. They show that if $X$ is such a
complex, then every surjective mapping $f:Y\to X$ that satisfies almost all
the local conditions of being a cover is close to a genuine cover $g:Y\to X$.

Random sparsification of graphs and their adjacency matrices is also a well
studied problem, and there are known randomized and deterministic algorithms
to sparsify graphs while keeping their spectral properties, e.g. [SS08],
[ST11], [LS17], [JS18] and [LXX20]. Furedi and Kolmos initiated the study of
random sparsified matrices [FK81] (see also the work of Vu [Vu07]). A
celebrated result by Spielman and Teng, studied sparsification of spectral
expanders by randomly removing edges [ST11]. However, the probability of
removing an edge in [ST11] varies according to the degrees of its vertices,
and we could not use its analysis as is. Hence, we prove a graph
sparsification result that is tailored for our needs.

###  1.7 Open questions

The construction we give in this paper is for two sided high dimensional
expansion. Is there also an extension of our algorithm or our analysis that
works on _one sided_ high dimensional expanders $X$?

All constructions of bounded-degree high dimensional expanders with
$\lambda<\frac{1}{2}$ rely on group theory (either deterministic or
randomized). Finding a combinatorical construction that does not rely on a
group for arbitrarily small $\lambda>0$ or even $\lambda=0.49$ is an open
problem. It is interesting to note that the theorem of Oppenheim mentioned
above [Opp18] only applies for $\lambda<\frac{1}{2}$. This seems to show that
$\lambda$-high dimensional expanders for $\lambda<\frac{1}{2}$ must have some
non-trivial structure.

Our construction has properties inherited by both the complex $X$, and the
clique complex of $Cay(\Gamma,S)$. There are many other interesting properties
that could be of interest in our construction. For example, one can repeat
this construction with groups and generating sets so that the links of the
clique complex of $Cay(\Gamma,S)$ are _small set expanders_ , but not
expanders themselves. Will the resulting complexes be small set expanders
(either locally or globally)? Another potentially interesting property is
coboundary and cosystolic expansion. Will the resulting complexes be
cosystolic expanders?

Our construction relies on infinite groups $\Gamma$ that are residually finite
and have expanding links. Besides the groups in [LSV05a], we are not aware of
groups that have these properties 222Not including trivial constructions such
as $(\Gamma\times\Gamma,S\times S)$.. Finding new examples of such groups is
interesting. The groups that were used in [KO18, KO21] are possible
candidates, as they already showed potential for construction of high
dimensional expanders. Note that [Zuk03] showed that any such $\Gamma$ has
Kazhdan’s property-$T$. This already constrains the types of groups we can
consider. [Gro03] defined a random model of groups that seems to have
expanding links, but it is not clear whether they are residually finite or
not. It will be interesting to understand if this model, or some variation to
it, could produce new examples of groups useful for our construction.

Another open question that may have algorithmic applications, is embedding
simplicial complexes in high dimensional expanders. That is, given a
simplicial complex $X$, is it possible to embed it in a high dimensional-
expander $X^{\prime}\supseteq X$, so that $|X^{\prime}|/|X|$ is constant. For
graphs this is easy, since given $G=(V,E)$, we can find an expander graph with
the same vertex set $H=(V,E^{\prime})$ and embed $G$ in $G^{\prime}=(V,E\cup
E^{\prime})$. This simple embedding in graphs is useful, for example, in the
PCP-theorem proof by [Din06]. Understanding when we also have such an
embedding in simplicial complexes could potentially lead to new algorithms for
solving constraint satisfaction problems.

Finally, [Dik+18] generalized the notion of high dimensional-expanders to
_expanding posets_. Another open direction of research is whether one could
use topological covers to construct new expanding posets.

###  1.8 Acknowledgments

I would like to express my deepest gratitude to Irit Dinur for her invaluable
comments and feedback that greatly improved this paper. I would also like to
thank Gil Melnik and Yael Hitron for their feedback on preliminary versions of
this paper.

###  1.9 Organization of this paper

Section 2 contains the preliminaries necessary for this paper. We formally
state and prove our main theorem about simplicial covers in Section 3, while
deferring some technical claims on sparsification of graphs to Section A. In
Section 4 we also show that for every fixed simplicial complex $C$, there is
an algorithm that receives a simplicial complex $X$ and outputs a sub-complex
$Y\subseteq X$ that is homomorphic to $C$. In Section 5 we show that when the
input complex $X$ has constant degree, we obtain deterministic algorithms for
constructing the covering families and for sparsification.

##  2 Preliminaries

###  2.1 Classical probability

######  Theorem 2.1 (Chernoff’s inequality).

Let $X_{1},X_{2},...,X_{n}$ be independent random variables. Denote
$\operatorname*{\mathbb{E}}[\sum_{j=1}^{n}X_{j}]=\mu$. Then for any
$\varepsilon\in(0,1)$ it holds that

$\operatorname*{\mathbb{P}}\left[{\lvert\sum_{j=1}^{n}X_{n}-\mu\rvert\geqslant\varepsilon\mu}\right]<2e^{-0.3\varepsilon^{2}\mu}.$

######  Theorem 2.2 (Hoeffding’s inequality).

Let $X_{1},X_{2},...,X_{n}$ be independent random variables. Let
$[a,b]\subseteq\mathbb{R}$ so that for all $j=1,2,...,n$ it holds that
$X_{j}\in[a,b]$. Denote $\operatorname*{\mathbb{E}}[\sum_{j=1}^{n}X_{j}]=\mu$.
Then for any $\varepsilon>0$ it holds that

$\operatorname*{\mathbb{P}}\left[{\lvert\sum_{j=1}^{n}X_{n}-\mu\rvert\geqslant\varepsilon\mu}\right]<2e^{\frac{-2\varepsilon^{2}\mu^{2}}{\sum_{j=1}^{n}(b_{i}-a_{i})^{2}}}.$

######  Theorem 2.3 (Lovazs Local Lemma, [EL74], algorithmic version by
[MT10]).

Let $X_{1},...,X_{d}$ be independent random variables. Let
$E_{1},E_{2},...,E_{n}$ be events determined by these random variables. For
every $E_{i}$ we denote by
$A_{i}=\left\\{j\left|\;\vphantom{jE_{i},E_{j}\text{ are not
independent}}\right.E_{i},E_{j}\text{ are not independent}\right\\}$. Assume
that there are $\alpha_{i}\in[0,1)$ so that for every event

$\operatorname*{\mathbb{P}}\left[{E_{i}}\right]\leqslant\alpha_{i}\prod_{j\in
A_{i}}(1-\alpha_{j}).$

Then $\operatorname*{\mathbb{P}}\left[{\neg E_{1}\wedge\neg
E_{2}\wedge...\wedge\neg E_{n}}\right]>0$. Moreover, there exists a randomized
algorithm that finds assignments to $X_{1},X_{2},...,X_{d}$ so that all the
events $E_{1},E_{2},...,E_{n}$ don’t occur. The algorithm runs in an expected
time of $\sum_{i=1}^{n}\frac{|A_{i}|\alpha_{i}}{1-\alpha_{i}}$.

Note that when all $|A_{i}|<R$, if one takes $\alpha_{i}=\frac{1}{R}$ and
shows that
$\operatorname*{\mathbb{P}}\left[{E_{i}}\right]\leqslant\frac{1}{e(R+1)}$,
then this theorem promises us there exists an assignment so that
$\operatorname*{\mathbb{P}}\left[{\neg E_{1}\wedge\neg
E_{2}\wedge...\wedge\neg E_{n}}\right]>0$. Moreover, it gives us a polynomial
time algorithm to find such an assignment to $X_{1},X_{2},...,X_{d}$.

###  2.2 Expander graphs

A graph $G=(V,E)$ is a finite set $V$, the vertices, and
$E\subseteq\binom{V}{2}$, the edges. Graphs in this paper are assumed to be
with no isolated vertices. The graphs we consider have some probability
distribution $\nu:E\to[0,1]$, and we assume henceforth that $\nu(e)\neq 0$ for
every edge $e\in E$. As a convention $\nu(e^{\prime})=0$ for every
$e^{\prime}\notin E$. Sometimes it is convenient to consider oriented edges
$\overset{\to}{E}=\left\\{(u,v),(v,u)\left|\;\vphantom{(u,v),(v,u)\\{u,v\\}\in
E}\right.\\{u,v\\}\in E\right\\}$. For an oriented edge we define
$\nu(u,v)=\frac{1}{2}\nu(\\{u,v\\})$.

The probabilities on edges give rise to a probability measure on $V$, i.e.
$\nu(v)=\frac{1}{2}\sum_{w\sim
v}\operatorname*{\mathbb{P}}\left[{\\{v,w\\}}\right]=\sum_{w\sim v}\nu(w,v)$.
This probability measure defines an inner product on $\ell_{2}(V)$ the space
of real valued functions on the vertices $f,g:V\to\mathbb{R}$ by

$\langle f,g\rangle:=\operatorname*{\mathbb{E}}_{{v\in
V}}\left[f(v)g(v)\right],$

where the expectation is with respect to $\nu$. Every graph induces a random
walk on its vertices; the transition probability from $v$ to $u$ is

$\nu(u|v):=\frac{\nu(uv)}{\sum_{u^{\prime}\sim v}\nu(u^{\prime}v)}.$

Denote by $A=A(G)$ the Markov operator associated with this random walk. We
associate $A$ with the matrix indexed by $V\times V$ where $A(v,u)=\nu(u|v)$.
We call this operator the _normalized adjacency operator_ (in this paper we
will refer to it as the adjacency operator). $A$ is an operator on real valued
functions on the vertices, where

$\forall v\in V\;Af(v)=\operatorname*{\mathbb{E}}_{{u\sim
v}}\left[f(u)\right]\left(=\sum_{u\sim v}\nu(u|v)f(u).\right)$

It is well known that $A$ is self adjoint with respect to the inner product
defined above. Its eigenvalues are in the interval $[-1,1]$. We denote its
eigenvalues by
$\lambda_{1}\geqslant\lambda_{2}\geqslant...\geqslant\lambda_{n}$ (with
multiplicities). The largest eigenvalue is always $\lambda_{1}=1$, and it is
obtained by the constant function. The second eigenvalue is strictly less than
$1$ if and only if the graph is connected.

######  Definition 2.4 (spectral expanders).

Let $G$ be a graph and let $0\leqslant\lambda<1$. $G$ is a _$\lambda$ -one
sided spectral expander_, if

$\lambda_{2}\leqslant\lambda.$

$G$ is a _$\lambda$ -two sided spectral expander_, if

$\max(\lvert\lambda_{2}\rvert,\lvert\lambda_{n}\rvert)\leqslant\lambda.$

In this paper, when saying a graph is a $\lambda$-spectral expander, we mean
it is a $\lambda$-_two sided_ spectral expander.

####  2.2.1 Bipartite Graphs and Bipartite Expanders

A bipartite graph is a graph where the vertex set can be partitioned to two
independent sets $V=L\mathbin{\mathaccent 0{\cdot}\cup}R$, called sides. We
sometimes denote such a bipartite graph by $G=(L,R,E)$.

##### The Bipartite Adjacency Operator

In a bipartite graph, we view each side as a separate probability space, where
for any $v\in L$ (resp. $R$), $\nu(v)=\sum_{w\sim v}\nu(vw)$. We can define
the _bipartite adjacency operator_ as the operator
$B:\ell_{2}(L)\to\ell_{2}(R)$ by

$\forall f\in\ell_{2}(L),v\in R,\;Bf(v)=\operatorname*{\mathbb{E}}_{{w\sim
v}}\left[f(u)\right]$

where the expectation is taken with respect to the probability space $L$,
conditioned on being adjacent to $v$. There is a similar operator
$B^{*}:\ell_{2}(R)\to\ell_{2}(L)$ as the bipartite operator for the opposite
side. As the notation suggests, $B^{*}$ is adjoint to $B$ with respect to the
inner products of $\ell_{2}(L),\ell_{2}(R)$.

We denote by $\lambda(B)$ the spectral norm of $B$ when restricted to
$\ell_{2}^{0}(L)=\\{{\mathbf{1}}\\}^{\bot}$, the orthogonal complement of the
constant functions (according to the inner product the measure induces).
Namely

$\lambda(B)=\sup\left\\{\langle Bf,g\rangle\left|\;\vphantom{\langle
Bf,g\rangle\lVert g\rVert,\lVert f\rVert=1,f\bot{\mathbf{1}}_{L}}\right.\lVert
g\rVert,\lVert f\rVert=1,f\bot{\mathbf{1}}_{L}\right\\}.$

######  Definition 2.5 (Bipartite Expander).

Let $G$ be a bipartite graph, let $\lambda<1$. We say $G$ is a _$\lambda$
-bipartite expander_, if $\lambda(B)\leqslant\lambda$.

It is easy to show that a bipartite graph is a $\lambda$-bipartite expander if
and only if it is a $\lambda$-one sided spectral expander. So we use these
terms interchangeably on bipartite graphs.

####  2.2.2 Expander Mixing Lemma

A classical result in expander graphs is the _expander mixing lemma_ , that
intuitively says that the weight of the edges between any two vertex sets
$S,T\subset V$ is proportionate to the probabilities of $S,T$. We denote by
$E(S,T)$ the edge set between $S$ and $T$.

######  Lemma 2.6 (Expander Mixing Lemma).

Let $G=(V,E)$ be a $\lambda$-two sided spectral expanders. Then for any
$S,T\subset V$

$\lvert\nu(E(S,T))-\nu(S)\nu(T)\rvert\leqslant\lambda\sqrt{\nu(S)\nu(T)(1-\nu(S))(1-\nu(T))}.$
(2.1)

∎

Bipartite graphs have their own type of expander mixing lemma:

######  Lemma 2.7 (Bipartite Expander Mixing Lemma).

Let $G=(L,R,E)$ be a $\lambda$-bipartite expander. Then for any $S\subset
L,T\subset R$

$\lvert\nu(E(S,T))-\nu(S)\nu(T)\rvert\leqslant\lambda\sqrt{\nu(S)\nu(T)(1-\nu(S))(1-\nu(T))}.$
(2.2)

∎

Bilu and Linial gave a converse to the expander mixing lemma:

######  Theorem 2.8 ([BL06]).

Let $A$ be a normalized adjacency-operator of a bipartite graph
$H^{\prime}=(A,B,E^{\prime})$. Assume that for all $S\subseteq A,T\subseteq B$
it holds that

$\lvert\nu(E(S,T))-\nu(S)\nu(T)\rvert\leqslant\alpha\sqrt{\nu(S)\nu(T)}.$

Then $\lambda(A)\leqslant 260\alpha(1+\log_{2}(3/\alpha)).$

The Theorem in [BL06] assumes $H^{\prime}$ is regular. We show their proof
extends to arbitrary weighted graphs in Section B.

###  2.3 Graph homomorphisms

Let $G=(V,E)$ and $H=(V^{\prime},E^{\prime})$ be graphs. We say that $f:V\to
V^{\prime}$ is a _graph homomorphism_ if for any edge $\\{u,v\\}\in E$ it
holds that $\\{f(v),f(u)\\}\in E^{\prime}$. If $f$ is surjective we say that
$f$ an $H$-coloring of $G$, and that $G$ is $H$-colorable. In addition, if for
every edge ${a,b}\in E^{\prime}$ there is $\\{u,v\\}\in E$ so that
$f(u)=a,f(v)=b$ then we say that $G$ is _non-degeneratly $H$-colorable_ and
that $f$ is a _non-degenerate $H$-coloring_. We depict this in Figure 1.

Let $G=(V,E),H=(V^{\prime},E^{\prime})$ be graphs. We say that $G$ _covers_
$H$ if there is a graph homomorphism $f:V\to V^{\prime}$ so that for every
$v\in V$, $f$ restricted to a neighbourhood of $v$ a bijection to the
neighbourhood of $f(v)$.

Figure 1: $G$ is an $H$-colorable graph.

When $(H,\nu_{H}),(G,\nu_{G})$ have probability measures, then a non-
degenerate $H$-coloring defines a _new_ measure $\nu_{f}$ on $G$ as follows.
For $uv\in\overset{\to}{E}$ so that $f(u)=a,f(b)=b$,

$\nu_{f}(uv):=\nu_{H}(ab)\frac{\nu_{G}(uv)}{\sum_{u^{\prime}v^{\prime}:f(u^{\prime}v^{\prime})=ab}\nu_{G}(u^{\prime}v^{\prime})}.$

In other words, we sample (oriented or non oriented) edges in $E$ by the
following process:

  1. 1.

Sample an edge $(a,b)\in\overset{\to}{E^{\prime}}$.

  2. 2.

Sample an edge $(u,v)\in\overset{\to}{E}$ conditioned on its image being
$\\{a,b\\}$.

We stress that $\nu_{f}$ could be different than $\nu_{G}$ the original
measure on $G$. For example it always holds that
$\nu_{f}(f^{-1}(a))=\nu_{H}(a)$, regardless of $\nu_{G}(f^{-1}(a))$.

When $G$ is an $H$-colorable graph, we can partition the vertices of $G$ by
$V=\bigcup_{a\in V^{\prime}}S_{a}$ where $S_{a}=\left\\{v\in
V\left|\;\vphantom{v\in Vf(v)=a}\right.f(v)=a\right\\}$. In Section A we show
that when $H$ is an expander and the bipartite graphs between the parts in the
partition of $G$ are bipartite expanders, then
$(G,\operatorname*{\mathbb{P}}_{f})$ is also an expander:

######  Claim 2.9.

Let $H=(V^{\prime},E^{\prime})$ be a $\lambda$-two sided (one-sided) spectral
expander. Let $G=(V,E)$ and let $f:V\to V^{\prime}$ be a non-degenerate
$H$-coloring of $G$. Assume that for every $\\{a,b\\}\in E^{\prime}$ the
bipartite graph between $S_{a},S_{b}$ is $\eta$-bipartite spectral expander
(with respect to the conditional weights
$\frac{\nu_{G}(uv)}{\sum_{u^{\prime}v^{\prime}:f(u^{\prime}v^{\prime})=ab}\nu_{G}(u^{\prime}v^{\prime})}$
for $uv\in S_{a}\times S_{b}$). Then the weighted graph $(G,\nu_{f})$ is a
$\max\\{\lambda,\eta\\}$-two sided (one sided) spectral expander.

###  2.4 Simplicial complexes and high dimensional expanders

We include here the basic definitions needed for our results. For a more
comprehensive introduction to this topic we refer the reader to [DK17] and the
references therein.

A simplicial complex is a hypergraph that is downward closed with respect to
containment. It is called $d$-dimensional if the largest hyperedge has size
$d+1$. We refer to $X(\ell)$ as the hyperedges (also called faces) of size
$\ell+1$. $X(0)$ are the vertices. For a face $s$ and $\ell\leqslant d$ we
denote by $deg_{\ell}(s)=\lvert\left\\{t\in X(\ell)\left|\;\vphantom{t\in
X(\ell)s\subseteq t}\right.s\subseteq t\right\\}\rvert$.

It will sometimes be useful to consider oriented faces. We denote by

$\overset{\to}{X}(\ell)=\left\\{(v_{0},v_{1},...,v_{\ell})\left|\;\vphantom{(v_{0},v_{1},...,v_{\ell})\\{v_{0},v_{1},...,v_{\ell}\\}\in
X(\ell)}\right.\\{v_{0},v_{1},...,v_{\ell}\\}\in X(\ell)\right\\}.$

We define a weighted simplicial complex. Suppose we have a $d$-dimensional
simplicial complex $X$ and a probability distribution $\nu:X(d)\to[0,1]$. We
consider the following sampling for choosing lower dimensional faces:

  1. 1.

Choose some $d$-face $s_{d}=\\{v_{0},v_{1},...,v_{d}\\}\in X(d)$ with
probability $\nu(s_{d})$.

  2. 2.

Choose an ordering $\overset{\to}{s}_{d}=(v_{0},v_{1},...,v_{d})$ uniformly at
random.

For any $(v_{0},v_{1},...,v_{k})\in\overset{\to}{X}(k)$ we denote by

$\operatorname*{\mathbb{P}}\left[{(v_{0},v_{1},...,v_{k})}\right]=\operatorname*{\mathbb{P}}_{{(u_{0},u_{1},...,u_{d})\in\overset{\to}{X}(d)}}\left[u_{0}=v_{0},u_{1}=v_{1},...,u_{k}=v_{k}\right],$

the probability of sampling an ordered face so that $(v_{0},v_{1},...,v_{k})$
is its prefix. For an unordered face $s\in X(k)$, we denote by

$\operatorname*{\mathbb{P}}\left[{s}\right]=\frac{1}{\binom{d+1}{k+1}}\sum_{s^{\prime}\in
X(d),s^{\prime}\supseteq s}\nu(s^{\prime}).$

This is the probability of sampling $(v_{0},v_{1},...,v_{d})$ so that
$s=\\{v_{0},v_{1},...,v_{k}\\}$ is the underlying set of the first
$k$-vertices.

From here throughout the rest of the paper, when we refer to a simplicial
complex $X$, we always assume that there is a probability measure on it
constructed as above.

A link of a face in a simplicial complex, is a generalization of a
neighbourhood of a vertex in a graph:

######  Definition 2.10 (link of a face).

Let $s\in X(k)$ be some $k$-face. The _link_ of $s$ is a $d-(k+1)$-dimensional
simplicial complex defined by:

$X_{s}=\\{t\backslash s:s\subseteq t\in X\\}.$

The associated probability measure $\nu_{X_{s}}$, for the link of $s$ is
defined to be the probability of sampling $t$ in the process above given that
we sampled $s$. It is proportional equal to
$\nu_{X_{s}}(t)=\frac{\nu_{X}(t\cup s)}{\binom{|t|+|s|}{|s|}\nu(s)}$.

For an oriented face $(v_{0},v_{1},...,v_{\ell})\in\overset{\to}{X}(\ell)$ we
denote by $X_{(v_{0},v_{1},...,v_{\ell})}=X_{\\{v_{0},v_{1},...,v_{\ell}\\}}$
the link of its underlying set. Let
$(u_{0},u_{1},...,u_{\ell})\in\overset{\to}{X}(\ell)$, whose underlying set is
$s=\\{u_{0},u_{1},...,u_{\ell}\\}$. Let
$(v_{\ell+1},v_{\ell+2},...,v_{\ell+k+2})\in\overset{\to}{X}_{s}(k)$. Then it
is easy to verify that

$\operatorname*{\mathbb{P}}_{{\nu_{X_{s}}}}\left[(v_{\ell+1},v_{\ell+2},...,v_{\ell+k+2})\right]=\frac{\operatorname*{\mathbb{P}}_{{X}}\left[(u_{0},u_{1},...,u_{\ell},v_{\ell+1},v_{\ell+2},...,v_{\ell+k+2})\right]}{\operatorname*{\mathbb{P}}_{{X}}\left[(u_{0},u_{1},...,u_{\ell})\right]}.$

######  Definition 2.11 (1-skeleton).

The _$1$ -skeleton_ of a simplicial complex $X$ with some probability measure
as define above, is the graph whose vertices are $X(0)$ and edges are $X(1)$,
with (the restriction of) the probability measures of $X$ to the vertices and
edges.

We are ready to define our notion of high dimensional expanders.

######  Definition 2.12 (one-sided and two-sided high dimensional expander).

Let $0\leqslant\lambda<1$. A simplicial complex $X$ is a _$\lambda$ -two sided
link expander_ (or $\lambda$-two sided HDX) if for every $-1\leqslant
k\leqslant d-2$ and every $s\in X(k)$, the underlying graph of the link
$X_{s}$ is a $\lambda$-two sided spectral expander.

Similarly, $X$ is a _$\lambda$ -one sided link expander_ (or $\lambda$-one
sided HDX) if for every $-1\leqslant k\leqslant d-2$ and every $s\in X(k)$,
the underlying graph of the link $X_{s}$ is a $\lambda$-one sided spectral
expander.

When $X$ is a graph, this definition coincides with the definition of a
spectral expander.

A theorem by [Opp18] shows that expansion “trickles down”, that is, expansion
of links of $d-2$-faces imply expansion of links of $d-1$-faces (if they are
connected).

######  Theorem 2.13 (Theorem 5.2 in [Opp18]).

If for all $s\in X(k)$, $\lambda(X_{s})\leqslant\lambda$, for some
$\lambda\in(0,\frac{1}{2}]$, then for any $r\in X(k-1)$, s.t. $X_{r}$’s
$1$-skeleton is connected,
$\lambda_{2}(X_{r})\leqslant\frac{\lambda}{1-\lambda}$.

###  2.5 Simplicial homomorphisms

Let $X,Y$ be two pure $d$-dimensional simplicial complexes. A _simplicial
homomorphism_ is a function $f:X(0)\to Y(0)$ so that every $k$-face $s\in X$
is mapped by $f$ to a face $k$-face $f(s)\in Y(k)$. We say that $f$ is a _non-
degenerate $Y$-coloring_ if for every $d$-face $t\in Y(d)$ there exists some
$d$-face $s\in X(d)$ so that $f(s)=t$.

A surjective _function_ (not necessarily a coloring) $f:X(0)\to Y(0)$ induces
a measure $\mu_{f}$ on $X$ defined by the following sampling process:

  1. 1.

Sample a $d$-face $t\in Y(d)$.

  2. 2.

Sample a $d$-face $s\in X(d)$ given that $f(s)=t$.

We note that by taking a subcomplex $X^{\prime}\subseteq X$ that contains all
faces in $X$ that are in the support of $\mu_{f}$, then $f:X^{\prime}(0)\to
Y(0)$ is a non-degenerate coloring (we can also induce a measure on
$X^{\prime}$ so that for every $d$-face $s\in X^{\prime}(d)$,
$\nu_{X}^{\prime}(s)=\nu_{X}(s)/\nu_{X}(X^{\prime}(d))$).

We say that two simplicial complexes $X,Y$ are _isomorphic_ if there exists a
bijection $f:X(0)\to Y(0)$ so that $s\in X$ if and only if $f(s)\in Y$. We
then denote $X\cong Y$.

##### Simplicial homomorphisms and oriented faces

Let $\overset{\to}{s}=(v_{0},v_{1},...,v_{d})\in\overset{\to}{X}(d)$, whose
underlying set $s=\\{v_{0},v_{1},...,v_{d}\\}$. Let
$f(\overset{\to}{s})=(f(v_{0}),f(v_{1}),...,f(v_{d}))$ and let
$f(s)=\\{f(v_{0}),f(v_{1}),...,f(v_{d})\\}$.

its probability is

$\operatorname*{\mathbb{P}}_{{\mu_{f}}}\left[\overset{\to}{s}\right]=\frac{1}{(d+1)!}\operatorname*{\mathbb{P}}_{{\mu_{f}}}\left[s\right]=\frac{1}{(d+1)!}\operatorname*{\mathbb{P}}_{{Y}}\left[f(s)\right]\operatorname*{\mathbb{P}}_{{s^{\prime}\in
X(d)}}\left[s^{\prime}=s\left|\;\vphantom{s^{\prime}=sf(s^{\prime})=f(s)}\right.f(s^{\prime})=f(s)\right]$
$=\operatorname*{\mathbb{P}}_{{Y}}\left[f(\overset{\to}{s})\right]\operatorname*{\mathbb{P}}_{{s^{\prime}\in
X(d)}}\left[s^{\prime}=s\left|\;\vphantom{s^{\prime}=sf(s^{\prime})=f(s)}\right.f(s^{\prime})=f(s)\right].$

For every $s^{\prime}$ so that $f(s^{\prime})=f(s)$ there is a single
orientation $\overset{\to}{s^{\prime}}$ of $s^{\prime}$ so that
$f(\overset{\to}{s^{\prime}})=f(\overset{\to}{s})$ so this is equal to

$=\operatorname*{\mathbb{P}}_{{Y}}\left[f(\overset{\to}{s})\right]\operatorname*{\mathbb{P}}_{{\overset{\to}{s}^{\prime}\in\overset{\to}{X}(d)}}\left[\overset{\to}{s}^{\prime}=\overset{\to}{s}\left|\;\vphantom{\overset{\to}{s}^{\prime}=\overset{\to}{s}f(\overset{\to}{s}^{\prime})=f(\overset{\to}{s})}\right.f(\overset{\to}{s}^{\prime})=f(\overset{\to}{s})\right].$

Hence we can also describe $\mu_{f}$ via the sampling process of oriented
faces:

  1. 1.

Sample an oriented $d$-face $\overset{\to}{t}\in\overset{\to}{Y}(d)$.

  2. 2.

Sample an oriented $d$-face $\overset{\to}{s}\in\overset{\to}{X}(d)$ given
that $f(\overset{\to}{s})=\overset{\to}{t}$.

###  2.6 Simplicial covers

######  Definition 2.14 (Simplicial cover).

Let $X,Y$ be two pure $d$-dimensional simplicial complexes. We say $Y$
_covers_ $X$ if there exists a surjective simplicial homomorphism $f:Y\to X$
so that for every non-empty face $s\in Y$, $f|_{Y_{s}(0)}$ is a simplicial
isomorphism between $Y_{s}$ and $X_{f(s)}$.

Simplicial covers are the combinatorial equivalent of _topological covers_.
These are usually classified and analyzed by the _fundamental group_ of a
simplicial complex as a topological space, and the _universal cover_. For more
on this, see [Sur84]. In this paper however, we use an alternative description
of covers via the non-abelian cocycles (defined below). We define what we need
below, however we will not give full proofs (but we refer the reader again to
[Sur84]).

Let $X$ be a connected finite $d$-dimensional simplicial complex (for
$d\geqslant 2$), where $X(0)=\\{v_{1},v_{2},...,v_{n}\\}$ (the vertices are
ordered in some arbitrary order). Let $\Gamma$ be a group (not necessarily
finite). Let $f:X(1)\to\Gamma$ be some labeling. We say that $f$ is a
$\Gamma$-cocycle if for every triangle $v_{i}v_{j}v_{k}\in X(2)$ where $i<j<k$
it holds that

$f(v_{i}v_{j})f(v_{j}v_{k})f(v_{i}v_{k})^{-1}=e$

where $e$ is the identity in $\Gamma$. We denote the set of cocycles by
$Z_{1}(X,\Gamma)$.

For a cocycle $f\in Z_{1}(X,\Gamma)$ the $f$-cover of $X$ is the following
simplicial complex.

######  Definition 2.15 (Group cover construction).

Let $X$ be a pure $d$-dimensional simplicial complex, and $\Gamma$ be a finite
group. Let $f\in Z_{1}(X,\Gamma)$. The $f$-cover of $X$, denoted by
$\tilde{X}=X^{f}$ is a pure $d$ dimensional simplicial complex defined as
follows. The vertex set $\tilde{X}(0)=X(0)\times\Gamma$. The $d$-faces are all
sets $s=\\{(v_{i_{0}},g_{0}),...,(v_{i_{d}},g_{d})\\}$ so that (1)
$\\{v_{i_{0}},v_{i_{1}},...,v_{i_{d}}\\}\in X(d)$ and (2) for every two
distinct $i_{j_{1}},i_{j_{2}}$ so that $i_{j_{1}}<i_{j_{2}}$,
$f(v_{i_{j_{1}}}v_{i_{j_{2}}})=g_{i_{j_{1}}}^{-1}g_{i_{j_{2}}}$.

If $X$ is measured, then
$\mu_{\tilde{X}}(s)=\mu_{X}(s|_{X})\frac{1}{|\Gamma|}$, where $s|_{X}$ of a
face $s=\\{(v_{i_{0}},g_{0}),...,(v_{i_{k}},g_{k})\\}$ is
$s|_{X}=\\{v_{i_{0}},...,v_{i_{k}}\\}\in X(k)$.

One can show that $\tilde{X}$ indeed covers $X$ with the map
$\phi:\tilde{X}\to X$, $\phi(v_{i},g)=v_{i}$. We note for the curious reader
that there is also an inverse to this statement, see [Sur84] Proposition 2.3
for a precise statement.

We are interested in simplicial complexes that are connected. The following
claim characterizes the connected components of $X^{f}$.

Let
$\overset{\to}{X}(1)=\left\\{(v_{i},v_{j}),(v_{j},v_{i})\left|\;\vphantom{(v_{i},v_{j}),(v_{j},v_{i})v_{i}v_{j}\in
X(1)}\right.v_{i}v_{j}\in X(1)\right\\}$ be the set of directed edges on $X$.
For a labeling $f:X(1)\to\Gamma$, we denote by
$\overset{\to}{f}:\overset{\to}{X}(1)\to\Gamma$ the function

$\displaystyle\overset{\to}{f}(v_{i},v_{j})=\begin{cases}f(v_{i}v_{j})&i<j\\\
f(v_{i}v_{j})^{-1}&i>j\end{cases}.$ (2.3)

######  Claim 2.16.

Let $X$ be a $d$-dimensional simplicial complex whose $1$-skeleton is
connected. Fix some arbitrary $v\in X(0)$ and denote by $H_{v}\subseteq G$ to
be the set of all elements $g\in G$ for which there is a cycle
$v=v_{i_{0}},v_{i_{1}},v_{i_{2}},...,v_{i_{m}}=v$ such that
$g=\overset{\to}{f}(v_{i_{0}},v_{i_{1}})\overset{\to}{f}(v_{i_{1}},v_{i_{2}})\overset{\to}{f}(v_{i_{2}},v_{i_{3}})...\overset{\to}{f}(v_{i_{m-1}},v_{i_{m}})$.

Then $H_{v}$ is a subgroup of $\Gamma$. Moreover, for every
$[g]\in\Gamma/H_{v}$ there is a connected component in the cover $X^{f}$ of
$X$.

We prove the claim below, but the following corollary is all we need for our
result:

######  Corollary 2.17.

Let $X$ be a $d$-dimensional simplicial complex whose $1$-skeleton is
connected. $X^{f}$ is connected if and only if $H_{v}=G$ for some $v\in X(0)$.

Finally, we note that if $f\in Z_{1}(X,\Gamma)$ and $N\trianglelefteq\Gamma$
is a normal subgroup, then $f_{N}\in Z_{1}(X,\Gamma/N)$ that is defined by
$f_{N}(v)=f(v)N$ is also a cocycle. Thus if $\Gamma$ has an infinite sequence
of finite-indexed normal subgroups $N_{1},N_{2},...$ whose index goes to
infinity, then any $f\in Z_{1}(X,\Gamma)$ gives rise to an infinite family of
simplicial complexes that cover $X$, namely, $\\{X^{f_{N_{m}}}\\}_{m}$.

###### Proof of Claim 2.16.

$e\in H_{v}$ as the trivial loop gives $e$. If $g_{1},g_{2}\in H_{v}$ then
concatenating their cycles gives the element $g_{1}g_{2}$. For an element
$g\in H_{v}$, with a cycle $v=v_{i_{0}},v_{i_{1}},v_{i_{2}},...,v_{i_{m}}=v$.
The reverse cycle $v=v_{i_{m}},v_{i_{m-1}},v_{i_{m-2}},...,v_{i_{0}}=v$ shows
that $g^{-1}\in H_{v}$. Thus $H_{v}$ is a subgroup of $\Gamma$.

Next we show that every vertex $(v,g)$ is connected $(v,g^{\prime})$ if and
only if $g^{\prime}\in gH$: Recall that every edge in $X^{f}$ is
$(u,h)\tilde{(}w,h\overset{\to}{f}(uw))$. Thus any path
$((u_{0},g_{0}),(u_{1},g_{1}),...,(u_{m},g_{m}))$ implies that
$g_{m}=g_{0}\overset{\to}{f}(u_{0}u_{1})\overset{\to}{f}(u_{1}u_{2})...\overset{\to}{f}(u_{m-1}u_{m}).$
In particular, any path from
$(v_{0}=v,g_{0}),(v_{1},g_{1}),...,(v_{m}=v,g_{m})$ implies that
$g_{m}=g_{0}\overset{\to}{f}(vv_{1})\overset{\to}{f}(v_{1}v_{2})...\overset{\to}{f}(v_{m-1}v).$
As $(v_{0}=v,v_{1},...,v_{m}=v)$ is a cycle from $v$ to itself, then
$\overset{\to}{f}(v_{1}v_{2})...\overset{\to}{f}(v_{m-1}v)\in H_{v}$. Thus
$(v,g)$ is connected only to
$\left\\{(v,g^{\prime})\left|\;\vphantom{(v,g^{\prime})g^{\prime}\in
gH_{v}}\right.g^{\prime}\in gH_{v}\right\\}$.

On the other hand, for every $g^{\prime}\in gH$, there exists a cycle
$(v_{0}=v,v_{1},...,v_{m}=v)$, so that
$\overset{\to}{f}(v_{1}v_{2})...\overset{\to}{f}(v_{m-1}v)=g^{-1}g^{\prime}$.
Hence the path
$(v,g),(v_{1},g\overset{\to}{f}(vv_{1})),...,(v_{m}=v,g\overset{\to}{f}(v_{1}v_{2})...\overset{\to}{f}(v_{m-1}v))$
goes from $(v,g)$ to $(v,g(g^{-1}g^{\prime}))$.

Finally, we note that every vertex $(u,h)$ is connected to at least one
$(v,g)$ (since there is a path from $u$ to $v$ that lifts to a path from
$(u,h)$ to _some_ $(v,g)$). We’ve shown that that every two vertices in a set
$\\{v\\}\times gH_{v}$ are connected to one another, that every other vertex
is connected to at least one of these sets, and that two distinct
$\\{v\\}\times gH_{v}$ and $\\{v\\}\times g^{\prime}H_{v}$ are disconnected.
This shows that there is a connected component for every
$gH_{v}\in\Gamma/H_{v}$. ∎

###  2.7 The clique complex of a Cayley graph

Let $\Gamma$ be a finitely presented group (not necessarily finite), and let
$S=\\{s_{1},s_{2},...,s_{m}\\}$ a finite symmetric set of generators. We
define $C(\Gamma,S)$, as the clique complex that arises from the Cayley graph
$Cay(\Gamma,S)$. More explicitly, the vertex set is $\Gamma$, the labeled
edges are all pairs $(s_{i},s_{k})_{s_{j}}$ so that $s_{i}s_{j}=s_{k}$, and
the $d$-faces are all $d$-cliques in this graph. While this complex is
infinite, the neighbourhood of every vertex is of finite size $|S|$.

We limit ourselves to groups and generating sets where there exists some
$d\geqslant 1$ so that every edge is in some $(d+1)$-clique. In this case, the
resulting complex is _pure_ and $(d+1)$-dimensional. We abuse definitions and
say that an infinite complex is an $\eta$-high dimensional expander if all its
links (not including the complex itself) are $\eta$-spectral expanders.

######  Example 2.18.

[LSV05] showed that for any $d>0$ and prime power $q^{e}$, the group
$PGL_{d}(\mathbb{F}_{q^{e}})$ has a generating set $S$ of size $m=m(d)$ so
that $C(\Gamma,S)$ is a pure $d$-dimensional simplicial complex. Moreover, all
links of $C(\Gamma,S)$ are $\eta$-one-sided spectral expanders for $\eta$ that
goes to $0$ as $q^{e}$ tends to infinity. By using Theorem 2.13 one can show
that low dimensional skeletons of these complexes are also two-sided spectral
expanders.

##  3 Random high dimensional expanders from covers

In this section we present our construction of high dimensional expanders that
are based on covers. We first define the simplicial complexes that are
suitable for our construction.

######  Definition 3.1.

Let $c,r>1$ and $\eta>0$. Let $X$ be a $d$-dimensional pure simplicial complex
and denote by $Q=\max_{v\in X(0)}\deg_{d}(v)$. We say that $X$ is
$(c,r,\eta)$-_suitable_ if

  1. 1.

$X$ is an $\eta$-two-sided high dimensional expander.

  2. 2.

For every $0\leqslant\ell\leqslant d-2$, $\sigma\in X(\ell)$ and every $v\in
X_{\sigma}(0)$, the degree of $v$ in the $1$-skeleton of $X_{\sigma}(0)$ is at
least $c(1+\log Q)$.

  3. 3.

For every $0\leqslant\ell\leqslant d-2$ and $\sigma\in X(\ell)$, the weight of
every edge in $e\in X_{\sigma}(1)$ is between $\frac{1}{r|X_{\sigma}(1)|}$ and
$\frac{r}{|X_{\sigma}(1)|}$. Moreover, the weight of every vertex $v\in
X_{\sigma}(0)$ is between $\frac{1}{r|X_{\sigma}(0)|}$ and
$\frac{r}{|X_{\sigma}(0)|}$.

Note that a $(c,r,\eta)$-suitable simplicial complex is also
$(c^{\prime},r^{\prime},\eta^{\prime})$-suitable for any $c^{\prime}\leqslant
c$, $r^{\prime}\geqslant r$ and $\eta^{\prime}\geqslant\eta$.

######  Theorem 3.2 (Main).

For every pair of integers $d,m$ there exists some $c,r>1,\eta>0$ so that the
following holds. Let $\Gamma$ be a group with a generating set $S$ of size
$m$. Assume that $C(\Gamma,S)$ is a $d$-dimensional $\frac{\lambda}{2}$-high
dimensional expander for some $\lambda<1$. Let $X$ be a $(c,r,\eta)$-suitable
$d$-dimensional simplicial complex. Then there exists some $Y\subseteq X$ so
that:

  1. 1.

$Y$ is an $d$-dimensional $\lambda$-high dimensional expander.

  2. 2.

$Y$ has a connected $\Gamma$-cover.

  3. 3.

$Y$ contains $\Omega_{m,d}(1)$ fraction of the faces of $X$.

There is a randomized algorithm that outputs $Y$ in expected polynomial time.

######  Remark 3.3.

We prove Theorem 3.2 in an existential manner, using the Lovasz Local Lemma.
Once existence is establish, we use the algorithmic version Theorem 2.3 by
[MT10] as a black box to obtain an algorithm that outputs $Y$.

###  3.1 Proof outline

As discussed in the introduction, we prove Theorem 3.2 via the probablistic
method. Fix a group $\Gamma$, and a high dimensional expander $X$ that satisfy
the assumptions of the theorem. We sample a function
$f:X(1)\to\\{s_{1},...,s_{m}\\}$ uniformly at random, and remove all faces
$s\in X$ that contain a triangle $v_{i}v_{j}v_{k}\in X$ so that
$f(v_{i}v_{j})f(v_{j}v_{k})f(v_{i}v_{k})^{-1}\neq e$ (where $i<j<k$). Denote
by $Y\subseteq X$ the resulting sub-complex.

We cannot prove that $Y$ will be a high dimensional expander with high
probability. For example, if $Q\ll|X(d)|$ (where $Q$ is the maximal $d$-degree
of a vertex), then with high probability there exists a face $\tau\in X(d-2)$
with a disconnected link. This is because the event that a face $\tau$ has a
disconnected link depends only on $poly(Q)$ edges (the edges whose distance
from $\tau$ is at most $2$). Thus, the probability is a function of $Q$ only.
When $Q$ stays constant and $|X(d)|$ grows to infinity, the number of faces
with a disconnected link will grow in expectation.

This is where the Lovasz Local Lemma comes into play. For every face $\tau\in
X$ we will define a “bad event” $E_{\tau}$, that informally, says that the
link of $\tau$ is not an expander graph 333The formal definition of $E_{\tau}$
is more involved. We also want that when all $E_{\tau}$ don’t occur, then $Y$
will have a connected $\Gamma$-cover and that $Y$ will contain a constant
fraction of the faces $X$..

To use the Lovasz Local Lemma, we show that these events
$E_{\tau},E_{\tau^{\prime}}$ are independent whenever the distance between
every pair of vertices $v\in\tau,u\in\tau^{\prime}$ is greater than $2$. Thus
every $E_{\tau}$ depends on $poly(Q)$ other $E_{\tau^{\prime}}$. This makes
sense since the structure of the link of a face $\tau\in X$, depends only on
the value of $f$ on edges $uv$ so that $\tau\cup uv\in X$.

Furthermore, we show that the probability of $E_{\tau}$ is at most
$1/Q^{\ell}$ for $\ell$ as large as we need (this is where the fact that $X$
is $(c,r,\eta)$-suitable for appropriate $c,r,\eta$ comes into play). Now we
can apply the Lovasz Local Lemma, and get that $\bigwedge_{t\in X}\neg E_{t}$
occurs with positive probability. This implies that the resulting sub-complex
$Y$ is a high dimensional expander (the same argument will show the other
properties required from $Y$ occur as well).

###  3.2 Notation for the proof

######  Definition 3.4.

Let $f:X(1)\to\\{s_{1},...,s_{m}\\}$.

  1. 1.

We say a face $\sigma\in X$ _is satisfied by $f$_ if for every triangle
$v_{i}v_{j}v_{k}\subseteq\sigma$ so that $i<j<k$ it holds that
$f(v_{i}v_{j})f(v_{j}v_{k})f(v_{i}v_{k})^{-1}=e$.

  2. 2.

For a face $\sigma\in X$, we say that $\sigma$ is _maximally satisfied_ if
there exists $\tau\in X(d)$ so that $\sigma\subseteq\tau$ and $\tau$ is
satisfied by $f$.

Note that vertices and edges are (vacuously) satisfied by any $f$. We observe
the following about satisfied faces.

######  Observation 3.5.

A face $\\{v_{0},v_{1},...,v_{r}\\}$ is satisfied if and only if
$\\{f(v_{0}v_{1}),f(v_{0}v_{2}),...,f(v_{0}v_{r})\\}\cup\\{e\\}$ is a face in
$C(\Gamma,S)$, if and only if
$\\{f(v_{0}v_{1}),f(v_{0}v_{2}),...,f(v_{0}v_{r})\\}\cup\\{e\\}$ is a clique
in $Cay(\Gamma,S)$.

This observation follows from the fact that whenever
$f(v_{i}v_{j})f(v_{j}v_{k})f(v_{i}v_{k})^{-1}=e$ this implies that
$e,f(v_{i}v_{j}),f(v_{i}v_{k})$ are a triangle in the Cayley graph of
$\Gamma,S$.

######  Definition 3.6.

Let $f:X(1)\to\\{s_{1},...,s_{m}\\}$. The _$f$ -pruning_ of $X$ is the
simplicial complex $Y$ whose vertices are $Y(0)=X(0)$ and faces are all $t\in
X$ that are maximally satisfied by $f$.

We imbue $\overset{\to}{Y}(d)$ with the following measure, where we sample an
oriented $(d-1)$-face in the link of the unit $e$ in $C(\Gamma,S)$,
$(s_{i_{0}}s_{i_{1}},...,s_{i_{d-1}})\in C_{e}(\Gamma,S)$, and then sample an
oriented $d$-face $(u_{0},u_{1},...,u_{d})\in Y$ so that
$f(u_{0}u_{j})=s_{i_{j}}$ and for every $j_{1},j_{2}\neq 0$,
$f(u_{j_{1}}u_{j_{2}})=s_{j_{1}}^{-1}s_{j_{2}}$. This induces a measure over
$Y(d)$ by taking the underlying set of $(u_{0},u_{1},...,u_{d})$. As
$\operatorname*{\mathbb{P}}\left[{(u_{0},u_{1},...,u_{d})}\right]=\operatorname*{\mathbb{P}}\left[{(u_{\pi(0)},u_{\pi(1)},...,u_{\pi(d)})}\right]$
for any permutation $\pi$, it holds that
$\operatorname*{\mathbb{P}}\left[{u_{0},u_{1},...,u_{d}}\right]=(d+1)!\operatorname*{\mathbb{P}}\left[{(u_{0},u_{1},...,u_{d})}\right]$.
This measure is only possible if for every $C(\Gamma,S)$,
$\\{s_{i_{0}}s_{i_{1}},...,s_{i_{d}}\\}\in C_{e}(\Gamma,S)$ there exists a
face in $Y$ so that $f(u_{0}u_{j})=s_{i_{j}}$ and for every $j_{1},j_{2}\neq
0$, $f(u_{j_{1}}u_{j_{2}})=s_{j_{1}}^{-1}s_{j_{2}}$. When this is not possible
we do not consider $Y$ as measured.

######  Definition 3.7.

Fix $f:X(1)\to\\{s_{1},...,s_{m}\\}$, and let $\sigma\in X(\ell)$ be a
satisfied face for $\ell\leqslant d-2$. The _satisfaction graph_ of $\sigma$,
denoted by $G_{\sigma}=(V_{\sigma},E_{\sigma})$ is the following:

  * –

The vertices are all $v\in X_{\sigma}(0)$ so that $\sigma\mathbin{\mathaccent
0{\cdot}\cup}v$ is satisfied.

  * –

The edges are all $uv\in X_{\sigma}(1)$ so that $uw\mathbin{\mathaccent
0{\cdot}\cup}\sigma$ is satisfied.

Let $\sigma=\\{v_{0},v_{1},...,v_{r}\\}$ be some $f$-satisfied face. Denote by
$f(v_{0}v_{j})=s_{i_{j}}$ and let $a=\\{e\\}\cup\\{s_{i_{j}}\\}_{j=1}^{r}$.
Recall that $C_{a}$ is the link of $a$ in the complexes induced by cliques in
$Cay(\Gamma,S)$. The satisfaction graph $G_{\sigma}$ has a $C_{a}$-coloring
$\psi_{\sigma}:V_{\sigma}(0)\to C_{a}(0)$ by $\psi_{\sigma}(u)=f(v_{0}u)$. The
fact that this is a coloring following from Observation 3.5. We consider the
measure on $G_{\sigma}$ to be the measure induced by the coloring
$\psi_{\sigma}$ as described in Section 2.5. More explicitly, we sample an
edge $uv\in E_{\sigma}$ by sampling $s_{i}s_{j}\in C_{a}$ and then we sample
an edge $uv\in E_{\sigma}$ so that

###  3.3 The proof

###### Proof of Theorem 3.2.

Consider the probabilistic experiment where we sample
$f:X(1)\to\\{s_{1},...,s_{m}\\}$ uniformly at random and set $Y\subseteq X$ to
be the $f$-pruning of $X$. Define the following events for faces in $\tau\in
X$:

  * *

$AT(\tau)$, the event where for some face
$\tau=\\{v_{0},v_{1},...,v_{\ell}\\}\in X(\ell)$, there exists an $\ell+1$
tuple $(s_{i_{0}},s_{i_{1}},...,s_{i_{\ell}})$ so that the probability (in
$X_{\tau}$) of $u\in X_{\tau}(0)$ so that that
$f(v_{0}u)=s_{i_{0}},f(v_{1}u)=s_{i_{1}},...,f(v_{\ell}u)=s_{i_{\ell}}$ is
either greater than $\geqslant\frac{r^{2}}{m^{\ell+1}}$ or smaller than
$\leqslant\frac{1}{r^{2}m^{\ell+1}}$. (AT stands for “atypical tuple”). Note
that as this should hold for all tuples, then this doesn’t depend on the
chosen orientation of $\tau$.

  * *

$NE(\tau)$, the event where the satisfaction graph $G_{\tau}$ is not a
$\frac{\lambda}{2}$-spectral expander (NE stands for “not expander”).

  * *

$BC(\tau)$, for $\tau\in X(0)$, the event where there exists some $s_{i}\in S$
so that every for every triangle $\tau uw\in X(2)$, it holds that
$\overset{\to}{f}(\tau u)\overset{\to}{f}(u,w)\overset{\to}{f}(w\tau)\neq
s_{i}$444Recall that by (2.3) the definition of
$\overset{\to}{f}:\overset{\to}{X}(1)\to\Gamma$ is
$\overset{\to}{f}(v_{i},v_{j})=f(v_{i}v_{j})$ if $i<j$ and
$\overset{\to}{f}(v_{i},v_{j})=f(v_{i}v_{j})^{-1}$ otherwise. (BC stands for
“bad cover”).

These events allow us to define
$\left\\{E_{\tau}\left|\;\vphantom{E_{\tau}\tau\in X\setminus
X(d)}\right.\tau\in X\setminus X(d)\right\\}$ as in the proof outline:

$\displaystyle E_{\tau}=\begin{cases}AT(\tau)&\tau\in X(d-1)\\\ AT(\tau)\cup
NE(\tau)&\tau\in X(\ell),1\leqslant\ell\leqslant d-2\\\ AT(\tau)\cup
NE(\tau)\cup BC(\tau)&\tau\in X(0)\end{cases}.$ (3.1)

The formula is ambiguous when $d=2$. In this case we define
$E_{\tau}=AT(\tau)\cup NE(\tau)\cup BC(\tau)$ for all vertices $\tau\in X(0)$.

Finally let $\mathcal{G}=\bigwedge_{\tau\in X\setminus X(d)}\neg E_{\tau}$. We
claim the following:

######  Claim 3.8.

When $\mathcal{G}$ occurs, then

  1. 1.

$Y$ is an $d$-dimensional $\lambda$-high dimensional expander.

  2. 2.

$Y$ has a connected $\Gamma$-cover.

  3. 3.

$Y$ contains $\Omega_{m,d}(1)$ fraction of the faces of $X$.

######  Claim 3.9.

The event $\mathcal{G}$ occurs with positive probability.

The proof is complete given these claims. ∎

###### Proof of Claim 3.8.

We assert that when $\neg AT(\tau)$ holds for all $\tau\in X\setminus X(d)$
the measure of the $1$-skeleton in every link $X_{\sigma}$ is similar to the
measure induced by $G_{\sigma}$ for every $\sigma\in X$.

######  Claim 3.10.

When $\bigcup_{\tau\in X\setminus X(d)}\neg AT(\tau)$ occurs, then

  1. 1.

Let $j\leqslant d-1$ and
$\overset{\to}{\sigma}=(v_{0},v_{1},...,v_{j})\in\overset{\to}{X}(j)$ be some
satisfied face. Let
$\bar{s}=\\{s_{i_{\ell_{1}},i_{\ell_{2}}}\\}_{\ell_{1}\neq\ell_{2}}$ be so
that $s_{i_{\ell_{1}},i_{\ell_{2}}}=f(v_{\ell_{1}}v_{\ell_{2}})$ is the
labeling of the edges of $\sigma$555formally $\bar{s}$ is a function that
receives as input $\ell_{1}\neq\ell_{2}\in\\{0,1,...,j\\}$ and outputs some
$s_{\ell_{1},\ell_{2}}\in S$.. Let
$\hat{\sigma}=(s_{i_{0},i_{1}},s_{i_{0}i_{2}},...,s_{i_{0},i_{j}})$. Then

$r^{-9d}\operatorname*{\mathbb{P}}_{{C_{e}}}\left[\hat{\sigma}\right]\operatorname*{\mathbb{P}}_{{X}}\left[\overset{\to}{\sigma}\left|\;\vphantom{\overset{\to}{\sigma}\bar{s}}\right.\bar{s}\right]\leqslant\operatorname*{\mathbb{P}}_{{Y}}\left[\overset{\to}{\sigma}\right]\leqslant
r^{9d}\operatorname*{\mathbb{P}}_{{C_{e}}}\left[\hat{\sigma}\right]\operatorname*{\mathbb{P}}_{{X}}\left[\overset{\to}{\sigma}\left|\;\vphantom{\overset{\to}{\sigma}\bar{s}}\right.\bar{s}\right],$

where
$\operatorname*{\mathbb{P}}_{{X}}\left[\overset{\to}{\sigma}\left|\;\vphantom{\overset{\to}{\sigma}\bar{s}}\right.\bar{s}\right]$
is the probability of sampling $(u_{0},u_{1},...,u_{j})\in X(j)$ given that we
sampled some $(u_{0}^{\prime},u_{1}^{\prime},...,u_{j}^{\prime})\in X(j)$ so
that its edges are labeled
$f(u_{\ell_{1}}^{\prime}u_{\ell_{2}}^{\prime})=s_{i_{\ell_{1}},i_{\ell_{2}}}$.
We interpret $\operatorname*{\mathbb{P}}_{{C_{e}}}\left[\hat{\sigma}\right]=0$
when $\sigma\notin C_{e}$.

  2. 2.

For every $-1\leqslant j\leqslant d-2$, every $\sigma\in X(j)$ and
$\overset{\to}{uv}\in\overset{\to}{Y}_{\sigma}(1)$ or $w\in Y_{\sigma}(0)$ it
holds that

$r^{-15d}\leqslant\frac{\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[\overset{\to}{uv}\right]}{\operatorname*{\mathbb{P}}_{{G_{\sigma}}}\left[\overset{\to}{uv}\right]}\leqslant
r^{15d}.$
$r^{-15d}\leqslant\frac{\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[w\right]}{\operatorname*{\mathbb{P}}_{{G_{\sigma}}}\left[w\right]}\leqslant
r^{15d}.$

We prove this claim in Section 3.6. In particular, the first item implies that
every satisfied face is also maximally satisfied since it has positive
probability. This implies that the $1$-skeleton of $Y_{\tau}$ and $G_{\tau}$
are the same as sets. The second item implies that for every $\tau$, the
$\psi_{\tau}$ coloring is non-degenerate and the the measures of $G_{\tau}$
and $Y_{\tau}$ are similar.

  1. 1.

$Y$ is an $d$-dimensional $\lambda$-high dimensional expander.

If $\mathcal{G}$ occurs, then for every $\tau\in X$ of dimension $\leqslant
d-2$, the $1$-skeleton of a link $Y_{\tau}$ is the satisfaction graph
$G_{\tau}$ (since every satisfied face is also maximally satisfied). Moreover,
fix some $\tau$ and let $A$ is the adjacency matrix of the $1$-skeleton of
$Y_{\tau}$ and $\tilde{A}$ is the adjacency matrix of $G_{\tau}$ defined via
the non-degenerate coloring $\psi_{\tau}$. The spectral norm of $A$ is the
operator norm of the matrix $B=A-J_{1}$ where
$(A-J_{1})_{u,v}=\operatorname*{\mathbb{P}}_{{w\in
Y_{\tau}(0)}}\left[w=v\left|\;\vphantom{w=vw\sim u}\right.w\sim
u\right]-\operatorname*{\mathbb{P}}_{{Y_{\tau}}}\left[v\right]$ and similarly
the spectral norm of $\tilde{A}$ is the operator norm of $\tilde{B}=A-J_{2}$
where $(A-J_{2})_{u,v}=\operatorname*{\mathbb{P}}_{{w\in
G_{\tau}}}\left[w=v\left|\;\vphantom{w=vw\sim u}\right.w\sim
u\right]-\operatorname*{\mathbb{P}}_{{G_{\tau}}}\left[v\right]$.

By the second item of Claim 3.10 and direct calculations, the difference
matrix $\mathcal{E}=B-\tilde{B}$ is a matrix so that in every entry $(u,v)$

$\lvert{\mathcal{E}_{\tau}}(v,u)\rvert\leqslant(r^{30d}-1)\cdot\left(\operatorname*{\mathbb{P}}_{{w\in
G_{\tau}}}\left[w=v\left|\;\vphantom{w=vw\sim u}\right.w\sim
u\right]+\operatorname*{\mathbb{P}}_{{G_{\tau}}}\left[v\right]\right).$

Thus the $\ell_{1}$ norm of every row is at most $2(r^{30d}-1)$. This implies
that $\lVert\mathcal{E}\rVert_{op}\leqslant 2(r^{30d}-1)$, and hence

$\lambda(Y_{\tau})=\lVert
B\rVert_{op}\leqslant\lVert\tilde{B}\rVert_{op}+2(r^{30d}-1)=\lambda(G_{\tau})+2(r^{30d}-1).$

By $\neg NE(\tau)$, we have that $\lambda(G_{\tau})\leqslant\frac{\lambda}{2}$
and so if we choose $r$ so that $2(r^{30d}-1)\leqslant\frac{\lambda}{2}$ we
get that $\lambda(Y_{\tau})\leqslant\lambda$.

  2. 2.

$Y$ has a connected $\Gamma$-cover.

The cover is the one induced by $f$ itself. By Corollary 2.17 it is enough to
fix some $v\in Y(0)$ and show that for every $g\in\Gamma$ there is a cycle in
$Y(1)$, $(v=v_{0},v_{1},...,v_{t}=v)$ so that

$\overset{\to}{f}(v_{0},v_{1})\overset{\to}{f}(v_{1},v_{2})\cdot...\cdot\overset{\to}{f}(v_{t-1},v_{t})=g.$

The cycle need not be simple. If $\mathcal{G}$ occurs the $1$-skeleton of $X$
and of $Y$ are the same, so its enough to find such a cycle in $X(1)$. Fix an
arbitrary vertex $v\in X(0)$. When $\neg BC(v)$ holds, for every generator
$s_{i}$ there is a path $(v,u,w,v)$ (in the $1$-skeleton) so that
$\overset{\to}{f}(v,u)\overset{\to}{f}(u,w)\overset{\to}{f}(w,v)=s_{i}$. In
particular, this implies that for every
$g=s_{i_{1}}s_{i_{2}}...s_{i_{r}}\in\Gamma$ we can concatenate the cycles for
$s_{i_{1}},s_{i_{2}},...,s_{i_{r}}$ to get a cycle that generates $g$ as
required.

  3. 3.

$Y$ contains $\Omega_{m,d}(1)$ fraction of the faces of $X$.

If $\mathcal{G}$ occurs, if an $\ell$-face satisfies $f$ there are at least
$\frac{1}{2m^{d}}$-fraction of the $\ell+1$-faces that contain it that also
satisfy $f$. Thus by induction, at least
$\left(\frac{1}{2m^{d}}\right)^{d-\ell}$-fraction of the $\ell$-faces of $X$
that appear in $Y$ (where the basis of the induction is by the fact that all
edges of $X$ appear in $Y$).

∎

###### Proof of Claim 3.9.

To show that $\mathcal{G}$ has positive probability we use Lovasz Local Lemma
Theorem 2.3. First, for a given $\tau\in X$ we bound the number
$\tau^{\prime}\in X$ so that $E_{\tau}$ and $E_{\tau^{\prime}}$ are not
independent.

Note that $AT(\tau),NE(\tau)$ and $BC(\tau)$ depend only on the value $f(uv)$
for edges $uv\in X(1)$ that either intersect $\tau$, or so that at least one
of $u,v\in X_{\tau}(0)$. $E_{\tau}$ is independent of the value of $f(uv)$ for
the rest of the edges. Thus, for every $\tau,\tau^{\prime}\in X$, if
$E_{\tau},E_{\tau^{\prime}}$ are not independent, then there is a path of
length at-most $2$ edges from a vertex in $\tau$ to a vertex in
$\tau^{\prime}$.

Denote by $Q$ is the maximal number of $d$-faces that a contain some fixed
vertex $v\in X(0)$. Let $R$ be the number of edges adjacent to a vertex $v\in
X(0)$. For a fixed $\tau$, there are at most $d2^{d}Q(1+R+R^{2})$ faces
$\tau^{\prime}\in X$ so that $E_{\tau},E_{\tau^{\prime}}$ depend on the same
edge. This (crude) bound is obtained as follows: we have at most $d$ choices
for $v\in\tau$, then we have $1+R+R^{2}$ choices for $u\in X(0)$ so that $u$
is connected to $v$ by a path of length $\leqslant 2$. There are at most $Q$
$d$-faces that contain $u$ hence there are at most $Q2^{d}$ faces on all
levels that contain $u$. Denote $K=d2^{d}Q(1+R+R^{2})$, and we record that
$K=poly(Q)$.

If we show that for all $\ell<d$ and $\tau\in X(\ell)$ it holds that

$\operatorname*{\mathbb{P}}\left[{E_{\tau}}\right]<\frac{1}{(K+1)e}$ (3.2)

then by the Lovazs Local Lemma, we will be promised that $\mathcal{G}$ occurs
with some positive probability. The $e$ in (3.2) is Euler’s number.

To show (3.2), we need the following assertions.

######  Lemma 3.11.

There exists $c,r>1$ and $\eta>0$ so that the following guarantee holds for
any $(c,r,\eta)$-suitable $d$-dimensional simplicial complex $X$ with maximal
$d$-degree $Q$. Let $\tau\in Y(j)$. Then

$\operatorname*{\mathbb{P}}\left[{NE(\tau)}\right]\leqslant
8m^{3}|X_{\tau}(0)|^{2}e^{\log|X_{\tau}(0)|-\mu c\log
Q}+(|X_{\tau}(0)|+1)m^{d}e^{0.03m^{-d}(r-1)^{2}c\log Q}.$

Here $\mu=\mu(r,\lambda,m,d)$ is some positive constant.

That is, the satisfaction graph $G_{\tau}$ is a $\frac{\lambda}{2}$-spectral
expander with probability at least
$1-8m^{3}|X_{\tau}(0)|^{2}e^{\log|X_{\tau}(0)|-\mu c\log Q}\
-(|X_{\tau}(0)|+1)m^{d}e^{0.03m^{-d}(r-1)^{2}c\log Q}$.

######  Claim 3.12.

Let $X$ be $(c,r,\eta)$-suitable with maximal $d$-degree $Q$. Let $\tau\in
X(\ell)$ for $\ell\leqslant d-1$. Then
$\operatorname*{\mathbb{P}}\left[{AT(\tau)}\right]\leqslant
m^{d}e^{-0.03m^{-d}(r-1)^{2}c\log Q}$.

######  Claim 3.13.

Let $X$ be $(c,r,\eta)$-suitable with maximal $d$-degree $Q$, let $\ell<d$.
Fix $v\in X(0)$. Then

$\operatorname*{\mathbb{P}}\left[{BC(v)}\right]<\left(1-\frac{1}{m^{2}}\right)^{clogQ}.$

That is, the probability that there exists some $s_{i}\in S$ so that for every
cycle $(v,u,w,v)$, it holds that
$\overset{\to}{f}(vu)\overset{\to}{f}(uw)\overset{\to}{f}(wv)\neq s_{i}$ is at
most $\left(1-\frac{1}{m^{2}}\right)^{clogQ}$.

For every $\tau\in X$, $|X_{\tau}(0)|\leqslant Q$. Thus in the assertions
above, the upper bounds on the probabilities of $AT(\tau),NE(\tau)$ and
$BC(\tau)$ are all of the form $poly(Q)\cdot e^{-\Omega(c\log Q))}$ where the
hidden constants depend on $m,d,\lambda,r$. Hence by fixing some values of
$m,d,\lambda,r$ one can take large enough $c$ and small enough $\eta$ so that
the bounds are all $\leqslant\frac{1}{5(K+1)e}$ for any $(c,r,\eta)$-suitable
simplicial complexes $X$.

Thus (3.2) holds. ∎

We first prove Claim 3.12 and Claim 3.13. Then we prove Lemma 3.11.

###### Proof of Claim 3.12.

Fix $\tau=\\{u_{0},u_{1},...,u_{\ell}\\}\in X(\ell)$. Recall that the measure
of every vertex in the link is
$\frac{1}{r|X_{\tau}(0)|}\leqslant\operatorname*{\mathbb{P}}\left[{v}\right]\leqslant\frac{r}{|X_{\tau}(0)|}$.
Thus for every tuple $\bar{s}=(s_{i_{0}},s_{i_{1}},...,s_{i_{\ell}})$, the
_number_ of vertices $v\in X_{\tau}(0)$ so that
$f(u_{0}v)=s_{i_{0}},f(u_{1}v)=s_{i_{1}},...,f(u_{\ell}v)=s_{i_{\ell}}$ is
between $r^{-1}m^{-d}|X_{\tau}(0)|$ and $rm^{-d}|X_{\tau}(0)|$, then $\neg
AT(\tau)$ doesn’t hold.

For a fixed tuple $\bar{s}=(s_{i_{0}},s_{i_{1}},...,s_{i_{\ell}})$ the
probability that $v\in X_{\tau}(0)$ has that
$f(u_{0}v)=s_{i_{0}},f(u_{1}v)=s_{i_{1}},...,f(u_{\ell}v)=s_{i_{\ell}}$ is
$m^{-d}$. Let $E(v,\bar{s})$ be this event. As
$\left\\{E(v,\bar{s})\left|\;\vphantom{E(v,\bar{s})v\in
X_{\tau}(0)}\right.v\in X_{\tau}(0)\right\\}$ are independent. Let $R_{s}$ be
the random variable counting the number of $E(v,\bar{s})$. The fraction of
$v\in X_{\tau}(0)$ so that $E(v,\bar{s})$ holds is greater than $r^{2}m^{-d}$
or smaller than $r^{2}m^{-d}$ when $\lvert
R_{s}-m^{-d}|X_{\tau}(0)|\rvert\geqslant(r-1)|X_{\tau}(0)|$. By Chernoff’s
bound,

$\operatorname*{\mathbb{P}}\left[{\lvert
R_{s}-m^{-d}|X_{\tau}(0)|\rvert\geqslant(r-1)|X_{\tau}(0)|}\right]\leqslant
e^{-0.03m^{-d}(r-1)^{2}|X_{\tau}(0)|}.$

Thus by a union bound over all tuples $\bar{s}$, the probability that
$AT(\tau)$ occurs is at most $m^{d}e^{-0.03m^{-d}(r-1)^{2}|X_{\tau}(0)|}$.

∎

###### Proof of Claim 3.13.

Fix $v\in X(0)$, and let $u\in X_{v}(0)$.

  1. 1.

There are at least $c\log Q$ triangles that contain $uv$.

  2. 2.

All triangles share only the edge $vu$. The rest of the edges $uw,wv$ appear
only in one three-cycle each.

  3. 3.

Thus the probability that
$\overset{\to}{f}(vu)\overset{\to}{f}(uw)\overset{\to}{f}(wv)=s_{i}$ is
greater or equal to the probability that
$f(uw)=f(vu)^{-1}\;\hbox{and}\;f(wv)=s_{i}$, which is $\frac{1}{m^{2}}$.
Furthermore, these events are all independent from one another (given _any_
value $f(vu)$).

  4. 4.

Hence the probability that this doesn’t occur for any triangle as above is at
most $\left(1-\frac{1}{m^{2}}\right)^{c\log Q}$. We multiply by $m=|S|$ as a
union bound on all $s_{i}\in S$.

∎

###  3.4 Structure of a satisfaction graph

In order to prove Lemma 3.11, we give a description of the satisfaction graph
of $G_{\tau}$ for $\tau\in X(\ell),\ell\leqslant d-2$. We already saw that as
sets $G_{\tau}$ is equal to the $1$-skeleton of $Y_{\tau}$ when
$\bigcap_{\sigma}\neg AT(\sigma)$ holds. Recall the definition of
$C(\Gamma,S)$ to be the (possibly infinite) simplicial complex whose faces are
cliques in the Cayley graph of $\Gamma$ with generators $S$.

Order $\tau=\\{u_{0},u_{1},...,u_{\ell}\\}$ arbitrarily, and denote by
$s_{i_{j}}=\overset{\to}{f}(u_{0}u_{j})$. Denote by
$a=\\{e,s_{i_{1}},s_{i_{2}},...,s_{i_{\ell}}\\}$, and let $C_{a}$ be the link
of $a\in C(\Gamma,S)$. Fixing the values of $f$ on all the edges in $\tau$, we
use Observation 3.5 to describe the satisfaction graph $G_{\tau}$ according to
the following probabilistic experiment:

  1. 1.

Vertex sampling: sample $f(u_{i}v)$ for every $v\in X_{\tau}(0)$ and
$u_{i}\in\tau$. We sample $v$ into $G_{\tau}$ if and only if $\tau\cup v$ is
satisfied by $f$.

This step partitions $X_{\tau}(0)$ to distinct sets according to the values of
$f(u_{0}v)$. Denote by $S_{i}$ all vertices $v$ so that
$\overset{\to}{f}(u_{0}v)=s_{i}$.

  2. 2.

Edge sampling: Sample $f(vv^{\prime})$ for all edges $vv^{\prime}\in
X_{\tau}(1)$. For every edge $s_{i}s_{j}\in C_{a}(1)$ there exists some
$s_{i,j}$ so that $s_{i}s_{i,j}=s_{j}$. In the edge sample step an edge
$vv^{\prime}\in X_{\tau}(1)$ is sampled into $Y_{\tau}(1)$ if and only if
$v\in S_{i},v^{\prime}\in S_{j}$, and $f(vv^{\prime})=s_{i,j}$ for some edge
$s_{i}s_{j}$ in the link of $a$.

For every $s_{i}\in C_{a}(0)$, the probability that $v\in X_{\tau}(0)$ is
sampled into $S_{i}$ is $m^{-(\ell+1)}$: this is the probability that
$\overset{\to}{f}(u_{0}v)=s_{i}$, and the rest of the edges
$\overset{\to}{f}(u_{i}v)$ are chosen so that all triangles in $\tau\cup v$
are satisfied. Every two $v,v^{\prime}\in X_{\tau}(0)$ are sampled
independently in this step.

Now consider the edge sample step. Let $v\in S_{i},v^{\prime}\in S_{j}$ be so
that $vv^{\prime}\in X_{\tau}(1)$. If $s_{i}$ and $s_{j}$ are not connected in
$C_{a}$ then the edge $vv^{\prime}\notin Y_{\tau}(1)$ (as $a\cup s_{i}s_{j}$
is not a clique in $C(\Gamma,S)$).

Finally, let $s_{i}s_{j}\in C_{a}(1)$, i.e. $a\cup s_{i}s_{j}$ is a clique in
$C(\Gamma,S)$. Denote by $s_{i,j}\in S$ the element so that
$s_{i}s_{i,j}=s_{j}$ (there is such an element since $a\cup s_{i}s_{j}$ is a
clique in $C(\Gamma,S)$). Then for every $vv^{\prime}\in X_{\tau}(1)$ so that
$v\in S_{i},v^{\prime}\in S_{j}$, the edge $vv^{\prime}\in Y_{\tau}(1)$ if and
only if $f(vv^{\prime})=s_{i,j}$. By Observation 3.5 this is the only possible
assignment for $vv^{\prime}$ so that $\tau\cup vv^{\prime}$ is satisfied by
$f$, and since $\tau\cup vv^{\prime}$ is a $d$-dimensional face, it is sampled
into $Y$ if and only if it is satisfied.

To summarize, $Y_{\tau}$ is obtained by vertex removal, partitioning the
remaining vertices to random sets $S_{i}$, and for every pair of sets
$S_{i},S_{j}$ so that $s_{i},s_{j}$ are in the link of $a$, random sub-
sampling of the edges between $S_{i},S_{j}$. From this explanation we can
conclude the following:

######  Claim 3.14.

There is a $C_{a}$-coloring of $Y_{\tau}$, $\psi_{\tau}:Y_{\tau}(0)\to
C_{a}(0),\;\psi_{\tau}(v)=f(u_{0}v).$ ∎

###  3.5 Proof of Lemma 3.11

We shall use the following assertions proven in Section A.

######  Claim (Restatement of Claim 2.9).

Let $H=(V^{\prime},E^{\prime})$ be a $\lambda$-two sided (one-sided) spectral
expander. Let $G=(V,E)$ and let $f:V\to V^{\prime}$ be a non-degenerate
$H$-coloring of $G$. Assume that for every $\\{a,b\\}\in E^{\prime}$ the
bipartite graph between $S_{a},S_{b}$ is $\eta$-bipartite spectral expander
(with respect to the conditional weights
$\frac{\nu_{G}(uv)}{\sum_{u^{\prime}v^{\prime}:f(u^{\prime}v^{\prime})=ab}\nu_{G}(u^{\prime}v^{\prime})}$
for $uv\in S_{a}\times S_{b}$). Then the weighted graph $(G,\nu_{f})$ is a
$\max\\{\lambda,\eta\\}$-two sided (one sided) spectral expander.

######  Proposition 3.15.

Let $G=(V,E)$ be a $\lambda$-two-sided spectral expander over $n$ vertices for
$\lambda\leqslant 0.0001$. Let $r>1$ be so that every edge has weight between
$\frac{1}{r|E|}$ and $\frac{r}{|E|}$. Assume further that every vertex has
weight between $\frac{1}{r|V|}$ and $\frac{r}{|V|}$. Let
$p\in(0,\frac{1}{2})$. Consider the sampling of a random bipartite graph
$H=(A,B,E^{\prime})$ as follows:

  1. 1.

Sample a set $A\subseteq V$ by adding every $v\in V$ to $A$ independently with
probability $p$.

  2. 2.

Sample a set $B\subseteq V\setminus A$ by adding every $v\in V\setminus A$ to
$B$ independently with probability $\frac{p}{1-p}$.

  3. 3.

take the edges of $H$ to be $E^{\prime}=E(A,B)$.

Then $H$ is a $\frac{100}{p^{3}}\lambda$-bipartite spectral expander with
probability $\geqslant 3ne^{-0.2\lambda^{2}p^{2}r^{-2}D}$, where $D$ is the
minimal degree of a vertex in $G$.

######  Lemma 3.16.

Let $p\in(0,1)$. Let $H=(A,B,E)$ be an $n$-vertex bipartite graph so that
every edge has weight between $\frac{1}{r|E|}$ and $\frac{r}{|E|}$ for some
$r>1$. Let $0<\varepsilon<0.05$ and
$0<\lambda<(1-0.25\varepsilon)\varepsilon^{3}p^{3}$. Denote by
$\mu=0.5r^{-2}\varepsilon^{3/2}p^{3/2}(1-0.25\varepsilon)((1-0.25\varepsilon)\varepsilon^{3}p^{3}-\lambda)$.
Let $D\in\mathbb{N}$ so that $\mu D>2\log n+5$.

Assume that $\min_{v\in A\cup B}deg(v)\geqslant D$ and that $H$ is a
$\lambda$-spectral expander. Let $H^{\prime}=(A,B,E^{\prime})$ be a random
subgraph where every edge is sampled in $H^{\prime}$ with probability $p$.

Then with probability at least $1-5n^{2}e^{-\mu D}$, $H^{\prime}$ is a
$260\varepsilon(1+\ln(3/\varepsilon))$-spectral expander.

###### Proof of Lemma 3.11.

Recall that by Claim 3.14 there is a $C_{a}$ coloring of $Y_{\tau}$, $\\\
psi_{\tau}(v)=f(u_{0}v)$.

The probability that $AT(\tau)$ or $AT(\tau\cup\\{v\\})$ occurs for some $v\in
X_{\tau}(0)$ is at most $(|X_{\tau}(0)|+1)m^{d}e^{-0.03m^{-d}(r-1)^{2}c\log
Q}$ (by Claim 3.12). When all these events do not occur, the $C_{a}$ coloring
is non-degenerate; every possible label $s_{i}\in C_{a}$ is given to a vertex
(due to $\neg AT(\tau)$), and for a vertex $v$ labeled $s_{i}$, every possible
edge also appears (due to $\neg AT(\tau\cup\\{v\\}$). Thus we can use Claim
2.9.

By assumption $C_{a}$ is a $\frac{\lambda}{2}$-spectral expander, so we need
to verify that for every edge $s_{i}s_{j}\in C_{a}$, the bipartite subgraph
graph between elements labeled $s_{i}$ and those labeled $s_{j}$ is also an
$\frac{\lambda}{2}$ bipartite expander.

There are at most $m^{2}$ edges in the link of $Cay(\Gamma,S)$. For each edge
$s_{i}s_{j}$, we bound the probability that the induced bipartite subgraph
between $S_{i},S_{j}$ is _not_ a $\frac{\lambda}{2}$-bipartite expander. If we
show that this probability is bounded by
$8m|X_{\tau}(0)|e^{\log|X_{\tau}(0)|-\mu c\log Q}$ then by a union bound over
the $m^{2}$ edge we can conclude. Denote by $s_{i,j}$ the generator so that
$s_{i}s_{i,j}(s_{j})^{-1}=e$.

By Proposition 3.15 the bipartite graph between the $S_{i}$ and the preimage
of $S_{j}$ _in $X_{\tau}$_ is not a $O(\eta/m^{1.5d^{2}})$-expander with
probability $\leqslant 3|X_{\tau}(0)|e^{-0.2\lambda^{2}r^{-2}c\log Q}$. By
Lemma 3.16, whenever the graph between $S_{i},S_{j}$ in _in $X_{\tau}$_ is a
$O(\eta/m^{1.5d^{2}})$-expander, the graph in $Y_{\tau}$ is not a
$\frac{\lambda}{2}$-expander with probability at most
$3|X_{\tau}(0)|^{2}e^{\mu c\log Q-log|X_{\tau}(0)|}$ for some $\mu>0$. Summing
up the probability that the said events mentioned, and taking union bounds
over all $m^{2}$ subgraphs induced by $s_{i}s_{j}$ we get the desired bound. ∎

###  3.6 Proof of Claim 3.10

######  Claim (Restatement of Claim 3.10).

When $\bigcup_{\tau\in X\setminus X(d)}\neg AT(\tau)$ occurs, then

  1. 1.

Let $j\leqslant d-1$ and
$\overset{\to}{\sigma}=(v_{0},v_{1},...,v_{j})\in\overset{\to}{X}(j)$ be some
satisfied face. Let
$\bar{s}=\\{s_{i_{\ell_{1}},i_{\ell_{2}}}\\}_{\ell_{1}\neq\ell_{2}}$ be so
that $s_{i_{\ell_{1}},i_{\ell_{2}}}=f(v_{\ell_{1}}v_{\ell_{2}})$ is the
labeling of the edges of $\sigma$666formally $\bar{s}$ is a function that
receives as input $\ell_{1}\neq\ell_{2}\in\\{0,1,...,j\\}$ and outputs some
$s_{\ell_{1},\ell_{2}}\in S$.. Let
$\hat{\sigma}=(s_{i_{0},i_{1}},s_{i_{0}i_{2}},...,s_{i_{0},i_{j}})$. Then

$r^{-9d}\operatorname*{\mathbb{P}}_{{C_{e}}}\left[\hat{\sigma}\right]\operatorname*{\mathbb{P}}_{{X}}\left[\overset{\to}{\sigma}\left|\;\vphantom{\overset{\to}{\sigma}\bar{s}}\right.\bar{s}\right]\leqslant\operatorname*{\mathbb{P}}_{{Y}}\left[\overset{\to}{\sigma}\right]\leqslant
r^{9d}\operatorname*{\mathbb{P}}_{{C_{e}}}\left[\hat{\sigma}\right]\operatorname*{\mathbb{P}}_{{X}}\left[\overset{\to}{\sigma}\left|\;\vphantom{\overset{\to}{\sigma}\bar{s}}\right.\bar{s}\right],$

where
$\operatorname*{\mathbb{P}}_{{X}}\left[\overset{\to}{\sigma}\left|\;\vphantom{\overset{\to}{\sigma}\bar{s}}\right.\bar{s}\right]$
is the probability of sampling $(u_{0},u_{1},...,u_{j})\in X(j)$ given that we
sampled some $(u_{0}^{\prime},u_{1}^{\prime},...,u_{j}^{\prime})\in X(j)$ so
that its edges are labeled
$f(u_{\ell_{1}}^{\prime}u_{\ell_{2}}^{\prime})=s_{i_{\ell_{1}},i_{\ell_{2}}}$.
We interpret $\operatorname*{\mathbb{P}}_{{C_{e}}}\left[\hat{\sigma}\right]=0$
when $\sigma\notin C_{e}$.

  2. 2.

For every $-1\leqslant j\leqslant d-2$, every $\sigma\in X(j)$ and
$\overset{\to}{uv}\in\overset{\to}{Y}_{\sigma}(1)$ or $w\in Y_{\sigma}(0)$ it
holds that

$r^{-15d}\leqslant\frac{\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[\overset{\to}{uv}\right]}{\operatorname*{\mathbb{P}}_{{G_{\sigma}}}\left[\overset{\to}{uv}\right]}\leqslant
r^{15d}.$
$r^{-15d}\leqslant\frac{\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[w\right]}{\operatorname*{\mathbb{P}}_{{G_{\sigma}}}\left[w\right]}\leqslant
r^{15d}.$

For $\ell\leqslant d$ and
$\bar{s}=(s_{i_{0},i_{1}},s_{i_{0},i_{2}},...,s_{i_{\ell-1},i_{\ell}})$. We
denote by $s_{\leqslant j}$ the tuple restricted to indexes less or equal to
$j$ and $s_{>j}$ to be the rest of the indexes. Let

$T(X,\bar{s})=\left\\{(v_{0},v_{1},...,v_{\ell})\in\overset{\to}{X}(\ell)\left|\;\vphantom{(v_{0},v_{1},...,v_{\ell})\in\overset{\to}{X}(\ell)\forall
j_{1},j_{2}\;\overset{\to}{f}(v_{j_{1}}v_{j_{2}})=s_{j_{1},j_{2}}}\right.\forall
j_{1},j_{2}\;\overset{\to}{f}(v_{j_{1}}v_{j_{2}})=s_{j_{1},j_{2}}\right\\}.$

For a tuple $\bar{u}=(v_{0},v_{1},...,v_{j})$ we also denote by

$T(X,\bar{s},\bar{u})=\left\\{(v_{j+1},v_{j+2},...,v_{\ell})\left|\;\vphantom{(v_{j+1},v_{j+2},...,v_{\ell})(v_{0},v_{1},...,v_{j},v_{j+1},v_{j+2},...,v_{\ell})\in
T(X,\bar{s})}\right.(v_{0},v_{1},...,v_{j},v_{j+1},v_{j+2},...,v_{\ell})\in
T(X,\bar{s})\right\\}.$

Let $\bar{u}\in\overset{\to}{X}(j)$ and let
$\bar{s}=(s_{i_{0},i_{1}},s_{i_{0},i_{2}},...,s_{i_{\ell},i_{\ell+1}})$ be so
that $s_{\leqslant\ell}$ is the edge labeling of $\bar{u}$ (i.e.
$f(u_{j_{1}}u_{j_{2}})=s_{i_{j_{1}},i_{j_{2}}}$). The $\neg AT(\bar{u})$
implies that

$\operatorname*{\mathbb{P}}_{{X_{u}(0)}}\left[T(X,\bar{s},\bar{u})\right]\approx
m^{-(j+1)}.$

The next claim is a generalization of this property.

######  Proposition 3.17.

Let $-1\leqslant\ell,j$ be integers so that $\ell+j\leqslant d-1$. Let
$t=(v_{0},v_{1},...,v_{\ell})\in\overset{\to}{X}(\ell)$ and
$\bar{s}=(s_{i_{0},i_{1}},...,s_{i_{\ell+j},i_{\ell+j+1}})$ so that $t\in
T(X,\bar{s}_{\leqslant\ell})$. Then

$r^{-3d}m^{\binom{\ell+1}{2}-\binom{\ell+j+2}{2}}\leqslant\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{t}(j)}}\left[T(X,\bar{s},t)\right]\leqslant
r^{3d}m^{\binom{\ell+1}{2}-\binom{\ell+j+2}{2}}.$ (3.3)

This proposition says that whenever we condition on a face having some
specific labeling on the edges $\bar{s}$ then this is (approximately)
multiplying by a constant independent of $\bar{s}$.

###### Proof of Claim 3.10.

For a face $\tau=(v_{0},v_{1},...,v_{\ell})\in X(\ell)$ we denote by
$\bar{s}_{\tau}=(s_{i_{0},i_{1}},...,s_{i_{\ell-1},i_{\ell}})$ be so that
$\tau\in T(X,\bar{s}_{\tau})$. We denote by
$\hat{\sigma}=(s_{\tau,i_{0},i_{1}},...,s_{\tau,i_{0},i_{j}})$. When $\tau$ is
satisfied we denote by $s_{\hat{\tau}}=s_{\tau}$; this is well defined since
when $\tau$ is satisfied, $s_{\tau}$ is determined by $\hat{\tau}$ since

$s_{i_{j_{1}},i_{j_{2}}}=f(v_{j_{1}}v_{j_{2}})\overset{satisfaction}{=}f(v_{0}v_{j_{1}})^{-1}f(v_{0}v_{j_{2}})=s_{i_{0}i_{j_{1}}}^{-1}s_{i_{0},i_{j_{2}}}.$

For a tuple $\rho=(u_{0},u_{1},...,u_{j})$ we denote
$\tau\circ\rho=(v_{0},v_{1},...,v_{\ell},u_{0},u_{1},...,u_{j})$ the
concatenation operation.

For the first item, fix some
$\sigma=(v_{0},v_{1},...,v_{j})\in\overset{\to}{X}(j)$ that is a satisfied
face. Recall that by Observation 3.5 $\hat{\sigma}\in C_{e}(j-1)$. The
probability of $\sigma$ is

$\displaystyle\operatorname*{\mathbb{P}}_{{Y}}\left[\sigma\right]$
$\displaystyle=\sum_{\tau\in\overset{\to}{Y}(d),\tau=\sigma\circ\rho}\operatorname*{\mathbb{P}}_{{\overset{\to}{Y}(d)}}\left[\tau\right]=\sum_{\tau\in\overset{\to}{Y}(d),\tau=\sigma\circ\rho}\operatorname*{\mathbb{P}}_{{C}}\left[\hat{\tau}\right]\frac{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(d)}}\left[\tau\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(d)}}\left[T(X,s_{\tau})\right]}$
(3.4)
$\displaystyle=\sum_{\hat{\tau}=\hat{\sigma}\circ\hat{\rho}}\frac{\operatorname*{\mathbb{P}}_{{C}}\left[\hat{\tau}\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(d)}}\left[T(X,s_{\tau})\right]}\sum_{\tau^{\prime}=\sigma\circ\rho,\;s_{\tau^{\prime}}=s_{\hat{\tau}}}\operatorname*{\mathbb{P}}_{{X}}\left[\tau^{\prime}\right]$
$\displaystyle=\sum_{\hat{\tau}=\hat{\sigma}\circ\hat{\rho}}\frac{\operatorname*{\mathbb{P}}_{{C}}\left[\hat{\tau}\right]\cdot\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\right]\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma}(d-\ell-1)}}\left[T(X,s_{\tau},\sigma)\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(d)}}\left[T(X,s_{\tau})\right]}.$

By utilizing Proposition 3.17 on
$\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma}(d-\ell-1)}}\left[T(X,s_{\tau},\sigma)\right]$
and on
$\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(d)}}\left[T(X,s_{\tau})\right]$
we have that

$r^{-6d}m^{\binom{d+1}{2}-\binom{\ell+1}{2}}\cdot\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e}(j)}}\left[\hat{\sigma}\right]\cdot\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\right]\leqslant\operatorname*{\mathbb{P}}_{{Y}}\left[\sigma\right]\leqslant
r^{6d}m^{\binom{d+1}{2}-\binom{\ell+1}{2}}\cdot\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e}(j)}}\left[\hat{\sigma}\right]\cdot\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\right].$
(3.5)

By Proposition 3.17

$r^{-3d}\operatorname*{\mathbb{P}}_{{X}}\left[T(X,s_{\sigma})\right]^{-1}\leqslant
m^{\binom{d+1}{2}-\binom{\ell+1}{2}}\leqslant
r^{3d}\operatorname*{\mathbb{P}}_{{X}}\left[T(X,s_{\sigma})\right]^{-1}.$
(3.6)

We plug (3.6) in (3.5) and use the fact that
$\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\right]\cdot\operatorname*{\mathbb{P}}_{{X}}\left[T(X,s_{\sigma})\right]^{-1}=\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\left|\;\vphantom{\sigma
s_{\sigma}}\right.s_{\sigma}\right]$ to get the first item.

For the second item, we note that for oriented faces
$\sigma\in\overset{\to}{X}(j)$ and $\tau\in\overset{\to}{X}_{\sigma}(\ell)$,
it holds that

$\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[\tau\right]=\frac{\operatorname*{\mathbb{P}}_{{Y}}\left[\sigma\circ\tau\right]}{\operatorname*{\mathbb{P}}_{{Y}}\left[\sigma\right]}\overset{\eqref{eq:bound-
on-prob-of-
face}}{\leqslant}r^{12d}\frac{\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e}}}\left[\widehat{\sigma\circ\tau}\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e}}}\left[\hat{\sigma}\right]}\cdot\frac{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j+\ell+1)}}\left[\tau\circ\sigma\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\right]}m^{\binom{\ell+j+2}{2}-\binom{\ell+1}{2}}\leqslant$
$r^{15d}\frac{\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e}}}\left[\widehat{\sigma\circ\tau}\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e}}}\left[\hat{\sigma}\right]}\cdot\frac{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j+\ell+1)}}\left[\tau\circ\sigma\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(j)}}\left[\sigma\right]\operatorname*{\mathbb{P}}_{{X_{\sigma}}}\left[T(X,s_{\sigma\circ\tau})\right]}\leqslant$
$r^{15d}\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e\cup\hat{\sigma}}}}\left[\hat{\tau}\right]\operatorname*{\mathbb{P}}_{{X_{\sigma}(\ell)}}\left[\tau\left|\;\vphantom{\tau
s_{\tau}}\right.s_{\tau}\right].$

Where the second inequality is because Proposition 3.17 implies that

$r^{-3d}\operatorname*{\mathbb{P}}_{{X_{\sigma}}}\left[T(X,s_{\sigma\circ\tau})\right]^{-1}\leqslant
m^{\binom{\ell+j+2}{2}-\binom{\ell+1}{2}}\leqslant
r^{3d}\operatorname*{\mathbb{P}}_{{X}}\left[T(X,s_{\sigma\circ\tau})\right]^{-1}.$
(3.7)

Thus

$\frac{\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[\tau\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e\cup\hat{\sigma}}}}\left[\hat{\tau}\right]\operatorname*{\mathbb{P}}_{{X_{\sigma}(\ell)}}\left[\tau\left|\;\vphantom{\tau
s_{\tau}}\right.s_{\tau}\right]}\leqslant r^{15d}.$

The symmetric inequalities in the other direction also give us

$\frac{\operatorname*{\mathbb{P}}_{{Y_{\sigma}}}\left[\tau\right]}{\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e\cup\hat{\sigma}}}}\left[\hat{\tau}\right]\operatorname*{\mathbb{P}}_{{X_{\sigma}(\ell)}}\left[\tau\left|\;\vphantom{\tau
s_{\tau}}\right.s_{\tau}\right]}\geqslant r^{-15d}.$

In particular, for $\tau=uv\in\overset{\to}{X}_{\sigma}(1)$ or $\tau=v\in
X_{\sigma}(0)$, we have by the definition of $G_{\sigma}$ that

$\operatorname*{\mathbb{P}}_{{\overset{\to}{C}_{e\cup\hat{\sigma}}}}\left[\hat{\tau}\right]\operatorname*{\mathbb{P}}_{{X_{\sigma}}}\left[\tau\left|\;\vphantom{\tau
s_{\tau}}\right.s_{\tau}\right]=\operatorname*{\mathbb{P}}_{{G_{\sigma}}}\left[\tau\right].$

Thus item 2 holds. ∎

We turn to proving Proposition 3.17. Although the proof is heavy with
notation, the intuitive idea is simple. For every $\ell-1$-face
$\sigma=(v_{0},v_{1},...,v_{\ell-1})$, and every assignment
$(s_{i_{0},i_{\ell}},s_{i_{1},i_{\ell}},...,s_{i_{d-1},i_{\ell}})$ the
fraction of $\ell$-faces $(v_{0},v_{1},...,v_{\ell-1},u)$ so that
$f(v_{j}u)=s_{i_{j},i_{\ell}}$ is approximately $m^{-\ell}$ since $\neg AT$
holds for $\sigma$.

Thus it also holds that for an assignment
$(s_{i_{0},i_{\ell}},s_{i_{1},i_{\ell}},...,s_{i_{d-1},i_{\ell}},s_{i_{0},i_{\ell+1}},s_{i_{1},i_{\ell+1}},...,s_{i_{\ell},i_{\ell+1}})$,
that the fraction of $(\ell+1)$-faces $(v_{0},v_{1},...,v_{\ell-1},u,w)$ so
that $f(v_{j}u)=s_{i_{j},i_{\ell}}$ _and_ $f(v_{j}w)=s_{i_{j},i_{\ell+1}}$ is
a $m^{-(\ell+1)}$-fraction of the $\ell$-faces
$(v_{0},v_{1},...,v_{\ell-1},u)$ so that $f(v_{j}u)=s_{i_{j},i_{\ell}}$ (since
for every fixed $(v_{0},v_{1},...,v_{\ell-1},u)$ $\neg AT$ also holds). This
argument propagates up to the $\ell+k$-faces, faces for every $k$ which is the
content of the proposition.

###### Proof of Proposition 3.17.

Let us first prove the proposition assuming $\ell+j=d-1$, and show the general
case below. Let $\bar{s}$ be a tuple of $\binom{d+1}{2}$ indexes as in the
proposition. Recall that $\bar{s}_{\leqslant\ell}$ be the restriction of
$\bar{s}$ to $s_{j_{1},j_{2}}$ so that $j_{1},j_{2}\leqslant\ell$.

We prove the right-hand inequality (the proof for left-hand inequality is the
same up to flipping the inequalities). We will show by induction on
$k\leqslant j-2$ that

$\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma}(d)}}\left[T(X,\bar{s},\sigma)\right]\leqslant
r^{2(k+1)}m^{\binom{\ell+1}{2}-\binom{\ell+k+2}{2}}\max_{\bar{v}=(v_{0},v_{1},...,v_{k})\in
T(X,s_{\leqslant\ell+k+1})}\;\;\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\bar{v}}(d-\ell-k-1)}}\left[T(X,\bar{s},\sigma\circ\bar{v})\right]$
(3.8)

where we recall that $\sigma\circ\bar{v}$ is concatenation of the two tuples.
Given (3.8) we note that for every $\bar{v}=(v_{0},v_{1},...,v_{d-1})\in
T(X,s_{\leqslant d-1})$, the probability
$\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\bar{v}}(0)}}\left[T(X,\bar{s},\bar{v})\right]$
is at most $r^{2}m^{-d-1}$ by $\neg AT(\bar{v})$ and (3.3) follows (for
$\ell+j=d-1$) .

Indeed, for the base case $k=0$, we note that

$\displaystyle\operatorname*{\mathbb{P}}_{{\overset{\to}{X}(d)}}\left[T(X,\bar{s})\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{{v_{0}\in
X_{\sigma}(0)}}\left[\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ
v_{0}}(d-1)}}\left[T(X,\bar{s},\sigma\circ v_{0})\right]\right]$
$\displaystyle\leqslant r^{2}m^{-(\ell+1)}\max_{v_{0}\in
T(X,\bar{s_{\leqslant\ell+1}},\sigma)}\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{v_{0}}(d-\ell-1)}}\left[T(X,\bar{s},v_{0})\right].$

The inequality is because when $v_{0}\notin
T(X,\bar{s_{\leqslant\ell+1}},\sigma)$ then
$\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ
v_{0}}(d-1)}}\left[T(X,\bar{s},\sigma\circ v_{0})\right]=0$. On the other
hand, $\neg AT(\sigma)$ implies that the fraction of $v\in X_{\sigma}(0)$ so
that the probability of $v\in T(X,\bar{s_{\leqslant\ell+1}},\sigma)$ is
$\leqslant r^{2}m^{-\ell-1}$. We note that when $\ell=-1$ then we can’t use
the assumption about $AT(\emptyset)$, but in this case $m^{-(\ell+1)}=1$ so
the bound still holds.

Assume that (3.8) holds for $k$ and we show it for $k+1$. For any fixed
$\bar{v}=(v_{0},v_{1},...,v_{k})\in\overset{\to}{X}_{\sigma}(k)$, it holds by
$\neg AT(\sigma\circ(v_{0},v_{1},...,v_{\ell}))$ that there are at most
$rm^{-k+\ell+1}$-fraction of $v_{\ell+k+1}\in
X_{\sigma\circ(v_{0},v_{1},...,v_{k})}(0)$ so that
$\overset{\to}{f}(v_{j}v_{\ell+k+1})=s_{i_{j},i_{\ell+k+1}}$. Thus

$\displaystyle\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\bar{v}}(d-\ell-k-1)}}\left[T(X,\bar{s},\sigma\circ\bar{v})\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{{v_{\ell+k+1}\in\overset{\to}{X}_{\bar{v}}(0)}}\left[\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ\bar{v}\circ
v_{\ell+k+1}}(d-\ell-k-2)}}\left[T(X,\bar{s},\sigma\circ\bar{v}\circ
v_{\ell+k+1}))\right]\right]$ (3.9)
$\displaystyle=\operatorname*{\mathbb{P}}_{{v_{\ell+k+1}\in\overset{\to}{X}_{\bar{v}}(0)}}\left[T(X,\bar{s}_{\leqslant\ell+k+2},\bar{v})\right]\cdot$
$\displaystyle\operatorname*{\mathbb{E}}_{{v_{\ell+k+1}\in
T(X,\bar{s}_{\leqslant\ell+k+1},\sigma\circ\bar{v})}}\left[\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ\bar{v}\circ
v_{\ell+k+1})}(d-\ell-k-2)}}\left[T(X,\bar{s},\sigma\circ\bar{v}\circ
v_{\ell+1})\right]\right]$ $\displaystyle\overset{\neg
AT(\bar{v})}{\leqslant}r^{2}m^{-(\ell+k+2)}\operatorname*{\mathbb{E}}_{{v_{\ell+k+1}\in
T(X,\bar{s}_{\leqslant\ell+k+1},\sigma\circ\bar{v})}}\left[\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ\bar{v}\circ
v_{\ell+k+1})}(d-\ell-k-2)}}\left[T(X,\bar{s},\sigma\circ\bar{v}\circ
v_{\ell+1})\right]\right]$ $\displaystyle\leqslant
r^{2}m^{-(\ell+k+2)}\max_{v_{\ell+k+1}\in
T(X,\bar{s}_{\leqslant\ell+k+1},\sigma\circ\bar{v})}\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ\bar{v}\circ
v_{\ell+k+1})}(d-\ell-k-2)}}\left[T(X,\bar{s},\sigma\circ\bar{v}\circ
v_{\ell+1})\right].$

Here the second equality is because whenever $v_{\ell+k+1}\notin
T(X,\bar{s}_{\leqslant\ell+k+2},\bar{v})$ then
$T(X,\bar{s},\sigma\circ\bar{v}\circ v_{\ell+1})=\emptyset$. Plugging this
back in (3.8) and using Pascal’s identity we have that

$\displaystyle\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma}(d)}}\left[T(X,\bar{s},\sigma)\right]$
$\displaystyle\leqslant
r^{2(k+1)}m^{\binom{\ell+1}{2}-\binom{\ell+k+2}{2}}\max_{\bar{v}\in
T(X,s_{\leqslant\ell+k+1})}\;\;\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\bar{v}}(d-\ell-k-1)}}\left[T(X,\bar{s},\sigma\circ\bar{v})\right]$
$\displaystyle\leqslant r^{2(k+2)}\max_{\bar{v}\in T(X,s_{\leqslant
k+1}),v_{\ell+k+1}\in
T(X,\bar{s}_{\leqslant\ell+k+1},\sigma\circ\bar{v})}\operatorname*{\mathbb{P}}_{{\overset{\to}{X}_{\sigma\circ\bar{v}\circ
v_{\ell+k+1})}(d-\ell-k-2)}}\left[T(X,\bar{s},\sigma\circ\bar{v}\circ
v_{\ell+1})\right]$

Note that $\bar{v}\in T(X,s_{\leqslant\ell+k+1})$ and $v_{\ell+1}\in
T(X,\bar{s}_{\leqslant\ell+k+2},\sigma\circ\bar{v})$ if and only if
$\bar{v}\circ v_{\ell+1}\in T(X,\bar{s}_{\leqslant\ell+k+2})$ so the statement
follows.

Finally, we can prove the statement for $\ell+j<d-1$. For $\bar{s}$ of length
$\binom{\ell+j^{\prime}+2}{2}$ let $R$ be the set of all $\bar{s^{\prime}}$ of
length $\binom{d+1}{2}$ so that $s^{\prime}_{\leqslant\ell+j+2}=s$. The size
of $R$ is $m^{\binom{d+1}{2}-\binom{\ell+j^{\prime}+2}{2}}$. Then

$\operatorname*{\mathbb{P}}\left[{T(X,s,\sigma)}\right]=\sum_{s^{\prime}\in
R}\operatorname*{\mathbb{P}}\left[{(X,s^{\prime},\sigma)}\right]\leqslant
m^{\binom{d+1}{2}-\binom{\ell+j^{\prime}+2}{2}}\cdot
r^{3d}m^{\binom{\ell+1}{2}-\binom{d+1}{2}},$

which is what we need to show. The other inequality follows similarly. ∎

###  3.7 Instantiating the construction

##### The groups

As stated in Section 2.7, for every $\lambda>0$ and $d>0$, [LSV05] constructed
infinite groups $\Gamma$ with generating sets $S$ so that the Cayley complex
$Cay(\Gamma,S)$ is has $\lambda$-expanding links. These groups are residually
finite, and thus they have infinite finite indexed subgroups
$N_{1},N_{2},N_{3},...\unlhd\Gamma$. It holds that $S\cap N_{i}=\emptyset$.
Thus for every $f:Y\to S$ obtained by Theorem 3.2, the function
$f_{i}:Y(1)\to\Gamma/N_{i},\;f_{N_{i}}(e)=f(e)N_{i}$ gives rise to a cover
$Y^{f_{i}}$ which is finite.

##### The complexes $X$

  * –

The complete $d$-dimensional complex with $n$ vertices, has all the properties
needed from $X$ in Theorem 3.2 for large enough $n$. We don’t usually think of
the complete complex as being bounded-degree. However, recall that $X$ is a
single complex and the sequence of covers grows to infinity in size.

  * –

The complexes defined by [LSV05] or [KO18] _don’t_ suffice for this theorem
since the weights in their links are not uniform or close to uniform as
required by Theorem 3.2. However, a the work by Friedgut and Iluz [FI20] shows
how to transform some high dimensional expanders to high dimensional expanders
in which the degree is regular in every link, and the weights are uniform.
This work applies to the high dimensional expanders in [KO18].

  * –

By tensoring, we can also satisfy the requirement that the links be _locally
dense_ , i.e. that if the maximal number of $d$-faces covering a vertex $v$ is
$Q$, then every $1$-skeleton of a link has a minimal degree of at least $c\log
Q$ (for a large enough $c$). If the degree in every link is too low, then
instead of $X$ we can take the complex $X^{t}$, which is a tensor product
between $X$ and the complete complex over $t$-vertices. This complex is
explicitly defined as follows:

    1. 1.

$X^{t}(0)=\\{1,2,...,t\\}\times X(0)$.

    2. 2.

$X^{t}(d)=$

$\left\\{\\{(i_{0},v_{0}),(i_{1},v_{1}),(i_{2},v_{2}),...,(i_{d},v_{d})\\}\left|\;\vphantom{\\{(i_{0},v_{0}),(i_{1},v_{1}),(i_{2},v_{2}),...,(i_{d},v_{d})\\}\\{v_{1},...,v_{d}\\}\in
X(d),\;\\{i_{0},i_{1},...,i_{d}\\}\subseteq\\{1,2,...,t\\}\text{ of size
d+1}}\right.\\{v_{1},...,v_{d}\\}\in
X(d),\;\\{i_{0},i_{1},...,i_{d}\\}\subseteq\\{1,2,...,t\\}\text{ of size
d+1}\right\\}.$

That is, the faces are all matchings between sets in $X(d)$ and subsets of
size $d+1$ of the set $\\{1,2,...,t\\}$.

The measure on $d$ faces is by sampling a $d$-face
$\\{v_{0},v_{1},...,v_{d}\\}\in X(d)$, sampling a set of size $d+1$ from
$\\{i_{0},i_{1},...,i_{d}\\}\subseteq\\{1,2,...,d\\}$ uniformly, and then
sampling a matching $\\{(i_{0},v_{0}),.,,,(i_{d},v_{d})\\}$.

######  Claim 3.18.

    1. 1.

$X^{t}$ has $t\cdot|X(0)|$ vertices.

    2. 2.

If the maximal degree (i.e. $d$-faces covering a vertex) in $X$ was $Q$, then
the maximal degree in $X^{t}$ is $d!\binom{t}{d}Q$.

    3. 3.

Let $d-2$-face $\sigma^{\prime}=\\{(i_{0},v_{0}),...,(i_{d-2},v_{d-2})\\}$
where $\\{v_{0},...,v_{d-2}\\}=\sigma\in X(d-2)$. The $1$-skeleton of its link
$X^{t}_{\sigma^{\prime}}$ is the tensor product of the link of $X_{\sigma}$
and the complete graph over $t-(d-1)$ vertices. In particular, if $X_{\sigma}$
was a $\lambda$-spectral expander, then $X^{t}_{\sigma}$ is a
$\lambda$-spectral expander for a large enough $t$.

    4. 4.

If the faces in $X$ had uniform weights, then so do the faces in $X^{t}$.

    5. 5.

The minimal degree in all links grow at least by a multiplicative factor of
$t-(d+1)$. Thus for any $c>$ there is a large enough $t$ so that the minimal
degree of a vertex in a link greater than $c\cdot\max_{v\in
X^{t}(0)}deg_{d}(v)$.

We leave the verification of these statements to the reader.

##  4 Combining two simplicial complexes

In this section we construct a random simplicial complex $Y$ from two given
simplicial complexes $X$ and $C$. The vertices of $Y(0)=X(0)$ but the link of
every face $t\in Y(\ell)$ is homomorphic to a link of a face in $C(\ell)$.
Moreover, when $X,C$ are high dimensional expanders, then $Y$ is a high
dimensional expander as well. The random construction in this section is
similar to the one in Section 3.

######  Theorem 4.1.

Let $m\in\mathbb{N}$ and let $C$ be a $d$-dimensional simplicial complex with
$m$ vertices that is a $\lambda$-high dimensional expander. There exists
universal constants $r=r(m),c=c(m),\eta=\eta(m)$ so that the following holds.
Let $X$ be a $(c,r,\eta)$-suitable $d$-dimensional simplicial complex777as in
Definition 3.1. Then there exists some $Y\subseteq X$ so that $Y$ is an
$d$-dimensional $\frac{2\lambda}{1-2\lambda}$-high dimensional expander, and
so that $Y$ has a _non-degenerate $C$-coloring_. $Y$ contains $\Omega_{m}(1)$
of the faces of $X$. Moreover, there is a randomized algorithm that outputs
$Y$ in expected polynomial time.

######  Remark 4.2.

As in the proof of Theorem 3.2. We show that $Y$ exists using Lovazs Local
Lemma. The randomized algorithm follows directly from the algorithmic version
of this theorem by [MT10]. See Section 2 for more details.

We use the techniques we developed in Section 3. Let $f:X(0)\to C(0)$. We say
a face $s=\\{v_{0},v_{1},...,v_{\ell}\\}\in X(\ell)$ is satisfied by $f$ if
$f(s)=\\{f(v_{0}),f(v_{1}),...,f(v_{\ell})\\}\in C(\ell)$. The $f$-pruning of
$X$ is the simplicial complex $Y$ whose vertices are $Y(0)=X(0)$ and whose
$d$-faces are all $s\in X(d)$ that are satisfied by $f$. By construction
$f:Y(0)\to C(0)$ is a simplicial homomorphism from $Y$ to $C$.

Consider the following random process:

  1. 1.

Sample a function $f:X(0)\to Y(0)$ uniformly at random.

  2. 2.

Let $Y=Y_{f}$ be the $f$-pruning of $X$.

  3. 3.

If $f:Y(0)\to C(0)$ is not a non-degenerate $C$-coloring we output $FAIL$.
Otherwise we output $Y$.

We denote the distribution defined by this process $D(C,X)$.

The measure of $Y$ is the coloring measure defined in Section 2.5. Namely, to
sample a $d$-face $t\in Y(d)$:

  1. 1.

We sample $s\in C(d)$.

  2. 2.

We sample $t\in Y(d)$ given that $f(t)=s$.

In order to prove Theorem 4.1, we show that this process has a positive
probability of sampling a high dimensional-expander $Y$ with the properties
described above via the Lovasz Local Lemma.

###### Proof of Theorem 4.1.

As in the proof of Theorem 3.2 we define the satisfaction graph. For
$\ell\leqslant d-2$ and a satisfied face $\sigma\in X(\ell)$, the
_satisfaction graph_ of $\sigma$, denoted by
$G_{\sigma}=(V_{\sigma},E_{\sigma})$ is the following:

  * –

The vertices are all $v\in X_{\sigma}(0)$ so that $\sigma\mathbin{\mathaccent
0{\cdot}\cup}v$ is satisfied.

  * –

The edges are all $uv\in X_{\sigma}(1)$ so that $uw\mathbin{\mathaccent
0{\cdot}\cup}\sigma$ is satisfied.

The link of $\sigma$ has a $C_{f(\sigma)}$ coloring. When it is non-degenerate
this also induces a measure on $G_{\sigma}$.

We define the following events for faces $\tau\in X$:

  * *

$NE(\tau)$, the event where the $1$-skeleton of $G_{\tau}$ is not a
$\lambda$-spectral expander.

  * *

$AC(\tau)$, for a face $\tau=\\{u_{0},u_{1},...,u_{\ell}\\}\in X(\ell)$, the
event that $\tau$ is satisfied by $f$, colored by
$a=\\{f(u_{0}),...,f(u_{\ell})\\}$ and there is some $b\in C_{a}(0)$ such that
no $u\in X_{\tau}(0)$ is has color $f(u)=b$ (MC stands for “atypical color”).

These events allow us to define
$\left\\{E_{\tau}\left|\;\vphantom{E_{\tau}\tau\in X\setminus
X(d)}\right.\tau\in X\setminus X(d)\right\\}$:

$\displaystyle E_{\tau}=\begin{cases}AC(\tau)&\tau\in X(d-1)\\\ AC(\tau)\cup
NE(\tau)&\tau\in X(j),j\leqslant d-1\\\ \end{cases}.$ (4.1)

Finally let $\mathcal{G}=\bigwedge_{\tau\in X\setminus X(d)}\neg E_{\tau}$. We
claim the following:

######  Claim 4.3.

When $\mathcal{G}$ occurs, then

  1. 1.

$Y$ is an $d$-dimensional $\frac{2\lambda}{1-\lambda}$-high dimensional
expander.

  2. 2.

$Y$ contains $\Omega_{m,d}(1)$ fraction of the faces of $X$.

  3. 3.

$f:Y(0)\to C$ is a non-degenerate $C$-coloring.

######  Claim 4.4.

The event $\mathcal{G}$ occurs with positive probability.

The proof is done given these claims. ∎

###### Proof sketch of Claim 4.3.

  1. 1.

$Y$ is an $d$-dimensional $\frac{2\lambda}{1-2\lambda}$-high dimensional
expander.

Similar to the proof of Theorem 3.2, the fact that $\neg AT(\tau)$ occurs for
all $\tau$ promises us that the $1$-skeletons of all proper links $Y_{\tau}$
are the satisfaction graphs as sets, and that their measure is similar to the
measure induced by the coloring. $NE(\tau)$ promises us that $G_{\tau}$ are
$\lambda$-spectral expanders. Hence (similar to the argument in Theorem 3.2)
it holds that all proper links are $2\lambda$-two sided spectral expanders.

To show that the underlying graph itself in a $\frac{2\lambda}{1-2\lambda}$ we
will use Theorem 2.13. To use it we need to show that the $1$-skeleton of $Y$
itself is connected.

First we note that similar to Theorem 3.2, whenever $\neg AC(\tau)$ holds for
all $\tau$, then a face is in $Y$ if and only if it is satisfied.

To show connectivity it is enough to show that for every edge $vw\in X(1)$
there is a path from $v$ to $w$ in $Y$. If $vw\in Y(1)$ we are done.
Otherwise, this implies (by $\neg AC(vw)$) that $vw$ isn’t satisfied by $f$.
This implies that $d(f(v),f(w))=p>1$. By $\neg AT(vw)$, there is some $u$ so
that $vu\in X(1)$, $vu$ is satisfied by $f$ (i.e. $d(f(v),f(u))=1$ as
$f(u)f(v)\in\overset{\to}{C}(1)$) and $d(f(u),f(w))=p-1$. In addition, $u,w$
are neighbours in $X$. We take $u$ to be the next vertex in our path, and
proceed in this process until we reach a vertex $u^{\prime}$ so that
$d(f(u^{\prime}),f(w))=1$. This vertex is connected to $w$ as required.

  2. 2.

$Y$ contains $\Omega_{m,d}(1)$ fraction of the faces of $X$: this follows
directly from $\neg AC(\tau)$ as in Theorem 3.2.

  3. 3.

$f:Y(0)\to C(0)$ is a non-degenerate $C$-coloring:

We first explain why $f$ is surjective. Let $x\in C(0)$ and let $a=f(v)$ for
an arbitrary vertex $v$. By $\neg AC(v)$ for every neighbour $b\tilde{a}$ in
$C$, there is a neighbour of $u\tilde{v}$ colored by $b$. Thus by taking a
path $(a=r_{0},r_{1},...,r_{k}=x)$ we can inductively find vertices colored by
$r_{1},r_{2},...,r_{k}=x$.

Now for a $d$-face $\\{a_{0},...,a_{d}\\}$ we take a vertex $v_{0}$ so that
$f(v_{0})=a_{0}$. By $\neg AC(v_{0})$, $v_{0}$ has a neighbour $v_{1}\in
X_{v_{0}}(0)$ so that $f(v_{1})=a_{1}$. By $\neg MC(v_{0}v_{1})$, there is a
vertex $v_{2}\in X_{v_{0}v_{1}}(0)$ so that $f(v_{2})=a_{2}$. Note that this
implies that $\\{v_{0},v_{1},v_{2}\\}$ is satisfied by $f$. Continuing this
process shows there is a face $\\{v_{0},v_{1},...,v_{d}\\}\in X(d)$ that is
colored by $f(v_{0})=a_{0},...,f(v_{d})=a_{d}$ as required.

∎

###### Proof of Claim 4.4.

To show that $\mathcal{G}$ has positive probability we use Lovasz Local Lemma
Theorem 2.3.

Similar to the proof of Theorem 3.2, it is easy to verify that for every
$\tau,\tau^{\prime}\in X$, if $E_{\tau},E_{\tau^{\prime}}$ are not
independent, then there is a path of length at-most $2$ from a vertex in
$\tau$ to a vertex in $\tau^{\prime}$.

Thus, denoting $Q$ the maximal $d$-degree of a vertex in $X$, for every
$\tau\in X$, the event $E_{\tau}$ depends only on $K=poly(Q)$ events
$E_{\tau^{\prime}}$ (the polynomial depends on $d$).

If we show that for all $\tau\in X\setminus X(d)$ it holds that

$\operatorname*{\mathbb{P}}\left[{E_{\tau}}\right]<\frac{1}{(K+1)e}$

then by the Lovazs Local Lemma, we will be promised that $\mathcal{G}$ occurs
with some positive probability.

To use Lovazs Local Lemma, we need to upper bound the probabilities of the
events $NE(\tau),AC(\tau)$ by $\frac{1}{2(K+1)e}$. The bounds on
$NE(\tau),AC(\tau)$ are the same as in the proof of Theorem 3.2. We leave the
details for the reader.

The Theorem follows. ∎

##  5 Deramdomizing the constructions

In this section we show that when $X$ has bounded degree then we have
deterministic algorithmic versions for Theorem 3.2 and Theorem 4.1.

To do so, we use the work of Chandrasekaran, Goyal and Haeupler [CGH13] that
gave a derandomization to the for Lovazs Local Lemma’s algorithm. We cite a
less general result than the result in their paper that suits our needs.

######  Theorem 5.1 ([CGH13], Theorem 5).

Let $X_{1},...,X_{p}$ be independent random variables over a finite domain of
size $m$. Let $E_{1},E_{2},...,E_{n}$ be events determined by these random
variables. For every $E_{i}$ we denote by
$A_{i}=\left\\{j\left|\;\vphantom{jE_{i},E_{j}\text{ are not
independent}}\right.E_{i},E_{j}\text{ are not independent}\right\\}$.

  1. 1.

There is some constant $k$ so that for every $i=1,2,...,n$, $|A_{i}|\leqslant
k$.

  2. 2.

Every $E_{n}$ depends on at most $r$ random variables.

  3. 3.

For every partial assignment $\\{X_{i}=s_{i}\\}_{i\in I}$ and every $E_{j}$,
there is an algorithm that runs in time $T$ and calculates
$\operatorname*{\mathbb{P}}\left[E_{j}\left|\;\vphantom{E_{j}\\{X_{i}=s_{i}\\}_{i\in
I}}\right.\\{X_{i}=s_{i}\\}_{i\in I}\right]$.

  4. 4.

There exists some $\varepsilon>0$ so that

$\operatorname*{\mathbb{P}}\left[{E_{i}}\right]\leqslant\left(\frac{1}{e(k+1)}\right)^{1+\varepsilon}.$

Then there exists a deterministic algorithm that finds assignments to
$X_{1},X_{2},...,X_{d}$ so that all the events $E_{1},E_{2},...,E_{n}$ do not
occur. The algorithm runs in time
$O\left(Tm(p+n+r+k)^{3+2/\varepsilon}\varepsilon^{-2}\right)$.

We will use this theorem on simplicial complexes $X$. We will think of
$p,n\leqslant|X|$, $r=O(\log|X|)$, $k=\operatorname{poly}\log|X|$, and $T=\exp
r=O(|X|^{O(\log m)})$. $\varepsilon>0$ will be some constant bounded away from
$0$ and $m$ (the domain of the $X_{i}$’s) will be some large constant. In this
regime of parameters the run time simplifies to $\operatorname{poly}(|X|)$.

Using Theorem 5.1 we can show the following variant of Theorem 3.2.

######  Theorem 5.2 (Derandomization of Theorem 3.2).

For every pair of integers $d,m$ there exists some $c,r>1,\eta>0$ so that the
following holds. Let $\Gamma$ be a group with a generating set $S$ of size
$m$. Assume that $C(\Gamma,S)$ is a $d$-dimensional $\frac{\lambda}{2}$-high
dimensional expander for some $\lambda<1$. Let $X$ be a $(c,r,\eta)$-suitable
$d$-dimensional simplicial complex888as in Definition 3.1.. Then there exists
some $Y\subseteq X$ so that:

  1. 1.

$Y$ is an $d$-dimensional $\lambda$-high dimensional expander.

  2. 2.

$Y$ has a connected $\Gamma$-cover.

  3. 3.

$Y$ contains $\Omega_{m,d}(1)$ fraction of the faces of $X$.

There is a deterministic algorithm that runs in time polynomial in
$O(m^{O(L)}|X|^{O(1)})$ and outputs $Y$, where $L=\max_{v\in X(0)}\lvert
X_{v}\rvert$. The $O$ notation hides some dependence on $d$. In particular,
when $L=O(\log(|X|))$ the algorithm runs in $\operatorname{poly}(|X|)$ time.

###### Proof sketch of Theorem 5.2.

In the proof of Theorem 3.2 we defined every
$\left\\{E_{\tau}\left|\;\vphantom{E_{\tau}\tau\in X}\right.\tau\in
X\right\\}$. Our independent random variables were
$\left\\{f(e)\left|\;\vphantom{f(e)e\in X(1)}\right.e\in X(1)\right\\}$. We
calculate $n,p,m,r,T,k,\varepsilon$ that appear in the statement of Theorem
5.1:

  1. (n)

Obviously $n=\lvert\left\\{E_{\tau}\left|\;\vphantom{E_{\tau}\tau\in
X}\right.\tau\in X\right\\}\rvert=|X|$.

  2. (p)

$p=\lvert\left\\{f(e)\left|\;\vphantom{f(e)e\in X(1)}\right.e\in
X(1)\right\\}\rvert=|X(1)|\leqslant|X|$.

  3. (m)

$m=|S|$ (which was also denoted by $m$ in the theorem statement).

  4. (r)

One can verify by the definition given to $E_{\tau}$, that $E_{\tau}$ only
depend on edges that are contained in some face, which shares a vertex with
$\tau$. Therefore the number of $f(e)$ that $E_{\tau}$ depends on is at most
$\lvert\tau\rvert\binom{d+1}{2}L=O(L)$ (when we think of $d$ as a constant).

  5. (T)

We can calculate the probability
$\operatorname*{\mathbb{P}}\left[E_{\tau}\left|\;\vphantom{E_{\tau}\\{f(e_{i})=s_{i}\\}_{i\in
I}}\right.\\{f(e_{i})=s_{i}\\}_{i\in I}\right]$ by exhaustively going over all
possible assignments the $r$ edges that $E_{\tau}$ depends on, and counting
the fraction of assignments that fall into $E_{\tau}$. Checking whether some
assignment is in $E_{\tau}$ amounts to calculating eigenvalues of an adjacency
operator or counting the number of faces that got assigned some specific
assignment. All possible in $\operatorname{poly}(|X|)$ time. The number of
possible assignments is at most $m^{r}$ (it is an upper bound that since some
values may have already been set by conditioning on some partial assignment).
Hence $T=m^{O(L)}\operatorname{poly}|X|$.

  6. (k)

We saw in the proof of Claim 3.9 that the number of $E_{\tau}^{\prime}$ that
$E_{\tau}$ depends on in $k=\operatorname{poly}(L)$.

  7. ($\varepsilon$)

In the proof of Claim 3.9 we show that
$\operatorname*{\mathbb{P}}\left[{E_{\tau}}\right]\leqslant\frac{1}{(k+1)e}=\frac{1}{\operatorname{poly}(L)}$.
We do so by showing that
$\operatorname*{\mathbb{P}}\left[{E_{\tau}}\right]\leqslant\operatorname{poly}(L,m)\cdot\eta^{c\log
Q}$ where $Q$ is the number of $d+1$-faces that are contained in the link of
$\tau$, and $\eta=\eta_{m,d}<1$ some constant. Then we argue that taking $c$
to be large enough, we can make this less or equal to
$\operatorname*{\mathbb{P}}\left[{E_{\tau}}\right]\leqslant\frac{1}{(k+1)e}$.
But taking a large enough $c$ could also make this less or equal to
$\operatorname*{\mathbb{P}}\left[{E_{\tau}}\right]\leqslant\left(\frac{1}{(k+1)e}\right)^{2}$.
So for an appropriate $c$ we can set $\varepsilon=1$.

Thus by Theorem 5.1, there is a deterministic algorithm that outputs $Y$ as in
the theorem statement in $O(m^{O(L)}|X|^{O(1)})$. ∎

######  Theorem 5.3.

Let $m\in\mathbb{N}$ and let $C$ be a $d$-dimensional simplicial complex with
$m$ vertices that is a $\lambda$-high dimensional expander. There exists
universal constants $r=r(m),c=c(m),\eta=\eta(m)$ so that the following holds.
Let $X$ be a $(c,r,\eta)$-suitable $d$-dimensional simplicial complex999as in
Definition 3.1.. Then there exists some $Y\subseteq X$ so that $Y$ is an
$d$-dimensional $\frac{2\lambda}{1-2\lambda}$-high dimensional expander, and
so that $Y$ has a _non-degenerate $C$-coloring_. $Y$ contains $\Omega_{m}(1)$
of the faces of $X$. Moreover, there is a deterministic algorithm that finds
$Y$ and runs in time $O(|C|^{O(L)}|X|^{O(1)})$, where $L=\max_{v\in
X(0)}\lvert X_{v}\rvert$. In particular, when $L=O(\log(|X|))$ and $|C|=O(1)$
then the algorithm runs in time $\operatorname{poly}(|X|)$.

The proof of Theorem 5.3 follows the same calculation of parameters and is
therefore omitted.

## References

  * [Gar73] Howard Garland  “$p$-Adic Curvature and the Cohomology of Discrete Subgroups of $p$-Adic Groups”  In _Ann. of Math._ 97.3, 1973, pp. 375–423  DOI: 10.2307/1970829
  * [EL74] Paul Erdős and Lovász László  “Problems and results on 3-chromatic Hypergraphs and some related questions”  In _Coll Math Soc J Bolyai_ 10, 1974
  * [FK81] Z. Furedi and J. Komlos  “The eigenvalues of random symmetric matrices”  In _Combinatorica_ 1, 1981, pp. 233–241  DOI: 10.1007/BF02579329
  * [Sur84] David Surowski  “Covers of simplicial complexes and applications to geometry”  In _Geometriae Dedicata_ 16, 1984, pp. 35–62  DOI: 10.1007/BF00147420
  * [Ami+01] Alon Amit, Nathan Linial, Jirí Matousek and Eyal Rozenman  “Random lifts of graphs”  In _Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2001, pp. 883–894  DOI: 10.1145/365411.365801
  * [AL02] Alon Amit and Nathan Linial  “Random Graph Coverings I: General Theory and Graph Connectivity”  In _Combinatorica_ 22, 2002, pp. 1–18  DOI: 10.1007/s004930200000
  * [Fri03] Joel Friedman  “Relative expanders or weakly relatively Ramanujan graphs”  In _Duke Mathematical Journal_ 118.1 Duke University Press, 2003, pp. 19–35  DOI: 10.1215/S0012-7094-03-11812-8
  * [Gro03] M. Gromov  “Random walk in random groups”  In _Geom. Funct. Anal._ 13, 2003, pp. 73–146  DOI: 10.1007/s000390300002
  * [Zuk03] A. Zuk  “Property (T) and Kazhdan constants for discrete groups”  In _Geom. Funct. Anal._ 13, 2003, pp. 643–670
  * [LSV05] Alexander Lubotzky, Beth Samuels and Uzi Vishne  “Explicit constructions of Ramanujan complexes of type $\tilde{A_{d}}$”  In _European J. Combin._ 26.6, 2005, pp. 965–993  DOI: 10.1016/j.ejc.2004.06.007
  * [LSV05a] Alexander Lubotzky, Beth Samuels and Uzi Vishne  “Ramanujan complexes of type $\tilde{A_{d}}$”  In _Israel J. Math._ 149.1, 2005, pp. 267–299  DOI: 10.1007/BF02772543
  * [BL06] Yehonatan Bilu and Nathan Linial  “Lifts, Discrepancy and Nearly Optimal Spectral Gap”  In _Combinatorica_ , 2006  DOI: https://doi.org/10.1007/s00493-006-0029-7
  * [Din06] Irit Dinur  “The PCP theorem by gap amplification”  In _Proc. 38th ACM Symp. on Theory of Computing_ , 2006, pp. 241–250
  * [HLW06] Shlomo Hoory, Nathan Linial and Avi Wigderson  “Expander Graphs and Their Applications”  In _Bull. Amer. Math. Soc._ 43.04 American Mathematical Society (AMS), 2006, pp. 439–562  DOI: 10.1090/s0273-0979-06-01126-8
  * [LM06] Nathan Linial and Roy Meshulam  “Homological Connectivity Of Random 2-Complexes”  In _Combinatorica_ 26, 2006, pp. 475–487  DOI: 10.1007/s00493-006-0027-9
  * [Vu07] Van H. Vu  “Spectral norm of random matrices”  In _Combinatorica_ 27, 2007, pp. 721–736  DOI: 10.1007/s00493-007-2190-z
  * [SS08] Daniel A. Spielman and Nikhil Srivastava  “Graph sparsification by effective resistances”  In _Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008_ ACM, 2008, pp. 563–568  DOI: 10.1145/1374376.1374456
  * [MW09] Roy Meshulam and N. Wallach  “Homological connectivity of random _k_ -dimensional complexes”  In _Random Struct. Algorithms_ 34.3, 2009, pp. 408–417  DOI: 10.1002/rsa.20238
  * [Gro10] M. Gromov  “Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry”  In _Geom. Funct. Anal._ 20, 2010, pp. 416–526  DOI: 10.1007/s00039-010-0073-8
  * [MT10] Robin A. Moser and Gábor Tardos  “A Constructive Proof of the General LováSz Local Lemma”  In _J. ACM_ , 2010  DOI: 10.1145/1667053.1667060
  * [ST11] Daniel A. Spielman and Shang-Hua Teng  “Spectral Sparsification of Graphs”  In _SIAM Journal on Computing_ 40.4, 2011, pp. 981–1025  DOI: 10.1137/08074489X
  * [CGH13] Karthekeyan Chandrasekaran, Navin Goyal and Bernhard Haeupler  “Deterministic Algorithms for the Lovász Local Lemma”  In _SIAM Journal on Computing_ 42.6, 2013, pp. 2132–2155  DOI: 10.1137/100799642
  * [KKL14] Tali Kaufman, David Kazhdan and Alexander Lubotzky  “Ramanujan Complexes and Bounded Degree Topological Expanders”  In _Proc. $55$th IEEE Symp. on Foundations of Comp. Science (FOCS)_, 2014, pp. 484–493  DOI: 10.1109/FOCS.2014.58
  * [MSS15] Adam W. Marcus, Daniel A. Spielman and Nikhil Srivastava  “Interlacing families I: Bipartite Ramanujan graphs of all degrees”  In _Annals of Mathematics_ 182, 2015, pp. 307–325  DOI: 10.4007/annals.2015.182.1.7
  * [Pud15] Doron Puder  “Expansion of random graphs: new proofs, new results”  In _Invent. math._ , 2015  DOI: 10.1007/s00222-014-0560-x
  * [EK16] Shai Evra and Tali Kaufman  “Bounded degree cosystolic expanders of every dimension”  In _Proc. $48$th ACM Symp. on Theory of Computing (STOC)_, 2016, pp. 36–48  DOI: 10.1145/2897518.2897543
  * [DK17] Irit Dinur and Tali Kaufman  “High dimensional expanders imply agreement expanders”  In _Proc. $58$th IEEE Symp. on Foundations of Comp. Science (FOCS)_, 2017, pp. 974–985  DOI: 10.1109/FOCS.2017.94
  * [LS17] Yin Tat Lee and He Sun  “An SDP-based algorithm for linear-sized spectral sparsification”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017_ ACM, 2017, pp. 678–687  DOI: 10.1145/3055399.3055477
  * [Lub17] Alexander Lubotzky  “High Dimensional Expanders”  In _Proceedings of the International Congress of Mathematicians (ICM 2018)_ , 2017, pp. 705–730  DOI: 10.1142/9789813272880_0027
  * [Dik+18] Yotam Dikstein, Irit Dinur, Yuval Filmus and Prahladh Harsha  “Boolean function analysis on high-dimensional expanders”  In _Proc. $20$th International Workshop on Randomization and Computation (RANDOM)_ 116, 2018  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2018.37
  * [JS18] Arun Jambulapati and Aaron Sidford  “Efficient _Õ_(_n_ /_$\varepsilon$_) Spectral Sketches for the Laplacian and its Pseudoinverse”  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018_ SIAM, 2018, pp. 2487–2503  DOI: 10.1137/1.9781611975031.159
  * [KO18] 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_ , STOC 2018  Los Angeles, CA, USA: Association for Computing Machinery, 2018, pp. 773–786  DOI: 10.1145/3188745.3188782
  * [Opp18] Izhar Oppenheim  “Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps”  In _Discrete Comput. Geom._ 59.2, 2018, pp. 293–330  DOI: 10.1007/s00454-017-9948-x
  * [AJT19] 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_ , 2019, pp. 180–201  DOI: 10.1109/FOCS.2019.00021
  * [Ana+19] 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”  New York, NY, USA: Association for Computing Machinery, 2019  DOI: 10.1145/3313276.3316385
  * [DD19] 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
  * [DM19] Irit Dinur and Roy Meshulam  “Near Coverings and Cosystolic Expansion – an example of topological property testing”, 2019  eprint: arXiv:1909.08507
  * [CLY20] Michael Chapman, Nathan Linial and Peled Yuval  “Expander Graphs — Both Local and Global”  In _Combinatorica_ 40, 2020, pp. 473–509  DOI: 10.1007/s00493-019-4127-8
  * [FI20] Ehud Friedgut and Yonatan Iluz  “Hyper-regular graphs and high dimensional expanders”, 2020  eprint: arXiv:2010.03829
  * [LXX20] Ming-Jun Lai, Jiaxin Xie and Zhiqiang Xu  “Graph Sparsification by Universal Greedy Algorithms”, 2020  URL: https://arxiv.org/abs/2007.07161
  * [LMY20] Siqi Liu, Sidhanth Mohanty and Elizabeth Yang  “High-Dimensional Expanders from Expanders”  In _11th Innovations in Theoretical Computer Science Conference (ITCS 2020)_ 151, Leibniz International Proceedings in Informatics (LIPIcs), 2020, pp. 12:1–12:32  DOI: 10.4230/LIPIcs.ITCS.2020.12
  * [CLV21] Zongchen Chen, Kuikui Liu and Eric Vigoda  “Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ Association for Computing Machinery, 2021, pp. 1537–1550  URL: https://doi.org/10.1145/3406325.3451035
  * [Gol21] Louis Golowich  “Improved Product-Based High-Dimensional Expanders”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)_ 207, 2021  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.38
  * [KO21] 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)_ 198, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 84:1–84:16  DOI: 10.4230/LIPIcs.ICALP.2021.84
  * [OP22] Ryan O’Donnell and Kevin Pratt  “High-Dimensional Expanders from Chevalley Groups”  In _37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA_ 234, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 18:1–18:26  DOI: 10.4230/LIPIcs.CCC.2022.18

##  Appendix A Sparsification of expander graphs

In this section, we prove the necessary results we need in order to analyze
the edge removal process in the links and prove Lemma 3.11.

###  A.1 Proof of Claim 2.9

Recall that for measured graphs
$G=(V,E,\nu_{G}),H=(V^{\prime},E^{\prime},\nu_{H})$ and a non-degenerate
$H$-coloring $f:V\to V^{\prime}$ of $G$, we defined the measure $\nu_{f}(vu)$
on the edges of $G$ by the following process:

  1. 1.

Sample an edge $ab\in E^{\prime}$.

  2. 2.

Sample an edge $uv\in E$ given that $f(u)=a,f(v)=b$.

######  Claim (Restatement of Claim 2.9).

Let $H=(V^{\prime},E^{\prime})$ be a $\lambda$-two sided (one-sided) spectral
expander. Let $G=(V,E)$ and let $f:V\to V^{\prime}$ be a non-degenerate
$H$-coloring of $G$. Assume that for every $\\{a,b\\}\in E^{\prime}$ the
bipartite graph between $S_{a},S_{b}$ is $\eta$-bipartite spectral expander
(with respect to the conditional weights
$\frac{\nu_{G}(uv)}{\sum_{u^{\prime}v^{\prime}:f(u^{\prime}v^{\prime})=ab}\nu_{G}(u^{\prime}v^{\prime})}$
for $uv\in S_{a}\times S_{b}$). Then the weighted graph $(G,\nu_{f})$ is a
$\max\\{\lambda,\eta\\}$-two sided (one sided) spectral expander.

###### Proof of Claim 2.9.

We prove the claim with respect to two sided expansion (i.e. we assume that
$H$ is a two-sided spectral expander, and show that $G$ is a two sided
spectral expander). We comment about adjusting the proof to one sided spectral
expanders at the end of the proof.

Let $A$ be the normalized adjacency operator of $G$ with respect to $\nu_{f}$.
Let $g,f\bot{\mathbf{1}}$ be any two functions with norm $1$. We need to show
that

$\langle Af,g\rangle\leqslant\max\\{\lambda,\eta\\}.$ (A.1)

Let

$W_{C}=\left\\{h:V\to\mathbb{R}\left|\;\vphantom{h:V\to\mathbb{R}\forall v\in
V^{\prime},u\in A_{v},h(v)=h(u)}\right.\forall v\in V^{\prime},u\in
A_{v},h(v)=h(u)\right\\}.$
$W_{0}=\left\\{h:V\to\mathbb{R}\left|\;\vphantom{h:V\to\mathbb{R}\forall v\in
V^{\prime},\operatorname*{\mathbb{E}}_{{u\in
A_{v}}}\left[h(u)\right]=0}\right.\forall v\in
V^{\prime},\operatorname*{\mathbb{E}}_{{u\in
A_{v}}}\left[h(u)\right]=0\right\\}.$

We note that $W_{C}\oplus W_{0}$ is an orthogonal decomposition of $L_{2}(V)$.
Furthermore, $A(W_{C})\subseteq W_{C},A(W_{0})\subseteq W_{0}$. Thus we can