# Expanderizing Higher Order Random Walks

Vedat Levi Alev Hebrew University of Jerusalem –<EMAIL_ADDRESS>Shravas Rao Portland State University –<EMAIL_ADDRESS>
We study a variant of the down-up (also known as the Glauber dynamics) and up-
down walks over an $n$-partite simplicial complex, which we call _expanderized
higher order random walks_ – where the sequence of updated coordinates
correspond to the sequence of vertices visited by a random walk over an
auxiliary expander graph $H$. When $H$ is the clique with self loops on $[n]$,
this random walk reduces to the usual down-up walk and when $H$ is the
directed cycle on $[n]$, this random walk reduces to the well-known systematic
scan Glauber dynamics. We show that whenever the usual higher order random
walks satisfy a log-Sobolev inequality or a Poincaré inequality, the
expanderized walks satisfy the same inequalities with a loss of quality
related to the two-sided expansion of the auxillary graph $H$. Our
construction can be thought as a higher order random walk generalization of
the derandomized squaring algorithm of Rozenman and Vadhan (RANDOM 2005).

We study the mixing times of our expanderized walks in two example cases: We
show that when initiated with an expander graph our expanderized random walks
have mixing time (i) $O(n\log n)$ for sampling a uniformly random list
colorings of a graph $G$ of maximum degree $\Delta=O(1)$ where each vertex has
at least $(11/6-\ee)\Delta$ and at most $O(\Delta)$ colors, (ii)
$O_{\etch}\parens*{\frac{n\log n}{(1-\norm*{\Jay}_{\opp})^{2}}}$ for sampling
the Ising model with a PSD interaction matrix $\Jay\in\RR^{n\times n}$
satisfying $\norm{\Jay}_{\opp}\leq 1$ and the external field
$\etch\in\RR^{n}$– here the $O(\bullet)$ notation hides a constant that
depends linearly on the largest entry of $\etch$. As expander graphs can be
very sparse, this decreases the amount of randomness required to simulate the
down-up walks by a logarithmic factor.

We also prove some simple results which enable us to argue about log-Sobolev
constants of higher order random walks and provide a simple and self-contained
analysis of local-to-global $\Phi$-entropy contraction in simplicial complexes
– giving simpler proofs for many pre-existing results.

##  1 Introduction

###  1.1 Higher Order Random Walks, Systematic Scan, and Expanderized Walks

111All concepts and random walks we define in this introductory section of the
paper, will be formally defined in Section 2 and Section 3

Let $U_{1},\cdots,U_{n}$ be a collection of finite sets. The _down-up walk
$\Duw$_ on $\Omega\subset U_{1}\times\cdots U_{n}$ with respect to a given
distribution $\pi:\Omega\to\RRp$, also known as the _Glauber dynamics_ on
$\Omega$ according to $\pi$, is the following simple process: Starting from an
arbitrary tuple $\omega^{(0)}$, we obtain the $(t+1)$-st tuple
$\omega^{(t+1)}$ visited by this random walk from the $t$-th tuple
$\omega^{(t)}$ as follows,
0.85 Update Rule for the Down-Up Walk, $\Duw$

  1. 1.

sample a uniformly random coordinate $i\sim\uni_{[n]}$,

  2. 2.

sample a random tuple $\omega^{(t+1)}\sim\pi$ conditional on
$\omega^{(t+1)}_{j}=\omega^{(t)}_{j}$ for all $j\in[n]\setminus\set i$.

The following variant of the down-up walk, called the _systematic scan $\Psc$_
on $\Omega$ according to $\pi$, is a variant of the down-up walk $\Duw$ which
uses less randomness and is easier to implement in practice: starting from an
arbitrary tuple $\omega^{(0)}$, we obtain the $(t+1)$-st tuple
$\omega^{(t+1)}$ visited by this random walk from the $t$-th tuple
$\omega^{(t)}$ as follows, 0.85Update Rule for the Systematic Scan, $\Psc$

  1. 1.

set $i=t+1\pmod{n}$,

  2. 2.

sample a random tuple $\omega^{(t+1)}\sim\pi$ conditional on
$\omega^{(t+1)}_{j}=\omega^{(t)}_{j}$ for all $j\in[n]\setminus\set i$.

In both cases, the coordinate $i$ that is sampled on the first step of the
update can be thought as a vertex visited by the simple random walk on a
graph. For the down-up walk, this is a random walk on the clique with self-
loops, whereas for the systematic scan this is a (deterministic) walk on the
directed cycle.

The main object of study in this paper will be the so-called _expanderized
down-up walk_ $\Paqx$ on $\Omega$ with respect to the distribution
$\pi:\Omega\to\RRpp$ and the $k$-regular graph $H=([n],E)$ for some constant
$k$. Starting this random-walk from an arbitrary coordinate $i^{(0)}\in[n]$
and an arbitrary tuple $\omega^{(0)}$, we obtain the $(t+1)$-st coordinate
$i^{(t+1)}$ and tuple $\omega^{(t+1)}$ according to the following update rule,
0.9 Update Rule for the Expanderized Down-Up Walk $\Paqx$

  1. 1.

sample a random neighbor $s$ of $i^{(t)}$ in $H$,

  2. 2.

sample a random tuple $\omega^{(t+1)}\sim\pi$ conditional on
$\omega^{(t+1)}_{j}=\omega^{(t)}_{j}$ for all $j\in[n]\setminus\set s$,

  3. 3.

set $i^{(t+1)}$ to be a random neighbor of $s$ in $H$.

We notice that according to the above update rule when $i^{(0)}$ is sampled
uniformly at random and $H$ equals the clique with self-loops on $[n]$ the
evolution of $\omega^{(t)}$ is as dictated by the down-up walk $\Duw$.
Similarly, when $i^{(0)}=1$ and $H$ is the directed cycle, the evolution of
$\omega^{(t)}$ is as dictated by the systematic scan $\Psc$.

The main contribution of this paper is an analysis of the expanderized down-up
walk assuming, (i) the graph $H$ is a spectral expander222i.e. all non-trivial
eigenvalues of $H$ are bounded away from 1 and (ii) the down-up walk $\Duw$
satisfies some kind of isoperimetric inequality, e.g. a log-Sobolev inequality
or a Poincaré inequality. Indeed our methods allow us to extend our results to
all down-up and up-down walks.

###  1.2 Motivation: Systematic Scan, Expander Graphs, and Derandomized
Squaring

The systematic scan $\Psc$ is a random walk of great practical and theoretical
interest. Yet, rapid mixing results for this walk are only known under
restricted circumstances [DR00, Hay06, DGJ06, DGJ08, RR15, FGW+23] and it is
very hard to directly relate the rapid mixing of $\Duw$ to that of $\Psc$. A
particularly useful framework for establishing rapid mixing for the down-up
walk is the method of high-dimensional expansion, in particular the frameworks
of spectral independence and entropic independence [AL20, ALO20, CLV20, CLV21,
CE22, AJK+22, AJK+21, AJK+23] which led to many breakthrough results in the
field of sampling algorithms.

In [AP23], an attempt was made to study the mixing of the systematic
scan333More formally, $n$ successive steps of the systematic scan, which the
authors call the _sequential sweep_ $\Psq$. using techniques of high-
dimensional expansion – while their techniques allowed them to establish rapid
mixing results for constant dimensional partite simplicial complexes, their
result is too restrictive to take advantage of mixing results obtained through
spectral independence or entropic independence. As a step towards directly
being able to take advantage of the mixing results for $\Duw$, which could
potentially be obtained through the high-dimensional expansion framework, we
introduce our expanderized down-up walks $\Paqx$. As expander graphs have
proven themselves very successful at approximating dense objects, we hope –
and indeed also prove – that transfering mixing time bounds from the usual
down-up walks to our expanderized walks to be an easier task than establishing
mixing times for $\Psc$. As expander graphs can be very sparse, our
expanderized walks can be thought as replacing the sparse object used in the
definition of the systematic scan $\Psc$, i.e. the directed cycle, with
another sparse yet highly connected object – an expander graph with constant
degree.

In spirit, the expanderized walks can be thought as a higher order random walk
analogue of the derandomized squaring algorithm introduced in [RV05]. This
algorithm was introduced to simplify the seminal result of [Rei08] concerning
the existence of a logspace algorithm for deciding undirected connectivity.
The derandomized squaring operation uses an auxiliary $k$-regular expander
graph $H$ on the vertex set $[d]$ to approximate the square of a graph
$d$-regular graph $G$ on $[n]$. Whereas the actual square $G^{2}$ is a
$d^{2}$-regular graph, by picking $k=O(1)$ one can ensure that the
_derandomized square_ is $O(d)$-regular, i.e. a much sparser object. This
result rests on the observation that the actual square $G^{2}$ is obtained
from the graph $G$ by attaching a clique to every vertex – replacing this
clique with an expander graph suffices to ensure that the resulting
_derandomized square_ is closed to the actual square. Fortunately, the same
intuition also leads to proofs showing that the expanderized walks approximate
the standard walks well.

###  1.3 Our Results

#### Expanderized Walks

Our main contribution in this paper is the study and analysis of expanderized
higher order random walks. Since throughout the paper we use the language of
simplicial complexes, we recall some basics: A simplicial complex $X$ is a
downward closed collection of subsets of some finite set $U$. We write
$X^{(j)}$ to denote the subsets in $X$ of size $j$ – we call the cardinality
of the largest element in $X$ the rank of $X$ and elements of $X$ its faces.
We call $(X,\pi)$ a weighted simplicial complex of rank $n$, where
$\pi:X^{(n)}\to\RRpp$ is a probability distribution on $X^{(n)}$. Throughout,
we will assume that $X$ is obtained by taking the downward closure of some
collection of interest, i.e. we have $X^{(n)}=\Omega$ where $\Omega$ is a
collection of $n$-elemented sets and $X^{(j)}$ is the collection of
$j$-elemented subsets which are contained in $\omega\in\Omega$ for all
$j=0,\ldots,n-1$. We will say $X$ is an $n$-partite simplicial complex, if it
is of rank $n$ and there exists some finite sets $U_{1},\ldots,U_{n}$ such
that $X^{(n)}$ can be identified with a subset of $U_{1}\times\cdots\times
U_{n}$. For example by, identifying the tuple $(u_{1},\ldots,u_{n})$ with the
set $\set*{(1,u_{1}),\ldots,(n,u_{n})}$. The sets $U_{1},\ldots,U_{n}$ are
called the sides of the simplicial complex. For $\omega\in X^{(n)}$ and
$S\subset[n]$, we will write $\omega_{S}$ for the restriction of $\omega$ to
the coordinates in $S$, i.e. if $\omega=(u_{1},\ldots,u_{n})$ we identify
$\omega_{S}$ with the set $\set*{(s,u_{s})\mid s\in S}$. For now, we will
restrict our attention to partite simplicial complexes. In particular, every
element in $\widehat{\omega}\in X^{(\ell)}$ in a partite simplicial complex
can be obtained from a face $\omega\in X^{(n)}$ and some
$S\in\binom{[n]}{\ell}$, by setting $\widehat{\omega}=\omega_{S}$. Whereas the
choice of $\omega$ is not unique, the choice of $S$ is. For
$\widehat{\omega}\in X^{(<n)}$ we denote this unique choice by
$\typ(\widehat{\omega})$.

We now recall the following random walks between $X^{(n)}$ and $X^{(\ell)}$.
The first random walk is the so-called down-up walk $\Duw_{n\lra\ell}$, which
is also known as the Glauber dynamics with block size $(n-\ell)$. Starting
from an arbitrary face $\omega^{(0)}\in X^{(n)}$, we obtain the $t$-th face
$\omega^{(t)}\in X^{(n)}$ that we visit, from the $(t-1)$-st face
$\omega^{(t-1)}$ according to the following update rule, 0.85 Update Rule for
the Down-Up Walk According to $\pi$, $\Duw_{n\lra\ell}$

  1. 1.

sample a uniformly random set of coordinates $S\sim\uni_{\binom{[n]}{\ell}}$,

  2. 2.

sample a random tuple $\omega^{(t+1)}\sim\pi$ conditional on
$\omega^{(t+1)}_{S}=\omega^{(t)}_{S}$.

We notice that for $\ell=n-1$, this is the same walk we have defined in the
preceding section.

We also recall the up-down walk $\Udw_{\ell\lra n}$ between $X^{(\ell)}$ and
$X^{(n)}$ (according to $\pi$) – where $(X,\pi)$ is a partite simplicial
complex. This is the random walk that starts from an arbitrary face
$\widehat{\omega}^{(0)}\in X^{(\ell)}$, and determines the $t$-th face
$\widehat{\omega}^{(t)}$ visited by this random walk using the $(t-1)$-st face
$\widehat{\omega}^{(t-1)}$ according to the following update rule, 0.85 Update
Rule for the Up-Down Walk According to $\pi$, $\Duw_{\ell\lra n}$

  1. 1.

sample a random face $\omega\sim\pi$ conditional on containing
$\widehat{\omega}^{(t-1)}$,

  2. 2.

sample a uniformly random set $S\sim\uni_{\binom{[n]}{\ell}}$,

  3. 3.

output $\widehat{\omega}^{(t)}=\omega_{S}$.

Given a degree regular graph $H$ on the vertex set $\binom{[n]}{\ell}$, we
define the expanderized up-down walk between $X^{(\ell)}$ and $X^{(n)}$ (via
$H$ according to $\pi$), as a random walk which starts from an arbitrary face
$\widehat{\omega}^{(0)}\in X^{(\ell)}$ and picks the $t$-th face visited
$\widehat{\omega}^{(t)}$ by this random walk using the $(t-1)$-st face
$\widehat{\omega}^{(t-1)}$ according to the following update rule, 0.85 Update
Rule for the Expanderized Up-Down Walk via $H$ according to $\pi$,
$\Papx_{\ell\lra n}$

  1. 1.

sample a random face $\omega\sim\pi$ conditional on containing
$\widehat{\omega}^{(t-1)}$,

  2. 2.

sample a random neighbor $S$ of $\typ(\widehat{\omega}^{(t-1)})$ in $H$,

  3. 3.

output $\widehat{\omega}^{(t)}=\omega_{S}$.

Finally, we define the expanderized down-up walk $\Paqx_{n\lra\ell}$ between
$X^{(n)}$ and $X^{(\ell)}$ according to $\pi$ as the following random walk on
$X^{(n)}\times\binom{[n]}{\ell}$, starting from an arbitrary pair
$(\omega^{(0)},S^{(0)})\in X^{(n)}\times\binom{[n]}{\ell}$, this walk picks
the $t$-th pair visited by this random walk as follows, 0.9 Update Rule for
the Expanderized Down-Up Walk $\Paqx_{n\lra\ell}$

  1. 1.

sample a random neighbor $T$ of $S^{(t-1)}$ in $H$,

  2. 2.

sample a random tuple $\omega^{(t)}\sim\pi$ conditional on
$\omega^{(t)}_{T}=\omega^{(t-1)}_{T}$,

  3. 3.

set $S^{(t)}$ to be a random neighbor of $T$ in $H$.

######  Remark 1.1.

Once the expanderized down-up walk reaches stationarity, the face component
will be distributed according to $\pi$. Similarly, once the expanderized up-
down walk reaches stationarity, it will be distributed according to the
correct marginal distribution of $\pi$. Both random walks are reversible.

We also recall that the spectral gap $\Gap(\Pii)$ of a reversible random walk
matrix $\Pii\in\RR^{\Omega\times\Omega}$ is defined to be,

$\Gap(\Pii)=1-\lambda(\Pii),$

where $\lambda(\Pii)$ denotes the two-sided expansion expansion of $\Pii$,
i.e. $\lambda(\Pii)=\max\set*{\lambda_{2}(\Pii),|\lambda_{\min}(\Pii)|}$.444In
the main body of the paper we will adopt the convention
$\Gap(\Pii)=1-\lambda_{2}(\Pii)$, but to keep our exposition simple we will
work with the two-sided expansion parameter $\lambda(\Pii)$ throughout the
introduction.

It is well known that a bound on the spectral gap translates into a bound on
the mixing time of the random walk $\Pii$. The following bound is well known,
cf. [MT05, Proposition 1.12]

######  Theorem 1.2.

Let $\Pii\in\RR^{\Omega\times\Omega}$ be a reversible random walk matrix with
stationary distribution $\pi:\Omega\to\RRpp$, i.e. $\pi\Pii=\pi$. We have,

$\Tmix(\Pii,\ee)\leq\frac{1}{1-\lambda(\Pii)}\cdot\log\frac{1}{\ee\cdot\sqrt{\min_{\omega\in\Omega}\pi(\omega)}}.$

We now describe our results concerning expanderized random walks, which we
will be proven in Section 3.

######  Theorem 1.3 (Simplified Version of Corollary 3.7).

Let $(X,\pi)$ be an $n$-partite simplicial complex and $H$ a degree regular
graph on the vertex set $\binom{[n]}{\ell}$ where $0\leq\ell\leq n$. Writing
$\Duw_{n\lra\ell}$ and $\Udw_{\ell\lra n}$ for the down-up walk and up-down
walks between $X^{(\ell)}$ and $X^{(n)}$ according to $\pi$, and
$\Papx_{\ell\lra n}$ for the expanderized up-down walk via $H^{\prime}=H^{2}$
and $\Paqx_{n\lra\ell}$ for the expanderized down-up walk via $H$, we have

$\Gap\parens*{\Paqx_{n\lra\ell}}\geq\Gap\parens*{\Duw_{n\lra\ell}}\cdot\Gap(H^{2})~{}~{}\textrm{and}~{}~{}\Gap\parens*{\Papx_{\ell\lra
n}}\geq\Gap\parens*{\Udw_{\ell\lra n}}\cdot\Gap(H).$

######  Remark 1.4.

We note that the difference in the dependence on $\Gap(H)$ between the bounds
of $\Gap\parens*{\Paqx_{n\lra\ell}}$ and $\Gap\parens*{\Papx_{\ell\lra n}}$ is
an artifact of the update rule of the two walks, which we have chosen to
ensure that the down- and up-movements of the expanderized walks to be
adjoints of each other. In particular, in the expanderized down-up walk a
sequence of two random vertices in $H$ is sampled, while in the expanderized
up-down only one vertex is sampled.

Similarly, we recall that the entropy functional $\Ent_{\pi}(\eff)$ is defined
as,

$\Ent_{\pi}(\eff)=\Exp_{\omega\sim\pi}\eff(\omega)\log\eff(\omega)-\parens*{\Exp_{\pi}\eff}\log\parens*{\Exp_{\pi}\eff}.$

We recall that the entropy contraction constant $\EC(\Pii)$ and the log-
Sobolev constant $\LS(\Pii)$ of a reversible random walk
$\Pii\in\RR^{\Omega\times\Omega}$ are the largest constants $C_{ec}\geq 0$ and
$C_{ls}\geq 0$ respectively, satisfying the following inequalities for all
$\eff\in\RRp^{\Omega}$,

$\displaystyle\Ent_{\pi}(\Pii\eff)$
$\displaystyle~{}\leq~{}(1-C_{ec})\cdot\Ent_{\pi}(\eff),$ $\displaystyle
C_{ls}\cdot\Ent_{\pi}(\eff^{2})$
$\displaystyle~{}\leq~{}\mathcal{E}_{\Pii}(\eff,\eff)$

where we have written $\mathcal{E}_{\Pii}(\bullet,\bullet)$ for the Dirichlet
form of the random walk $\Pii$. We recall that the entropy contraction
constant $\EC(\Pii)$ allows establishing a sharper bound on the mixing time,

######  Theorem 1.5 ([BCP+21]).

There exists a universal constant $C$ such that, for any reversible random
walk $\Pii\in\RR^{\Omega\times\Omega}$ with stationary distribution
$\pi:\Omega\to\RRpp$, i.e. $\pi\Pii=\pi$. We have

$\Tmix(\Pii,\ee)\leq\frac{C}{\EC(\Pii)}\cdot\parens*{{\log\log\frac{1}{\min_{\omega\in\Omega}\pi(\omega)}+\log\ee^{-1}}},$

where the constant $C$ does not depend on the pair $(\Pii,\pi)$ and
$\EC(\Pii)$ denotes the entropy contraction constant of the random walk
$\Pii$.

We can prove the following bounds for the entropy contraction of expanderized
walks,

######  Theorem 1.6 (Simplified Version of Corollary 3.8).

Let $(X,\pi)$ be a weighted $n$-partite simplicial complex and $H$ a degree-
regular graph on $\binom{[n]}{\ell}$ where $0\leq\ell\leq n$. Then, writing
$\Duw_{n\lra\ell}$ for the down-up walk between $X^{(n)}$ and $X^{(\ell)}$
according to $\pi$, $\Udw_{\ell\lra n}$ for the up-down walk on between
$X^{(\ell)}$ and $X^{(n)}$ according to $\pi$, $\Paqx_{n\lra\ell}$ for the
expanderized down-up walk via $H$, and $\Papx$ for the expanderized up-down
walk via the graph $H^{2}$ we have

$\EC\parens*{\Paqx_{\ell\lra n}}\geq\LS\parens*{\Udw_{\ell\lra
n}}\cdot\Gap(H^{2})~{}~{}\textrm{and}~{}~{}\EC\parens*{\Papx_{\ell\lra
n}}\geq\LS\parens*{\Udw_{\ell\lra n}}\cdot\Gap(H^{2}),$

where $\Gap(\bullet)$ is as defined before.

Both Theorem 1.3 and Theorem 1.6 follow from an argument showing that the
expanderized up-down walks attain a good approximation for a dampened version
of the regular up-down walks,

######  Theorem 1.7 (Simplified Version of Theorem 3.6).

Let $(X,\pi)$ be an $n$-partite simplicial complex and $0\leq\ell\leq n$.
Writing $\Udw_{\ell\lra n}$ for up-down walk between $X^{(\ell)}$ and
$X^{(n)}$ according to $\pi$ and $\Papx$ for the expanderized up-down walk
between $X^{(\ell)}$ and $X^{(n)}$ via a degree-regular graph $H$ on
$\binom{[n]}{\ell}$, we have

$\norm*{\Papx_{\ell\lra n}-(1-\lambda(H))\cdot\Udw_{\ell\lra
n}}_{\opp}\leq\lambda(H),$

where $\lambda(H)$ is the two-sided expansion of $H$ defined by
$\lambda(H)=\max\set*{\lambda_{2}(H),\lambda_{\min}(H)|}$.

This result is proven using ideas from the derandomized graph squaring
algorithm of [RV05]: One can think of the up-down walk as running a random
walk on a clique when picking which vertex to remove while going down555Step
(2) in the presentation above. – the expanderized up-down walk replaces this
clique with an expander graph and as a result achieves a good approximation of
the up-down walk. The statements of Theorem 1.3 and Theorem 1.6 concerning the
expanderized down-up walk are obtained by noticing that the expanderized down-
up walk can be decomposed into an expanderized down- and an expanderized up-
walk. We use the up-down walk in our proofs as we notice that the type
identifies each face of $\omega^{(\ell)}\in X^{(\ell)}$ with a unique subset
in $\binom{[n]}{\ell}$, i.e. the vertex set of $H$. This differs from the
analysis of [RV05] in the following manner. In the expanderized up-down walk,
the face we are at after step (1) and the randomness used in step (2) is not
enough to determine which face we arrive at after step (3). In particular, if
we start from different faces before step (1), it is possible to arrive at
different faces after step (3), even if the face we are at after step (1) and
the randomness used in step (2) is the same. On the other hand, in a typical
derandomized product construction á la [RV05], this would necessitate arriving
at the same vertex.

Whereas Theorem 1.3 shows that the loss one suffers in the spectral gap is
related to the spectral gap of $H$ is not surprising, we note that Theorem 1.6
shows that one can obtain entropy contraction for the expanderized walks
paying only a price for the expansion of $H$ – and not it’s entropy
contraction factor $\EC(H)$ which can be considerably worse, especially if $H$
is a sparse graph. This is achieved by the following intermediate inequality,
which by appealing to an argument of [Mic97] can be used to bound the entropy
contraction constants,

######  Theorem 1.8 (Simplified Version of Corollary 3.8).

Let $(X,\pi)$ be an $n$-partite simplicial complex and let $H$ be a degree
regular graph on the vertex set $\binom{[n]}{\ell}$. Writing $\Udw_{\ell\lra
n}$ for the up-down walk between $X^{(\ell)}$ and $X^{(n)}$ according to $\pi$
and $\Papx_{\ell\lra n}$ for the expanderized up-down walk between
$X^{(\ell)}$ and $X^{(n)}$ via $H$, we have

$\LS\parens*{\Papx_{\ell\lra n}}\geq\LS\parens*{\Udw_{\ell\lra
n}}\cdot\Gap(H).$

#### Sampling Using the Expanderized Walks

In Section 5 we analyze the mixing times of expanderized walks for two
different problems (i) sampling $q$-colorings of a graph $G$ with maximum
degree $\Delta=O(1)$ where $O(\Delta)\geq q\geq(11/6-\ee)\Delta$ and (ii)
sampling from the Ising model with interaction matrix $\Jay\in\RR^{n\times n}$
and external field $\etch\in\RR^{n\times n}$ under the assumption that $\Jay$
is PSD and satisfies $\norm*{\Jay}_{\opp}\leq 1$. Before presenting our
results, we briefly talk about these problems and state of the art sampling
results for them.

We note that lifting rapid mixing results of the usual down-up walk to the
setting of expanderized walks often proceeds in black-box fashion, and these
examples are chosen as representative results obtained with fundamentally
different techniques. In particular, this list of applications is chosen as
representative applications and is not meant be exhaustive. For example, one
can easily extend our results to prove rapid mixing in the case of $p$-spin
models [AJK+23, Lee23] and ferromagnetic Ising/Potts models [BCC+22] under the
suitable assumptions ensuring bounded marginals.

Let $q\in\NN$ and a graph $G=(V,E)$ on $n:=|V|$ vertices be given: a
$q$-coloring $\chi:V\to[q]$ of a graph $G=(V,E)$ is an assignment of vertices
to colors in $[q]$ such that no two pair of adjacent vertices receive the same
color, i.e. $\chi(u)\neq\chi(v)$ for all $\set*{u,v}\in E$. In the sampling
problem, one is interested minimizing the the number of colors in relation to
the maximum degree $\Delta$ of this graph – a natural conjecture is that the
down-up walk mixes in time $O(n\log n)$ whenever $q\geq\Delta+2$. An $O(n\log
n)$ mixing time bound for $q>2\Delta$ was established by [Jer95], which was
simplified by [BD97]. Then, an $O(n^{2})$ mixing time was proven by [Vig00] in
the case $q>11/6\Delta$. Recently, this bound was improved for to
$q>(11/6-\ee)\Delta$ in the recent work of [CDM+19] where $\ee\approx 10^{-5}$
is a small constant. Finally, an $O(n\log n)$ mixing time was proven by
[Liu21, BCC+22] under the assumption that $\Delta=O(1)$. We show that
expanderized random walks rapidly mix in the setting where [Liu21, BCC+22]’s
result holds,

######  Theorem 1.9 (Simplified Version of Theorem 5.1).

Let $G$ be a graph on $n$ vertices of maximum degree $\Delta\leq O(1)$ and
$H_{n}$ be a labelled graph on $[n]$ of constant degree and two-sided
expansion $\lambda(H_{n})$ bounded away from 1. Then, for some absolute
constant $\ee\approx 10^{-5}$,666See [CDM+19] and any $K=O(1)$, if
$(11/6+K)\Delta\geq q\geq(11/6-\ee)\cdot\Delta$, the mixing time of the
expanderized down-up walk $\Paqx_{n}$ on $q$-colorings of $G$ with auxilary
graph $H_{n}$ satisfies,

$\Tmix(\Paqx_{n},\ee)\leq C_{0}\cdot n\parens*{\log n+\log\ee^{-1}},$

where $C_{0}$ is a universal constant not depending on $n$ but on $\Delta$.

We note that by [Alo21a], for each large enough $n\in\NN$, one can
_efficiently_ construct a graph $H_{n}$ that will satisfy the requirements of
Theorem 1.9. Our proof of Theorem 1.9 almost follows in blackbox fashion
assuming [Liu21, BCC+22]’s result. Furthermore, we note that our algorithm
will require $O(n\log n)$ random bits in total – as in every step we require
$O(1)$ bits to sample the vertex whose color we update and $O(1)$ bits to
sample a new color for this vertex. The usual down-up walk in contrast, would
need at least $\Omega(n\log^{2}n)$ random bits, as in every step the cost of
sampling the vertex whose color we update is $\Omega(\log n)$ bits.

The Ising model $\mu:=\mu_{\Jay,\etch}$ with interaction matrix
$\Jay\in\RR^{n\times n}$ and external field $\etch\in\RR^{n}$ is a probability
distribution on the hypercube $\set*{+1,-1}^{n}$ which assigns to each
$\eks\in\set*{+1,-1}^{n}$ the measure,

$\mu(\eks)=\frac{\exp\parens*{\frac{1}{2}\cdot\inpr*{\eks,\Jay\eks}+\inpr*{\etch,\eks}}}{Z(\Jay,\etch)}~{}~{}\textrm{where}~{}~{}Z(\Jay,\etch)=\sum_{\eks\in\set*{+1,-1}^{n}}\exp\parens*{\frac{1}{2}\cdot\inpr*{\eks,\Jay\eks}+\inpr*{\etch,\eks}}.$

Quite recently, [EKZ22] established that the spectral gap of the down-up walk
on the hypercube according to $\mu$ is at least
$\frac{1-\norm*{\Jay}_{\opp}}{n}$ when $\Jay$ is PSD and has small operator
norm, i.e. $\norm*{\Jay}_{\opp}<1$. In particular, this implies a mixing time
of $O\parens*{\frac{n}{1-\norm*{\Jay}_{\opp}}(n+\norm*{\etch}_{\ell_{1}})}$.
Subsequently, this spectral gap bound was promoted to a bound on the modified-
log Sobolev constant by [AJK+22]. By employing a clever argument based on the
_approximate exchange property_ [ALO+21b], they established a mixing time
bound of $O(n\log n)$ – bypassing the dependence on the external field $\etch$
completely.

We show that in this setting, the expanderized walks mix rapidly so long as
the maximum entry $\norm*{\etch}_{\ell_{\infty}}$ does not depend on $n$.

######  Theorem 1.10 (Simplified Version of Theorem 5.3).

Let $(X^{(\Jay,\etch)},\mu_{\Jay,\etch})$ be the simplicial complex defined
above corresponding to the Ising model defined by the interaction matrix
$\Jay\in\RR^{n\times n}$ and external field $\etch\in\RR^{n}$ and $H_{n}$ a
constant degree graph whose two-sided expansion is a constant – bounded away
from 1. Under the assumption that $\Jay$ is PSD and satisfies
$\norm*{\Jay}_{\opp}\leq 1$, the following bound holds for the expanderized
down-up walk with the auxillary graph $H_{n}$,

$\Tmix(\Paqx_{n},\ee)\leq\frac{O\parens*{\norm*{\etch}_{\ell_{\infty}}}\cdot
n}{(1-\norm*{\Jay}_{\opp})^{2}}\parens*{\log(n+\norm*{\etch}_{\ell_{1}})+\log\ee^{-1}},$

where the $O(\bullet)$ notation hides a universal constant not depending on
$n$ or $\Jay$.

The $\norm*{\etch}_{\ell_{\infty}}$ blow-up in the mixing time is due to the
reliance of our entropy contraction bounds on the log-Sobolev constant of the
up-down walk. When $\norm*{\etch}_{\ell_{\infty}}=O(1)$ and
$\norm*{\Jay}_{\opp}\ll 1$, we note that – ignoring numerical difficulties in
simulating biased coins – this random walk requires $O(n\log n)$ random bits
as the walk in Theorem 1.9. In this regime the standard Glauber dynamics still
requires $O(n\log^{2}n)$ random bits. In case where every 2 by 2 principle
submatrix of $\Jay$ has operator norm at most $\theta$, we can replace the
$(1-\norm*{\Jay}_{\opp})^{2}$ in the denominator by
$(1-\norm*{\Jay}_{\opp})\cdot(1-\theta)$.

#### Functional Inequalities on Simplicial Complexes

We also prove results which will provide us with the tools necessary to take
advantage of Theorem 1.6 in settings of interest to the random sampling
community. Our main tool here is the Garland method [Gar73] – more generally
the local-to-global method. The improvements we make to the state of the art
results are modest at best and in most cases can be recaptured by the local-
to-global method of [AASV21]. However, since our proofs are very simple and to
the best of our knowledge contain some results which have not explicitly
appeared in the literature before (such as Corollary 1.12), we choose to
include them in the present paper.

We recall that given a distribution $\pi:\Omega\to\RRpp$, and a convex
function $\Phi:\RRp\to\RRp$, the $\Phi$-entropy functional
$\Ent_{\pi}^{\Phi}(\eff)$ is defined as follows for all
$\eff\in\RRp^{\Omega}$,

$\Ent_{\pi}^{\Phi}(\eff)=\Exp_{\omega\sim\pi}\Phi(\eff(\omega))-\Phi\parens*{\Exp_{\omega\sim\pi}\eff(\omega)}.$

We say that the random walk $\Pii\in\RR^{\Omega_{1}\times\Omega_{2}}$ with two
distinguished measures $\pi_{1}:\Omega_{1}\to\RRpp$ and
$\pi_{2}:\Omega\to\RRpp$ satisfying $\pi_{1}\Pii_{1}=\pi_{2}$ is said to
satisfy a $\Phi$-entropy contraction inequality with constant $C>0$ if the
following equality holds for all $\eff\in\RR^{\Omega_{2}}$,

$\Ent_{\pi_{1}}\parens*{\Pii\eff}\leq(1-C)\cdot\Ent_{\pi_{2}}\parens*{\eff}.$

The largest constant $C$ for which such an inequality holds is called the
$\Phi$-entropy contraction constant of $\Pii$ and is denoted by
$\CF_{\Phi}(\Pii)$. Given a simplicial complex $(X,\pi)$ of rank $n$ – not
necessarily partite – we will prove several results concerning the
$\Phi$-entropy contraction of the so-called up-walk $\Upo_{\ell\to
n}\in\RR^{X^{(\ell)}\times X^{(n)}}$ between $X^{(\ell)}$ and $X^{(n)}$. The
right action of $\Upo_{\ell\to n}$ on $\eff\in\RR^{X^{(n)}}$ is defined by,

$[\Upo_{\ell\to
n}\eff](\widehat{\omega})=\Exp_{\omega\sim\pi}\sqbr*{\eff(\omega)\mid\omega\supset\widehat{\omega}}~{}~{}\textrm{for
all}~{}~{}\widehat{\omega}\in X^{(\ell)}.$

For the choice of $\Phi(t)=t\log t$, the $\Phi$-entropy
functi$\Ent_{\pi}^{\Phi}(\bullet)$ corresponds to the usual entropy functional
$\Ent_{\pi}(\bullet)$ defined above and $\CF_{\Phi}(\Pii)$ is simply
$\EC(\Pii)$. For the choice of $\Phi(t)=t^{2}$, $\Ent^{\Phi}_{\pi}(\bullet)$
simply corresponds to the variance functional $\Var_{\pi}(\bullet)$ – further
it is well understood that that $\CF_{\Phi}(\Upo_{\ell\to n})$ corresponds to
the spectral gap of the walk $\Duw_{n\lra\ell}$.

We note that the concepts of $\Phi$-entropy and $\Phi$-entropy contraction are
dual concepts to the concept of $f$-divergences and strong data processing
inequalities studied in the context of higher order random walks in [AASV21,
AJK+21, AJK+23, Lee23] and more generally in [Cha04, Rag16]. In particular,
this duality is the reason why we study the $\Phi$-entropy contraction of the
up-walk whereas the works mentioned above study the $f$-divergence contraction
for the down-walk $\Doo_{n\to\ell}\in\RR^{X^{(n)}\times X{{}^{(}\ell)}}$,
whose left action on distributions $\mu:X^{(n)}\to\RRp$ is defined by,

$\sqbr*{\mu\Doo_{n\to\ell}}(\widehat{\omega})=\sum_{\omega\in
X^{(n)},\atop\omega\supset\widehat{\omega}}\frac{\mu(\omega)}{\binom{n}{\ell}}~{}~{}\textrm{for
all}~{}~{}\widehat{\omega}\in X^{(\ell)}.$

The two concepts coincide for the special class of homogenous $\Phi$-entropy,
cf. [Rag16], which includes the $\Phi$-entropies induced by $\Phi(t)=t^{2}$
and $\Phi(t)=t\log t$.

The local $\Phi$-entropy contraction $\lc_{\Phi}(\varnothing)$ in $(X,\pi)$ is
defined as the smallest constant $c>0$ satisfying the following inequality,

$\Ent_{\pi_{1}}\parens*{\Upo_{1\to n}\eff}\leq
c\cdot\Ent_{\pi}(\eff)~{}~{}\textrm{for all}~{}~{}\eff\in\RRp^{\Omega},$

where $\pi_{1}$ is the marginal distribution on $X^{(1)}$ obtained by,

$\pi_{1}(x)=\frac{1}{n}\cdot\Pr_{\omega\sim\pi}[x\in\omega]~{}~{}\textrm{for
all}~{}~{}x\in X^{(1)}.$

Similarly, we define the constant $\lec(\widehat{\omega})$ in $(X,\pi)$
analogously by passing to the simplicial complex
$(X_{\widehat{\omega}},\pi^{(\widehat{\omega})})$, where we set

$X_{\widehat{\omega}}=\set*{\omega\setminus\widehat{\omega}\mid\omega\supset\widehat{\omega},\omega\in
X},$

and define the distribution
$\pi^{(\widehat{\omega})}:X_{\omega}^{(n-|\widehat{\omega}|)}\to\RRpp$ by,

$\pi^{(\widehat{\omega})}(\alpha)=\Pr_{\omega\sim\pi}\sqbr*{\omega=\widehat{\omega}\sqcup\alpha\mid\omega\supset\widehat{\omega}}.$

We show,

######  Theorem 1.11 (Simplified Version of Theorem 4.1).

Let $(X,\pi)$ be a simplicial complex of rank $n$ and $\Phi:\RRp\to\RRp$ a
convex function. We write $\lc^{(i)}_{\Phi}(X,\pi)=\max_{\widehat{\omega}\in
X^{(i)}}\lc_{\Phi}(\widehat{\omega})$. Then,

$\CF_{\Phi}\parens*{\Upo_{\ell\lra
n}}\geq\prod_{j=0}^{\ell-1}\parens*{1-\lc^{(j)}_{\Phi}(X,\pi)}.$

Our proof of Theorem 1.11 is a simple instantiation of the Garland method and
is inspired by the exposition in [CE22] combined with the chain rule for
$\Phi$-entropy. After submitting our results to arxiv, it came to our
attention that the same proof technique for proving Theorem 1.11 already
appeared in [Liu23] in the context of variance contraction – though only for
the case $\ell=n-1$.

Let $\widehat{\omega}\in X$ be such that $|\widehat{\omega}|\leq n-2$. We
recall that the link graph
$G_{\widehat{\omega}}=(X^{(1)}_{\widehat{\omega}},X^{(2)}_{\widehat{\omega}},c_{\widehat{\omega}})$
with the vertex set $X_{\widehat{\omega}}^{(1)}$ and the edge set
$X_{\widehat{\omega}}^{(2)}$ where

$\textrm{for all}~{}~{}x,y\in X_{\widehat{\omega}}^{(1)}~{}~{}\textrm{we
have}~{}~{}c_{\widehat{\omega}}(x,y)=\begin{cases}0&~{}\textrm{if}~{}x=y,\\\
\Pr\sqbr*{\omega\supset\widehat{\omega}\sqcup\set*{x,y}\mid\omega\supset\widehat{\omega}}&~{}\textrm{otherwise.}\end{cases}$

We will write $\Emm_{\widehat{\omega}}$ for the random walk matrix of the
graph $G_{\widehat{\omega}}$ where transitions are taken with probability
proportional to the weight function. A direct consequence of Theorem 1.11 is
the following bound on the spectral gap,

######  Corollary 1.12 (Spectral Gap Bound).

Let $(X,\pi)$ be a simplicial complex of rank $n$ and $0\leq\ell\leq n$.
Writing $\Gap_{k}(X,\pi):=\min_{x\in X^{(k)}}\Gap(\Emm_{x})$ we have

$\Gap(\Duw_{n\leftrightarrow\ell})\geq\frac{n-\ell}{n}\cdot\prod_{i=0}^{\ell-1}\Gap_{i}(X,\pi).$

This result is best compared with the following result due to [AL20],

######  Theorem 1.13.

Let $(X,\pi)$ a simplicial complex of rank $n$. Writing
$\Gap_{k}(X,\pi):=\min_{\widehat{\omega}\in
X^{(k)}}\Gap(\Emm_{\widehat{\omega}})$ for all $0\leq k\leq n-2$, we have

$\Gap(\Duw_{n\lra n-1})\geq\frac{1}{n}\cdot\prod_{i=0}^{n-2}\Gap_{i}(X,\pi).$

Similar results to Corollary 1.12 for variance contraction was proven in
[CLV20, GM21, SV23], however for the case $\ell=n-1$ they do not necessarily
recover the main result of [AL20] whereas Corollary 1.12 does indeed recover
this guarantee.

When $\Phi(t)=t\log t$, we will simply write $\lec(\widehat{\omega})$ in place
of $\lc_{\Phi}(\widehat{\omega})$. We note that this immediately implies,

######  Corollary 1.14.

Let $(X,\pi)$ a simplicial complex of rank $n$ and $0\leq\ell\leq n$. Writing
$\lec_{k}(X,\pi):=\min_{\widehat{\omega}\in X^{(k)}}\lec(\widehat{\omega})$
for all $0\leq k\leq\ell-1$, we have

$\EC(\Upo_{\ell\to n})\geq\prod_{i=0}^{\ell-1}\parens*{1-\lec_{i}(X,\pi)}.$

We observe that when the distribution $\pi$ is $a$-entropically independent in
the sense of [AJK+22], we have $\lec_{i}(X,\pi)=\frac{1}{a\cdot(n-i)}$ and the
resulting lowerbound in Corollary 1.14 is the same as the bound given in
[AJK+22].

We also note that we can relate the entropy contraction constant
$\EC(\Upo_{\ell\to n})$ to the log-Soblev constant thusly. We call the
distribution $\pi$ over $X^{(n)}$ $b$-marginally bounded if we have,

$\Pr_{\omega\sim\pi}\sqbr*{x\in\omega\mid\widehat{\omega}\subset\omega}\geq
b~{}~{}\textrm{or}~{}~{}\Pr_{\omega\sim\pi}\sqbr*{x\in\omega\mid\widehat{\omega}\subset\omega}=0$

for all $x\in X_{\widehat{\omega}}^{(1)}$.

######  Lemma 1.15 (Simplified Version of Lemma 4.3).

Let $(X,\pi)$ be a simplicial complex of rank $n$. For any
$\widehat{\omega}\in X$, we set $\Gap(\Emm_{\widehat{\omega}})$. where
$\Emm_{\widehat{\omega}}$ is the link of $\widehat{\omega}$ and
$\Gap(\bullet)$ denotes the spectral gap. Then $\Duw_{n\lra\ell}$ for the up-
down walk between $X^{(n)}$ and $X^{(\ell)}$ and $\Udw_{n-1}$ for the up-down
walk between $X^{(n-1)}$ and $X^{(n)}$ (both according to $\pi$), we have

Recalling that $\EC(\bullet)$ denotes the $\Phi$-entropy contraction for
$\Phi(t)=t\log t$, we have

$\displaystyle\LS(\Duw_{n\lra\ell})$
$\displaystyle~{}\geq~{}C_{b,\ell}\cdot\EC\parens*{\Upo_{\ell\to n}},$
$\displaystyle\LS(\Udw_{n-1})$
$\displaystyle~{}\geq~{}C_{b}\cdot\Gap_{n-2}(X,\pi)\cdot\EC(\Upo_{n-2\to
n-1}),$

where $C_{b}$ and $C_{b,\ell}$ are constants depending on $b$ and $n-\ell$
only.

######  Remark 1.16.

Here we are thinking $C_{b}=O(\log(1/b)^{-1})$ and
$C_{b,\ell}=O((\ell\cdot\log(1/b))^{-1})$, i.e. the dependence of $C_{b}$ and
$C_{b,\ell}$ on $b$ is inversely logarithmic. Similarly, the dependence of
$C_{b,\ell}$ on $\ell$ inversely linear.

In particular, when the distribution at hand is $b$-marginally bounded for
some $b=O(1)$ and $\ell=O(1)$ is a constant, Lemma 1.15 in conjunction with
Theorem 1.6 indicates in the entropy contraction of our expanderized random
walk we only pay a price according to the two-sided expansion of the graph
$H_{n}$ that we use in Theorem 1.6.

###  1.4 Related Work

High dimensional expansion has proven itself to be a very successful research
program for establishing mixing times for down-up walks. For example [KM17,
DK17, KO18, DDFH18, AL20] use spectral local-to-global arguments for
establishing spectral gap bounds for these walks. In conjunction with the
spectral independence framework, due to [ALO20, CGSV20, FGYZ20], these results
paved the way for many new in the field of random sampling: rapid mixing of
the down-up walk for the hardcore model in the uniqueness regime [ALO20],
rapid mixing of the down-up walk for sampling graph colorings in correlation
decay regime [FGYZ20, CGSV20], optimal mixing for many Markov chains of
interest[CLV21, BCC+22, Liu21]. For more information regarding spectral
independence, we refer the reader to the excellent survey [SV23] and the
references therein. In [AJK+21, AJK+23, CLV21, GM21] local-to-global
strategies for establishing entropic contraction bounds was studied. In [CE22]
a connection between these local-to-global methods and the stochastic
localization framework of [Eld13] was explored. We refer to the works [Kla18,
Eld20, Che21, KM22, ES22, EKZ22] and references therein for applications of
the stochastic localization framework. Our inductive strategy for establishing
$\Phi$-entropy contraction on simplicial complexes is heavily inspired by the
presentation in [CE22]. In [Lee23] mixing estimates about the walk
$\Duw_{n\lra n-1}$ is used to obtain estimates for $\Duw_{n\lra\ell}$ for all
$\ell<n-1$. The key intuition behind this work is the observation that the
down move of the down-up walk is (passively) utilizing an expander, the down-
move of the down-up walk of the so-called _Bernoulli-Laplace model_ , and that
one can use the expansion of this walk to show that once $\ell$ decreases the
mixing times estimates get better and better. Morally, this is very similar to
our idea of picking the replacement-indices for our expanderized walks via an
expander walk as opposed to sampling them uniformly at random. For other
classical techniques which can be used to bound mixing times of Markov chains,
we refer the reader to the texts [AF95, MT05, WLP09].

In contrast with down-up walks, results establishing rapid mixing for the
random walk $\Psc$ are fewer [DR00, Hay06, DGJ06, RR15] and mostly rely on
estimates on the Dobrushin matrix [Dob70]. [AP23] studied the mixing time of
this random walk using techniques of high dimensional expansion, however their
techniques fell short of establishing mixing time bounds under the assumption
of spectral independence.

The work of [FGW+23] is also related to our work in spirit. In this work, the
authors show that under suitable assumptions a wide array of random walks,
including the single site systematic scan $\Psc$ and the down-up walk $\Duw$,
can be derandomized, i.e. they devise efficient deterministic counting
algorithms on the basis of rapid mixing results for these chains. It is an
interesting question whether one can carefully pick the expander graph $H$, to
make this derandomization task more efficient.

As mentioned above our expanderized random walks are heavily inspired by the
derandomized squaring algorithm of [RV05]. This algorithm was initially used
to give an alternative and simpler proof of the seminal result of [Rei08]
concerning the derandomization of the complexity class $\mathbf{SL}$ and
establishing $\mathbf{SL}=\mathbf{L}$. Concretely, both [Rei08] and the
subsequent work of [RV05] show the existence of a deterministic logspace
algorithm deciding undirected graph connectivity. Since then, the derandomized
squaring algorithm has also found other uses in derandomization, e.g. [MRSV17,
MRSV21]. We conclude by noting that the inital algorithm of [Rei08] was based
on the zigzag product construction [RVW00], which has also inspired research
in the field of high dimensional expansion [KK20]. For more information on
expander graphs, we refer the reader to the excellent survey [HLW06].

###  1.5 Organization

Our results about expanderized walks are to be found in Section 3. Our results
about functional inequalities and local-to-global analysis in simplicial
complexes are to be found in Section 4. These two sections can be read
independently of each other. In Section 5 we give some example instances where
expanderized walks mix rapidly by utilizing the results proven in Section 3
and Section 4.

###  1.6 Open Questions and Future Directions

  * •

A current limitation of our method for proving optimal, $O(n\log n)$, mixing
times for many problems on $n$-vertex graphs is our reliance on the log-
Sobolev constant $\LS(\Udw)$ of the up-down walk to bound the entropy
contraction $\EC(\Paqx)$ of expanderized walks. This presents a natural
blocker to extend our methods beyond cases where the target distributions are
marginally bounded. One can alternatively try to bound the entropy contraction
directly, however a naive calculation shows that it is difficult to avoid a
blow up related to the entropy contraction $\EC(H)$ of the graph $H$ here. It
is a natural question whether a more cunning analysis, not relying on the log-
Sobolev constant, can show that the loss in the entropy contraction one will
suffer when passing from the usual walks to the expanderized walks depends
only on the two-sided expansion of $H$.

  * •

Our Theorem 1.7 shows that the expanderized up-down walks are close to the
regular up-down walks. Can we use this result or a result of similar flavor to
establish the hypercontractivity of an expanderized noise operator over a
simplicial complex? We recall that for $\rho\in[0,1]$ the usual noise operator
$\Tee_{\rho}\in\RR^{X^{(n)}\times X^{(n)}}$ is defined by the equation

$\Tee_{\rho}=\sum_{j=0}^{n}\rho^{j}(1-\rho)^{n-j}\cdot\binom{n}{j}\cdot\Duw_{n\lra
j}.$

In [BHKL22a, BHKL22b, GLL22] the hypercontractivity of the noise operator was
established in various cases of interest. An expanderized hypercontractive
noise operator a simplicial complex can be useful in constructing sparser
integrality examples for many problems of interest.

### Acknowledgements

VLA and SR would like to thank Fernando Granha Jeronimo for many insightful
discussions concerning expander graphs. VLA was supported by the ERC grant of
Alex Lubotzky (European Union’s Horizon 2020/882751), the ISF grant 2669/21
and ERC grant 834735 of Gil Kalai, and ISF grant 2990/21 of Ori Parzanchevski.
SR was supported by the National Science Foundation under Grant No. 2348489.

##  2 Preliminaries

###  2.1 Linear Algebra

We will denote functions and vectors by bold faces, i.e. $\eff\in\RR^{V}$. The
indicator function of $i\in V$ will be denoted by $\one_{i}$, i.e.
$\one_{i}(j)=0$ for all $j\neq i$ and $\one_{i}(i)=1$. For $A\subseteq V$, we
will write $\one_{A}=\sum_{a\in A}\one_{a}$. We will adopt the convention of
using $\pi,\nu,\mu:V\to\RRp$ for various probability distributions over $V$.

Let $\eff,\gee\in\RR^{V}$ and a measure $\pi:V\to\RRpp$ be given. We will use
the notations $\langle\eff,\gee\rangle_{\pi}$ and $\norm{\eff}_{\pi}$ to
denote the inner-product and the norm with respect to the distribution $\pi$,
i.e.

$\langle\eff,\gee\rangle_{\pi}=\Exp_{x\sim\pi}\eff(x)\gee(x)=\sum_{x\in
V}\pi(x)\cdot\eff(x)\gee(x)~{}~{}\textrm{ and
}~{}~{}\norm{\eff}_{\pi}^{2}=\langle\eff,\eff\rangle_{\pi}.$ (1)

Given $\eff,\gee\in\RR^{n}$ we will write $\inpr*{\eff,\gee}_{\ell_{2}}$ for
the inner-product between $\eff$ and $\gee$ in the counting measure, i.e.
$\inpr*{\eff,\gee}_{\ell_{2}}=\sum_{i=1}^{n}\eff(i)\gee(i)$. We will also
write $\norm*{\eff}_{\ell_{1}},\norm*{\eff}_{\ell_{2}}$, and
$\norm*{\eff}_{\ell_{\infty}}$ for the $\ell_{1},\ell_{2},$ and
$\ell_{\infty}$ norms of $\eff$ respectively. Formally,

$\norm*{\eff}^{2}_{\ell_{2}}=\sum_{i=1}^{n}\eff(i)^{2}~{}~{}\textrm{;}~{}~{}\norm*{\eff}_{\ell_{1}}=\sum_{i=1}^{n}|\eff(i)|~{}~{}\textrm{;
and ;}~{}~{}\norm*{\eff}_{\ell_{\infty}}=\max_{i\in[n]}|\eff(i)|.$

#### Matrices and Eigenvalues

In this section, we will recall some results concerning eigenvalues and
eigenvectors of matrices.

Serif faces will be used to denote matrices, i.e. $\Aye,\Bee\in\RR^{U\times
V}$. We will call a matrix $\Bee\in\RR^{U\times V}$ row stochastic if rows of
$\Bee$ sum up to 1 and $\Bee$ contains no negative entries. Formally,

$\textrm{for all }u\in U,v\in V~{}~{}\Bee(u,v)\geq
0~{}~{}\textrm{and}~{}~{}\Bee\one=\one.$ (row stochastic)

Let $\Bee\in\RR^{U\times V}$ and distributions $\pi_{U}:U\to\RRpp$ and
$\pi_{V}:V\to\RRpp$ be given. The adjoint $\Bee^{*}$ of $\Bee$ with respect to
the measures $\pi_{U}$ and $\pi_{V}$ is the unique matrix which satisfies the
following equation,

$\langle\eff,\Bee\gee\rangle_{\pi_{U}}=\langle\Bee^{*}\eff,\gee\rangle_{\pi_{V}}~{}~{}\textrm{
for all }\eff\in\RR^{U},\gee\in\RR^{V}.$ (adjoint)

If $U=V$ and $\pi_{U}=\pi_{V}$, the operator $\Bee$ is called self-adjoint
when $\Bee^{*}=\Bee$. If $\Bee$ is a row-stochastic matrix, we will call
$\Bee^{*}$ the time-reversal of $\Bee$ with respect to $\pi_{U},\pi_{V}$ and
say that $\Bee$ is reversible if $\Bee=\Bee^{*}$. It is well known that the
operator $\Bee^{*}\in\RR^{V\times U}$ is uniquely determined by the choice of
$\Bee\in\RR^{U\times V}$ and the inner-products defined by $\pi_{U}$ and
$\pi_{V}$ (see e.g. [SC97, p. 318]),

######  Proposition 2.1.

Let $\Bee\in\RR^{U\times V}$ be arbitrary. We write $\Bee^{*}$ for the adjoint
operator to $\Bee$ with respect to the inner-products defined by the
distributions $\pi_{U}$ and $\pi_{V}$. Then,

$\Bee^{*}(y,x)=\Bee(x,y)\cdot\frac{\pi_{U}(x)}{\pi_{V}(y)}~{}~{}\textrm{for
all}~{}~{}x\in U,y\in V.$

We also recall the following standard fact which is an immediate consequence
of Proposition 2.1,

######  Fact 1.

If $\Bee\in\RR^{U,V}$ is a row-stochastic matrix satisfying
$\pi_{U}\Bee=\pi_{V}$, then the adjoint matrix $\Bee^{*}$ with respect to
$\pi_{U},\pi_{V}$ is also row-stochastic and satisfies
$\pi_{V}\Bee^{*}=\pi_{U}$.

It is well known that a self-adjoint matrix $\Aye\in\RR^{V\times V}$ has $|V|$
real eigenvalues. We will write,

$\lambda_{1}(\Aye)\geq\lambda_{2}(\Aye)\geq\cdots\geq\lambda_{|V|}(\Aye):=\lambda_{\min}(\Aye),$

for the sequence of eigenvalues of $\Aye$ sorted in decreasing order. We say
that the matrix is positive semi-definite, henceforth PSD, if it is self-
adjoint and satisfies $\lambda_{\min}(\Aye)\geq 0$.

Given a matrix $\Aye\in\RR^{V\times V}$ and a distribution $\mu:V\to\RRpp$, we
will write $\norm*{\Aye}_{\opp,\mu}$ for the operator norm of $\Aye$, defined
in the following manner

$\norm*{\Aye}_{\opp,\mu}:=\max\set*{\left.\frac{\norm*{\Aye\eff}_{\mu}}{\norm{\eff}_{\mu}}~{}\right|~{}\eff\in\RR^{V}~{}\textrm{and}~{}\eff\neq
0}.$ (operator norm)

If $\Aye$ is self-adjoint with respect to the measure $\mu$, we have
$\norm*{\Aye}_{\opp,\mu}=\max\set*{\lambda_{1}(\Aye),|\lambda_{\min}(\Aye)|}$.
When $\mu$ is the counting measure, we will simply write
$\norm{\bullet}_{\ell_{2}}$.

Similarly when $\Aye\in\RR^{V\times V}$ is a reverisble row-stochastic matrix,
with stationary measure $\mu$. We will write $\lambda(\Aye)$ for the two-sided
expansion of $\Aye$. Formally,

$\lambda(\Aye)=\max\set*{\lambda_{2}(\Aye),\Abs*{\lambda_{\min}(\Emm)}}.$
(two-sided expansion)

When $\Aye$ represents the simple random walk over an undirected graph
$H=(V,E)$, i.e.

$\Aye(i,j)=\frac{\one[\set*{i,j}\in E]}{\deg(i)}~{}~{}\textrm{for
all}~{}~{}i,j\in V,$

we will simply write $\lambda(H)$ instead of $\lambda(\Aye)$. For convenience,
we recall

######  Fact 2.

Let $H=(V,E)$ be a $k$-regular graph and suppose $\Aye$ represents the random
walk over $H$. Then, $\uni_{V}\Aye=\uni_{V}$, i.e. the uniform distribution on
$V$ is stationary for $\Aye$.

We note that there exist infinite families of graphs such that every graph $H$
in the family has constant degree and $\lambda(H)$ bounded above by a constant
bounded above by $1$ [LPS86, Mar88]. In this paper, we will consider families
that contain graphs on $n$ vertices for _every_ sufficiently large $n$. Such
constructions were given in [Alo21a], and in particular were based on the
infinite families from [LPS86, Mar88]. We refer the reader to the excellent
survey [HLW06] for more information on expander graphs. For our purposes we
will only need to rely on the following result,

######  Theorem 2.2 (Theorem 1.1 in [Alo21a], simplified).

For every prime number $p\equiv 1\pmod{4}$, and every sufficiently large
$n>n_{0}(p)$, there exists a strongly explicit777i.e. the list of neighbors of
any vertex can be generated deterministically in time $\plog(n)$ construction
of a $d$-regular graph $H_{n}$ on $n$-vertices with
$\lambda(H_{n})\leq\frac{(1+\sqrt{2})\sqrt{d-1}+o(1)}{d}$, where the $o(1)$
vanishes as $n$ tends to infinity.

We emphasize that if the prime $p\equiv 1\pmod{4}$ is a constant, i.e. has no
dependency on $n$, then the graph $H_{n}$ is a $d$-regular expander graph with
$d=O(1)$ and $\lambda(H_{n})=1-\ee$ for some constant $\ee:=\ee(p)$, i.e. the
two-sided expansion of $H_{n}$ is bounded away from 1.

The following variational characterizations of
$\lambda_{2}(\bullet),\lambda_{\min}(\bullet),$ and $\lambda(\bullet)$ are
simple consequences of the Courant-Fischer-Weyl principle and the Perron-
Frobenius Theorem, see for example [Bha13, HJ12, AF95].

######  Fact 3.

Let $\Aye\in\RR^{V\times V}$ be a reversible row-stochastic matrix with
respect to the measure $\mu:V\to\RRpp$. Then, the following hold,

  1. 1.

$\lambda_{2}(\Aye)=\max\set*{\left.\frac{\inpr*{\eff,\Aye\eff}_{\mu}}{\norm{\eff}^{2}_{\mu}}~{}\right|~{}\eff\in\RR^{V}\setminus\boldsymbol{0},\inpr*{\eff,\one}_{\mu}=0},$

  2. 2.

$\lambda_{\min}(\Aye)=\min\set*{\left.\frac{\inpr*{\eff,\Aye\eff}_{\mu}}{\norm{\eff}^{2}_{\mu}}~{}\right|~{}\eff\in\RR^{V}\setminus\boldsymbol{0},\inpr*{\eff,\one}_{\mu}=0},$

  3. 3.

$\lambda(\Aye)=\max\set*{\left.\frac{\norm*{\Aye\eff}_{\mu}}{\norm{\eff}_{\mu}}~{}\right|~{}\eff\in\RR^{V}\setminus\boldsymbol{0},\inpr*{\eff,\one}_{\mu}=0}$,

  4. 4.

$\lambda(\Aye)=\max\set*{\left.\frac{\Abs*{\inpr*{\eff,\Aye\eff}_{\mu}}}{\norm{\eff}^{2}_{\mu}}~{}\right|~{}\eff\in\RR^{V}\setminus\boldsymbol{0},\inpr*{\eff,\one}_{\mu}=0}$.

We will also make use of the following simple result,

######  Fact 4.

Let a matrix $\Aye\in\RR^{U\times V}$ and measures $\mu_{U}:U\to\RRpp$ and
$\mu_{V}:V\to\RRpp$ be given, such that $\mu_{U}\Aye=\mu_{V}$. Assume without
loss of generality that $|U|\leq|V|$, then

$\lambda_{j}(\Aye\Aye^{*})=\lambda_{j}(\Aye^{*}\Aye)~{}~{}\textrm{for
all}~{}~{}j=1,\ldots,|U|,$

where $\Aye^{*}$ is the adjoint of $\Aye$ with respect to the measures
$\mu_{U}$ and $\mu_{V}$.

###  2.2 Probability Distributions

We will denote the probability simplex with vertices $\Omega$ by
$\triangle_{\Omega}$, i.e.

$\triangle_{\Omega}=\set*{\left.\mu:\Omega\to\RRp~{}\right|~{}\sum_{\omega\in\Omega}\mu(\omega)=1}$
(probability simplex)

Throughout the paper, we will assume $\Omega$ (or $X^{(n)}$) to be a set of
$n$-tuples for some $n\geq 1$. Given a set $S\subset[n]$, the projection of
$\Omega$ on $S$ is denoted by $\Omega[S]$ , i.e.

$\Omega[S]=\set*{(\omega_{s})_{s\in
S}:(\omega_{1},\ldots,\omega_{n})\in\Omega}.$ (projection)

For $\omega_{S}\in\Omega_{S}$, the notations $\Omega_{\omega_{S}}$ and
$\mu^{(\omega_{S})}$ will be used for the $\omega_{S}$-pinning of $\Omega$ and
$\mu_{S}$ respectively, where

$\Omega_{\omega_{S}}=\set*{\bar{\omega}\in\Omega[S^{c}]:\omega_{S}\oplus\bar{\omega}\in\Omega}~{}~{}\textrm{and}~{}~{}\mu^{(\omega_{S})}(\bar{\omega})=\frac{\mu(\omega_{S}\oplus\bar{\omega})}{\sum_{\tilde{\omega}\in\Omega[S^{c}]}\mu(\omega_{S}\oplus\tilde{\omega})},$
($\omega_{S}$-pinning)

We recall that the total variation distance $\norm{\mu-\nu}_{\TV}$ between two
distributions $\mu,\nu\in\triangle_{\Omega}$ is defined as follows,

$\norm*{\mu-\nu}_{\TV}=\frac{1}{2}\cdot\sum_{\omega\in\Omega}\Abs*{\mu(\omega)-\nu(\omega)}$
(total variation distance)

Finally, we talk about some conventions that we will use throughout the paper:
(i) We will be using the notation $\uni_{A}\in\triangle_{A}$ to denote the
uniform distribution over various finite sets $A$. (ii) When we want to
emphasize that the a distribution $\mu\in\triangle_{\Omega}$ has full support,
we will simply write $\mu:\Omega\to\RRpp$ and emphasize in words that $\mu$ is
a distribution as opposed to writing $\mu\in\triangle_{\Omega}.$

Finally we recall that the product distribution
$\mu\tensor\nu\in\triangle_{\Omega\times\Omega^{\prime}}$, given
$\mu\in\triangle_{\Omega}$ and $\nu\in\triangle_{\Omega^{\prime}}$ is defined
by setting

$(\mu\tensor\nu)(\omega,\omega^{\prime})=\mu(\omega)\cdot\nu(\omega^{\prime})~{}~{}\textrm{for
all}~{}~{}\omega\in\Omega,\omega^{\prime}\in\Omega.$

###  2.3 Functional Inequalities, Isoperimetric Constants, and Mixing Times

Given a distribution $\mu\in\triangle_{\Omega}$ and a convex function
$\Phi:\RRp\to\RRp$ $\Phi$-entropy functional $\Ent^{\Phi}_{\mu}(\bullet)$ is
defined by the equation,

$\Ent^{\Phi}_{\mu}(\eff)=\Exp_{\omega\sim\mu}\Phi\parens*{\eff(\omega)}-\Phi\parens*{\Exp_{\omega\sim\pi_{n}}\eff(\omega)}$
($\Phi$-entropy)

for all $\eff\in\RRp^{\Omega}.$

We also recall that for the special choices of $\Phi(t)=t\log t$ and
$\Phi(t)=t^{2}$, the $\Phi$-entropy equals the variance functional
$\Var_{\mu}(\bullet)$ and entropy functional $\Ent_{\mu}(\bullet)$
respectively.

$\displaystyle\Ent_{\mu}(\eff)$
$\displaystyle~{}=~{}\Exp_{\omega\sim\mu}\sqbr*{\eff(\omega)\log\eff(\omega)}-\parens*{\Exp_{\omega\sim\mu}\eff(\omega)}\log\parens*{\Exp_{\omega\sim\mu}\eff(\omega)},$
(entropy) $\displaystyle\Var_{\mu}(\eff)$
$\displaystyle~{}=~{}\Exp_{\omega\sim\mu}\eff(\omega)^{2}-\parens*{\Exp_{\omega\sim\mu}\eff(\omega)}^{2}.$
(variance)

######  Remark 2.3.

We notice that when $\eff=c\cdot\one$ for some constant $c\in\RRp$, we have
$\Ent_{\mu}^{\Phi}(\eff)=0$.

Let $\Pii\in\RR^{\Omega\times\Omega}$ be a reversible Markov chain, with
stationary measure of $\pi$. A Poincaré inequality for $\Pii$ is an inequality
of the form,

$C\cdot\Var_{\pi}(\eff)\leq\inpr*{\eff,(\Ide-\Pii)\eff}_{\pi}~{}~{}\textrm{for
all}~{}~{}\eff\in\RR^{\Omega}.$ (Poincaré inequality)

The largest constant $C>0$ for which this inequality holds, is called the
Poincaré constant or the spectral gap of $\Pii$ and is denoted by
$\Gap(\Pii)$. This nomenclature is due to the following well-known consequence
of the Courant-Fischer-Weyl Principle,

$\Gap(\Pii)=\min\set*{\left.\frac{\inpr*{\eff,(\Ide-\Pii)\eff}_{\pi}}{\Var_{\pi}(\eff)}~{}\right|~{}\Var_{\pi}(\eff)\neq
0}=1-\lambda_{2}(\Pii).$ (spectral gap)

The modified log-Sobolev (mLSI) and the log-Sobolev (LSI) inequalities for a
reversible random walk $\Pii\in\RR^{\Omega\times\Omega}$ with stationary
measure $\pi$ are defined to be,

$\displaystyle C_{0}\cdot\Ent_{\pi}(\eff)$
$\displaystyle~{}\leq~{}\inpr*{\eff,(\Ide-\Pii)\log\eff}_{\pi}$
$\displaystyle\textrm{for all}~{}~{}\eff\in\RR_{\geq 0}^{\Omega},$ (mLSI)
$\displaystyle C_{1}\cdot\Ent_{\pi}(\eff^{2})$
$\displaystyle~{}\leq~{}\inpr*{\eff,(\Ide-\Pii)\eff}_{\pi}$
$\displaystyle\textrm{for all}~{}~{}\eff\in\RR_{\geq 0}^{\Omega}.$ (LSI)

The largest constants $C_{0},C_{1}\geq 0$ for which mLSI and LSI hold are
called the modified log-Sobolev constant and the log-Sobolev constant of
$\Pii$ respectively – and they are denoted by $\MLS(\Pii)$ and $\LS(\Pii)$.
Formally,

$\displaystyle\MLS(\Pii)$
$\displaystyle~{}=~{}\inf\set*{\left.\frac{\inpr*{\eff,(\Ide-\Pii)\log\eff}_{\pi}}{\Ent_{\pi}(\eff)}~{}\right|~{}\Ent_{\pi}(\eff)\neq
0,\eff\in\RR_{\geq 0}^{\Omega}},$ (2) $\displaystyle\LS(\Pii)$
$\displaystyle~{}=~{}\inf\set*{\left.\frac{\inpr*{\eff,(\Ide-\Pii)\eff}_{\pi}}{\Ent_{\pi}(\eff^{2})}~{}\right|~{}\Ent_{\pi}(\eff)\neq
0,\eff\in\RR_{\geq 0}^{\Omega}}.$ (3)

######  Fact 5 ([DSC+96]).

Let $\pi:\Omega\to\RR_{>0}$ be a probability distribution and write
$\Jay_{\pi}=\one\cdot\pi$, i.e. $\Jay_{\pi}$ is the walk with stationary
measure $\pi$ which mixes in a single step.

Then, $\LS(\Jay_{\pi})\geq\frac{1-2\pi_{\star}}{\log(\pi_{\star}^{-1}-1)}$ if
$|\supp(\pi)|>2$ else $\LS(\Jay_{\pi})=1$. More generally for any reversible
Markov chain $\Emm\in\RR^{\Omega\times\Omega}$ and stationary distribution
$\pi$, we have
$\LS(\Emm)\geq\frac{1-2\pi_{\star}}{\log(\pi_{\star}^{-1}-1)}\cdot\Gap(\Emm)$
if $|\supp(\pi)|>2$ else $\LS(\Jay_{\pi})=\Gap(\Emm)$.

For a convex function $\Phi:\RRp\to\RRp$, we also define the $\Phi$-entropy
contraction constant $\CF_{\Phi}(\Pii)$ of a Markov chain
$\Pii\in\RR^{\Omega_{1}\times\Omega_{2}}$ satisfying $\pi_{1}\Pii=\pi_{2}$ for
some choice of measures
$\pi_{1}\in\triangle_{\Omega_{1}},\pi_{2}\in\triangle_{\Omega_{2}}$, as the
solution to the following variational problem,

$\CF_{\Phi}(\Pii)=1-\sup\set*{\left.\frac{\Ent^{\Phi}_{\pi_{1}}(\Pii\eff)}{\Ent^{\Phi}_{\pi_{2}}(\eff)}~{}\right|~{}\eff\in\RRp^{\Omega},\Ent^{\Phi}_{\pi_{2}}(\eff)\neq
0}.$ ($\Phi$-entropy contraction)

We note that $\CF_{\Phi}(\Pii)$ cruicially depends on the choice of
distributions $\pi_{1},\pi_{2}$. Since for our purposes the choice of measures
$\pi_{1}$ and $\pi_{2}$ will always be clear, we will supress this dependency.

It is equivalent to define $\CF_{\Phi}(\Pii)$ as the largest constant
$C\in\RRp$ such that the inequality,

$\Ent^{\Phi}_{\pi}(\Pii\eff)\leq(1-C)\cdot\Ent^{\Phi}_{\pi}(\eff),$

is valid for each $\eff\in\RRp$. When $\Phi(t)=t\log t$, we will simply write
$\EC(\Pii)$ in place of $\CF_{\Phi}(\Pii)$. Similarly, for the choice of
$\Phi(t)=t^{2}$, it is easy to observe that
$\CF_{\Phi}(\Pii)=\Gap(\Pii^{*}\Pii)$.

######  Remark 2.4.

$\Phi$-entropy contraction and the quantity $\CF_{\Phi}(\Pii)$ is closely
related to the concept of $f$-divergence contraction, studied in the context
of higher-order random walks in the works of [AJK+22, AJK+21, Lee23]. We note
that for the choices of $\Phi(t)=f(t)=t^{2}$ and $\Phi(t)=f(t)=t\cdot\log t$,
$f$-divergence contraction for the walk $\Pii$ is equivalent to $\Phi$-entropy
contraction $\Pii^{*}$. This equivalence holds for the more general class of
homogenous entropies associated with $\Phi(t)=f(t)$ [Rag16], i.e. convex
functions $\Phi:\RRp\to\RRp$, for which there is a function
$\kappa:\RRp\to\RRp$ that satisfies,

$\Ent^{\Phi}_{\pi_{1}}(c\cdot\eff)=\kappa(c)\cdot\Ent^{\Phi}_{\pi_{2}}(\eff),$

for each $\eff\in\RRp^{\Omega}$. For more information on $\Phi$-entropy
contraction and $f$-divergence contraction we refer the reader to [Cha04,
Rag16, BLM13], and the references therein.

We will also need the following consequence of Jensen’s inequality.

######  Fact 6 (Data Processing Inequality).

Let $\Pii\in\RR^{\Omega_{1}\times\Omega_{2}}$ be a row-stochastic matrix,
satisfying $\pi_{1}\Pii=\pi_{2}$ for probability distributions
$\pi_{1}:\Omega_{1}\to\RRpp$ and $\pi_{2}:\Omega_{2}\to\RRpp$. Then, for any
convex function $\Phi:\RRp\to\RRp$, we have2

$\Ent_{\pi_{1}}^{\Phi}\parens*{\Pii\eff}\leq\Ent^{\Phi}_{\pi_{2}}\parens*{\eff}~{}~{}\textrm{for
all}~{}~{}\eff\in\RRp^{\Omega_{2}}.$

In particular, for any $\Quu\in\RR^{\Omega_{2}\times\Omega_{3}}$ with a
measure $\pi_{3}:\Omega_{3}\to\RRpp$ such that $\pi_{2}\Quu=\pi_{3}$, we have
$\CF_{\Phi}(\Pii\Quu)\geq\CF_{\Phi}(\Pii)$ and
$\CF_{\Phi}(\Pii\Quu)\geq\CF_{\Phi}(\Quu).$

We provide a proof for 6 in Section A.1.

We also recall the following relations between the constants
$\MLS(\bullet),\LS(\bullet)$, and $\EC(\bullet)$.

######  Lemma 2.5 (Lemma 16, [AJK+22]).

Let $\Pii\in\RR^{\Omega\times\Omega}$ be a reversible row-stochastic matrix
with stationary distribution $\pi$. Then,

$\MLS(\Pii)\geq\EC(\Pii)$

######  Remark 2.6.

Lemma 2.5 can be generalized to show that contraction results for the
$\Phi$-entropy can be utilized to obtain functional inequalities called
$\Phi$-Sobolev inequalities. We refer to [BLM13, Section 14] and [Rag16,
Section 4] for more information on this topic.

######  Lemma 2.7 (Proposition 6, [Mic97]).

Let $\Pii\in\RR^{\Omega_{1}\times\Omega_{2}}$ satisfying
$\mu_{1}\Pii=\mu_{2}$, for distributions $\mu_{1}:\Omega_{1}\to\RRpp$ and
$\mu_{2}:\Omega\to\RRpp$. We have,

$\EC(\Pii)\geq\LS(\Pii^{*}\Pii).$

######  Remark 2.8.

The statements of Lemma 2.5 and Lemma 2.7 have minor cosmetic changes from the
statements of [AJK+22, Lemma 16] and [Mic97, Lemma 6] respectively.

The statement in [AJK+22, Lemma 16] considers the contraction of divergences,
rather than contraction of entropies. These are equivalent by Remark 2.4.
Additionally, their definition of the modified log-Sobolev inequality (mLSI)
differs from ours by a factor of 2.

The statement in [Mic97, Lemma 6] assumes square operators. However, as
observed in [CLV21, Lemma 5.11] the proof can be extended to rectangular
operators also. For completeness, we provide a proof in Section A.2 – we use
their proof as a template and make the minimal syntactic changes necessary.

The $\ee$-mixing time $\Tmix(\Pii,\ee)$ of the random walk is the least time
point $t\in\NN$, such that the distribution $\mu^{(t)}=\mu^{(0)}\Pii^{t}$ of
the random walk $\Pii$ is guaranteed to be $\ee$-close to the stationary
distribution $\pi$ in the total variation distance regardless of the initial
distribution $\mu^{(0)}$. In particular,

$\Tmix(\Pii,\ee)=\min\set*{\left.t\in\NN~{}\right|~{}\norm*{\mu^{(t)}-\pi}_{\TV}\leq\ee~{}~{}\textrm{for
all}~{}~{}\mu^{(0)}\in\triangle_{\Omega}}$ ($\ee$-mixing time)

It is well known that the functional inequalities and the corresponding
isoperimetric constants introduced previously can be used to bound mixing
times. We recall two of these results,

######  Theorem 2.9 ([BCP+21]).

There exists a universal constant $C$ such that, for any reversible random
walk $\Pii\in\RR^{\Omega\times\Omega}$ with stationary distribution
$\pi:\Omega\to\RRpp$, i.e. $\pi\Pii=\pi$. We have

$\Tmix(\Pii,\ee)\leq\frac{C}{\EC(\Pii)}\cdot\parens*{{\log\log\frac{1}{\min_{\omega\in\Omega}\pi(\omega)}+\log\ee^{-1}}},$

where the constant $C$ does not depend on the pair $(\Pii,\pi)$ and
$\EC(\Pii)$ denotes the entropy contraction constant of the random walk
$\Pii$.

The following result is also well-known, see e.g. [MT05]

######  Theorem 2.10.

Let $\Pii\in\RR^{\Omega\times\Omega}$ be a reversible random walk matrix with
stationary distribution $\pi:\Omega\to\RRpp$, i.e. $\pi\Pii=\pi$. We have,

$\Tmix(\Pii,\ee)\leq\frac{1}{1-\lambda(\Pii)}\cdot\log\frac{1}{\ee\cdot\sqrt{\min_{\omega\in\Omega}\pi(\omega)}},$

where $\lambda(\Pii)$ is the two-sided expansion of $\Pii$. If $\Pii$ is PSD,
then $1-\lambda(\Pii)=\Gap(\Pii)$.

###  2.4 (Partite) Simplicial Complexes

A simplicial complex is a downward closed collection of subsets of a finite
set $U$. Formally, $X\subset 2^{U}$ and whenever $\beta\in X$ for all
$\alpha\subset\beta$ we have $\alpha\in X$. The rank of a face $\alpha$ is
$|\alpha|$. Given some $j$, we will adopt the notation $X^{(j)}$ to refer to
the collection faces of $X$ of rank $j$ and the notation $X^{(\leq j)}$ to
refer to the collection of faces of $X$ of rank at most $j$, i.e.

$X^{(j)}:=X\cap\binom{U}{j}~{}~{}\textrm{and}~{}~{}X^{(\leq
j)}:=\bigcup_{i=0}^{j}X^{(i)}.$

We say $X$ is a simplicial complex of rank $n$ if the largest rank of any face
$\alpha\in X$ is $n$. We note that by definition $X^{(0)}=\set{\varnothing}$.

We say that a simplicial complex $X$ of rank $n$ is pure, if any face
$\alpha\in X^{(j)}$ for any $j<n$ is contained in another face $\beta\in
X^{(n)}$. Equivalently, in a pure simplicial complex the only inclusion
maximal faces are those of maximal rank. In this article, we will only deal
with pure simplicial complexes.

A rank-$n$ pure simplicial complex $X$ is called $n$-partite if we can
partition $X^{(1)}$ into disjoint sets $X[1],\ldots,X[n]$ such that

$\textrm{for all}~{}\beta\in X^{(n)}~{}\textrm{and for
all}~{}i=1,\ldots,n~{}~{}\textrm{we have}~{}~{}|\beta\cap X[i]|=1.$

We will call the sets $X[1],\ldots,X[n]$ the sides of the complex $X$.
Equivalently, every element of a rank-$n$ face $\beta\in X[n]$ comes from a
distinct side $X[i]$. We observe that a bipartite graph is a 2-partite
simplicial complex.

######  Remark 2.11.

Our notation differs slightly from the preceding work, the notation $X(j)$ in
the preceding work is often used to denote what we have called $X^{(j+1)}$,
i.e. $X(j)$ is the set of $j$-dimensional faces. We have avoided this notation
to (i) prevent potential confusion with $X[j]$ and (ii) to avoid refering to
an $n$-partite complex as an $(n-1)$-dimensional $n$-partite complex, as was
done in e.g. [Opp18, DD19].

To keep our nomenclature simple, we will simply refer to a pure $n$-partite
simplicial complex of rank $n$ as an $n$-partite simplicial complex, i.e. we
will not consider $n$-partite complexes which are not pure.

For a face $\alpha\in X$ we introduce the notation,
$\typ(\alpha)=\set*{i\in[n]:\alpha\cap X[i]\neq\varnothing}$ for the type of
the face $\alpha$, i.e. the collection of sides of $X$ that $\alpha$
intersects.

For any $i\in[n]$ and $\beta\in X^{(n)}$ we will write $\beta_{i}\in X^{(1)}$
for the unique element of $\beta$ satisfying $\set{\beta_{i}}=\beta\cap X[i]$.
We will refer to $\beta_{i}$ as the $i$-th coordinate of $\beta$. We will also
write $\beta_{T}=\set*{\beta_{t}:t\in T}$ for all $T\subset[n]$. We extend
this notation to arbitrary faces $\alpha\in X$ and $T\subset\typ(\alpha)$. In
keeping with the view that a face $\alpha\in X$ with
$\typ(\alpha)=\set*{t_{1},\ldots,t_{k}}$ can be represented as a tuple
$(a_{t_{1}},\cdots,a_{t_{k}})$, we will favour the notation
$\alpha\oplus\alpha^{\prime}$ to denote the union of two faces
$\alpha,\alpha^{\prime}\in X$ with
$\typ(\alpha)\cap\typ(\alpha^{\prime})=\varnothing$ over the usual notation
$\alpha\cup\alpha^{\prime}$.

We observe that for facets $\beta\in X^{(n)}$, i.e. faces of maximal rank, we
have $\typ(\beta)=[n]$. Given, $\alpha\in X$ we recall that the link
$X_{\alpha}$ is defined as,

$X_{\alpha}=\set{(\beta\setminus\alpha)\in X:\beta\in X,\beta\supset\alpha}.$

The following observation is immediate,

######  Fact 7.

Let $X$ be an $n$-partite simplicial complex with sides $X[1],\ldots,X[n]$ and
$\alpha\in X^{(j)}$ for some $j\in[0,n]$. Then, the simplicial complex
$X_{\alpha}$ is an $(n-j)$-partite simplicial complex with sides
$X_{\alpha}[j]:=X[j]\cap X_{\alpha}^{(1)}$ for $j\in[n]\setminus\typ(\alpha)$.

For $T\subset[n]$, we will also introduce the notation $X[T]$ to refer to all
faces of $X$ of type $T$, i.e.

$X[T]=\set*{\alpha\in X:\typ(\alpha)=T}.$

Notice,

$X^{(n)}=X[1,\ldots,n]~{}~{}\textrm{and}~{}~{}X^{(j)}=\bigcup_{T\in\binom{[n]}{j}}X[T].$

#### Weighted Simplicial Complexes

A weighted simplicial complex $(X,\pi)$ of rank $n$ is a pure simplicial
complex of rank $n$ where $\pi:=\pi_{n}$ is a probablity distribution on
$X^{(n)}$ with full support, i.e. $\pi\in\triangle_{X^{(n)}}$ and
$\supp(\pi)=X^{(n)}$. For $j\in[0,n-1]$, we inductively define the probability
distributions $\pi_{j}:X^{(j)}\to\RR$ as

$\pi_{j}(\alpha)=\frac{1}{j+1}\sum_{\beta\in
X[j+1],\atop\beta\subset\alpha}\pi_{j+1}(\beta).$ (4)

The distribution $\pi_{j}(\alpha)$ can be thought as the probability of
sampling $\alpha\in X^{(j)}$ by first sampling some $\beta\sim\pi_{j+1}$ and
then removing one of the elements of $\beta$ uniformly at random. The
following proposition generalizes this observation, and follows from a simple
inductive argument (cf. [AL20, Proposition 2.3.1])

######  Proposition 2.12.

Let $(X,\pi)$ be a simplicial complex of rank $n$. For all $0\leq j\leq k\leq
n$ and $\alpha\in X^{(j)}$, one has

$\pi_{j}(\alpha)=\frac{1}{\binom{k}{j}}\sum_{\beta\supset\alpha,\atop\beta\in
X^{(k)}}\pi_{k}(\beta).$

Similarly, given a face $\alpha\in X^{(j)}$, we define the distribution
$\pi^{(\alpha)}$ on $X_{\alpha}^{(n-j)}$ by conditioning $\pi$ on the
containment of $\alpha$, i.e. for all $\alpha^{\prime}\in X_{\alpha}^{(n-j)}$
we have,

$\pi_{n-j}^{(\alpha)}(\alpha^{\prime})=\frac{\pi_{d}(\alpha\cup\alpha^{\prime})}{\sum_{\beta\in
X^{(n)},\atop\beta\supset\alpha}\pi_{n}(\beta)}=\frac{\pi_{d}(\alpha\cup\alpha^{\prime})}{\binom{n}{j}\cdot\pi_{j}(\alpha)},$
(5)

where the last part is due to Proposition 2.12. Analogously, we have

######  Proposition 2.13.

Let $(X,\pi)$ be a simplicial complex of rank $n$. Let $\alpha\in X^{(j)}$ and
$\tau\in X_{\alpha}^{(\ell)}$ be faces for some $0\leq\ell\leq j\leq n$. Then,

$\pi_{l}^{(\alpha)}(\tau)=\frac{\pi_{j+\ell}(\alpha\cup\tau)}{\binom{j+\ell}{\ell}\cdot\pi_{j}(\alpha)}.$

Of particular importance to us will be the link graph
$\Emm_{\alpha}\in\RR^{X^{(1)}_{\alpha}\times X^{(1)}_{\alpha}}$ given any
$\alpha\in X^{(\leq n-2)}$. We recall that for all distinct pairs of vertices
$x,y\in X_{\alpha}^{(1)}$, we have

$\Emm_{\alpha}(x,y)=\pi^{(\alpha\cup\set
x)}(y)=\frac{\Pr_{\omega\sim\pi_{n}}\sqbr*{\left.\omega\supset\alpha\cup\set{x,y}~{}\right|~{}\omega\supset\alpha\cup\set
x}}{n-|\alpha|-1},$ (link)

and $\Emm_{\alpha}(x,x)=0$ for all $x\in X_{\alpha}^{(1)}.$

###  2.5 Higher Order Random Walks on Simplicial Complexes

Let $(X,\pi)$ be a simpicial complex of rank $n$. The up-down walk
$\Udw_{\ell\lra n}:=\UpDown_{\ell\lra n}(X,\pi)$ between the $\ell$-th and
$n$-th levels, $X^{(\ell)}$ and $X^{(n)}$ respectively, is defined as the
following random walk on $X^{(\ell)}$: Starting from an arbitrary face
$\widehat{\omega}^{(0)}\in X^{(\ell)}$ for all $t\geq 1$ move from
$\widehat{\omega}^{(t-1)}$ to $\widehat{\omega}^{(t)}$ according to the
following simple rule, 0.85Update Rule For the Up-Down Walk, $\Udw_{\ell\lra
n}$

  * •

sample $\omega\sim\pi_{n}$, conditional on
$\omega\supset\widehat{\omega}^{(t-1)}$,

  * •

draw a uniformly subset among all the subsets of $\omega$ of size $\ell$, and
output it as $\widehat{\omega}$.

Similarly, the down-up walk $\Duw_{n\lra\ell}$ between the $n$-th and
$\ell$-th levels, $X^{(n)}$ and $X^{(\ell)}$ respectively, as the following
random walk $X^{(n)}$: Starting from an arbitrary $\omega^{(0)}\in X^{(n)}$
and moves from $\omega^{(t-1)}$ to $\omega^{(t)}$ according to the following
simple rule, 0.85Update Rule for the Down-Up Walk, $\Duw_{n\lra\ell}$

  * •

draw a subset $\widehat{\omega}$ of $\omega$ of size $\ell$, uniformly at
random,

  * •

draw a subset $\omega\sim\pi$ conditioned on containing $\widehat{\omega}$,
and output it as $\omega^{(t)}$.

It is well known, [AL20, DK17, DDFH18], that the random walks
$\Duw_{n\lra\ell}$ and $\Udw_{\ell\lra n}$ can be decomposed as a product of
random down- and up-movements on $X$. Formally, for $0\leq\ell\leq k\leq n$,
we define the up-walk $\Upo_{\ell\to k}:=\Upp_{\ell\to k}(X,\pi)$ and the
down-walk $\Doo_{k\to\ell}:=\Down_{k\to\ell}(X,\pi)$ as the following random
walks,

$\displaystyle\Upo_{\ell\to k}\parens*{\widehat{\omega},\omega}$
$\displaystyle~{}=~{}\pi_{k-\ell}^{(\widehat{\omega})}(\omega)=\frac{\one[\omega\supset\widehat{\omega}]\cdot\Pr_{\widetilde{\omega}\sim\pi_{n}}\sqbr*{\widetilde{\omega}\supset\omega\mid\widetilde{\omega}\supset\widehat{\omega}}}{\binom{n-\ell}{k-\ell}},$
(up-walk) $\displaystyle\Doo_{k\to\ell}\parens*{\omega,\widehat{\omega}}$
$\displaystyle~{}=~{}\frac{\one\sqbr*{\widehat{\omega}\subset\omega}}{\binom{k}{\ell}}.$
(down-walk)

######  Fact 8 (Folklore).

Let $(X,\pi)$ be a simplical complex of rank $n$, then writing
$\Duw_{n\lra\ell}:=\DownUp_{n\lra\ell}(X,\pi),\Udw_{\ell\lra
n}:=\Udw_{\ell\lra n}(X,\pi)$, $\Upo_{\ell\to n}=\Upp_{\ell\to n}(X,\pi)$, and
$\Doo_{n\to\ell}=\Down_{n\to\ell}(X,\pi)$ for the down-up, up-down, up- and
down-walks between the $n$-th and $\ell$-th levels of $X$ respectively, we
have

  1. 1.

$\parens*{\Upo_{\ell\to n}}^{*}=\Doo_{n\to\ell}$, i.e. the operators
$\Upo_{\ell\to n}$ and $\Doo_{n\to\ell}$ are adjoint operators with respect to
the measures $\pi_{n}$ and $\pi_{\ell}$,

  2. 2.

$\Udw_{\ell\lra n}=\Upo_{\ell\to n}\Doo_{n\to\ell}$ – in particular the
operator $\Udw_{\ell\lra n}$ is PSD,

  3. 3.

$\Duw_{n\lra\ell}=\Doo_{n\to\ell}\Upo_{\ell\to n}$ – in particular the
operator $\Duw_{n\lra\ell}$ is PSD.

For any $\widehat{\omega}\in X$ and any $0\leq\ell\leq
n^{\prime}=n-|\widehat{\omega}|$, we will write
$\Upo_{\widehat{\omega},\ell\to
n^{\prime}},\Doo_{\widehat{\omega},n^{\prime}\to\ell},\Udw_{\widehat{\omega},\ell\lra
n^{\prime}},$ and $\Duw_{\widehat{\omega},n^{\prime}\lra\ell}$ for the
corresponding up, down, up-down, and down-up walks in the complex
$(X_{\widehat{\omega}},\pi^{\widehat{\omega}})$.

###  2.6 Local to Global Analysis

Given a simplicial complex $(X,\pi)$ of rank $n$, we define the local
$\Phi$-entropy contraction factor $\lc_{\Phi}(\widehat{\omega})$ for any
$\widehat{\omega}\in X^{(\leq r-2)}$ as follows,

$\lc_{\Phi}(\widehat{\omega}):=\sup\set*{\left.\frac{\Ent^{\Phi}_{\pi^{(\widehat{\omega})}_{1}}(\Upo_{\widehat{\omega},1\to
n^{\prime}}\gee)}{\Ent^{\Phi}_{\pi^{(\widehat{\omega})}_{n^{\prime}}}(\gee)}~{}\right|~{}\gee\in\RR^{X_{\widehat{\omega}}^{(n^{\prime})}}~{}~{}\textrm{and}~{}~{}n^{\prime}=n-|\widehat{\omega}|.}$
(local $\Phi$-entropy contraction)

Equivalently, $\lc_{\Phi}(\widehat{\omega})\in\RR_{>0}$ is the smallest
constant satisfying the equality

$\Ent^{\Phi}_{\pi^{\widehat{\omega}}_{1}}(\Upo_{\widehat{\omega},1\to
n^{\prime}}\gee)\leq\lc_{\Phi}(\widehat{\omega})\cdot\Ent^{\Phi}_{\pi^{(\widehat{\omega})}_{n^{\prime}}}(\gee)~{}~{}\textrm{for
all}~{}~{}\gee\in\RR^{X_{\widehat{\omega}}^{(n^{\prime})}}~{}~{}\textrm{where}~{}~{}n^{\prime}=n-|\widehat{\omega}|.$

When $\Phi(t)=t\log t$, we will simply write $\lec(\widehat{\omega})$ in place
of $\lc_{\Phi}(\widehat{\omega})$. We also make the following observation for
the special case $\Phi(t)=t^{2}$, i.e. when $\Ent^{\Phi}_{\bullet}(\bullet)$
equals the variance functional $\Var_{\bullet}(\bullet)$. The following
proposition is well understood,

######  Proposition 2.14.

Let $(X,\pi)$ be a simplicial complex of rank $n$. Then, for the choice of
$\Phi(t)=t^{2}$, for any $\widehat{\omega}\in X^{(\leq n-2)}$ we have

$\lc_{\Phi}(\widehat{\omega})=\frac{1}{n-|\widehat{\omega}|}+\frac{n-|\widehat{\omega}|-1}{n-|\widehat{\omega}|}\cdot\lambda_{2}(\Emm_{\widehat{\omega}}),$

where $\Emm_{\widehat{\omega}}$ is the link graph of $\widehat{\omega}$.

We provide a proof for Proposition 2.14 in Section A.3.

A crucial tool we will be using in Section 4 is the so called Garland method,
due to [Gar73]. To this end, we define the localization
$\eff|_{\widehat{\omega}}\in\RR^{X_{\widehat{\omega}}(k-j)}$ of a function
$\eff\in\RR^{X^{(k)}}$ on a link $\widehat{\omega}\in X^{(j)}$ for $j\leq k$
as the following function,

$\eff|_{\widehat{\omega}}(\alpha)=\eff(\widehat{\omega}\sqcup\alpha)~{}~{}\textrm{for
all}~{}~{}\alpha\in X_{\widehat{\omega}}^{(k-j)}.$ (localization)

We first observe that by appealing to the chain rule for the $\Phi$-entropy,
one can obtain a convenient expression for it in terms of localizations.

######  Fact 9 (Chain Rule for $\Phi$-Entropy).

Let $(X,\pi)$ be a simplicial complex of rank $n$. For all $0\leq\ell\leq
r\leq n$ and non-negative $\eff\in\RRp^{X^{(r)}}$, we have

$\Ent^{\Phi}_{\pi_{r}}(\eff)=\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Ent^{\Phi}_{\pi_{\ell}}(\eff|_{\widehat{\omega}})+\Ent^{\Phi}_{\widehat{\omega}\sim\pi_{\ell}}\parens*{\Exp_{\alpha\sim\pi^{(\widehat{\omega})}_{r-\ell}}\eff|_{\widehat{\omega}}(\alpha)}.$

In particular,

$\Ent^{\Phi}_{\pi_{r}}(\eff)=\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Ent^{\Phi}_{\pi_{\ell}}(\eff|_{\widehat{\omega}})+\Ent_{\pi_{\ell}}\parens*{\Upo_{\ell\to
r}\eff},$

where $\Upo_{\ell\to r}:=\Upp_{\ell\to r}(X,\pi)$ is the up-walk on $X$

######  Proof 2.15.

The result follows by straight-forward computation,

$\displaystyle\Ent^{\Phi}_{\pi_{r}}(\eff)$
$\displaystyle~{}=~{}\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Exp_{\alpha\sim\pi^{(\widehat{\omega})}_{r-\ell}}\Phi(\eff|_{\widehat{\omega}}(\alpha))-\Phi\parens*{\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Exp_{\alpha\sim\pi^{(\widehat{\omega})}_{r-\ell}}\eff|_{\widehat{\omega}}(\alpha)},$
$\displaystyle~{}=~{}\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Ent^{\Phi}_{\pi^{(\widehat{\omega})}_{r-\ell}}(\eff|_{\widehat{\omega}})+\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Phi\parens*{\Exp_{\alpha\sim\pi^{(\widehat{\omega})}_{r-\ell}}\eff|_{\widehat{\omega}}(\alpha)}-\Phi\parens*{\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Exp_{\alpha\sim\pi^{(\widehat{\omega})}_{r-\ell}}\eff|_{\widehat{\omega}}(\alpha)},$
$\displaystyle~{}=~{}\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Ent^{\Phi}_{\pi_{\ell}}(\eff|_{\widehat{\omega}})+\Ent^{\Phi}_{\widehat{\omega}\sim\pi_{\ell}}\parens*{\Exp_{\alpha\sim\pi^{(\widehat{\omega})}_{r-\ell}}\eff|_{\widehat{\omega}}(\alpha)}.$

The second statement follows from the definition of the up-walk $\Upo_{\ell\to
r}$.

We also recall the following identities,

######  Lemma 2.16.

Let $(X,\pi)$ be a simplicial complex of rank $n$. Writing $\Duw_{n\lra
r}=\DownUp_{n\lra r}(X,\pi)$, $\Udw_{n-1}=\UpDown_{n-1\lra n}(X,\pi)$, and
$\Emm_{\widehat{\omega}}$ for the link of the face $\widehat{\omega}\in
X^{(\leq n-2)}$, for all $\eff\in\RR^{X^{(n)}}$ and $\ell\leq r\leq n$, we
have

  1. 1.

$\inpr*{\eff,\eff}_{\pi_{n}}=\Exp_{\widehat{\omega}\sim\pi_{\ell}}\inpr*{\eff|_{\widehat{\omega}},\eff|_{\widehat{\omega}}}_{\pi_{n-\ell}^{(\widehat{\omega})}}$,

  2. 2.

$\inpr*{\eff,\Duw_{n\lra
r}\eff}_{\pi_{n}}=\Exp_{\widehat{\omega}\sim\pi_{\ell}}\inpr*{\eff|_{\widehat{\omega}},\Duw_{\widehat{\omega},n-\ell\lra
r-\ell}\eff|_{\widehat{\omega}}}_{\pi_{n-\ell}^{(\widehat{\omega})}}$,

  3. 3.

$\inpr*{\eff,\Udw_{n-1}\eff}_{\pi_{n}}=\Exp_{\widehat{\omega}\sim\pi_{n-2}}\parens*{\inpr*{\eff|_{\widehat{\omega}},\parens*{\frac{\Ide}{n}+\frac{n-1}{n}\cdot\Emm_{\widehat{\omega}}}\eff|_{\widehat{\omega}}}_{\pi_{1}^{(\widehat{\omega})}}}$

Items (1) and (3) are folklore results, we refer the reader to [AL20, Lemma
3.7] for a proof. The second item is a straight-forward consequence of the
definition of the up-walk $\Upo_{\bullet_{2}\to\bullet_{1}}$ and that
$\Duw_{\bullet_{1}\lra\bullet_{2}}=\Doo_{\bullet_{1}\to\bullet_{2}}\Upo_{\bullet_{2}\to\bullet_{1}}$.
In particular, for any $\widehat{\omega}\in X^{(\ell)}$ and any
$\omega\supset\widehat{\omega}$ we have by the definition of the up-walk,

$[\Upo_{\widehat{\omega},r-\ell\to
n-\ell}\eff|_{\widehat{\omega}}](\omega\setminus\widehat{\omega})=[\Upo_{r\to
n}\eff](\omega).$ (6)

We recall the following result due to [Lee23],

######  Lemma 2.17 (Theorem 3.5, [Lee23]).

Let $(X,\pi)$ be an $n$-partite simplicial complex and let $0\leq k<n$.
Suppose we have $\EC(\Upo_{n-1\to n})\geq(Cn)^{-1}$ for some $C\in\RRpp$.
Then, we have

$\EC\parens*{\Upo_{k\to k+1}}\geq\frac{1}{(k+1)(C+1)},$

where we have written $\Upo_{\ell\to k}=\Upp_{\ell\to k}\parens*{X,\pi}$ for
the up-walk between $X^{(\ell)}$ and $X^{(k)}$

##  3 Expanderized Random Walks

Let $(X,\pi)$ be an $n$-partite simplicial complex. For any $\ell\leq n$, the
up-down walk $\Udw_{\ell\lra n}:=\UpDown_{\ell\lra n}(X,\pi)$ on the $\ell$-th
level $X^{(\ell)}$ of $X$ introduced in Section 2.5 admits the following
alternative description: Starting from an arbitrary face
$\widehat{\omega}^{(0)}\in X^{(\ell)}$ move from $\widehat{\omega}^{(t-1)}$ to
$\widehat{\omega}^{(t)}$ according to the following simple rule, 0.85Update
Rule for the Up-Down Walk, $\Udw_{\ell\lra n}$

  * •

sample $\omega\sim\pi$, conditional on
$\omega\supset\widehat{\omega}^{(t-1)}$,

  * •

sample $S\sim\uni_{\binom{[n]}{\ell}}$,

  * •

output $\widehat{\omega}^{(t)}=\omega_{S}$.

We will expanderize the up-down walk $\Udw_{\ell\lra n}$ in the following
manner: Given a $k$-regular labelled graph $H$ on the vertex set
$\binom{[n]}{\ell}$, we will denote the $a$-th neighbor of vertex $v$ by
$\Out_{H}(v,a)$. We define the expanderized up-down walk $\Papx_{\ell\lra
n}=\UpDown_{\ell\lra n}(X,\pi,H)$ as the walk which starts from an arbitrary
face $\widehat{\omega}^{(0)}$ and moves from $\widehat{\omega}^{(t-1)}$ to
$\widehat{\omega}^{(t)}$ according to the following simple rule, 0.85Update
Rule for the Expanderized Up-Down Walk, $\Papx_{\ell\lra n}$

  * •

sample $\omega\sim\pi$, conditional on
$\omega\supset\widehat{\omega}^{(t-1)}$,

  * •

sample $a\sim\uni_{[k]}$ and set
$S=\Out_{H}(\typ(\widehat{\omega}^{(t-1)}),a)$,888Where we recall that the
type of $\widehat{\omega}$ is the sides of the simplicial complex that
$\widehat{\omega}$ intersects

  * •

output $\widehat{\omega}^{(t)}=\omega_{S}$.

Similarly, the down-up walk $\Duw_{n\lra\ell}$ between the $n$-th level
$X^{(n)}$ and the $\ell$-th level $X^{(\ell)}$ of an $n$-partite simplicial
complex $(X,\pi)$ introduced in Section 2.5 admits the following alternative
description: Start from $\omega^{(0)}\in X^{(n)}$ and move from
$\omega^{(t-1)}$ to $\omega^{(t)}$ according to the following simple rule,
0.85Update Rule for the Down-Up Walk, $\Duw_{n\lra\ell}$

  * •

sample $S\sim\uni_{\binom{[n]}{\ell}}$ uniformly at random,

  * •

set $\widehat{\omega}=\omega_{S}$,

  * •

set $\omega^{(t)}$ to be a random face drawn from $\pi$, conditional on
containing $\widehat{\omega}$.

Similarly, we define the expanderized down-up walk
$\Paqx_{n\lra\ell}=\DownUp_{n\lra\ell}(X,\pi,H)$ to be the random walk on
$X^{(n)}\times\binom{[n]}{\ell}$, starting from an arbitrary face-subset pair
$(\omega^{(0)},S^{(0)})$ and move from $(\omega^{(t-1)},S^{(t-1)})$ to
$(\omega^{(t)},S^{(t)})$ according to the following simple rule, 0.85Update
Rule for the Expanderized Down-Up Walk, $\Paqx_{n\lra\ell}$

  * •

sample $a\sim\uni_{[k]}$ and set $S^{\prime}=\Out_{H}(S^{(t-1)},a)$,

  * •

set $\widehat{\omega}=\omega_{S^{\prime}}$,

  * •

set $\omega^{(t)}\sim\pi$ to be a random face conditional on containing
$\widehat{\omega}$,

  * •

sample $b\sim\uni_{[k]}$ and set $S^{(t)}=\Out_{H}(S^{(t-1)},b)$,

  * •

output $(\omega^{(t)},S^{(t)})$.

For convenience we also define the expanderized down- and up-walks given a
degree regular labelled graph $H=(\binom{[n]}{\ell},E)$

$\Qdo_{n\to\ell}=\Down_{n\to\ell}(X,\pi,H)\in\RR^{(X^{(n)}\times\binom{[n]}{\ell})\times
X^{(\ell)}}~{}~{}\textrm{and}~{}~{}\Qup_{\ell\to
n}=\Upp_{\ell\to[n]}(X,\pi,H)\in\RR^{X^{(\ell)}\times(X^{(n)}\times\binom{[n]}{\ell})},$

as follows,

$\Qdo_{n\to\ell}((\omega,S),\widehat{\omega})=\frac{\one[S\sim_{H}\typ(\widehat{\omega})]}{k}\cdot\one[\omega\supset\widehat{\omega}]~{}~{}\textrm{for
all}~{}~{}\omega\in X^{(n)},\widehat{\omega}\in
X^{(\ell)},S\in\binom{[n]}{\ell},$

and $\Qup_{\ell\to n}=\parens*{\Qdo_{n\to\ell}}^{*}$ where the adjoint is
taken with respect to the distributions
$\pi_{n}\tensor\uni_{\binom{[n]}{\ell}}$ and $\pi_{\ell}$, i.e.

$\Qup_{\ell\to
n}\parens*{\widehat{\omega},(\omega,S)}=\frac{\one[S\sim_{H}\typ(\widehat{\omega})]}{k}\cdot\Pr_{\widetilde{\omega}\sim\pi_{n}}\sqbr*{\widetilde{\omega}=\omega\mid\omega\supset\widehat{\omega}}~{}~{}\textrm{for
all}~{}~{}\omega\in X^{(n)},\widehat{\omega}\in
X^{(\ell)},S\in\binom{[n]}{\ell},$

and the notation $T\sim_{H}S$ is used to denote the adjacency relation in the
graph $H$, i.e. $\set*{S,T}\in E(H)$.

We summarize the random movements described by the expanderized up- and down-
walks in words as follows: The expanderized down-walk $\Qdo_{n\to\ell}$ first
samples a random neighbor of $T$ of $S$ in $\binom{[n]}{\ell}$, and then
restricts the coordinates of $\omega$ to $T$, i.e. moves to $\omega_{T}$. The
expanderized up-walk $\Qup_{\ell\to n}$ on the other hand first samples a
facet $\omega\in X^{(n)}$ from $\pi$ conditional on containing
$\widehat{\omega}$ and after picking a random neighbor $S$ of
$\typ(\widehat{\omega})$ in $H$ moves to $(\omega,S)$.

######  Proposition 3.1.

For any $n$-partite pure simplicial complex $(X,\pi)$ and a $k$-regular
labelled graph $H=(\binom{[n]}{\ell},E)$, writing
$\Qdo_{n\to\ell}=\Down_{n\to\ell}(X,\pi,H)$ and $\Qup_{\ell\to
n}=\Upp_{\ell\to n}(X,\pi,H)$ we have,

$\parens*{\pi_{n}\tensor\uni_{\binom{[n]}{\ell}}}\Qdo_{n\to\ell}=\pi_{\ell}~{}~{}\textrm{and}~{}~{}\pi_{\ell}\Qup_{\ell\to
n}=\pi_{n}\tensor\uni_{\binom{[n]}{\ell}}.$

######  Proof 3.2.

Let $(\omega,S)\sim\pi_{n}\tensor\uni_{\binom{[n]}{\ell}}$ be a random sample.
Notice that a random neighbor of $S$ in $H$ is still distributed uniformly at
random as the uniform distribution stationary for the random walk over a
$k$-regular graph, q.v. 2. Thus, conditional on $\omega$, a single step of
$\Qdo_{n}$ ends up restricting $\omega$ to a random set of coordinates $S$ –
this precisely yields the distribution $\pi_{\ell}$, q.v. Proposition 2.12.

The second statement follows since $\Qup_{\ell\to n}$ is the adjoint operator,
q.v. Proposition 2.1.

The following is easy to verify,

######  Corollary 3.3.

For any $n$-partite simplicial complex $(X,\pi)$ and $k$-regular labelled
graph $H=\parens*{\binom{[n]}{\ell},E)}$,

  * •

$\UpDown_{\ell\lra n}(X,\pi,H^{2})=\Upp_{\ell\to
n}(X,\pi,H)\cdot\Down_{n\to\ell}(X,\pi,H)$,

  * •

$\DownUp_{n\lra\ell}(X,\pi,H)=\Down_{n\to\ell}(X,\pi,H)\cdot\Upp_{\ell\to
n}(X,\pi,H)$.

We now summarize several useful properties of the expanderized up- and down-
walks,

######  Corollary 3.4.

Let $(X,\pi)$ be an $n$-partite complex and $H=(\binom{[n]}{\ell},E)$ a
$k$-regular graph. For any $\ell\leq n$, writing $\Papx_{\ell\lra
n}=\UpDown_{\ell\lra n}(X,\pi,H^{2})$,
$\Paqx_{n\lra\ell}=\DownUp_{n\lra\ell}(X,\pi,H)$
$\Qdo_{n\to\ell}=\Down_{n\to\ell}(X,\pi,H)$ and $\Qup_{\ell\to
n}=\Upp_{\ell\to n}(X,\pi,H)$ we have,

  1. 1.

$(\pi_{n}\tensor\uni_{\binom{[n]}{\ell}})\Paqx_{n\lra\ell}=\pi_{n}\tensor\uni_{\binom{[n]}{\ell}}$,
i.e. $\pi_{n}\tensor\uni_{\binom{[n]}{\ell}}$ is the stationary distribution
of $\Paqx_{n\lra\ell}$,

  2. 2.

$\pi_{\ell}\Papx_{\ell\lra n}=\pi_{\ell}$, i.e. $\pi_{\ell}$ is the stationary
distribution of $\Papx_{\ell\lra n}$.

  3. 3.

$\Paqx_{n\lra\ell}$ and $\Papx_{\ell\lra n}$ are PSD operators.

  4. 4.

$\Papx_{\ell\lra n}$ and $\Paqx_{n\lra\ell}$ are self-adjoint operators.

Since in our proofs it will be more convenient to use $\Papx_{\ell\lra
n}:=\UpDown_{\ell\lra n}(X,\pi,H)$ directly, initialized with $H$ and not
$H^{2}$, we also note the following.

######  Proposition 3.5.

Let $(X,\pi)$ be an $n$-partite complex and $H=(\binom{[n]}{\ell},E)$ a
$k$-regular graph. Then, the expanderized up-down walk $\Papx_{\ell\lra
n}:=\UpDown_{\ell\lra n}(X,\pi,H)$ has the stationary distribution
$\pi_{\ell}$ and is reversible.

As Corollary 3.4 reaches the same end by replacing $H$ with $H^{2}$ we will
postpone the proof of Proposition 3.5 to Section A.4.

Now, we present the results we prove for expanderized random walks. Our first
result shows that the expanderized up-down walk approximates the usual up-down
walk in the operator norm,

######  Theorem 3.6.

Let $(X,\pi)$ be an $n$-partite simplicial complex and let $H$ be a
$k$-regular labelled graph on the vertex set $\binom{[n]}{\ell}$. Writing
$\Papx_{\ell\lra n}:=\UpDown(X,\pi,H)$ and $\Udw_{\ell\lra n}:=\UpDown(X,\pi)$
for the expanderized- and the regular up-down walks on $X^{(\ell)}$, we have

$\norm*{\Papx_{\ell\lra n}-\parens*{1-\lambda(H)}\cdot\Udw_{\ell\lra
n}}_{\opp,\pi_{\ell}}\leq\lambda(H).$

We present the proof of Theorem 3.6 in Section 3.1.

Theorem 3.6 immediately implies the following bounds for the spectral gap of
expanderized walks,

######  Corollary 3.7.

Let $(X,\pi)$ be an $n$-partite simplicial complex and let $H$ be a
$k$-regular labelled graph on the vertex set $\binom{[n]}{\ell}$. Writing
$\Papx_{\ell\lra n}:=\UpDown(X,\pi,H)$, $\Udw_{\ell\lra n}=\UpDown_{\ell\lra
n}(X,\pi)$, $\Paqx_{n\lra\ell}=\DownUp(X,\pi,H)$, and
$\Duw_{n\lra\ell}=\DownUp_{n\lra\ell}(X,\pi)$, we have

$\displaystyle\Gap\parens*{\Papx_{\ell\lra n}}$
$\displaystyle~{}\geq~{}\Gap\parens*{\Udw_{\ell\lra n}}\cdot\Gap^{\star}(H),$
$\displaystyle\Gap\parens*{\Paqx_{n\lra\ell}}$
$\displaystyle~{}\geq~{}\Gap\parens*{\Duw_{n\lra\ell}}\cdot\Gap^{\star}(H^{2}),$

where $\Gap^{\star}(G)=1-\lambda(G)$ and $\lambda(G)$ denotes the two-sided
expansion of the graph $G$.

Unfortunately, a bound on the spectral gap is in many settings not enough to
obtain optimal mixing time bounds. We show however, that Theorem 3.6 allows us
to transfer log-Sobolev inequalities (LSI) for the usual up-down walks to the
expanderized up-down walks,

######  Corollary 3.8.

Let $(X,\pi)$ be an $n$-partite simplicial complex and let $H$ be a
$k$-regular labelled graph on the vertex set $\binom{[n]}{\ell}$. Writing
$\Papx_{\ell\lra n}:=\UpDown_{\ell\lra n}(X,\pi,H)$ and $\Udw_{\ell\lra
n}:=\UpDown_{\ell\lra n}(X,\pi)$ for the up-down walk on $X^{(\ell)}$, we have

$\LS\parens*{\Papx_{\ell\lra n}}\geq\LS\parens*{\Udw_{\ell\lra
n}}\cdot\Gap^{\star}(H),$

where $\Gap^{\star}(H)=1-\lambda(H)$ and $\lambda(H)$ denotes the two-sided
expansion of the graph $H$.

We will prove Corollary 3.8 in Section 3.3. We state a convenient corollary of
Corollary 3.8 which immediately follows from Lemma 2.7, Corollary 3.4, and the
data processing inequality 6,

######  Corollary 3.9.

Let $(X,\pi)$ be an $n$-partite simplicial complex and let $H$ be a
$k$-regular labelled graph on the vertex set $\binom{[n]}{\ell}$. Then,
writing $\Qdo_{n\lra\ell}=\Down_{n\to\ell}(X,\pi,H)$ and $\Udw_{\ell\lra
n}=\UpDown_{\ell\lra n}(X,\pi)$ we have,

$\EC(\Qdo_{n\lra\ell})\geq\LS(\Udw_{\ell\lra n})\cdot\Gap^{\star}(H^{2}).$

In particular, we have for $\Papx_{\ell\lra n}:=\UpDown_{\ell\lra
n}(X,\pi,H^{2})$ and $\Paqx_{n\lra\ell}=\DownUp_{n\lra\ell}(X,\pi,H)$,

$\EC(\Papx_{\ell\lra n})\geq\LS(\Udw_{\ell\lra
n})\cdot\Gap^{\star}(H^{2})~{}~{}\textrm{and}~{}~{}\EC(\Paqx_{n\lra\ell})\geq\LS(\Udw_{\ell\lra
n})\cdot\Gap^{\star}(H^{2}),$

where $\Gap^{\star}(H^{2})=1-\lambda(H^{2})$ and $\lambda(H^{2})$ denotes the
two-sided expansion of the graph $H^{2}$.

As we will see in Section 5, Corollary 3.9 will indeed allow us to prove
optimal mixing time bounds for the expanderized walks in many cases of
interest.

###  3.1 Expanderized Up-Down Walk Approximates the Up-Down Walk Well, Proof
of Theorem 3.6

######  Proof 3.10 (Proof of Theorem 3.6 ).

For convenience, we will write $\Papx:=\Papx_{\ell\lra n}$ and
$\Udw:=\Udw_{\ell\lra n}$. Let $\Emm$ denote the random-walk matrix of the
graph $H$ where each transition occurs with the probability $1/k$ and $\Jay$
for the random-walk matrix of the clique over $\binom{[n]}{\ell}$ with self-
loops, i.e. $\Jay=\one\one^{\top}/\binom{[n]}{\ell}$. We will write,
$\lambda:=\lambda(\Emm).$

Let $S\in\binom{[n]}{\ell}$ be arbitrary and suppose some $\bar{\omega}\in
X^{(\ell)}$ is given such that $\typ(\bar{\omega})=S$.

For all $\eff\in\RR^{X^{(\ell)}}$, we have

$[\Papx\eff](\bar{\omega})=\sum_{\widehat{\omega}\in
X[S^{c}]}\Pr_{\omega\sim\pi}[\omega_{S^{c}}=\widehat{\omega}\mid\omega_{S}=\bar{\omega}]\cdot\sum_{a\in[k]}\frac{\eff\parens*{(\bar{\omega}\oplus\widehat{\omega})_{\Out_{H}(S,a)}}}{k}.$

Similarly, we have

$[\Udw\eff](\bar{\omega})=\sum_{\widehat{\omega}\in
X[S^{c}]}\Pr_{\omega\sim\pi}[\omega_{S^{c}}=\widehat{\omega}\mid\omega_{S}=\bar{\omega}]\sum_{T\in\binom{[n]}{\ell}}\frac{\eff\parens*{(\bar{\omega}\oplus\widehat{\omega})_{T}}}{\binom{n}{\ell}}.$

For any given facet $\omega\in X^{(n)}$ we define the function
$\gee_{\omega}\in\RR^{\binom{[n]}{\ell}}$ as,
$\gee_{\omega}(T)=\eff\parens*{\omega_{T}}$.

We have,

$[\Emm\gee_{\omega}](T)=\sum_{a\in[k]}\frac{\eff\parens*{\omega_{\Out_{H}(T,a)}}}{k}~{}~{}\textrm{and}~{}~{}[\Jay\gee_{\omega}](i)=\sum_{T\in\binom{[n]}{\ell}}\frac{\eff\parens*{\omega_{T}}}{\binom{n}{\ell}}.$

Thus, we have

$\displaystyle[\Papx\eff](\bar{\omega})$
$\displaystyle~{}=~{}\sum_{\widehat{\omega}\in
X[S^{c}]}\Pr_{\omega\sim\pi}[\omega_{S^{c}}=\widehat{\omega}\mid\omega_{S}=\bar{\omega}]\cdot[\Emm\gee_{\bar{\omega}\oplus\widehat{\omega}}](S),$
(7) $\displaystyle[\Udw\eff](\bar{\omega})$
$\displaystyle~{}=~{}\sum_{\widehat{\omega}\in
X[S^{c}]}\Pr_{\omega\sim\pi}[\omega_{S^{c}}=\widehat{\omega}\mid\omega_{S}=\bar{\omega}]\cdot[\Jay\gee_{\bar{\omega}\oplus\widehat{\omega}}](S).$
(8)

In particular combining Eq. 7 and Eq. 8 and noticing that for $\omega\sim\pi$
the law of $\omega_{S^{c}}$ conditional on $\omega_{S}=\bar{\omega}$ is given
by $\pi_{n-\ell}^{(\widehat{\omega})}$,

$\displaystyle\norm*{(\Papx-(1-\lambda)\Udw)\eff}^{2}_{\pi_{\ell}}$
$\displaystyle~{}=~{}\Exp_{\bar{\omega}\sim\pi_{\ell}}\parens*{\Exp_{\widehat{\omega}\sim\pi^{(\bar{\omega})}_{n-\ell}}\sqbr*{[\Emm\gee_{\bar{\omega}\oplus\widehat{\omega}}](\typ(\bar{\omega}))-(1-\lambda)[\Jay\gee_{\bar{\omega}\oplus\widehat{\omega}}](\typ(\bar{\omega}))}}^{2},$
$\displaystyle~{}\leq~{}\Exp_{\bar{\omega}\sim\pi_{\ell}}\Exp_{\widehat{\omega}\sim\pi^{(\bar{\omega})}_{n-\ell}}\sqbr*{\parens*{[\Emm\gee_{\bar{\omega}\oplus\widehat{\omega}}](\typ(\bar{\omega}))-(1-\lambda)[\Jay\gee_{\bar{\omega}\oplus\widehat{\omega}}](\typ(\bar{\omega}))}^{2}}.$

where the last inequality is obtained by appealing to Jensen’s inequality and
the convexity of $t\to t^{2}$.

Now, we observe the law of $\bar{\omega}\oplus\widehat{\omega}$ obtained by
first sampling $\bar{\omega}\sim\pi_{\ell}$ and then
$\widehat{\omega}\sim\pi^{(\bar{\omega})}$ is given by $\pi$. Furthermore, any
$\omega\in X^{(n)}$ occurs exactly $\binom{[n]}{\ell}$ times in the
expectation above – once for each $S\in\binom{[n]}{\ell}$ acting as
$\typ(\bar{\omega})$, which happens with probability $\binom{n}{\ell}^{-1}$.
Thus,

$\displaystyle\norm*{(\Papx-(1-\lambda)\Udw)\eff}^{2}_{\pi_{\ell}}$
$\displaystyle~{}\leq~{}\Exp_{\omega\sim\pi_{n}}\sqbr*{\Exp_{S\sim\uni_{\binom{[n]}{\ell}}}\parens*{[(\Emm-(1-\lambda)\Jay)\gee_{\omega}](S)}^{2}},$
$\displaystyle~{}\leq~{}\Exp_{\omega\sim\pi_{n}}\sqbr*{\lambda^{2}\cdot\norm{\gee_{\omega}}^{2}_{\uni_{\binom{[n]}{\ell}}}}$

where the last inequality is due to
$\norm{\Emm-(1-\lambda)\Jay}_{\opp,\uni_{\binom{[n]}{\ell}}}\leq\lambda$ as
$\lambda(\Emm)\leq\lambda$!

Now, we finally note

$\Exp_{\omega\sim\pi}\sqbr*{\norm{\gee_{\omega}}^{2}_{\uni_{\binom{[n]}{\ell}}}}=\Exp_{\omega\sim\pi}\sqbr*{\frac{1}{\binom{n}{\ell}}\sum_{S\in\binom{[n]}{\ell}}\eff(\omega_{S})^{2}}=\Exp_{\bar{\omega}\sim\pi_{\ell}}\eff(\bar{\omega})^{2}=\norm{\eff}^{2}_{\pi_{\ell}},$

The last equality is due to the observation that first sampling
$\omega\sim\pi$ and then outputting $\omega_{S}$ for
$S\sim\uni_{\binom{[n]}{\ell}}$ picked uniformly at random amounts to simply
sampling $\bar{\omega}\sim\pi_{\ell}$, q.v. Proposition 2.12.

In particular,

$\norm*{(\Papx-(1-\lambda)\Udw)\eff}_{\pi_{\ell}}\leq\lambda\cdot\norm{\eff}_{\pi_{\ell}}.$

As $\eff$ was picked arbitrarily, this allows us to conclude the proof of our
theorem by appealing to the definition of the operator norm.

###  3.2 A Spectral Gap Bound For Expanderized Higher Order Random Walks,
Proof of Corollary 3.7

######  Proof 3.11 (Proof of Corollary 3.7).

Suppose $\eff\in\RR^{X^{(\ell)}}$ is a unit vector, i.e.
$\norm*{\eff}_{\pi_{\ell}}=1$, satisfying $\Papx_{\ell\lra
n}\eff=\lambda(\Papx_{\ell\lra n})\eff.$ In particular,
$\inpr*{\eff,\one}_{\pi_{\ell}}=1$. By Proposition 3.5, the stationary
distribution of $\Papx$ and $\Udw_{\ell\lra n}$ are the same – thus we must
have $\norm{\Udw_{\ell\lra n}\eff}_{\pi_{\ell}}\leq\lambda(\Udw_{\ell\lra
n}).$

We have by the triangle inequality and Theorem 3.6,

$\displaystyle\lambda(\Papx_{\ell\lra n})$
$\displaystyle~{}=~{}\norm*{\Papx_{\ell\lra n}\eff}_{\pi_{n}},$
$\displaystyle~{}\leq~{}\norm{(\Papx_{\ell\lra n}-(1-\lambda(H))\Udw_{\ell\lra
n})\eff}_{\pi_{\ell}}+\norm*{(1-\lambda(H))\Udw_{\ell\lra
n}\eff}_{\pi_{\ell}},$
$\displaystyle~{}=~{}\lambda(H)+(1-\lambda(H))\cdot\lambda(\Udw_{\ell\lra
n}).$

Thus, we have

$\Gap(\Papx_{\ell\lra n})\geq
1-\lambda(H)-(1-\lambda(H))\cdot\lambda(\Udw_{\ell\lra
n})=(1-\lambda(H))\cdot(1-\lambda(\Udw_{\ell\lra
n}))=\Gap^{*}(H)\cdot\Gap(\Udw_{\ell\lra n}),$

where we have used that $\Udw_{\ell\lra n}$ is PSD to obtain the last
equality, q.v. 8. The analogous statement for $\Paqx_{n\lra\ell}$ follows from
4 and Corollary 3.3.

###  3.3 Log-Sobolev and Entropy Contraction Bounds For Expanderized Walks,
Proof of Corollary 3.8

######  Proof 3.12 (Proof of Corollary 3.8).

Let $\eff\in\RRp^{X^{(\ell)}}$ be an arbitrary function satisfying
$\Ent_{\pi_{\ell}}(\eff^{2})\neq 0$. We have,

$\displaystyle\frac{\inpr*{\eff,\parens*{\Ide-\Papx_{\ell\lra
n}}\eff}_{\pi_{\ell}}}{\Ent_{\pi_{\ell}}(\eff)^{2}}$
$\displaystyle~{}=~{}\frac{\inpr*{\eff,\parens*{\Ide-(1-\lambda(H))\cdot\Udw_{\ell\lra
n}}\eff}_{\pi_{\ell}}}{\Ent_{\pi_{\ell}}(\eff^{2})}+\frac{\inpr*{\eff,\parens*{(1-\lambda(H))\Udw_{\ell\lra
n}-\Papx_{\ell\lra n}}\eff}_{\pi_{\ell}}}{\Ent_{\pi_{\ell}}(\eff^{2})}.$

Notice that by Theorem 3.6, we should have

$\inpr*{\eff,\parens*{(1-\lambda(H))\Udw_{\ell\lra n}-\Papx_{\ell\lra
n}}\eff}_{\pi_{\ell}}\geq-\lambda(H)\cdot\inpr*{\eff,\Ide\eff}_{\pi_{\ell}}.$

Thus,

$\displaystyle\frac{\inpr*{\eff,\parens*{\Ide-\Papx_{\ell\lra
n}}\eff}_{\pi_{\ell}}}{\Ent_{\pi_{\ell}}(\eff)^{2}}$
$\displaystyle~{}\geq~{}\frac{\inpr*{\eff,\parens*{\Ide-\parens*{(1-\lambda(H))\cdot\Udw_{\ell\lra
n}+\lambda(H)\cdot\Ide}}\eff}_{\pi_{\ell}}}{\Ent_{\pi_{\ell}}(\eff^{2})},$
$\displaystyle~{}\geq~{}\LS\parens*{(1-\lambda(H))\cdot\Udw_{\ell\lra
n}+\lambda(H)\cdot\Ide},$ $\displaystyle~{}=~{}\LS(\Udw_{\ell\lra
n})\cdot\Gap^{\star}(H),$

where the last inequality is by noticing,

$\inpr*{\eff,\parens*{\Ide-\parens*{a\cdot\Ide+(1-a)\Pii}}\eff}_{\mu}=(1-a)\cdot\inpr*{\eff,\parens*{\Ide-\Pii}\eff}_{\mu},$

and the definition of the log-Sobolev inequality (LSI) and the log-Sobolev
constant (Eq. 3) . Appealing to the definition of the log-Sobolev inequality
(LSI) once again yields the result.

##  4 Functional Inequalities on Simplical Complexes

In this section, we will prove several functional inequalities involving the
down-up walk $\Duw_{n\lra\ell}$. For convenience we define the set
$\Cc_{\ell}(X)$ as the set of $\ell$-chains in $X$, i.e. the collection of
sequences

$\varnothing:=\omega^{(0)}\subsetneq\omega^{(1)}\subsetneq\cdots\subsetneq\omega^{(\ell)}\in
X^{(\ell)},$

such that $\omega^{(i)}\in X^{(i)}$ for all $i=0,\ldots,\ell$. Similarly, for
$x\in X^{(1)}$ we define $\Cc_{\ell}(x)$ as the set of $\ell$-chains in $X$
starting from $x\in X^{(1)}$, i.e. the collection of sequnces

$x=:\omega^{(1)}\subsetneq\omega^{(2)}\subsetneq\cdots\subsetneq\cdots\subsetneq\omega^{(\ell)},$

such that $\omega^{(i)}\in X^{(i)}$ for all $i=0,\ldots,\ell$.

######  Theorem 4.1.

For any $\widehat{\omega}\in X$, we set
$n_{\widehat{\omega}}=n-|\widehat{\omega}|$ and set
$\pi_{\widehat{\omega},\star}=\min_{\widetilde{\omega}\in
X_{\widehat{\omega}}^{n_{z}}}\pi_{\widehat{\omega}}^{(n_{\widehat{\omega}})}(\widetilde{\omega})$.
We have for all convex $\Phi:\RRp\to\RRp$ and $\eff\in\RR^{X^{(n)}}$.

$\Ent^{\Phi}_{\pi_{\ell}}\parens*{\Upo_{\ell\to
n}\eff}\leq\parens*{1-\min\set*{\left.\prod_{j=0}^{\ell-1}(1-\lc_{\Phi}(\omega^{(j)}))~{}\right|~{}\varnothing=:\omega^{(0)}\subsetneq\omega^{(1)}\subsetneq\cdots\subsetneq\omega^{(\ell)}\in\Cc_{\ell}(X)}}\cdot\Ent_{\pi_{r}}^{\Phi}(\eff).$
(9)

Equivalently,

$\CF_{\Phi}(\Upo_{\ell\to
n})\geq\min\set*{\left.\prod_{j=0}^{\ell-1}(1-\lc_{\Phi}(\omega^{(j)}))\right|\varnothing=:\omega^{(0)}\subsetneq\omega^{(1)}\subsetneq\cdots\subsetneq\omega^{(\ell)}\in\Cc_{\ell}(X)}.$
(10)

In particular, writing $\lc^{(i)}_{\Phi}(X,\pi)=\max_{\widehat{\omega}\in
X^{(i)}}\lc_{\Phi}(\widehat{\omega})$, we have

$\CF_{\Phi}\parens*{\Upo_{\ell\to
n}}\geq\prod_{j=0}^{\ell-1}\parens*{1-\lc^{(j)}_{\Phi}(X,\pi)}.$

As mentioned before our proof is inspired by the exposition in [CE22] and
follows the Garland method, [Gar73]. After submitting our results to arxiv, it
came to our attention that the same proof technique for proving Theorem 4.1
already appeared in [Liu23] in the context of variance contraction – though
only for the case $\ell=n-1$. We will list a few immediate consequences of
Theorem 4.1. The following bound is immediate given Proposition 2.14 and
Theorem 4.1,

######  Corollary 4.2 (Spectral Gap Bound).

Let $(X,\pi)$ be a simplicial complex of rank $n$. We have,

$\Gap(\Duw_{n\leftrightarrow\ell})\geq\frac{n-\ell}{n}\cdot\min\set*{\left.\prod_{i=0}^{\ell-1}\Gap(\Emm_{z_{i}})~{}\right|~{}\varnothing=:\omega^{(0)}\subsetneq\omega^{(1)}\subsetneq\cdots\subsetneq\omega^{(\ell)}\in\Cc_{\ell-1}(X)}.$
(11)

In particular, writing $\Gap_{k}(X,\pi):=\min_{x\in X^{(k)}}\Gap(\Emm_{x})$ we
have

$\Gap(\Duw_{n\leftrightarrow\ell})\geq\frac{n-\ell}{n}\cdot\prod_{i=0}^{\ell-1}\Gap_{i}(X,\pi).$

We also prove a useful lemma that shows we can directly relate the entropy
contraction constant to the log-Sobolev constant of the down-up walk,

######  Lemma 4.3.

Let $(X,\pi)$ be a simplicial complex of rank $n$. For any
$\widehat{\omega}\in X$, we set

$\pi^{\star}_{\widehat{\omega},k}=\min_{\widetilde{\omega}\in
X_{\widehat{\omega}}^{(k)}}\pi^{(\widehat{\omega})}_{k}(\widetilde{\omega}),~{}~{}\Gap_{n-2}(X,\pi)=\min_{\widehat{\omega}\in
X^{(n-2)}}\Gap(\Emm_{\widehat{\omega}}),~{}~{}\textrm{and}~{}~{}C_{\widehat{\omega},k}=\begin{cases}1&\pi^{\star}_{\widehat{\omega},k}>1/2,\\\
\frac{1-2\pi^{\star}_{\widehat{\omega},k}}{\log\parens*{\parens*{\pi^{\star}_{\widehat{\omega},k}}^{-1}-1}}&\textrm{otherwise}.\end{cases}$

where $\Emm_{\widehat{\omega}}$ is the link of $\widehat{\omega}$ and
$\Gap(\bullet)$ denotes the spectral gap.

Recalling that $\EC(\bullet)$ denotes the $\Phi$-entropy contraction for
$\Phi(t)=t\log t$, we have

$\displaystyle\LS(\Duw_{n\lra\ell})$
$\displaystyle~{}\geq~{}\min\set*{\left.C_{\omega^{(\ell)},n-\ell}~{}\right|~{}\omega^{(\ell)}\in
X^{(\ell)}}\cdot\EC\parens*{\Upo_{\ell\to n}},$ $\displaystyle\LS(\Udw_{n-1})$
$\displaystyle~{}\geq~{}\frac{n-1}{n}\cdot\min\set*{\left.C_{\omega^{(n-2)},1}~{}\right|~{}\omega^{(n-2)}\in
X^{(n-2)}}\cdot\Gap_{n-2}(X,\pi)\cdot\EC(\Upo_{n-2\to n-1}).$

In particular, writing $\lec_{i}(X,\pi):=\min_{\widehat{\omega}\in
X^{(i)}}\lec(\widehat{\omega})$ and $C_{\ell,k}=\min_{\widehat{\omega}\in
X^{(\ell)}}C_{\widehat{\omega},k}$,

$\displaystyle\LS(\Duw_{n\lra\ell})$
$\displaystyle~{}\geq~{}C_{\ell,n-\ell}\cdot\prod_{i=0}^{\ell-1}(1-\lec_{i}(X,\pi))$

We will prove this result in Section 4.2.

We notice that Theorem 4.1 in conjunction with Lemma 2.5 immediately implies
the following corollary,

######  Corollary 4.4.

Let $(X,\pi)$ be an $n$-partite simplicial complex,

$\MLS(\Duw_{n\lra\ell})\geq\EC(\Upo_{\ell\to
n})\geq\prod_{j=0}^{\ell-1}(1-\lec_{i}(X)).$

###  4.1 Proof of $\Phi$-Entropy Contraction Bounds, Theorem 4.1

######  Proof 4.5 (Proof of Theorem 4.1).

For $\ell=0$, the LHS is equal to 0 (Remark 2.3), thus we see the product in
Eq. 9 and Eq. 10 is taken over an empty set and equals 1. Thus, equality holds
in this case with $\CF_{\Phi}(\Upo_{0\to n})=1$. We proceed by induction on
the rank of the simplicial complex. We have by the chain rule for
$\Phi$-entropy (9),

$\Ent^{\Phi}_{\pi_{\ell}}(\Upo_{\ell\to
n}\eff)=\Exp_{x\sim\pi_{1}}\Ent^{\Phi}_{\pi^{(x)}_{\ell-1}}(\Upo_{x,\ell-1\to
n-1}\eff|_{x})+\Ent^{\Phi}_{\pi_{1}}(\Upo_{1\to n}\eff).$

Let $c:=\min_{x\sim X^{(1)}}\CF_{\Phi}(\Upo_{x,\ell-1\to n-1})$. By the
induction hypothesis,

$c\geq\min\set*{\left.\prod_{j=1}^{\ell-1}(1-\lc_{\Phi}(\omega^{(j)}))\right|x\in
X^{(1)},x=:\omega^{(1)}\subsetneq\omega^{(2)}\subsetneq\cdots\subsetneq\omega^{(\ell-1)}\in\Cc_{\ell-1}(x)}.$
(12)

Hence, we obtain,

$\displaystyle\Ent^{\Phi}_{\pi_{\ell}}(\Upo_{\ell\to n}\eff)$
$\displaystyle~{}\leq~{}(1-c)\Exp_{x\sim\pi_{1}}\Ent^{\Phi}_{\pi^{(x)}_{n-1}}(\eff|_{x})+\Ent^{\Phi}_{\pi_{1}}(\Upo_{1\to
n}\eff).$

Now, using the chain-rule (9) for $\Phi$-entropy once more, we have
$\Exp_{x\sim\pi_{1}}\Ent^{\Phi}_{\pi^{(x)}_{n-1}}(\eff|_{x})=\Ent^{\Phi}_{\pi_{n}}(\eff)-\Ent_{\pi_{1}}(\Upo_{1\to
n}\eff)$. Substituting this in,

$\displaystyle\Ent^{\Phi}_{\pi_{\ell}}(\Upo_{\ell\to n}\eff)$
$\displaystyle~{}=~{}(1-c)\cdot\parens*{\Ent_{\pi_{n}}^{\Phi}(\eff)-\Ent^{\Phi}_{\pi_{1}}(\Upo_{1\to
n}\eff)}+\Ent^{\Phi}_{\pi_{1}}(\Upo_{1\to n}\eff),$
$\displaystyle~{}=~{}(1-c)\cdot\Ent^{\Phi}_{\pi_{n}}(\eff)+c\cdot\Ent_{\pi_{1}}^{\Phi}(\Upo_{1\to
n}\eff).$

Now, using $\Ent_{\pi_{1}}^{\Phi}(\Upo_{1\to
n}\eff)\leq\lc_{\Phi}(\varnothing)\cdot\Ent_{\pi_{n}}^{\Phi}(\eff)$ we obtain

$\Ent^{\Phi}_{\pi_{\ell}}(\Upo_{\ell\to
n}\eff)\leq\parens*{1-c\cdot(1-\lc_{\Phi}(\varnothing))}\cdot\Ent^{\Phi}_{\pi_{n}}(\eff).$

Now, the statement follows from Eq. 12.

###  4.2 Proof of the log-Sobolev Inequality, Lemma 4.3

######  Proof 4.6 (Proof of Lemma 4.3).

We follow a similar strategy to what we have followed to establish Theorem
4.1. We have,

$\displaystyle\inpr*{\eff,\parens*{\Ide-\Duw_{n\lra\ell}}\eff}_{\pi_{n}}$
$\displaystyle~{}=~{}\inpr*{\eff,\eff}_{\pi_{n}}-\inpr*{\Upo_{\ell\to
n}\eff,\Upo_{\ell\to n}\eff}_{\pi_{\ell}},$
$\displaystyle~{}=~{}\Exp_{\widehat{\omega}\sim\pi_{\ell}}\sqbr*{\inpr*{\eff|_{\widehat{\omega}},\eff|_{\widehat{\omega}}}_{\pi^{(\widehat{\omega})}_{n-\ell}}-\Exp_{\widehat{\omega}\sim\pi_{\ell}}\inpr*{\Upo_{\widehat{\omega},0\to
n-\ell}\eff|_{\widehat{\omega}},\Upo_{\widehat{\omega},0\to
n-\ell}\eff|_{\widehat{\omega}}}_{\pi^{(\widehat{\omega})}_{n-\ell}}},$
$\displaystyle~{}=~{}\Exp_{\widehat{\omega}\sim\pi_{\ell}}\sqbr*{\inpr*{\eff|_{\widehat{\omega}},\parens*{\Ide-\Duw_{\widehat{\omega},n-\ell\lra
0}}\eff|_{\widehat{\omega}}}_{\pi_{n-\ell}^{(\widehat{\omega})}}},$
$\displaystyle~{}=~{}\Exp_{\widehat{\omega}\sim\pi_{\ell}}\sqbr*{\inpr*{\eff|_{\widehat{\omega}},\parens*{\Ide-\Jay_{\pi^{(\widehat{\omega})}_{n-\ell}}}\eff|_{\widehat{\omega}}}_{\pi^{(\widehat{\omega})}_{n-\ell}}},$

where we have used Items (1) and (2) of Lemma 2.16 to obtain the second
equality and have written $\Jay_{\mu}=\one\mu$ for the clique with respect to
$\mu$.

Now, by 5, we have $\LS\parens*{\Jay_{\pi^{(\widehat{\omega})}_{n-\ell}}}\geq
C_{\widehat{\omega},n-\ell}$ – where $C_{\widehat{\omega},n-\ell}$ is defined
as in the statement of Lemma 4.3. Thus, writing
$C_{\ell,n-\ell}:=\min_{\widehat{\omega}\in
X^{(\ell)}}C_{\widehat{\omega},n-\ell}$, we have

$\displaystyle\inpr*{\eff,\parens*{\Ide-\Duw_{n\lra\ell}}\eff}_{\pi_{n}}$
$\displaystyle~{}\geq~{}C_{\ell,n-\ell}\cdot\Exp_{\widehat{\omega}\sim\pi_{\ell}}\Ent_{\pi^{(\widehat{\omega})}_{n-\ell}}\parens*{\eff^{2}|_{\widehat{\omega}}},$
$\displaystyle~{}\geq~{}C_{\ell,n-\ell}\cdot\parens*{\Ent_{\pi_{n}}(\eff^{2})-\Ent_{\pi_{\ell}}\parens*{\Upo_{\ell\to
n}\eff^{2}}},$

where we have used the chain rule for entropy, 9, to obtain the last
statement.

Now, using the definition of $\Phi$-entropy contraction, i.e. writing for
$\Phi(t)=t\cdot\log t$,

$\Ent_{\pi_{\ell}}\parens*{\Upo_{\ell\to
n}\eff^{2}}\leq\parens*{1-\EC\parens*{\Upo_{\ell\to
n}}}\cdot\Ent_{\pi_{n}}\parens*{\eff^{2}}.$

Thus,

$\inpr*{\eff,\parens*{\Ide-\Duw_{n\lra\ell}}\eff}_{\pi_{n}}\geq
C_{\ell,n-\ell}\cdot\EC\parens*{\Upo_{\ell\to
n}}\cdot\Ent_{\pi_{n}}\parens*{\eff^{2}}.$

Now, the first statement follows by appealing to the definition of the log-
Sobolev inequality (LSI) and the log-Sobolev constant (Eq. 3). The second
statement concerning $\Duw_{n\lra\ell}$ now immediately follows from Theorem
4.1.

To obtain the log-Sobolev inequality for $\Udw_{n-1}$, we make use of Items
(1) and (3) in Lemma 2.16 and proceed as above. We have,

$\displaystyle\inpr*{\eff,\parens*{\Ide-\Udw_{n-1}}\eff}_{\pi_{n-1}}$
$\displaystyle~{}=~{}\frac{n-1}{n}\cdot\Exp_{\widehat{\omega}\sim\pi_{n-2}}\sqbr*{\inpr*{\eff|_{\widehat{\omega}},\parens*{\Ide-\Emm_{\widehat{\omega}}}\eff|_{\widehat{\omega}}}_{\pi_{1}^{(\widehat{\omega})}}}$

Now, appealing to 5, we obtain
$\LS(\Emm_{\widehat{\omega}})\geq\Gap(\Emm_{\widehat{\omega}})\cdot
C_{\widehat{\omega},1}$ for all $\widehat{\omega}\in X^{(n-2)}$. Thus,

$\displaystyle\inpr*{\eff,\parens*{\Ide-\Udw_{n-1}}\eff}_{\pi_{n-1}}$
$\displaystyle~{}\geq~{}\frac{n-1}{n}\cdot
C_{n-2,1}\cdot\Gap_{n-2}(X,\pi)\cdot\Exp_{\widehat{\omega}\sim\pi_{n-2}}\Ent_{\pi^{(\widehat{\omega})}_{1}}(\eff^{2}|_{\widehat{\omega}}),$
$\displaystyle~{}=~{}\frac{n-1}{n}\cdot
C_{n-2,1}\cdot\Gap_{n-2}(X,\pi)\cdot\parens*{\Ent_{\pi_{n-1}}(\eff^{2})-\Ent_{\pi_{\ell}}\parens*{\Upo_{n-2\to
n-1}\eff^{2}}},$ $\displaystyle~{}=~{}\frac{n-1}{n}\cdot
C_{n-2,1}\cdot\Gap_{n-2}(X,\pi)\cdot\EC\parens*{\Upo_{n-2\to
n-1}}\cdot\Ent_{\pi_{n-1}}(\eff^{2}),$ (13)

where we have appealed to the chain rule for entropy, 9, to obtain the first
equality.

##  5 Application: Sampling Using the Expanderized Walks

In the present section, we prove that the expanderized walks rapidly mix for
the (i) list-coloring problem and (ii) Ising models with bounded interaction
matrix. First, we describe the random sampling problems we are interested in
mention the state of the art sampling results we are interested in
expanderizing, and state our results. We will then presents proofs for our
applications in Section 5.1 and Section 5.2 respectively.

A list coloring instance $(G,\Lap)$ consists of a graph $G=(V,E)$ and a
collection of colours $\Lap=(L(v))_{v}$ for every vertex. A valid list
coloring of $(G,\Lap)$ is then a set of pairs $\set*{(v,c(v))}_{v\in V}$
satisfying the following two conditions,

  1. 1.

$c(v)\in L(v)$ for all vertices $v\in L$,

  2. 2.

$c(u)\neq c(v)$ for all edges $\set*{u,v}\in E$.

We will write $(X^{(G,\Lap)},\uni^{(G,\Lap)})$ for the simplicial complex of
proper list coloring of $(G,\Lap)$ weighted by the uniform distirbution
$(G,\Lap)$ on all list colorings, i.e.

$X^{(G,\Lap)}=\set*{\left.\alpha\subset\bigsqcup_{v\in V}\set*{v}\times
L(v)~{}\right|~{}\textrm{there exists a proper list coloring $\chi$ of
$(G,\Lap)$ such that}~{}\alpha\subset\chi}.$

We will show that the expanderized walks rapidly mix when sampling list
colorings of bounded degree graphs. Further, the lower bound in the number of
colors matches with the state of the art – see [CDM+19, Liu21, BCC+22].

######  Theorem 5.1.

Let $(G,\Lap)$ be a list-coloring instance where $G=(V,E)$ is a graph on $n$
vertices of maximum degree $\Delta\leq O(1)$ and $H_{n}$ be a labelled graph
on $[n]$ of constant two-sided expansion $\lambda(H_{n})$ bounded away from 1.
Then, for some absolute constant $\ee\approx 10^{-5}$,999See [CDM+19] and any
$K=O(1)$, if $(11/6+K)\Delta\geq|L(v)|\geq(11/6-\ee)\cdot\Delta$ for all
vertices $v\in V$, the mixing time of the expanderized walks
$\Papx_{n-1}=\UpDown_{\ell\lra n}(X^{(G,\Lap)},\uni^{(G,\Lap)},H^{2})$ and
$\Paqx_{n}=\DownUp_{n\lra\ell}(X^{(G,\Lap)},\uni^{(G,\Lap)},H)$ satisfies,

$\Tmix(\Papx_{n-1},\ee)\leq C_{1}\cdot n\parens*{\log
n+\log\ee^{-1}}~{}~{}\textrm{and}~{}~{}\Tmix(\Paqx_{n},\ee)\leq C_{2}\cdot
n\parens*{\log n+\log\log\ee^{-1}},$

where $C_{1}$ and $C_{2}$ are universal constants not depending on $n$ but on
$\Delta$.

######  Remark 5.2.

By Theorem 2.2, we can pick a constant degree graph as the graph $H_{n}$ in
the statement of Theorem 5.1. Thus, a single step of the random walk can be
implemented using $O(1)$-random bits – making the total number of random bits
used in the random walk $O(n\log n)$. In contrast, the standard down-up walk
or the up-down walk requires $O(\log n)$ random bits to perform a single step,
and $O(n\log^{2}n)$ random bits in total.

We recall that the Ising model $\mu_{\Jay,\etch}:\set*{+1,-1}^{n}\to\RRp$ with
interaction matrix $\Jay\in\RR^{n\times n}$ and external field
$\etch\in\RR^{n}$ from statistical physics is a probability distribution on
the hypercube satisfying,

$\mu_{\Jay,\etch}(\eks)=\frac{\exp\parens*{\frac{1}{2}\inpr*{\eks,\Jay\eks}_{\ell_{2}}+\inpr*{\etch,\eks}_{\ell_{2}}}}{Z(\Jay,\etch)}~{}~{}\textrm{where}~{}~{}Z(\Jay,\etch)=\sum_{\eks\in\set*{+1,-1}^{n}}\exp\parens*{\frac{1}{2}\inpr*{\eks,\Jay\eks}_{\ell_{2}}+\inpr*{\etch,\eks}_{\ell_{2}}}$
(14)

We notice that we can identify any $\eks\in\set*{+1,-1}^{n}$ with a value by
using the encoding,

$\eks^{\pm}=\set*{(i,\eks(i))\mid i\in[n]}.$

Thus, we define the simplicial complex $(X^{(\Jay,\etch)},\mu_{\Jay,\etch})$,
where

$X^{(\Jay,\etch)}=\set*{\alpha\subset[n]\setminus\set*{\pm 1}\mid\textrm{ for
each $i\in[n]$, $\alpha$ contains at most one element $(i,x)$}}.$

We show that our expanderize walks mix rapidly assuming that the external
field $\etch\in\RR^{n}$ is well-behaved, i.e. $\norm{\etch}_{\ell_{\infty}}$
does not grow with $n$,

######  Theorem 5.3.

Let $(X^{(\Jay,\etch)},\mu_{\Jay,\etch})$ be the simplicial complex defined
above corresponding to the Ising model defined by the interaction matrix
$\Jay\in\RR^{n\times n}$ and external field $\etch\in\RR^{n}$ and $H_{n}$ a
constant degree graph whose two-sided expansion is a constant bounded away
from 1. Under the assumption that $\Jay$ is PSD and satisfies
$\norm*{\Jay}_{\opp}\leq 1$, the following hold,

$\Tmix(\Papx_{n-1},\ee)\leq\frac{O\parens*{\norm*{\etch}_{\ell_{\infty}}}\cdot
n}{(1-\norm*{\Jay}_{\opp})^{2}}\parens*{\log(n+\norm*{\etch}_{\ell_{1}})+\log\ee^{-1}}~{}~{}\textrm{and}~{}~{}\Tmix(\Paqx_{n},\ee)\leq\frac{O\parens*{\norm*{\etch}_{\ell_{\infty}}}\cdot
n}{(1-\norm*{\Jay}_{\opp})^{2}}\parens*{\log(n+\norm*{\etch}_{\ell_{1}})+\log\ee^{-1}},$

where the $O(\bullet)$ notation hides a universal constant not depending on
$n,\Jay,$ or $\etch$. Furthermore, the term $(1-\norm*{\Jay}_{\opp})^{2}$ in
the denominator can be replaced with $(1-\norm*{\Jay}_{\opp})(1-\theta)$ if
the maximum operator norm of any two-by two principal submatrix of $\Jay$ is
$\theta$.

######  Remark 5.4.

By Theorem 2.2, we can pick a constant degree graph as the graph $H_{n}$ in
the statement of Theorem 5.3. Thus, ignoring numerical difficulties in
simulating biased coins, a single step of the random walk can be implemented
using $O(1)$-random bits – making the total number of random bits used in the
random walk $O(n\log n)$ when $\norm*{\etch}_{\ell_{\infty}}=O(1)$. In
contrast, the standard down-up walk or the up-down walk requires $O(\log n)$
random bits to perform a single step and $O(n\log^{2}n)$ random bits in total.

###  5.1 List Coloring of Bounded Degree Graphs

We make the following observations about the complex associated to proper list
colorings,

######  Proposition 5.5 (Folklore).

Let $(G=(V,E),\Lap)$ be a list-coloring instance. Let $K\in\NN$ satisfy
$\deg(v)+K_{+}\geq|L(v)|\geq\deg(v)+K_{-}$ for all $v\in V$. Then, writing
$(Y,\pi):=(X^{(G,\Lap)},\uni^{(G,\Lap)})$ we have,

$\lambda_{2}\parens*{\Emm_{\widehat{\chi}}}\leq\frac{1}{K_{-}}~{}~{}\textrm{for
all}~{}~{}\widehat{\chi}\in Y^{(n-2)},$

where $\Emm_{\widehat{\chi}}$ is the link of the face $\widehat{\chi}$.

Similarly, for any $\widehat{\chi}\in Y^{(n-2)}$, we have $\min_{(u,c)\in
Y_{\widehat{\chi}}^{(1)}}\pi_{1}^{(\widehat{\chi})}(u,c)\geq\frac{K_{-}}{(\Delta+K_{+})^{2}}$
where $\Delta=\max_{v\in V}\deg(v)$.

######  Proof 5.6 (Proof Sketch).

The face $\widehat{\chi}$ fixes the color of all but two distinct vertices
$u,v\in V$. Writing $A_{\widehat{\chi}}(u)$ and $A_{\widehat{\chi}}(v)$ for
the colors available to $u$ and $v$ by assigning every other vertex a color
according to $\widehat{\chi}$, we observe that the graph $G_{\widehat{\chi}}$
which underlies the link $\Emm_{\widehat{\chi}}$ is bipartite with the
partition $\set u\times A_{\widehat{\chi}}(u)$ and $\set v\times
A_{\widehat{\chi}}(v)$. Further, if $\set{u,v}\not\in E$, this graph is a
complete bipartite graph and thus $\lambda_{2}(\Emm_{\widehat{\chi}})=0$.
Otherwise, the only edges missing from this graph are the pairs,

$\set*{\set*{(u,c),(v,c)}\mid c\in A_{\widehat{\chi}}(u)\cap
A_{\widehat{\chi}}(v)}.$ (15)

In particular, the edges missing from $G_{\widehat{\chi}}$ form a matching.
Thus, the adjacency matrix of $G_{\widehat{\chi}}$ is of the form $\Bee-\Aye$
where $\Bee$ is the adjacency matrix of the complete bipartite graph on this
bipartition and $\Bee$ and $\Aye$ corresponds to the adjacency matrix
corresponding to the edges in $\Aye$. Writing $\Dee$ for the degree matrix of
$G_{\widehat{\chi}}$, we observe $\Emm_{\widehat{\chi}}=\Dee^{-1}(\Bee-\Aye)$.

Now, by using eigenvalue-interlacing can conclude

$\lambda_{2}(\Emm_{\widehat{\chi}})=\lambda_{2}(\Dee^{-1}\cdot(\Bee-\Aye))\leq\parens*{\lambda_{2}(\Bee)+\norm*{\Aye}_{\opp}}\cdot\norm*{\Dee^{-1}}_{\opp}$

We notice now that $\lambda_{2}(\Bee)=0$ as it is the adjacency matrix of the
complete bipartite graph, $\norm{\Aye}_{\opp}=1$ as it is the adjacency matrix
of a matching, and $\norm*{\Dee^{-1}}_{\opp}=1/d$ where $d$ is the minimum
number of colors $c^{\prime}\in A_{\widehat{\chi}}(v)\setminus\set c$ for any
$c\in A_{\widehat{\chi}}(u)$, or vice versa. We notice that a color $c\in
L(v)$ is precisely not in $A_{\widehat{\chi}}(v)$, because there is a neighbor
$w\neq v$ of $u$ colored with the same color in $\widehat{\chi}$. There are
$\deg(u)-1$ such neighbors, thus $d\geq|L(u)|-\deg(u)\geq K_{-}$, which
concludes the proof of the claim about the eigenvalue.

Let $c\in A_{\widehat{\chi}}(u)$ be arbitrary. Suppose $\set{u,v}\not\in E$.
Then, it is easy to observe

$\pi_{1}^{(\widehat{\chi})}(u,c)=\frac{1}{|A_{\widehat{\chi}}(u)|}\geq\frac{1}{K_{-}},$

as in a random coloring conditional on $\widehat{\chi}$ any color $c\in
A_{\widehat{\chi}}(u)$ is equally likely.

If however $\set{u,v}\in E$, then we can easily see that there are
$|A_{\widehat{\chi}}(u)|\cdot|A_{\widehat{\chi}}(v)|-|A_{\widehat{\chi}}(u)\cap
A_{\widehat{\chi}}(v)|$ ways of completing $\widehat{\chi}$ to a full
coloring, and $|A_{\widehat{\chi}}(v)\setminus\set c|$ of them have $u$
colored with $c$. Thus,

$\pi^{(\widehat{\chi})}_{1}(u,c)\geq\frac{|A_{\widehat{\chi}}(v)\setminus\set
c|}{|A_{\widehat{\chi}}(u)|\cdot|A_{\widehat{\chi}}(v)|-|A_{\widehat{\chi}}(u)\cap
A_{\widehat{\chi}}(v)|}\geq\frac{K_{-}}{(\max\set*{\deg(u),\deg(v)}+K_{+})^{2}}.$

We recall the following result of [Liu21, BCC+22],

######  Theorem 5.7 (Theorem 1.2, [Liu21, BCC+22]).

Let $(G,\Lap)$ be a list-coloring instance where $G=(V,E)$ is a graph on $n$
vertices of maximum degree $\Delta\leq O(1)$. Then, for some absolute constant
$\ee\approx 10^{-5}$,101010See [CDM+19] if $|L(v)|\geq(11/6-\ee)\cdot\Delta$
for all vertices $v\in V$, then the spectral gap, modified log-Sobolev (Eq.
2), and the log-Sobolev constants (Eq. 3) of the down-up walk
$\Duw_{n}=\DownUp_{n\lra n-1}(X^{(G,\Lap)},\uni^{(G,\Lap)})$ on the collection
of proper list colorings is all $\Omega(n^{-1})$.

Then, the following corollary immediately follows by Lemma 2.7 and 8,

######  Corollary 5.8.

Let $(G,\Lap)$ be a list-coloring instance where $G=(V,E)$ is a graph on $n$
vertices of maximum degree $\Delta\leq O(1)$. Then, for some absolute constant
$\ee\approx 10^{-5}$, if $|L(v)|\geq(11/6-\ee)\cdot\Delta$ for all vertices
$v\in V$, then the up-operator $\Upo_{n-1\to n}=\Upp_{n-1\to
n}\parens*{X^{(G,\Lap)},\uni^{(G,\Lap)}}$ on the collection of proper list
colorings of $(G,\Lap)$ satisfies $\EC(\Upo_{n-1\to n})\geq\Omega(n^{-1})$.

######  Proof 5.9 (Proof of Theorem 5.1).

Notice that by Lemma 2.17, Corollary 5.8 implies that $\EC(\Upo_{n-2\to
n-1})\geq\Omega(n^{-1})$ since by Proposition 5.5 when $\Delta=O(1)$,
$C_{n-2}=\Omega(1)$, we have
$\Gap_{n-2}(X^{(G,\Lap)},\uni^{(G,\Lap)})=\Omega(1)$, by invoking Lemma 4.3 we
obtain that the up-down walk $\Udw_{n-1}=\UpDown_{n-1\lra
n}(X^{(G,\Lap)},\uni^{(G,\Lap)})$ satisfies,
$\LS(\Udw_{n-1})\geq\Omega(n^{-1})$. Then, by Corollary 3.9 and the assumption
that the two-sided expansion $\lambda(H_{n})$ is a constant bounded away from
1, we obtain $\EC(\Papx_{n}),\EC(\Paqx_{n-1})\geq\Omega(n^{-1})$. The result,
concerning mixing times follows using Theorem 2.9 and the observation that the
state space for both walks is of size at most
$n\cdot\parens*{(K+11/6)\cdot\Delta}^{n}$.

###  5.2 The Ising Model with Bounded Correlations

We recall that the Ising model $\mu_{\Jay,\etch}:\set*{+1,-1}^{n}\to\RRp$ from
statistical physics is a probability distribution on the hypercube satisfying,

$\mu_{\Jay,\etch}(\eks)=\frac{\exp\parens*{\frac{1}{2}\inpr*{\eks,\Jay\eks}_{\ell_{2}}+\inpr*{\etch,\eks}_{\ell_{2}}}}{Z(\Jay,\etch)}~{}~{}\textrm{where}~{}~{}Z(\Jay,\etch)=\sum_{\eks\in\set*{+1,-1}^{n}}\exp\parens*{\frac{1}{2}\inpr*{\eks,\Jay\eks}_{\ell_{2}}+\inpr*{\etch,\eks}_{\ell_{2}}}$
(16)

Quite recently, it was shown that the down-up walk
$\Duw_{n}=\DownUp_{n}(X^{(\Jay,\etch)},\etch)$ rapidly mixes whenever $\Jay$
is a PSD matrix of small enough operator norm, i.e. $\norm{\Jay}_{\opp}\ll 1$.

######  Theorem 5.10 ([EKZ22, AJK+22, Lee23]).

Let $(X^{(\Jay,\etch)},\mu_{\Jay,\etch})$ be the simplicial complex
corresponding to the Ising model defined by the interaction
matrix$\Jay\in\RR^{n\times n}$ and external field $\etch\in\RR^{n}$. Under the
assumption that $\Jay$ is PSD and satisfies $\norm*{\Jay}_{\opp}\leq 1$, the
following hold,

$\Gap(\Duw_{n})\geq\frac{1-\norm*{\Jay}_{\opp}}{n}~{}~{}\textrm{and}~{}~{}\EC\parens*{\Upo_{n-1\to
n}}\geq\frac{1-\norm*{\Jay}_{\opp}}{n},$

where $\Duw_{n}=\DownUp_{n\lra
n-1}\parens*{X^{(\Jay,\etch)},\mu_{\Jay,\etch}}$ and $\Upo_{n-1\to
n}=\Upp_{n-1\to n}\parens*{X^{(\Jay,\etch)},\mu_{\Jay,\etch}}$.

The spectral gap bound above is due to [EKZ22, Theorem 1] and implies a mixing
time bound of
$O\parens*{\frac{n}{1-\norm*{\Jay}_{\opp}}(n+\norm*{\etch}_{\ell_{1}})}$. This
mixing time bound was subsequently improved to $O\parens*{\frac{n\log
n}{1-\norm{\Jay}_{\opp}}}$ by [AJK+22] through a modified log-Sobolev
inequality and a clever argument utilizing the _approximate exchange property_
– which intially appeared in [ALO+21b] – allowing them to bypass the
dependence on $\etch$ completely. The concrete statement about entropy
contraction was shown in [Lee23, Theorem 4.1].

Now, we make the following observations,

######  Proposition 5.11.

Let $(Y,\mu):=(X^{(\Jay,\etch)},\mu_{\Jay,\etch})$ be the simplicial complex
defined above corresponding to the Ising model defined by $\Jay\in\RR^{n\times
n}$ and $\etch\in\RR^{n}$. Under the assumption that $\Jay$ is PSD and
satisfies $\norm*{\Jay}_{\opp}\leq 1$, the following hold,

  1. 1.

We have $\Gap_{n-2}\parens*{Y,\mu}=\min_{\widehat{\omega}\in
Y^{(n-2)}}\Gap\parens*{\Emm_{\widehat{\omega}}}\geq 1-\theta$ where
$\Emm_{\widehat{\omega}}$ is the link of $\widehat{\omega}$ in $(Y,\mu)$ and
$\theta$ is the maximum operator norm of any principal minor of $\Jay$. Notice
that $\theta\leq\norm*{\Jay}_{\opp}$.

  2. 2.

We have that for any $\widehat{\omega}\in Y^{(n-2)}$, $\min_{x\in
Y_{\widehat{\omega}}^{(1)}}\mu^{(\widehat{\omega})}_{1}(x)\geq\frac{1}{2}\cdot
e^{-4\cdot\norm*{\etch}_{\ell_{\infty}}-1}.$

######  Proof 5.12.

For convenience we write $(Y,\mu)=(X^{(\Jay,\etch)},\mu_{\Jay,\etch})$. Let
$\widehat{\omega}\in Y^{(n-2)}$ be arbitrary and suppose
$\typ(\widehat{\omega})=[n]\setminus\set*{a,b}$. Then, we observe that we
still have an ising model at our hands, for
$\Jay_{\widehat{\omega}}\in\RR^{2\times 2}$ and $\etch^{\prime}\in\RR^{2\times
2}$, where

$\Jay_{\widehat{\omega}}=\begin{pmatrix}J(a,a)&J(a,b)\\\
J(b,a)&J(b,b)\end{pmatrix}~{}~{}\textrm{and}~{}~{}\etch_{\widehat{\omega}}(x)=\begin{cases}\etch(a)&\textrm{
if }x=a\\\ \etch(b)&\textrm{ if }x=b.\end{cases}$

In particular, by Theorem 5.10, we have that the down-up walk
$\Duw_{\widehat{\omega},2\lra 1}$ satisfies spectral gap greater than
$\frac{1-\norm*{\Jay_{\widehat{\omega}}}_{\opp}}{2}$. We recall that this
down-up walk can be described as $\Doo_{\widehat{\omega},2\to
1}\Upo_{\widehat{\omega}\to 1}.$ Thus, by 4, we have

$\frac{1-\norm*{\Jay_{\widehat{\omega}}}_{\opp}}{2}\leq\Gap\parens*{\Duw_{\widehat{\omega},2\lra
1}}=\Gap\parens*{\Upo_{\widehat{\omega},1\to 2}\Doo_{\widehat{\omega},2\to
1}}=\Gap\parens*{\frac{\Ide}{2}+\frac{\Emm_{\widehat{\omega}}}{2}}=\frac{\Gap\parens*{\Emm_{\widehat{\omega}}}}{2}.$

In particular, by assumption we have $\Gap(\Emm_{\widehat{\omega}})\geq
1-\norm*{\Jay_{\widehat{\omega}}}\geq 1-\theta$. Notice that by eigenvalue
interlacing, we always have
$\norm*{\Jay_{\widehat{\omega}}}_{\opp}\leq\norm*{\Jay}_{\opp}$ which
establishes the bound on $\Gap(\Emm_{\widehat{\omega}})\geq
1-\norm*{\Jay}_{\opp}$ in the worst case.

For the second statement, we note that for all $\eks\in\set*{-1,1}^{2}$ we
have

$e^{-2\norm*{\etch}_{\ell_{\infty}}}\leq\exp\parens*{\frac{1}{2}\cdot\inpr*{\eks,\Jay_{\widehat{\omega}}\eks}_{\ell_{2}}+\inpr*{\etch_{\widehat{\omega}},\eks}_{\ell_{2}}}\leq
e^{2\norm*{\etch}_{\ell_{\infty}}+1},$

where we have used,

  * •

$0\leq\inpr*{\eks,\Jay\eks}_{\ell_{2}}\leq 1$ since
$\norm*{\eks}_{\ell_{2}}^{2}=2$, $\norm*{\Jay_{\widehat{\omega}}}_{\opp}\leq
1$, and $\Jay_{\widehat{\omega}}$ is PSD.

  * •

$-2\leq\inpr*{\etch,\eks}_{\ell_{2}}\leq 2$ since $\norm*{\eks}_{\ell_{1}}=2$.

Notice now, assuming for example that $a$ is represented by the first variable
in $\eks$, writing
$\Xi(\eks)=\exp\parens*{0.5\cdot\inpr*{\eks,\Jay_{\widehat{\omega}}\eks}_{\ell_{2}}+\inpr*{\etch_{\widehat{\omega}},\eks}_{\ell_{2}}}$

$\displaystyle\mu_{1}^{(\widehat{\omega})}(a,1)$
$\displaystyle~{}=~{}\frac{\Xi(+1,+1)+\Xi(+1,-1)}{Z(\Jay_{\widehat{\omega}},\etch_{\widehat{\omega}})=\Xi(+1,+1)+\Xi(+1,-1)+\Xi(-1,+1)+\Xi(-1,-1)},$
$\displaystyle~{}\geq~{}\frac{2\cdot e^{-2\norm*{\etch}_{\infty}}}{4\cdot
e^{2\norm*{\etch}_{\infty}+1}},$ $\displaystyle~{}\geq~{}\frac{1}{2}\cdot
e^{-4\cdot\norm*{\etch}_{\ell_{\infty}}-1}.$

as an analogous argument follows for all $(a,\pm 1)$ and $(b,\pm 1)$ the
argument follows.

######  Proof 5.13 (Proof of Theorem 5.3).

By invoking Theorem 5.10 and Lemma 2.17 with $C=(1-\norm*{\Jay}_{\opp})^{-1}$,
we note that the up-walk $\Up_{n-2\to n-1}=\Upp_{n-2\to n-1}(Y,\mu)$
satisfies,

$\EC\parens*{\Upo_{n-2\to
n-1}}\geq\frac{1}{n-1}\cdot\frac{1-\norm*{\Jay}_{\opp}}{2-\norm*{\Jay}_{\opp}}\geq\frac{1-\norm*{\Jay}_{\opp}}{2(n-1)}.$

Now, by appealing to Lemma 4.3 and Proposition 5.11, we get that the log-
Sobolev constant (Eq. 3) of the up-down walk $\Udw_{n-1}=\UpDown_{n-1\lra
n}(Y,\mu)$ is,

$\LS\parens*{\Udw_{n-1}}\geq\frac{1}{O\parens*{\norm*{\etch}_{\ell_{\infty}}}}\cdot\frac{1-\norm*{\Jay}_{\opp}}{n}\cdot\parens*{1-\theta},$

where we note that condition (2) in Proposition 5.11 implies that the
parameter $C_{n-2,1}$ in Lemma 4.3 is at most