# Sampling Proper Colorings on Line Graphs Using $(1+o(1))\Delta$ Colors

Yulin Wang<EMAIL_ADDRESS>Shanghai Jiao Tong University  Chihao Zhang
<EMAIL_ADDRESS>Shanghai Jiao Tong University  Zihan Zhang
<EMAIL_ADDRESS>Shanghai Jiao Tong University

###### Abstract

We prove that the single-site Glauber dynamics for sampling proper
$q$-colorings mixes in $O_{\Delta}(n\log n)$ time on line graphs with $n$
vertices and maximum degree $\Delta$ when $q>(1+o(1))\Delta$. The main tool in
our proof is the matrix trickle-down theorem developed by Abdolazimi, Liu and
Oveis Gharan in [ALOG21].

##  1 Introduction

A proper (vertex) $q$-coloring of a graph $G=(V,E)$ is an assignment of each
vertex to one of $q$ colors so that the colors of adjacent vertices are
distinct. Let $\Delta$ be the maximum degree of $G$. It has been widely
conjectured that the single-site Glauber dynamics for uniformly sampling
proper colorings on $G$ mixes rapidly as long as the number of colors $q$ is
at least $\Delta+2$. Since the seminal work of Jerrum [Jer95] and Salas and
Sokal [SS97] where Glauber dynamics was shown to be rapidly mixing when $q\geq
2\Delta$, a number of works devoted to resolving the conjecture and the
current best bound requires
$q\geq\left(\frac{11}{6}-\epsilon_{0}\right)\Delta$ for some
$\epsilon_{0}\approx 10^{-4}$ [CDM+19], which is still far from desired.

Another line of work to approach the conjecture is by considering special
graph families, with the most successful cases being those graphs with large
girths (e.g., [DF03, Mol04, DFHV13, CGŠV21, FGYZ20]). Notably in a very recent
work of Chen, Liu, Mani and Moitra [CLMM23], it was proven that for any
$\Delta\geq 3$, there exists a $\mathrm{g}>0$ such that for any graph $G$ with
the maximum degree at most $\Delta$ and the girth at least $\mathrm{g}$, the
single-site Glauber dynamics for sampling proper $q$-colorings on $G$ mixes
rapidly as long as $q\geq\Delta+3$. This result almost solves the
aforementioned conjecture regarding the case of large girth graphs.

A closely related problem is _sampling proper edge colorings_ , where one
assigns colors to the edges instead of vertices so that adjacent edges have
distinct colors. It is clear that a proper edge coloring of $G$ naturally
corresponds to a vertex coloring of the line graph of $G$ in which the
vertices are the edges of $G$ and two vertices are adjacent in the line graph
if and only if the corresponding edges are incident in $G$. As a result,
studying sampling proper colorings on line graphs is of particular interest.
Unlike graphs with a large girth which are “locally sparse”, line graphs are
“locally dense”. Specifically, a line graph is formed by gluing together
several cliques with each vertex belonging to exactly two cliques. Previous
methods such as coupling can hardly take advantage of this special structure
and therefore the rapid mixing condition for line graphs remains the same as
that for general graphs for a long time.

In a recent breakthrough, Abdolazimi, Liu and Oveis Gharan [ALOG21] developed
a new technique to establish rapid mixing results for Glauber dynamics, namely
the matrix trickle-down theorem, which can well-utilize the structural
information of the underlying graphs. As a result, it was shown in [ALOG21]
the Glauber dynamics for sampling colorings on line graphs mixes rapidly as
long as $q>\frac{10}{6}\Delta$. The technique, incorporating with recent
revolutionary development of the “local-to-global” scheme for high-dimensional
expanders [AL20, CLV21], yields optimal mixing time for certain Markov chains.
Specifically, the matrix trickle-down theorem is a generalization of the
trickle-down theorem in [Opp18] which established connections between the
spectral gaps of the local walks on links of the underlying simplicial
complexes. Instead of solely looking at the spectral gap, the matrix trickle-
down theorem takes into account the local walks themselves, and establishes
more general connections between (the transition matrix of) local walks on
links.

To apply the matrix trickle-down, one needs to design appropriate matrix upper
bounds for local walks while keeping their spectrum bounded. Moreover, these
matrices must satisfy certain inductive inequality constraints. The
construction of these matrix upper bounds is the main technical challenge
since one has to have precise control over the magnitudes of their
eigenvalues. In this work, we systematically study the constraints arising in
the matrix trickle-down theorem and provide an almost optimal construction of
matrix upper bounds for sampling proper colorings on line graphs. Our
construction has several advantages compared to the one in [ALOG21]:

  * •

Our construction of the matrix upper bounds for each local walk is explicit
and intuitive.

  * •

We directly relate the spectrum of each matrix upper bound to that of the
adjacent matrix of the line graph, which is a clique locally and is therefore
well-understood. Therefore, we can obtain desired spectrum bound in an
improved regime.

  * •

We reduce the existence of matrix upper bounds to the feasibility of a system
of inequalities, for which we give a complete characterization.

As a result, we obtain an $O_{\Delta}(n\log n)$111The notation $O_{\Delta}(f)$
means that the hidden constant before $f$ might depend on $\Delta$. mixing
time for bounded degree line graph colorings with $o(\Delta)$ extra colors.

######  Theorem 1.

Let $G=(V,E)$ be a line graph with $n$ vertices and maximum degree $\Delta$.
If $q\geq\Delta+31210\cdot\Delta/\log\Delta$, then the Glauber dynamics on the
$q$-colorings of $G$ has modified log-Sobolev constant $\Omega_{\Delta}(1/n)$,
and thus mixes in time $O_{\Delta}(n\log n)$.

Moreover, we obtain an $O(n^{19/9}\log q)$ mixing time on the (degree
unbounded) family of line graphs with $o(\Delta)$ extra colors.

######  Theorem 2.

Let $G=(V,E)$ be a line graph with $n$ vertices and maximum degree $\Delta$.
If $q\geq\Delta+31210\cdot\Delta/\log\Delta$, then the Glauber dynamics on the
$q$-colorings of $G$ has spectral gap larger than $n^{-10/9}$, and thus mixes
in time $O(n^{19/9}\log q)$.

In fact, our proofs hold for more general _list coloring instances_ with
$o(\Delta)$ extra colors. See Theorem 23 for the most general statement.

We will introduce necessary notations and some preliminary results in Section
2. In particular, we review the matrix trickle-down theorem in Section 2.5.
Then we describe our construction and prove the main results in Section 3. A
main ingredient of our proof, the analysis of the inequalities arising in the
matrix trickle-down theorem, is presented in Section 4. This analysis might be
of independent interest.

##  2 Preliminaries

###  2.1 Simplicial Complexes

Let $U$ be a universe. A _simplicial complex_ $\mathcal{C}\subseteq 2^{U}$ is
a collection of subsets of $U$ that is closed under taking subsets. That is,
if $\sigma\in\mathcal{C}$ and $\sigma^{\prime}\subseteq\sigma$, then
$\sigma^{\prime}\in\mathcal{C}$. Every $\sigma\in\mathcal{C}$ is called a
_face_ , and a face that is not a proper subset of any other face is called a
_maximal face_ or a _facet_. The dimension of a face $\sigma$ is
$\mathtt{dim}(\sigma):=\absolutevalue{\sigma}$, namely the number of elements
in $\sigma$. For every $k\geq 1$, we use
$\mathcal{C}_{k}:=\left\\{\sigma\in\mathcal{C}\,\colon\,\absolutevalue{\sigma}=k\right\\}$
to denote the set of faces of dimension $k$. The dimension of $\mathcal{C}$ is
the maximum dimension of faces in $\mathcal{C}$. We say $\mathcal{C}$ is a
_pure_ $n$-dimensional simplicial complex if all maximal faces in
$\mathcal{C}$ are of dimension $n$. In the following, we assume $\mathcal{C}$
is a pure $n$-dimensional simplicial complex. For every face
$\sigma\in\mathcal{C}$, we define its co-dimension
$\mathtt{codim}(\sigma):=n-\mathtt{dim}(\sigma)$.

Let $\pi_{n}$ be a distribution over the maximal faces $\mathcal{C}_{n}$. We
use the pair $(\mathcal{C},\pi_{n})$ to denote a _weighted simplicial complex_
where for each $1\leq k<n$, the distribution $\pi_{n}$ induces a distribution
$\pi_{k}$ over $\mathcal{C}_{k}$. Formally, for every $1\leq k<n$ and every
$\sigma^{\prime}\in\mathcal{C}_{k}$,

$\displaystyle\pi_{k}(\sigma^{\prime}):=\frac{1}{\binom{n}{k}}\sum_{\sigma\in\mathcal{C}_{n}\,\colon\,\sigma^{\prime}\subset\sigma}\pi_{n}(\sigma).$

One can easily verify that $\pi_{k}$ is a distribution on $\mathcal{C}_{k}$.
Combined with $\pi_{n}$ itself, for each $1\leq k\leq n$, the distribution
over $\mathcal{C}_{k}$ is defined. Sometimes, we omit the subscript when
$j=1$, i.e., we write $\pi$ for $\pi_{1}$.

For a face $\tau\in\mathcal{C}$ of dimension $k$, we define its _link_ as

$\displaystyle\mathcal{C}_{\tau}=\left\\{\sigma\setminus\tau\,\colon\,\sigma\in\mathcal{C}\land\tau\subseteq\sigma\right\\}.$

Clearly, $\mathcal{C}_{\tau}$ is a pure $(n-k)$-dimensional simplicial
complex. Similarly, for every $1\leq j\leq n-k$, we use $\mathcal{C}_{\tau,j}$
to denote the set of faces in $\mathcal{C}_{\tau}$ of dimension $j$. We also
use $\pi_{\tau,j}$ to denote the _marginal distribution_ on
$\mathcal{C}_{\tau,j}$. Formally, for every $\sigma\in\mathcal{C}_{\tau,j}$,

$\displaystyle\pi_{\tau,j}(\sigma):=\mathbf{Pr}_{\alpha\sim\pi_{k+j}}\left[\alpha=\tau\cup\sigma\,\colon\,\tau\subseteq\alpha\right]=\frac{\pi_{k+j}(\tau\cup\sigma)}{\binom{k+j}{k}\cdot\pi_{k}(\tau)}.$

We drop the subscript when $j=1$, i.e., we write $\pi_{\tau}$ for
$\pi_{\tau,1}$. Note that the marginal distributions $\pi_{\tau,j}$ are the
same as the distributions over $C_{\tau,j}$ induced from the weighted
simplicial comlex $\left(\mathcal{C}_{\tau},\pi_{\tau,m-k}\right)$, so there
is no ambiguty about this notation.

Let $(\mathcal{C}^{(1)},\pi^{(1)})$, $(\mathcal{C}^{(2)},\pi^{(2)})$ be two
pure weighted simplicial complexes of dimension $d_{1}$ and $d_{2}$
respectively. We can define another pure weighted simplicial complex
$(\mathcal{C},\pi)$ of dimension $d_{1}+d_{2}$ whose maximal faces are the
disjoint union of maximal faces of $\mathcal{C}^{(1)}$ and
$\mathcal{C}^{(2)}$. Moreover, $\pi$ is the product measure
$\pi^{(1)}\times\pi^{(2)}$. $(\mathcal{C},\pi)$ is also called the _product_
of $(\mathcal{C}^{(1)},\pi^{(1)})$ and $(\mathcal{C}^{(2)},\pi^{(2)})$. This
definition can be naturally generalized to the products of more than two
weighted simplicial complexes.

Then we define notations for matrices related to $\pi_{\tau}$. Define
$\Pi_{\tau}\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$ as
$\Pi_{\tau}\triangleq\operatorname{diag}(\pi_{\tau})$ supported on
$\mathcal{C}_{\tau,1}\times\mathcal{C}_{\tau,1}$. For convenience, define the
pseudo inverse
$\Pi_{\tau}^{-1}\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$ of
$\Pi_{\tau}$ as $\Pi_{\tau}^{-1}(x,x)=\pi_{\tau}(x)^{-1}$ for
$x\in\mathcal{C}_{\tau,1}$ and $0$ otherwise. Similarly, the pseudo inverse
square root
$\Pi_{\tau}^{-1/2}\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$is
defined as $\Pi_{\tau}^{-1/2}(x,x)=\pi_{\tau}(x)^{-1/2}$ for
$x\in\mathcal{C}_{\tau,1}$ and $0$ otherwise.

###  2.2 Vertex Coloring

Fix a color set $[q]=\left\\{1,2,\dots,q\right\\}$ where $q\in\mathbb{N}$. Let
$G=(V,E)$ be an undirected graph and
$\mathcal{L}=\left\\{L_{v}\subseteq[q]\,\colon\,v\in V\right\\}$ be a
collection of color lists associated with each vertex in $V$. For every $v\in
V$, we use $\ell_{v}:=\absolutevalue{L_{v}}$ to denote the size of $L_{v}$.
The pair $(G,\mathcal{L})$ is an instance of list-coloring. If there exists an
integer $\beta$ such that $|L_{v}|>\Delta(v)+\beta$ for any $v\in V$ where
$\Delta(v)$ is the degree of $v$, we call $(G,\mathcal{L})$ a $\beta$-extra
list-coloring instance.

We say $\sigma:V\rightarrow[q]$ is a proper coloring if $\sigma(v)\in L_{v}$
for any $v\in V$ and $\sigma(u)\neq\sigma(v)$ for any $\left\\{u,v\right\\}\in
E$. We also regard $\sigma$ as a set of pairs of vertex and color, namely
$\left\\{(v,c)\in V\times[q]\,\colon\,\sigma(v)=c\right\\}$. Let $\Omega$
denote the set of all proper colorings and $\mu$ be the uniform distribution
on $\Omega$. Let $\Lambda\subseteq V$ and $\tau\in[q]^{\Lambda}$. We say
$\tau$ is a proper partial coloring on $\Lambda$ if it is a proper coloring on
$(G[\Lambda],\mathcal{L}|_{\Lambda})$ where $G[\Lambda]$ is the subgraph of
$G$ induced by $\Lambda$ and
$\mathcal{L}|_{\Lambda}=\left\\{L_{v}\in\mathcal{L}\,\colon\,v\in\Lambda\right\\}$.
We also define $\mu^{\tau}$ on $\Omega$ as
$\mu^{\tau}(\cdot)=\mathbf{Pr}_{\sigma\sim\mu}\left[\cdot\subset\sigma\;\middle|\;\tau\subset\sigma\right]$.
For a subset $S\subseteq V\setminus\Lambda$ and a partial coloring $\omega$ on
$S$, define
$\mu^{\tau}_{S}(\omega)=\mathbf{Pr}_{\sigma\sim\mu}\left[\omega\subset\sigma\;\middle|\;\tau\subset\sigma\right]$.

Assume $\absolutevalue{V}=n$. The list-coloring instance $(G,\mathcal{L})$ can
be naturally represented as a weighted simplicial complex
$(\mathcal{C},\pi_{n})$ where $\mathcal{C}$ consists of all proper partial
colorings and $\pi_{n}=\mu$.

The following identity is useful throughout the paper:

######  Proposition 3.

Let $\Lambda\subseteq V$. For every partial coloring $\tau$ on $\Lambda$,
every $S\subseteq V\setminus\Lambda$ and partial coloring $\omega\in[q]^{S}$,
it holds that

$\mu^{\tau}_{S}(\omega)=\binom{\mathtt{codim}(\tau)}{|S|}\cdot\pi_{\tau,|S|}(\omega).$

###  2.3 Markov Chains and Mixing Time

Let $\Omega$ be a finite discrete state space. Let $P$ be the _transition
matrix_ of a Markov chain with the stationary distribution $\pi$. We say $P$
is _reversible_ with respect to the stationary distribution $\pi$ if it
satisfies the detailed balance condition, i.e., for every $x,y\in\Omega$, it
holds that

$\displaystyle\pi(x)P(x,y)=\pi(y)P(y,x).$

Only reversible chains are considered in this paper.

For a weighted simplicial complex $\left(\mathcal{C},\pi_{n}\right)$, the
_single-site Glauber dynamics_ on $\left(\mathcal{C},\pi_{n}\right)$ is a
Markov chain on $\mathcal{C}_{n}$ with the transition matrix

$P_{\mathtt{GL}}\left(\sigma,\sigma^{\prime}\right):=\begin{cases}\frac{1}{n}\sum_{x\in\sigma}\pi_{\sigma\setminus\left\\{x\right\\},1}\left(\left\\{x\right\\}\right)&\text{if
}\sigma=\sigma^{\prime},\\\
\frac{1}{n}\pi_{\sigma\cap\sigma^{\prime},1}\left(\sigma^{\prime}\setminus\sigma\right)&\text{if
}\sigma\cap\sigma^{\prime}\in\mathcal{C}_{n-1},\\\
0&\text{otherwise}.\end{cases}$

From an operational view, each transition of the Glauber dynamics, with the
current state being $\sigma$, consists of two steps:

  1. 1.

Uniformly select a random $x\in\sigma$.

  2. 2.

Select a $y\in\mathcal{C}_{\sigma\setminus\left\\{x\right\\},1}$ following the
distribution $\pi_{\sigma\setminus\left\\{x\right\\},1}$ and transfer to the
state $\sigma\setminus\left\\{x\right\\}\cup y$.

One can easily verify that the Glauber dynamics on
$\left(\mathcal{C},\pi_{n}\right)$ is reversible, with $\pi_{n}$ as the
stationary distribution.

We are concerned with the convergence rate of Markov chains, which is
described by the mixing time. The mixing time is defined as the duration
required for the total variation distance between
$\mu_{t}:=(P^{t})^{\top}\mu_{0}$ and the stationary distribution $\pi$ to
become smaller than $\varepsilon$, starting from any initial distribution
$\mu_{0}$. Formally,

$\displaystyle
t_{\mathtt{mix}}(\varepsilon):=\min_{t>0}\max_{\mu_{0}}D_{\mathtt{TV}}(\mu_{t},\pi)\leq\varepsilon,$

where
$D_{\mathtt{TV}}(\mu,\nu):=\frac{1}{2}\sum_{x\in\Omega}\absolutevalue{\mu(x)-\nu(x)}$
is the total variation distance.

For a reversible Markov chain $P$ on a discrete space $\Omega$, since $P$ is
self-adjoint with respect to the inner product induced by $\pi$, all
eigenvalues of $P$ are real. So we can define the _spectral gap_ of $P$ as
$\lambda(P):=1-\lambda_{2}(P)$, where $\lambda_{2}(P)$ denotes the second
largest eigenvalue of $P$. And the _absolute spectral gap_ of $P$ as
$\lambda_{\star}:=1-\max\left\\{|\lambda|\,\colon\,\lambda\text{ is an
eigenvalue of }P\text{ and }\lambda\neq 1\right\\}$. The following lemma
arises to bound the mixing time of a reversible Markov chain by its absolute
spectral gap.

######  Lemma 4 (Theorem 12.4 in [LPW17]).

For an irreducible reversible Markov chain $P$ on a discrete space,

$\displaystyle
t_{\mathtt{mix}}(P,\varepsilon)\leq\frac{1}{\lambda_{\star}(P)}\left(\frac{1}{2}\log\frac{1}{\pi_{\min}}+\log\frac{1}{2\varepsilon}\right),$
(1)

where $\pi_{\min}=\min_{x\in\Omega}\pi(x)$.

Notice that when all eigenvalues of $P$ are non-negative, the absolute
spectral gap in the above lemma equals the spectral gap. This is the case of
Glauber dynamics, as in Proposition 5.

###  2.4 Local-to-Global Scheme

The _local random walk_ $P_{\tau}$ on $\mathcal{C}_{\tau,1}$ is defined as

$\displaystyle
P_{\tau}(x,y)=\frac{\pi_{\tau,2}(\\{x,y\\})}{2\pi_{\tau,1}(x)},$

for all $x,y\in\mathcal{C}_{\tau,1}$. An operational view of the local chain
is as follows: when the current state is at $x\in\mathcal{C}_{\tau,1}$, move
to $y\in\mathcal{C}_{\tau,1}$ with probability proportional to
$\pi_{\tau,2}(\left\\{x,y\right\\})$. Note that we will treat $P_{\tau}$ as a
matrix in $[0,1]^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$ such that the
undefined entries are $0$. It is obvious that $P_{\tau}$ is reversible with
respect to $\pi_{\tau}$. Specifically, we denote the local random walk on
$\mathcal{C}_{1}$ by $P$, i.e.,

$\displaystyle P(x,y)=\frac{\pi_{2}(\\{x,y\\})}{2\pi_{1}(x)}.$

$P$ is also reversible with respect to $\pi$. We say a weighted simplicial
complex $(\mathcal{C},\pi_{n})$ is
$(\gamma_{0},\gamma_{1},\dots,\gamma_{n-2})$-_local spectral expander_ if for
any $0\leq k\leq n-2$ and $\tau\in\mathcal{C}_{k}$,
$\lambda_{2}(P_{\tau})\leq\gamma_{k}$.

We focus on the spectral gaps of local walks in this paper. As studied earlier
by [AL20], the local spectral expansion implies bounds for Glauber dynamics.

######  Proposition 5 ([AL20]).

Let $(\mathcal{C},\pi_{n})$ be a weighted simplicial complex where $\pi_{n}$
is a uniform distribution over proper list-colorings over a graph $G=(V,E)$
with $|V|=n$ and maximum degree $\Delta$. If
$\left(\mathcal{C},\pi_{n}\right)$ is a
$(\gamma_{0},\gamma_{1},\dots,\gamma_{n-2})$-local spectral expander, then

  1. 1.

all eigenvalues of the Glauber dynamics are real and non-negative;

  2. 2.

the second largest eigenvalue of the Glauber dynamics is at most
$1-\frac{1}{n}\prod_{i=0}^{n-2}(1-\gamma_{i})$.

The mixing time in terms of the local spectral expansion then follows from the
proposition and Lemma 4. To obtain a tighter mixing time bound, we employ the
following proposition concerning the local spectral expansion and the modified
log-Sobolev constant.

######  Proposition 6 ([CLV21]).

Let $(\mathcal{C},\pi_{n})$ be a weighted simplicial complex where $\pi_{n}$
is a uniform distribution over proper list-colorings of a graph $G=(V,E)$ with
$|V|=n$ and maximum degree $\Delta$. If $(\mathcal{C},\pi_{n})$ is a
$(\gamma_{0},\gamma_{1},\dots,\gamma_{n-2})$-local spectral expander with
$\gamma_{k}\leq\frac{\gamma}{n-k}$ for all $k$, then the modified log-Sobolev
constant is at least $\Omega_{\gamma,\Delta}(1/n)$, and the mixing time of the
Glauber dynamics is at most $O_{\gamma,\Delta}(n\log n)$.

###  2.5 Trickle-Down Theorems

The trickle-down theorem of Oppenheim states that the spectral gaps of local
walks in a certain dimension imply spectral gaps of local walks in larger
dimensions.

######  Proposition 7 (Trickle-Down Theorem in [Opp18]).

Given a weighted simplicial complex $(\mathcal{C},\pi_{d})$, suppose the
following holds:

  * •

$\lambda_{2}(P)<1$, i.e., the local walk $P$ is irreducible;

  * •

There exists some $0\leq\lambda\leq 1/2$ such that
$\lambda_{2}(P_{x})\leq\lambda$ for all $x\in\mathcal{C}_{1}$.

Then the local walk $P$ satisfies the spectral bound
$\lambda_{2}(P)\leq\frac{\lambda}{1-\lambda}$.

A more general version of the trickle-down theorem was established in
[ALOG21]. Instead of bounding the second largest eigenvalues of local walks,
it bounds the (transition matrix of) local walks directly.

A symmetric matrix $A$ is _positive semi-definite_ , written as $A\succeq 0$
if and only if all its eigenvalues are nonnegative. For two symmetric matrices
$A$ and $B$ of the same dimension, we write $A\succeq B$, or equivalently
$B\preceq A$ if and only if $A-B\succeq 0$. As a result, the binary relation
$\preceq$ defines an order between matrices called _Loewner Order_. For
brevity, we write $A\preceq_{\pi}B$ if $\Pi A\preceq\Pi B$ for any
$A,B\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$ in the following
statement.

######  Proposition 8 (Theorem 3.2 in [ALOG21]).

Given a $d$-dimensional weighted simplicial complex $(\mathcal{C},\pi_{d})$,
suppose the following conditions hold:

  * •

$\lambda_{2}(P)<1$ where $P$ is the local walk on $\mathcal{C}_{1}$;

  * •

For a family of matrices
$\left\\{N_{x}\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}\right\\}$
and a constant $\alpha\geq\frac{1}{2}$,

$P_{x}-\alpha\mathbf{1}\pi_{x}^{\top}\preceq_{\pi_{x}}N_{x}\preceq_{\pi_{x}}\frac{1}{2\alpha+1}I,$
(2)

where $\pi_{x}$ is the stationary distribution of $P_{x}$.

Then for any matrix $N\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$
satisfying $N\preceq_{\pi}\frac{1}{2\alpha}I$ and
$\Pi^{-1}\mathbf{E}_{x\sim\pi}\left[\Pi_{x}N_{x}\right]\preceq_{\pi}N-\alpha
N^{2}$, it holds that

$P-\left(2-\frac{1}{\alpha}\right)\cdot\mathbf{1}\pi^{\top}\preceq_{\pi}N.$

In particular, $\lambda_{2}(P)\leq\lambda_{1}(N)$.

We include a proof of Proposition 8 in Appendix A for completeness.

The following proposition is the main tool we will use to prove the main
theorems. It was obtained in [ALOG21] by applying Proposition 8 to simplicial
complexes inductively.

######  Proposition 9 (Theorem 1.3 in [ALOG21]).

Given a pure $d$-dimensional weighted simplicial complex
$(\mathcal{C},\pi_{d})$, if there exists a family of matrices
$\left\\{M_{\tau}\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}\right\\}$
satisfying

  * •

For every $\tau\in\mathcal{C}_{d-2}$,

$\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}\preceq
M_{\tau}\preceq\frac{1}{5}\Pi_{\tau};$

  * •

For every face $\tau\in\mathcal{C}_{d-k}$ with $k>3$, one of the following two
conditions hold:

    1. 1.

$M_{\tau}\preceq\frac{k-1}{3k-1}\Pi_{\tau}\quad\mbox{ and
}\quad\mathbf{E}_{x\sim\pi_{\tau}}\left[M_{\tau\cup\left\\{x\right\\}}\right]\preceq
M_{\tau}-\frac{k-1}{k-2}M_{\tau}\Pi^{-1}_{\tau}M_{\tau}$

    2. 2.

$(\mathcal{C}_{\tau},\pi_{\tau,k})$ is the product of $M$ pure weighted
simplicial complexes
$(\mathcal{C}^{(1)},\pi^{(1)}),\dots(\mathcal{C}^{(M)},\pi^{(M)})$ of
dimension $n_{1},\dots,n_{M}$ respectively and

$M_{\tau}=\sum_{i\in[M]\colon n_{i}\geq 2}\frac{n_{i}(n_{i}-1)}{k(k-1)}\cdot
M_{\tau\cup\eta_{i}}$

where $\eta_{i}=\eta\setminus\mathcal{C}^{(i)}_{1}$ for an arbitrary
$\eta\in\mathcal{C}_{\tau,k}$.

Then for every face $\tau\in\mathcal{C}_{d-k}$ with $k>2$, it holds that

$\Pi_{\tau}P_{\tau}-\frac{k}{k-1}\pi_{\tau}\pi_{\tau}^{\top}\preceq
M_{\tau}\preceq\frac{k-1}{3k-1}\Pi_{\tau}.$

In particular, $\lambda_{2}(P_{\tau})\leq\lambda_{1}(\Pi^{-1}M_{\tau})$.

###  2.6 Properties of Loewner Order

We collect some useful results on the properties of the Loewner order below.

######  Lemma 10.

Let $A,B$ be two matrices in $\mathbb{R}^{n\times n}$. For any constant
$\varepsilon>0$, we have $AB^{\top}+BA^{\top}\preceq\varepsilon
AA^{\top}+\frac{1}{\varepsilon}BB^{\top}$. Moreover,
$(A+B)(A+B)^{\top}\preceq(1+\varepsilon)AA^{\top}+\left(1+\frac{1}{\varepsilon}\right)BB^{\top}$
and
$(A-B)(A-B)^{\top}\succeq(1-\varepsilon)AA^{\top}+\left(1-\frac{1}{\varepsilon}\right)BB^{\top}$.

###### Proof.

Obviously

$\varepsilon
AA^{\top}+\frac{1}{\varepsilon}BB^{\top}-AB^{\top}-BA^{\top}=\left(\sqrt{\varepsilon}A-\frac{1}{\sqrt{\varepsilon}}B\right)\left(\sqrt{\varepsilon}A-\frac{1}{\sqrt{\varepsilon}}B\right)^{\top}\succeq
0.$

The second and third inequalities then follow from the first one by expanding
the respective LHS. ∎

We use $\mathtt{supp}\,A$ to denote the support of a matrix $A$, namely the
collection of coordinates with nonzero value.

######  Lemma 11.

Let $U$ be a finite set and $\left\\{U_{1},\dots,U_{n}\right\\}$ be a
collection of subsets of $U$. Let $A\in\mathbb{R}^{U\times U}$ be a matrix.
Assume $A=\sum_{i=1}^{n}A_{i}$ where each $A_{i}$ is a matrix satisfying
$\mathtt{supp}\,A_{i}\subseteq U_{i}\times U_{i}$. For every $v\in U$, let
$T(v):=\left\\{i\in[n]\,\colon\,v\in U_{i}\right\\}$. For every $i\in[n]$, let
$m_{i}:=\max_{v\in U_{i}}\absolutevalue{T(v)}$. Then

$AA^{\top}\preceq\sum_{i\in[n]}m_{i}\cdot A_{i}A_{i}^{\top}.$

###### Proof.

Let $A(v)$ denote the row in $A$ indexed by $v\in U$. For any
$x\in\mathbb{R}^{U}$,

$x^{\top}A^{\top}Ax=\|Ax\|^{2}=\sum_{v\in U}((Ax)_{v})^{2}=\sum_{v\in
U}\langle A(v),x\rangle^{2}.$ (3)

We write $A(v)=\sum_{i=1}^{n}A_{i}(v)=\sum_{i\in T(v)}A_{i}(v)$. Then

$\mathtt{RHS}\mbox{ of \eqref{eqn:mle-square-sum-1}}=\sum_{v\in
U}\langle\sum_{i\in T(v)}A_{i}(v),x\rangle^{2}=\sum_{v\in U}\left(\sum_{i\in
T(v)}\langle A_{i}(v),x\rangle\right)^{2}$ (4)

By Cauchy-Schwarz inequality,

$\left(\sum_{i\in T(v)}\langle
A_{i}(v),x\rangle\right)^{2}\leq|T(v)|\sum_{i\in T(v)}\langle
A_{i}(v),x\rangle^{2}.$

Therefore,

$\displaystyle\mathtt{RHS}\mbox{ of \eqref{eqn:mle-square-sum-2}}$
$\displaystyle\leq\sum_{v\in U}|T(v)|\sum_{i\in T(v)}\langle
A_{i}(v),x\rangle^{2}$ $\displaystyle=\sum_{i=1}^{n}\sum_{v:i\in
T(v)}|T(v)|\langle A_{i}(v),x\rangle^{2}$
$\displaystyle\leq\sum_{i=1}^{n}m_{i}\cdot x^{\top}A_{i}^{\top}A_{i}x.$

∎

######  Corollary 12.

Let $A_{1},\dots,A_{n}$ be a collection of symmetric matrices and $\Pi\succeq
0$. Then

$\left(\sum_{i=1}^{n}A_{i}\right)\Pi\left(\sum_{i=1}^{n}A_{i}\right)\preceq
n\sum_{i=1}^{n}A_{i}\Pi A_{i}.$

###### Proof.

It follows from Lemma 11 directly by substituting $A_{i}$ by $A_{i}\Pi^{1/2}$
and noting that $m_{i}\leq n$. ∎

######  Lemma 13.

Let $A$ be a matrix and $B,B^{\prime}$ be two symmetric matrices such that
$B\preceq B^{\prime}$. Then

$A^{\top}BA\preceq A^{\top}B^{\prime}A.$

###### Proof.

For any $\mathbf{x}$, we have

$\mathbf{x}^{\top}\left(A^{\top}B^{\prime}A-A^{\top}BA\right)\mathbf{x}=\mathbf{x}^{\top}A^{\top}(B^{\prime}-B)A\mathbf{x}\geq
0.$

∎

######  Lemma 14.

Let $A,B,\Pi$ be matrices where $B$ and $\Pi$ are diagonal. Assume $\Pi\succeq
0$. Then

$A\preceq\Pi B\iff\Pi^{-\frac{1}{2}}A\Pi^{-\frac{1}{2}}\preceq B.$

###### Proof.

Since $B,\Pi$ are diagonal, $\Pi B=\Pi^{1/2}B\Pi^{1/2}$. This lemma is then
implied by Lemma 13. ∎

##  3 Vertex Coloring on Line Graphs

In this section, we fix a graph $G=(V,E)$ which is the line graph of
$\widehat{G}=(\widehat{V},\widehat{E})$ with maximum degree
$\widehat{\Delta}$. As a result, $V=\widehat{E}$ and the maximum degree
$\Delta$ of $G$ is at most $2\widehat{\Delta}-2$. Let $(G,\mathcal{L})$ be a
$\beta$-extra list-coloring instance with $\beta\geq 2$. After fixing
notations in Section 3.1, we will construct matrices fulfilling requirements
of Proposition 9 in Section 3.2 and Section 3.3. Then we prove the main
theorems in Section 3.4.

###  3.1 Notations

We fix some notations that will be used throughout the construction. Some of
them might have been introduced in Section 2. Nevertheless, we summarize here
for easier reference.

Let $\Lambda\subseteq V$ and $\tau\in[q]^{\Lambda}$ be a _partial coloring_ of
$(G,\mathcal{L})$. We define

  * •

$\mathtt{col}(\tau):=\left\\{c\in[q]\,\colon\,\exists v,\;vc\in\tau\right\\}$
as the set of colors used by $\tau$;

  * •

$V_{\tau}:=\left\\{v\,\colon\,vc\in\mathcal{C}_{\tau,1}\right\\}=V\setminus\Lambda$
as the set of vertices _not_ colored by $\tau$;

  * •

$\overline{V}_{\tau}:=V\setminus V_{\tau}=\Lambda$ as the set of vertices
colored by $\tau$.

For any $S\subseteq\overline{V}_{\tau}$, we use
$\tau|_{S}:=\left\\{vc\,\colon\,vc\in\tau\land v\in S\right\\}$ to denote the
partial coloring obtained from $\tau$ by restricting on $S$. Let
$G_{\tau}:=G[V_{\tau}]$ be the subgraph induced by $V_{\tau}$, and
$\Delta_{\tau}(v)$ be the degree of $v\in V_{\tau}$ on $G_{\tau}$.

We define the color list after pinning $\tau$ as $L_{v}^{\tau}:=\left\\{c\in
L_{v}\,\colon\,vc\in\mathcal{C}_{\tau,1}\right\\}$ and
$\ell_{v}^{\tau}=\absolutevalue{L_{v}^{\tau}}$ for every $v\in V_{\tau}$.
Similarly, for every two distinct vertices $u,v\in V_{\tau}$, we define
$L_{uv}^{\tau}:=L_{u}^{\tau}\cap L_{v}^{\tau}$ and
$\ell_{uv}^{\tau}=\absolutevalue{L_{uv}^{\tau}}$. Then
$(G_{\tau},\mathcal{L}^{\tau})$ is the list-coloring instance after pinning
$\tau$ where $\mathcal{L}^{\tau}=\left\\{L^{\tau}_{v}\right\\}_{v\in
V_{\tau}}$.

For every $i\in\widehat{V}$, we use $V^{i}\subseteq V$ to denote the set of
edges in $\widehat{G}$ incident to $i$. By the definition of a line graph,
$G[V^{i}]$ is a clique in $G$. Let $V_{\tau}^{i}\subseteq V^{i}$ denote the
vertices of $V^{i}$ not in $\tau$, i.e., $V_{\tau}^{i}=V^{i}\cap V_{\tau}$.
Fix a color $c\in[q]$. We write $V^{c}=\left\\{vc\,\colon\,v\in V\land
vc\in\mathcal{C}_{1}\right\\}$ and $V_{\tau}^{i,c}=\left\\{vc\,\colon\,v\in
V_{\tau}^{i}\land vc\in\mathcal{C}_{\tau,1}\right\\}$. We also use
$h^{i,c}_{\tau}:=\absolutevalue{V^{i,c}_{\tau}}-1$ to denote the size of
$V_{\tau}^{i}$ minus one. Note that $G[V_{\tau}^{i}]$ is still a clique after
pinning $\tau$. Define $\mathtt{Adj}_{\tau}^{i,c}\in\mathbb{R}^{V^{c}\times
V^{c}}$ as
$\mathtt{Adj}_{\tau}^{i,c}(uc,vc)=\mathtt{Adj}_{\tau}^{i,c}(vc,uc)=1$ for
every distinct $uc,vc\in V^{i,c}_{\tau}$ and all other entries $0$, which is
obtained by appending the color $c$ to the indices of the adjacency matrix of
$G[V_{\tau}^{i}]$. Let $\mathtt{Id}_{\tau}^{i,c}\in\mathbb{R}^{V^{c}\times
V^{c}}$ be the identity matrix restricted on $V_{\tau}^{i,c}$, and similarly
$\mathtt{Id}^{c}_{\tau}\in\mathbb{R}^{V^{c}\times V^{c}}$ be the identity
matrix restricted on $V_{\tau}^{c}$.

###  3.2 Base Case

The base case of Proposition 9 is that

$\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}\preceq M_{\tau}$

for any $\tau$ with $\mathtt{codim}(\tau)=2$. Our construction of $M_{\tau}$
is similar to the one in [ALOG21]. We can explicitly write down
$\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}$ when
$\mathtt{codim}(\tau)=2$. Let $(G_{\tau},L^{\tau})$ be the instance of list-
coloring after pinning $\tau$ in $G$. If $G_{\tau}$ is disconnected, then
$\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}=\mathbf{0}$. In this case, we
let $M_{\tau}=\mathbf{0}$ be the all zero matrix. Otherwise, let
$G_{\tau}=(\left\\{u,v\right\\},\left\\{\left\\{u,v\right\\}\right\\})$. For
the sake of brevity, we drop the superscript $\tau$ of $L$ and $\ell$ in this
section. For every $c_{1}\in L_{u}$ and $c_{2}\in L_{v}$, we have

$\pi_{\tau}(uc_{1})=\frac{1}{2}\cdot\frac{\ell_{v}-\mathbbm{1}\left[c_{1}\in
L_{uv}\right]}{\ell_{u}\ell_{v}-\ell_{uv}},\quad\pi_{\tau}(vc_{2})=\frac{1}{2}\cdot\frac{\ell_{u}-\mathbbm{1}\left[c_{2}\in
L_{uv}\right]}{\ell_{u}\ell_{v}-\ell_{uv}}.$

Let $\mathbf{1}_{u}\in\mathbb{R}^{\mathcal{C}_{1}}$ be the vector with $1$ on
positions indexed by $uc$ for every $c\in L_{u}$ and $0$ otherwise. Define
$\mathbf{1}_{v}$ similarly. Let $\mathbf{1}_{L_{uv}}$ be the vector with $1$
on position indexed by $uc$ and $vc$ where $c\in L_{uv}$ and $0$ otherwise. We
can write $\pi_{\tau}$ as

$\pi_{\tau}=\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})}\left(\ell_{u}\mathbf{1}_{v}+\ell_{v}\mathbf{1}_{u}-\mathbf{1}_{L_{uv}}\right).$

For every $c_{1}\in L_{u}$ and $c_{2}\in L_{v}$, we have

$\Pi_{\tau}P_{\tau}(uc_{1},vc_{2})=\Pi_{\tau}P_{\tau}(vc_{2},uc_{1})=\begin{cases}\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})},&\mbox{
if }c_{1}\neq c_{2};\\\ 0,&\mbox{ otherwise.}\end{cases}$

Let $\mathbf{1}_{u,v}\in\mathbb{R}^{\mathcal{C}_{1}\times\mathcal{C}_{1}}$ be
the matrix where $\mathbf{1}_{u,v}(uc,vc)=\mathbf{1}_{u,v}(vc,uc)=1$ if $c\in
L_{uv}$ and the other entries are $0$.

As a result,

$\Pi_{\tau}P_{\tau}=\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})}\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}-\mathbf{1}_{u,v}\right).$

We can therefore express $\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}$ as

$\displaystyle\phantom{{}={}}\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}$
$\displaystyle=\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})^{2}}\left(\left(\ell_{u}\ell_{v}-\ell_{uv}\right)\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}-\mathbf{1}_{u,v}\right)-\left(\ell_{u}\mathbf{1}_{v}+\ell_{v}\mathbf{1}_{u}-\mathbf{1}_{L_{uv}}\right)\left(\ell_{u}\mathbf{1}_{v}^{\top}+\ell_{v}\mathbf{1}_{u}^{\top}-\mathbf{1}_{L_{uv}}^{\top}\right)\right)$
$\displaystyle\preceq\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})^{2}}\left(\left(\ell_{u}\ell_{v}-\ell_{uv}\right)\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}-\mathbf{1}_{u,v}\right)-\left(\frac{\left(\ell_{u}\mathbf{1}_{v}+\ell_{v}\mathbf{1}_{u}\right)\left(\ell_{u}\mathbf{1}_{v}^{\top}+\ell_{v}\mathbf{1}_{u}^{\top}\right)}{2}-\mathbf{1}_{L_{uv}}\mathbf{1}_{L_{uv}}^{\top}\right)\right),$

where we used Lemma 10.

We now claim that

$\left(\ell_{u}\mathbf{1}_{v}+\ell_{v}\mathbf{1}_{u}\right)\left(\ell_{u}\mathbf{1}_{v}^{\top}+\ell_{v}\mathbf{1}_{u}^{\top}\right)\succeq
2(\ell_{u}\ell_{v}-\ell_{uv})\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}\right).$

It follows from the claim that

$\displaystyle\Pi_{\tau}P_{\tau}-2\pi_{\tau}\pi_{\tau}^{\top}$
$\displaystyle\preceq\frac{\mathbf{1}_{L_{uv}}\mathbf{1}_{L_{uv}}^{\top}-(\ell_{u}\ell_{v}-\ell_{uv})\mathbf{1}_{u,v}}{2(\ell_{u}\ell_{v}-\ell_{uv})^{2}}=\colon\overline{M}_{\tau}.$

For every $c\in[q]$, define the matrix
$M_{\tau}^{c}\in\mathbb{R}^{\left\\{uc,vc\right\\}\times\left\\{uc,vc\right\\}}$
as $M_{\tau}^{c}=\mathbf{0}$ if $c\not\in L_{uv}$ and otherwise

$\displaystyle M_{\tau}^{c}$
$\displaystyle=\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})}\begin{bmatrix}0&-1\\\
-1&0\end{bmatrix}+\frac{1}{(\beta-1)^{2}}\begin{bmatrix}\frac{1}{2}\frac{\ell_{v}-1}{\ell_{u}\ell_{v}-\ell_{uv}}&0\\\
0&\frac{1}{2}\frac{\ell_{u}-1}{\ell_{u}\ell_{v}-\ell_{uv}}\end{bmatrix}$
$\displaystyle=\frac{1}{2(\ell_{u}\ell_{v}-\ell_{uv})}\begin{bmatrix}0&-1\\\
-1&0\end{bmatrix}+\frac{1}{(\beta-1)^{2}}\Pi_{\tau}\mathtt{Id}_{\tau}^{c}.$
(5)

Let $M_{\tau}$ be the block-diagonal matrix with block $M_{\tau}^{c}$ for each
$c\in L_{uv}$.

Let $I_{u,v}$ be matrix that $I_{u,v}(uc,uc)=I_{u,v}(vc,vc)=1$ if $c\in
L_{uv}$ and the other entries are $0$. Observing that the $uc$-th row
summation of $\mathbf{1}_{L_{uv}}\mathbf{1}_{L_{uv}}^{\top}$ is at most
$\ell_{uv}$, we have

$\frac{\mathbf{1}_{L_{uv}}\mathbf{1}_{L_{uv}}^{\top}}{2(\ell_{u}\ell_{v}-\ell_{uv})^{2}}\preceq\frac{\ell_{uv}}{2(\ell_{u}\ell_{v}-\ell_{uv})^{2}}I_{u,v}\preceq\frac{1}{2(\beta-1)(\ell_{u}\ell_{v}-\ell_{uv})}I_{u,v}\preceq\mathtt{diag}(M_{\tau}).$

Hence $\overline{M}_{\tau}\preceq M_{\tau}$.

It remains to verify the claim. Note that since
$\mathbf{1}_{v}\mathbf{1}_{v}^{\top}\succeq 0$,

$\displaystyle\left(\ell_{u}\mathbf{1}_{v}+\ell_{v}\mathbf{1}_{u}\right)\left(\ell_{u}\mathbf{1}_{v}^{\top}+\ell_{v}\mathbf{1}_{u}^{\top}\right)$
$\displaystyle=\ell_{u}\ell_{v}\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}\right)+\ell_{u}^{2}\mathbf{1}_{u}\mathbf{1}_{u}^{\top}+\ell_{v}^{2}\mathbf{1}_{v}\mathbf{1}_{v}^{\top}$
$\displaystyle\succeq\ell_{u}\ell_{v}\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}\right)+\ell_{u}^{2}\mathbf{1}_{u}\mathbf{1}_{u}^{\top}+(\ell_{v}-2\ell_{uv}/\ell_{u})^{2}\mathbf{1}_{v}\mathbf{1}_{v}^{\top}.$

Since $\ell_{u}\geq\beta\geq 2$, the coefficient
$\ell_{v}-2\ell_{uv}/\ell_{u}\geq 0$. Therefore, by Lemma 10, we have

$\ell_{u}^{2}\mathbf{1}_{u}\mathbf{1}_{u}^{\top}+(\ell_{v}-2\ell_{uv}/\ell_{u})^{2}\mathbf{1}_{v}\mathbf{1}_{v}^{\top}\succeq(\ell_{u}\ell_{v}-2\ell_{uv})\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}\right).$

And hence,

$\left(\ell_{u}\mathbf{1}_{v}+\ell_{v}\mathbf{1}_{u}\right)\left(\ell_{u}\mathbf{1}_{v}^{\top}+\ell_{v}\mathbf{1}_{u}^{\top}\right)\succeq
2(\ell_{u}\ell_{v}-\ell_{uv})\left(\mathbf{1}_{u}\mathbf{1}_{v}^{\top}+\mathbf{1}_{v}\mathbf{1}_{u}^{\top}\right).$

###  3.3 Induction Step

The induction step in Proposition 9 is to show that for every $\tau$ with
$\mathtt{codim}(\tau)=k>2$ and connected $G_{\tau}$,

$\mathbf{E}\left[M_{\tau\cup\left\\{x\right\\}}\right]\preceq
M_{\tau}-\frac{k-1}{k-2}M_{\tau}\Pi_{\tau}^{-1}M_{\tau}.$ (6)

For every $\tau$ and $c\in[q]$, we will define a matrix
$N_{\tau}^{c}\in\mathbb{R}^{V^{c}\times V^{c}}$ and let $M_{\tau}$ be the
block diagonal matrix with block $N_{\tau}^{c}$ for every $c\in[q]$. It is not
hard to see that we only require

$\mathbf{E}\left[N_{\tau\cup\left\\{x\right\\}}^{c}\right]\preceq
N_{\tau}^{c}-\frac{k-1}{k-2}N_{\tau}^{c}(\Pi_{\tau}^{c})^{-1}N_{\tau}^{c}$ (7)

to hold for every $c$, where $(\Pi_{\tau}^{c})^{-1}$ is $\Pi_{\tau}^{-1}$
restricted on $V^{c}\times V^{c}$. We now describe our construction of
$N^{c}_{\tau}$ for a fixed color $c$. From now on, when $c$ is clear from the
context, we will omit the superscript $c$ for matrices. For example, we will
write $N_{\tau}$, $N^{i}_{\tau}$, $\Pi_{\tau}$, $\mathtt{Adj}_{\tau}^{i}$,
$\mathtt{Id}_{\tau}^{i}$, $A_{\tau}$, $B_{\tau}$, $\dots$ instead of
$N^{c}_{\tau}$, $N^{i,c}_{\tau}$, $\Pi^{c}_{\tau}$,
$\mathtt{Adj}_{\tau}^{i,c}$, $\mathtt{Id}_{\tau}^{i,c}$, $A_{\tau}^{c}$,
$B_{\tau}^{c}$, $\dots$ respectively. Also we write $h_{\tau}^{i}$ for
$h_{\tau}^{i,c}$.

We write $N_{\tau}$ into the sum of a diagonal matrix and an off-diagonal
matrix, i.e.,

$N_{\tau}=\frac{1}{k-1}(A_{\tau}+\Pi_{\tau}B_{\tau}),$ (8)

where $A_{\tau}$ is an off-diagonal matrix and $B_{\tau}$ is a diagonal
matrix. For the off-diagonal matrix $A_{\tau}$, we further decompose it into
$A_{\tau}=\sum_{i\in\widehat{V}}A_{\tau}^{i}$, where
$A^{i}_{\tau}\in\mathbb{R}^{V^{c}\times V^{c}}$ with
$\mathtt{supp}\,A^{i}_{\tau}\subseteq V^{i}_{\tau}\times V^{i}_{\tau}$.

Plugging above into (7) and remembering that the superscript $c$ has been
omitted, we obtain

$(k-1)\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}+\Pi_{\tau\cup\left\\{x\right\\}}B_{\tau\cup\left\\{x\right\\}}\right]\preceq(k-2)\cdot\left(A_{\tau}+\Pi_{\tau}B_{\tau}\right)-\left(A_{\tau}+\Pi_{\tau}B_{\tau}\right)\Pi_{\tau}^{-1}\left(A_{\tau}+\Pi_{\tau}B_{\tau}\right).$

It follows from Corollary 12 that

$\left(A_{\tau}+\Pi_{\tau}B_{\tau}\right)\Pi_{\tau}^{-1}\left(A_{\tau}+\Pi_{\tau}B_{\tau}\right)\preceq
2A_{\tau}\Pi_{\tau}^{-1}A_{\tau}+2\Pi_{\tau}B_{\tau}^{2}.$

Since each vertex $v$ only occurs in $V^{i}$ and $V^{j}$ assuming
$v=\left\\{i,j\right\\}$ in $\widehat{G}$, by Lemma 11,

$A_{\tau}\Pi_{\tau}^{-1}A_{\tau}\preceq
2\sum_{i\in\widehat{V}}A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}.$

As a result, in order for (6) to hold, we only need to design $A_{\tau}^{i}$
for every $i\in\widehat{V}$ and $B_{\tau}$ satisfying

$\sum_{i\in\widehat{V}}\left((k-1)\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right]-(k-2)\cdot
A_{\tau}^{i}+4A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}\right)\preceq(k-2)\Pi_{\tau}B_{\tau}-(k-1)\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[\Pi_{\tau\cup\left\\{x\right\\}}B_{\tau\cup\left\\{x\right\\}}\right]-4\Pi_{\tau}\left(B_{\tau}\right)^{2}.$
(9)

####  3.3.1 Construction of $A_{\tau}^{i}$

A natural starting point (as did in [ALOG21]) is to recursively define
$A_{\tau}^{i}=\frac{k-1}{k-2}\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right]$
and this yields an explicit expression for $A_{\tau}^{i}$. However, under this
construction, the LHS of (9) becomes to
$4A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}$, which is too large for (9) to be
feasible in the regime we are interested in. Nevertheless, it is still helpful
to see what $A_{\tau}^{i}$ looks like under this recursive definition.

For the base case $V_{\tau}=\left\\{u,v\right\\}$, if $c\in L_{u}^{\tau}\cap
L_{v}^{\tau}$ and $i\in\widehat{V}$ is the common end vertex of $u,v$ in
$\widehat{G}$, let
$A_{\tau}^{i}=\frac{1}{2(\ell_{u}^{\tau}\ell_{v}^{\tau}-\ell_{uv}^{\tau})}\begin{bmatrix}0&-1\\\
-1&0\end{bmatrix}$. Otherwise set $A_{\tau}^{i}=0$. It is obvious that
$\sum_{i\in\widehat{V}}A_{\tau}^{i}=\mathtt{offdiag}(M_{\tau}^{c})$.

When $\mathtt{codim}\,\tau>2$, we can expand the recursion down to faces of
dimension $2$:

$\displaystyle A_{\tau}^{i}$
$\displaystyle=\frac{k-1}{k-2}\cdot\frac{k-2}{k-3}\cdots\frac{3}{2}\cdot\frac{2}{1}\cdot\mathbf{E}_{x_{1}\sim\pi_{\tau}}\left[\mathbf{E}_{x_{2}\sim\pi_{\tau\cup\left\\{x_{1}\right\\}}}\left[\dots\mathbf{E}_{x_{k-2}\sim\pi_{\tau\cup\left\\{x_{1},\dots,x_{k-3}\right\\}}}\left[A_{\tau\cup\left\\{x_{1},\dots,x_{k-2}\right\\}}^{i}\right]\right]\right]$
$\displaystyle=(k-1)\sum_{(x_{1},x_{2},\dots,x_{k-2})\in\mathcal{C}_{\tau,k-2}}\pi_{\tau}(x_{1})\pi_{\tau\cup\left\\{x_{1}\right\\}}(x_{2})\cdots\pi_{\tau\cup\left\\{x_{1},\dots,x_{k-3}\right\\}}(x_{k-2})A_{\tau\cup\left\\{x_{1},x_{2},\dots,x_{k-2}\right\\}}^{i}$
$\displaystyle=(k-1)\sum_{(x_{1},x_{2},\dots,x_{k-2})\in\mathcal{C}_{\tau,k-2}}\frac{\pi_{\tau,k-2}(\left\\{x_{1},x_{2},\dots,x_{k-2}\right\\})}{(k-2)!}A_{\tau\cup\left\\{x_{1},x_{2},\dots,x_{k-2}\right\\}}^{i}$
$\displaystyle=(k-1)\cdot\mathbf{E}_{\sigma\sim\pi_{\tau,k-2}}\left[A_{\tau\cup\sigma}^{i}\right].$

Recall that $h_{\tau}^{i}=\absolutevalue{V_{\tau}^{i,c}}-1$. In order to
decrease the LHS of eq. 9, we introduce a collection of positive coefficients
$a_{h}$ decreasing in $h$ for $1\leq h\leq\Delta$ whose value will be
determined later. Especially $a_{0}=0$. Define

$A_{\tau}^{i}=a_{h_{\tau}^{i}}\cdot(k-1)\cdot\mathbf{E}_{\sigma\sim\pi_{\tau,k-2}}\left[A_{\tau\cup\sigma}^{i}\right].$
(10)

When $h_{\tau}^{i}=0$, $A_{\tau}^{i}=\mathbf{0}$ is trivial. So in the
following analysis, we assume $h_{\tau}^{i}\geq 1$.

######  Lemma 15.

$\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right]=\frac{1}{k-1}\left((h-1)\frac{a_{h-1}}{a_{h}}+(k-2-(h-1))\right)\cdot
A_{\tau}^{i},$

where $h=h_{\tau}^{i}\geq 1$.

###### Proof.

For any $uc,vc\in V_{\tau}^{i,c}$,

$\displaystyle\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right](uc,vc)$
$\displaystyle=(k-2)\sum_{x\in\mathcal{C}_{\tau,1}}\frac{1}{k}\mu^{\tau}_{\overline{V}_{x}}(x)a_{h_{\tau\cup\left\\{x\right\\}}^{i}}\sum_{\sigma\in\mathcal{C}_{\tau\cup\left\\{x\right\\},k-3}}\frac{2}{(k-1)(k-2)}\mu^{\tau\cup\left\\{x\right\\}}_{\overline{V}_{\sigma}}(\sigma)A_{\tau\cup\left\\{x\right\\}\cup\sigma}^{i}(uc,vc)$
$\displaystyle=\frac{2}{k(k-1)}\sum_{x\in\mathcal{C}_{\tau,1}}\sum_{\sigma\in\mathcal{C}_{\tau\cup\left\\{x\right\\},k-3}}\mu^{\tau}_{\overline{V}_{x}}(x)\mu^{\tau\cup\left\\{x\right\\}}_{\overline{V}_{\sigma}}(\sigma)a_{h_{\tau\cup\left\\{x\right\\}}^{i}}A_{\tau\cup\left\\{x\right\\}\cup\sigma}^{i}(uc,vc)$
$\displaystyle=\frac{2}{k(k-1)}\sum_{\sigma^{\prime}\in\mathcal{C}_{\tau,k-2}}\mu^{\tau}_{\overline{V}_{\sigma^{\prime}}}(\sigma^{\prime})A_{\tau\cup\sigma^{\prime}}^{i}(uc,vc)\sum_{x\in\sigma^{\prime}}a_{h_{\tau\cup\left\\{x\right\\}}^{i}}$
$\displaystyle=\frac{2}{k(k-1)}\sum_{\sigma^{\prime}\in\mathcal{C}_{\tau,k-2}}\mu^{\tau}_{\overline{V}_{\sigma^{\prime}}}(\sigma^{\prime})A_{\tau\cup\sigma^{\prime}}^{i}(uc,vc)\left((h-1)a_{h-1}+(k-2-(h-1))a_{h}\right)$
$\displaystyle=\frac{1}{k-1}A_{\tau}^{i}(uc,vc)\left((h-1)\frac{a_{h-1}}{a_{h}}+(k-2-(h-1))\right).$

∎

It follows from the definition that $A_{\tau}^{i}$ is proportional to the
expectation of the base cases when the boundary is drawn from
$\pi_{\tau,k-2}$. For some technical reasons, we would like to isolate those
boundaries containing the color $c$. This leads us to the following lemma.

######  Lemma 16.

$A_{\tau}^{i}=\frac{a_{h}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\sum_{\begin{subarray}{c}\omega\in\mathcal{C}_{\tau,k}\colon\\\
\forall w\in V^{i}_{\tau}\colon\omega(w)\neq
c\end{subarray}}A^{i,\omega}_{\tau},$

where $A^{i,\omega}_{\tau}$ is the matrix satisfying for any $uc,vc\in
V_{\tau}^{i,c}$,

$A_{\tau}^{i,\omega}(uc,vc)=-\frac{\mathbbm{1}\left[c\in
L^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{v}\right]}{\left(\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{u}-1\right)\cdot\left(\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{v}-1\right)-\left(\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{uv}-1\right)}$

and all other entries $0$.

###### Proof.

Let $V^{\prime}:=V_{\tau}\setminus\left\\{u,v\right\\}$. We denote the set of
proper partial colorings restricted on $V^{\prime}\subset V_{\tau}$ when
$\tau$ is pinned by $\mathcal{C}_{\tau}^{V^{\prime}}$. Formally,
$\mathcal{C}_{\tau}^{V^{\prime}}=\left\\{\omega\in\mathcal{C}_{\tau}\,\colon\,\overline{V}_{\omega}=V^{\prime}\right\\}$.
It follows from eq. 10 that for any $uc,vc\in V_{\tau}^{i,c}$,

$\displaystyle A_{\tau}^{i}(uc,vc)$
$\displaystyle=a_{h}\cdot(k-1)\sum_{\sigma\in\mathcal{C}_{\tau,k-2}}\pi_{\tau}(\sigma)\cdot
A^{i}_{\tau\cup\sigma}(uc,vc)$
$\displaystyle=-\frac{a_{h}}{k}\sum_{\sigma\in\mathcal{C}_{\tau}^{V^{\prime}}}\mu_{V^{\prime}}^{\tau}(\sigma)\cdot\frac{\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{v}\right]}{\ell^{\tau\cup\sigma}_{u}\cdot\ell^{\tau\cup\sigma}_{v}-\ell^{\tau\cup\sigma}_{uv}}$
$\displaystyle=-\frac{a_{h}}{k}\cdot\sum_{\sigma\in\mathcal{C}_{\tau}^{V^{\prime}}}\frac{\absolutevalue{\left\\{\omega\in\mathcal{C}_{\tau,k}\,\colon\,\sigma\subseteq\omega\right\\}}}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\frac{\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{v}\right]}{\ell^{\tau\cup\sigma}_{u}\cdot\ell^{\tau\cup\sigma}_{v}-\ell^{\tau\cup\sigma}_{uv}}.$
(11)

Note that for every $\sigma\in\mathcal{C}_{\tau}^{V^{\prime}}$, we have

$\absolutevalue{\left\\{\omega\in\mathcal{C}_{\tau,k}\,\colon\,\sigma\subseteq\omega\right\\}}=\absolutevalue{\mathcal{C}_{\tau\cup\sigma,2}}=\ell^{\tau\cup\sigma}_{u}\cdot\ell^{\tau\cup\sigma}_{v}-\ell^{\tau\cup\sigma}_{uv}.$

Plugging this into eq. 11, we have

$A_{\tau}^{i}(uc,vc)=-\frac{a_{h}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\sum_{\sigma\in\mathcal{C}_{\tau}^{V^{\prime}}}\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{v}\right].$

Observe that if for a $\sigma\in\mathcal{C}_{\tau}^{V^{\prime}}$, it holds
that $\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{v}\right]=1$, then

$\absolutevalue{\left\\{\rho\in\mathcal{C}_{\tau\cup\sigma,2}\,\colon\,c\not\in\mathtt{col}(\rho)\right\\}}=\left(\ell^{\tau\cup\sigma}_{u}-1\right)\cdot\left(\ell^{\tau\cup\sigma}_{v}-1\right)-\left(\ell^{\tau\cup\sigma}_{uv}-1\right).$

We can further write $A_{\tau}^{i}(uc,vc)$ as

$\displaystyle A_{\tau}^{i}(uc,vc)$
$\displaystyle=-\frac{a_{h}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\sum_{\sigma\in\mathcal{C}_{\tau}^{V^{\prime}}}\absolutevalue{\left\\{\rho\in\mathcal{C}_{\tau\cup\sigma,2}\,\colon\,c\not\in\mathtt{col}(\rho)\right\\}}\cdot\frac{\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\tau\cup\sigma}_{v}\right]}{\left(\ell^{\tau\cup\sigma}_{u}-1\right)\cdot\left(\ell^{\tau\cup\sigma}_{v}-1\right)-\left(\ell^{\tau\cup\sigma}_{uv}-1\right)}$
$\displaystyle=-\frac{a_{h}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\sum_{\begin{subarray}{c}\omega\in\mathcal{C}_{\tau,k}\colon\\\
\omega(u)\neq c\land\omega(v)\neq c\end{subarray}}\frac{\mathbbm{1}\left[c\in
L^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{v}\right]}{\left(\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{u}-1\right)\cdot\left(\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{v}-1\right)-\left(\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{uv}-1\right)}$
$\displaystyle=\frac{a_{h}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\sum_{\begin{subarray}{c}\omega\in\mathcal{C}_{\tau,k}\colon\\\
\omega(u)\neq c\land\omega(v)\neq c\end{subarray}}A^{i,\omega}_{\tau}(uc,vc)$
$\displaystyle=\frac{a_{h}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\sum_{\begin{subarray}{c}\omega\in\mathcal{C}_{\tau,k}\colon\\\
\forall w\in V^{i}_{\tau}\colon\omega(w)\neq
c\end{subarray}}A^{i,\omega}_{\tau}(uc,vc),$

where the last line follows from the fact that $c\in
L^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{u}\cap
L^{(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}}_{v}$ implies $\forall
w\in V_{\tau}^{i}\setminus\left\\{u,v\right\\},\omega(w)\neq c$. ∎

####  3.3.2 Spectral analysis of $A_{\tau}^{i}$

In the following lemma, we show that each matrix $A^{i,\omega}_{\tau}$ can be
written as the sum of two matrices which we call the _main term_ and the
_remainder_ respectively. The main term only depends on the adjacency matrix
$Adj_{\tau}^{i}$ and $L_{u}$ terms under various boundary conditions and is
irrelevant to $L_{uv}$ terms. All the effects of $L_{uv}$ terms are collected
in the remainder.

For every $\omega\in\mathcal{C}_{\tau,k}$ such that
$c\not\in\mathtt{col}((\omega\cup\tau)|_{V^{i}_{\tau}})$, define
$\Xi_{\tau}^{i,\omega}\in\mathbb{R}^{V^{c}\times V^{c}}$ as the diagonal
matrix such that for every $uc\in V_{\tau}^{i,c}$:

$\Xi_{\tau}^{i,\omega}(uc,uc)=\frac{\mathbbm{1}\left[c\in
L^{(\tau\cup\omega)|_{V\setminus\left\\{u\right\\}}}_{u}\right]}{\ell^{(\tau\cup\omega)|_{V\setminus\left\\{u\right\\}}}_{u}-1}.$

######  Lemma 17.

$A^{i,\omega}_{\tau}=\Xi^{i,\omega}_{\tau}(-\mathtt{Adj}_{\tau}^{i}+\mathcal{R}_{\tau}^{i,\omega})\Xi_{\tau}^{i,\omega},$

where $\rho(\mathcal{R}_{\tau}^{i,\omega})\leq\frac{5h}{\beta-1}$.

###### Proof.

Let $uc,vc\in V_{\tau}^{i,c}$. To ease the notation, when $\tau$ and $\omega$
are clear from the context, we use $\Gamma(u)$ and $\Gamma(u,v)$ to denote the
partial coloring $(\tau\cup\omega)|_{V\setminus\left\\{u\right\\}}$ and
$(\tau\cup\omega)|_{V\setminus\left\\{u,v\right\\}}$ respectively. We also use
$\overline{\ell}_{u}^{\Gamma(u,v)}$ to denote $\ell_{u}^{\Gamma(u,v)}-1$ and
define
$\overline{\ell}_{v}^{\Gamma(u,v)},\overline{\ell}_{u}^{\Gamma(u)},\overline{\ell}_{v}^{\Gamma(v)}$
similarly.

Using our new notations, we have

$\Xi_{\tau}^{i}(uc,uc)=\frac{\mathbbm{1}\left[c\in
L^{\Gamma(u)}_{u}\right]}{\overline{\ell}^{\Gamma(u)}_{u}}.$

Observing that since
$c\not\in\mathtt{col}\left((\tau\cup\omega)|_{V^{i}_{\tau}}\right)$, we have

$\displaystyle\mathbbm{1}\left[c\in L^{\Gamma(u)}_{u}\right]$
$\displaystyle=\mathbbm{1}\left[c\in L^{\Gamma(u,v)}_{u}\right]$
$\displaystyle\mathbbm{1}\left[c\in L^{\Gamma(v)}_{v}\right]$
$\displaystyle=\mathbbm{1}\left[c\in L^{\Gamma(u,v)}_{v}\right].$

So we can write $A_{\tau}^{i,\omega}$ as

$\displaystyle A_{\tau}^{i,\omega}(uc,vc)$
$\displaystyle=-\frac{\mathbbm{1}\left[c\in
L^{\Gamma(u)}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\Gamma(v)}_{v}\right]}{\overline{\ell}^{\Gamma(u,v)}_{u}\overline{\ell}^{\Gamma(u,v)}_{v}-\overline{\ell}^{\Gamma(u,v)}_{uv}}$
$\displaystyle=\mathbbm{1}\left[c\in
L^{\Gamma(u)}_{u}\right]\cdot\mathbbm{1}\left[c\in
L^{\Gamma(v)}_{v}\right]\cdot\frac{1}{\overline{\ell}_{u}^{\Gamma(u)}\cdot\overline{\ell}_{v}^{\Gamma(v)}}\left(-1+\mathcal{R}_{\tau}^{i,\omega}(uc,vc)\right),$

where

$\mathcal{R}_{\tau}^{i,\omega}(uc,vc)=1-\frac{\overline{\ell}_{u}^{\Gamma(u)}\cdot\overline{\ell}_{v}^{\Gamma(v)}}{\overline{\ell}^{\Gamma(u,v)}_{u}\overline{\ell}^{\Gamma(u,v)}_{v}-\overline{\ell}^{\Gamma(u,v)}_{uv}}.$
(12)

By definition, it holds that
$\ell^{\Gamma(u,v)}_{u}-\ell_{u}^{\Gamma(u)}\in\left\\{0,1\right\\}$ and
$\ell^{\Gamma(u,v)}_{v}-\ell_{v}^{\Gamma(u)}\in\left\\{0,1\right\\}$.
Therefore,

$\displaystyle\absolutevalue{\mathcal{R}_{\tau}^{i,\omega}(uc,vc)}$
$\displaystyle=\frac{\absolutevalue{\overline{\ell}_{u}^{\Gamma(u)}\cdot\overline{\ell}_{v}^{\Gamma(v)}-\left(\overline{\ell}^{\Gamma(u,v)}_{u}\overline{\ell}^{\Gamma(u,v)}_{v}-\overline{\ell}^{\Gamma(u,v)}_{uv}\right)}}{\overline{\ell}^{\Gamma(u,v)}_{u}\overline{\ell}^{\Gamma(u,v)}_{v}-\overline{\ell}^{\Gamma(u,v)}_{uv}}$
$\displaystyle\leq\frac{\max\left\\{\overline{\ell}_{u}^{\Gamma(u)}+\overline{\ell}_{v}^{\Gamma(v)}+1,\overline{\ell}^{\Gamma(u,v)}_{uv}\right\\}}{\overline{\ell}^{\Gamma(u,v)}_{u}\overline{\ell}^{\Gamma(u,v)}_{v}-\overline{\ell}^{\Gamma(u,v)}_{uv}}$
$\displaystyle\leq\frac{\overline{\ell}^{\Gamma(u,v)}_{u}+\overline{\ell}^{\Gamma(u,v)}_{v}+3}{\overline{\ell}^{\Gamma(u,v)}_{u}\overline{\ell}^{\Gamma(u,v)}_{v}-\max\left\\{\overline{\ell}^{\Gamma(u,v)}_{u},\overline{\ell}^{\Gamma(u,v)}_{v}\right\\}}$
$\displaystyle\leq\frac{5}{\min\left\\{\overline{\ell}^{\Gamma(u,v)}_{u},\overline{\ell}^{\Gamma(u,v)}_{v}\right\\}-1}$
$\displaystyle\leq\frac{5}{\beta-1},$

where the last inequality follows from the fact that
$\overline{\ell}^{\Gamma(u,v)}_{u},\overline{\ell}^{\Gamma(u,v)}_{v}\geq\beta$.
Taking row summation of $\mathcal{R}_{\tau}^{i,\omega}$, we obtain that
$\rho(\mathcal{R}_{\tau}^{i,\omega})\leq\frac{5h}{\beta-1}$. ∎

In order to bound LHS of Equation 9, we introduce the following lemma.

######  Lemma 18 ([GKM15]).

For every $(u,c)\in\mathcal{C}_{\tau,1}$, it holds

$\frac{(1-\frac{1}{\beta})^{\Delta_{\tau}(u)}}{\ell^{\tau}_{u}}\leq\mu^{\tau}_{u}(c)\leq\frac{1}{\ell^{\tau}_{u}-\Delta_{\tau}(u)}.$

The proof of Lemma 18 is included in Appendix B. We assume
$\beta\geq\frac{\Delta}{\iota(\Delta)}+1$ where $\iota(\Delta)\geq 1$ is a
slowly increasing function. In the following two lemmas, we bound
$A_{\tau}^{i,\omega}\Pi_{\tau}^{-1}A_{\tau}^{i,\omega}$.

Let
$\mathcal{C}^{\prime}_{\tau,k}:=\left\\{\omega\in\mathcal{C}_{\tau,k}\,\colon\,\forall
w\in V^{i}_{\tau}\colon\omega(w)\neq c\right\\}$ be the set of partial
colorings in $\mathcal{C}_{\tau,k}$ where none of vertices in $V^{i}_{\tau}$
is colored $c$.

######  Lemma 19.

$A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}\preceq\frac{a_{h}^{2}\absolutevalue{\mathcal{C}^{\prime}_{\tau,k}}}{k^{2}\absolutevalue{\mathcal{C}_{\tau,k}}^{2}}\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}A_{\tau}^{i,\omega}\Pi^{-1}_{\tau}A_{\tau}^{i,\omega}$.

###### Proof.

It follows from Lemma 16 that

$A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}=\left(\frac{a_{h}}{k\cdot\absolutevalue{\mathcal{C}_{\tau,k}}}\right)^{2}\left(\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}A_{\tau}^{i,\omega}\right)\Pi^{-1}_{\tau}\left(\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}A_{\tau}^{i,\omega}\right)\stackrel{{\scriptstyle(\heartsuit)}}{{\preceq}}\frac{a_{h}^{2}\absolutevalue{\mathcal{C}^{\prime}_{\tau,k}}}{k^{2}\absolutevalue{\mathcal{C}_{\tau,k}}^{2}}\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}A_{\tau}^{i,\omega}\Pi^{-1}_{\tau}A_{\tau}^{i,\omega},$
(13)

where $(\heartsuit)$ is due to Corollary 12. ∎

In the following discussion, let
$\gamma=\frac{2(1+\iota(\Delta))\exp\left(\iota(\Delta)\right)}{\beta-1}$.

######  Lemma 20.

$A_{\tau}^{i,\omega}\Pi_{\tau}^{-1}A_{\tau}^{i,\omega}\preceq\gamma
k\cdot\Xi_{\tau}^{i,\omega}\left(\left(\mathtt{Adj}_{\tau}^{i}\right)^{2}+\frac{25h^{2}}{(\beta-1)^{2}}\mathtt{Id}_{\tau}^{i}\right)\Xi_{\tau}^{i,\omega}$.

###### Proof.

By Lemma 18, for any $uc\in V_{\tau}^{i,c}$,

$\Xi_{\tau}^{i,\omega}\Pi_{\tau}^{-1}(uc,uc)\leq\frac{\ell_{u}^{\tau}}{\ell_{u}^{\tau}-\Delta_{\tau}(u)-1}k\exp\left(\frac{\Delta_{\tau}(u)}{\beta}\right)\leq
k(1+\iota(\Delta))\exp\left(\iota(\Delta)\right).$ (14)

Then it follows from Lemma 17 and
$\Xi_{\tau}^{i,\omega}\preceq\frac{1}{\beta-1}\cdot\mathtt{Id}_{\tau}^{i}$
that

$\displaystyle A_{\tau}^{i,\omega}\Pi_{\tau}^{-1}A_{\tau}^{i,\omega}\preceq
k\gamma\Xi_{\tau}^{i,\omega}\left(\left(\mathtt{Adj}_{\tau}^{i}\right)^{2}+\frac{25h^{2}}{(\beta-1)^{2}}\mathtt{Id}_{\tau}^{i}\right)\Xi_{\tau}^{i,\omega}.$

∎

######  Lemma 21.

$\frac{1}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\Pi_{\tau}^{-1}\sum_{\omega\in\mathcal{C}_{\tau,k}^{\prime}}\Xi_{\tau}^{i,\omega}=\mathtt{Id}_{\tau}^{i}$.

###### Proof.

Let $uc\in V_{\tau}^{i,c}$. Recall that
$\pi_{\tau}(uc)=\frac{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{\tau,k}\,\colon\,\sigma(u)=c\right\\}}}{k\absolutevalue{\mathcal{C}_{\tau,k}}}$.
As we did in Lemma 16, we use the notation $C_{\tau}^{V^{\prime}}$ to
represent the set of proper partial colorings restricted on $V^{\prime}\subset
V_{\tau}$ when $\tau$ is pinned. Therefore,

$\displaystyle\frac{1}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\pi_{\tau}^{-1}(uc)\sum_{\omega\in\mathcal{C}_{\tau,k}^{\prime}}\Xi_{\tau}^{i,\omega}(uc,uc)$
$\displaystyle=\frac{1}{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{\tau,k}\,\colon\,\sigma(u)=c\right\\}}}\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}\frac{1}{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{(\tau\cup\omega)|_{V\setminus\left\\{u\right\\}},1}\,\colon\,\sigma(u)\neq
c\right\\}}}$
$\displaystyle=\frac{1}{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{\tau,k}\,\colon\,\sigma(u)=c\right\\}}}\sum_{\omega^{\prime}\in\mathcal{C}^{\prime
V_{\tau}\setminus\left\\{u\right\\}}_{\tau}}\frac{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{\tau\cup\omega^{\prime},1}\,\colon\,\sigma(u)\neq
c\right\\}}}{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{\tau\cup\omega^{\prime},1}\,\colon\,\sigma(u)\neq
c\right\\}}}$ $\displaystyle=\frac{\absolutevalue{\mathcal{C}^{\prime
V_{\tau}\setminus\left\\{u\right\\}}_{\tau}}}{\absolutevalue{\left\\{\sigma\in\mathcal{C}_{\tau,k}\,\colon\,\sigma(u)=c\right\\}}}$
$\displaystyle=1,$

where the second equation is obtained by taking the summation over the color
of $u$ when others are fixed. ∎

We are now ready to bound
$\left((k-1)\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right]-(k-2)\cdot
A_{\tau}^{i}+4A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}\right)$ in the LHS of
Equation 9.

######  Lemma 22.

There exists a sequence of non-negative numbers $\left\\{a_{h}\right\\}_{0\leq
h\leq\Delta}$ such that

$\Pi_{\tau}^{-\frac{1}{2}}\left((k-1)\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right]-(k-2)\cdot
A_{\tau}^{i}+4A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}\right)\Pi_{\tau}^{-\frac{1}{2}}\preceq\frac{96\cdot
h\cdot(1+\iota(\Delta))\iota(\Delta)\exp\left(\iota(\Delta)\right)}{(\beta-1)^{2}}\mathtt{Id}_{\tau}^{i}.$

###### Proof.

Applying Lemma 16 and Lemma 19, we obtain

$\mathtt{LHS}\preceq\frac{1}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\Pi_{\tau}^{-\frac{1}{2}}\left((h-1)(a_{h-1}-a_{h})\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}A_{\tau}^{i,\omega}+\frac{4a_{h}^{2}}{k}\cdot\frac{\absolutevalue{\mathcal{C}^{\prime}_{\tau,k}}}{\absolutevalue{\mathcal{C}_{\tau,k}}}\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}A_{\tau}^{i,\omega}\Pi^{-1}_{\tau}A_{\tau}^{i,\omega}\right)\Pi_{\tau}^{-\frac{1}{2}}.$

Then by Lemma 17 and Lemma 20, we can bound above by

$\frac{1}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\Pi_{\tau}^{-\frac{1}{2}}\left(\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}\Xi_{\tau}^{i,\omega}\left(-(h-1)(a_{h-1}-a_{h})\mathtt{Adj}_{\tau}^{i}+4a_{h}^{2}\gamma\left(\mathtt{Adj}_{\tau}^{i}\right)^{2}\right)\Xi_{\tau}^{i,\omega}+\mathtt{Remainder}\right)\Pi_{\tau}^{-\frac{1}{2}},$

where
$\gamma=\frac{2(1+\iota(\Delta))\exp\left(\iota(\Delta)\right)}{\beta-1}$ and
$\mathtt{Remainder}=\left((h-1)(a_{h-1}-a_{h})\frac{5h}{\beta-1}+4a_{h}^{2}\gamma\frac{25h^{2}}{(\beta-1)^{2}}\right)\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}\left(\Xi_{\tau}^{i,\omega}\right)^{2}$.

Let us bound the spectral radius of

$A:=-(h-1)(a_{h-1}-a_{h})\mathtt{Adj}_{\tau}^{i}+4a_{h}^{2}\gamma\left(\mathtt{Adj}_{\tau}^{i}\right)^{2}.$

Since the spectrum of $\mathtt{Adj}_{\tau}^{i}$ is $\left\\{-1,h\right\\}$,
picking $a_{h}=\frac{1}{1+4\gamma(h-1)}$ for $1\leq h\leq\Delta$, we have

$\rho(A)\leq\frac{4\gamma(1+4\gamma(h-1))h}{(4\gamma(h-2)+1)(4\gamma(h-1)+1)^{2}}\leq
4\gamma h$ (15)

for $h\geq 2$. In particular, when $h=1$, $\rho(A)\leq 4a_{h}^{2}\gamma
h^{2}=4\gamma$, which is consistent with the above bound. So we have
$\rho(A)\leq 4\gamma h$ for $h\geq 1$. Note that
$\Xi_{\tau}^{i,\omega}\preceq\frac{1}{\beta-1}\cdot\mathtt{Id}_{\tau}^{i}$, it
then follows from Equation 15 and Lemma 21 that

$\displaystyle\phantom{{}={}}\frac{1}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\Pi_{\tau}^{-\frac{1}{2}}\left(\sum_{\omega\in\mathcal{C}^{\prime}_{\tau,k}}\Xi_{\tau}^{i,\omega}\left(-(h-1)(a_{h-1}-a_{h})\mathtt{Adj}_{\tau}^{i}+4a_{h}^{2}\gamma\left(\mathtt{Adj}_{\tau}^{i}\right)^{2}\right)\Xi_{\tau}^{i,\omega}\right)\Pi_{\tau}^{-\frac{1}{2}}$
(16) $\displaystyle\preceq\frac{8\gamma
h}{\beta-1}\mathtt{Id}_{\tau}^{i}\preceq\frac{16\cdot(1+\iota(\Delta))\exp\left(\iota(\Delta)\right)\cdot
h}{(\beta-1)^{2}}\cdot\mathtt{Id}_{\tau}^{i}.$

A direct calculation yields that

$\frac{\Pi_{\tau}^{-\frac{1}{2}}\left(\mathtt{Remainder}\right)\Pi_{\tau}^{-\frac{1}{2}}}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\preceq\frac{8\gamma}{\beta-1}\frac{5h^{2}}{\beta-1}\mathtt{Id}_{\tau}^{i}\preceq\frac{80\cdot
h\cdot(1+\iota(\Delta))\iota(\Delta)\exp\left(\iota(\Delta)\right)}{(\beta-1)^{2}}\mathtt{Id}_{\tau}^{i}.$
(17)

Combining Equation 16 and Equation 17 finishes the proof.

∎

####  3.3.3 Construction of $B_{\tau}$

Notice that we only need to consider Equation 9, the inductive constraint,
when $G_{\tau}$ is conencted. For $\tau$ of co-dimension $k>2$ such that
$G_{\tau}$ is connected, we introduce coefficients
$\left\\{b^{\prime}_{h}\right\\}_{1\leq h\leq\Delta}$ and
$\left\\{b_{h}\right\\}_{1\leq h\leq\Delta}$ whose values will be determined
later, and define $B_{\tau}$ as follows:

$B_{\tau}(vc,vc)=\begin{cases}b^{\prime}_{\Delta_{\tau}(u)}&\text{if
}\Delta_{\tau}(v)=1,u\sim_{\tau}v;\\\ b_{\Delta_{\tau}(v)}&\text{if
}\Delta_{\tau}(v)\geq 2,\end{cases}$ (18)

for any $v\in V_{\tau}$ and all other entries are $0$ where $u\sim_{\tau}v$
means $u$ and $v$ are adjacent in $G_{\tau}$. When
$\Delta_{\tau}(v)=\Delta_{\tau}(u)=1$, this is exactly the base case
considered in Section 3.2. According to Section 3.2, we have
$b^{\prime}_{1}=\frac{1}{\left(\beta-1\right)^{2}}$.

Note that by Lemma 14, eq. 9 is equivalent to

$\displaystyle\begin{aligned}
\sum_{i\in\widehat{V}}\Pi_{\tau}^{-1/2}\left((k-1)\cdot\mathbf{E}_{x\sim\pi_{\tau}}\left[A_{\tau\cup\left\\{x\right\\}}^{i}\right]-(k-2)\cdot
A_{\tau}^{i}+4A_{\tau}^{i}\Pi_{\tau}^{-1}A_{\tau}^{i}\right)\Pi_{\tau}^{-1/2}\\\
\preceq(k-2)B_{\tau}-(k-1)\cdot\Pi_{\tau}^{-1}\mathbf{E}_{x\sim\pi_{\tau}}\left[\Pi_{\tau\cup\left\\{x\right\\}}B_{\tau\cup\left\\{x\right\\}}\right]-4B_{\tau}^{2}.\end{aligned}$
(19)

Denote the RHS of Equation 19 by $B$, i.e.,

$B:=(k-2)B_{\tau}-(k-1)\cdot\Pi_{\tau}^{-1}\mathbf{E}_{x\sim\pi_{\tau}}\left[\Pi_{\tau\cup\left\\{x\right\\}}B_{\tau\cup\left\\{x\right\\}}\right]-4B_{\tau}^{2}.$

Then we have

$\displaystyle\begin{aligned}
B(vc,vc)&=(k-2)B_{\tau}(vc,vc)-(k-1)\cdot\pi_{\tau}(vc)^{-1}\sum_{x\in\mathcal{C}_{\tau}}{\pi_{\tau}(x)\pi_{\tau\cup\left\\{x\right\\}}(vc)B_{\tau\cup\left\\{x\right\\}}}(vc,vc)-4B_{\tau}(vc,vc)^{2}\\\
&=(k-2)B_{\tau}(vc,vc)-(k-1)\cdot\sum_{x\in\mathcal{C}_{\tau}}{\pi_{\tau\cup\left\\{vc\right\\}}(x)B_{\tau\cup\left\\{x\right\\}}}(vc,vc)-4B_{\tau}(vc,vc)^{2}\end{aligned}$
(20)

where the last equality follows from the fact that
$\pi_{\tau}(x)\pi_{\tau\cup\left\\{x\right\\}}(vc)=\pi_{\tau\cup\left\\{vc\right\\}}(x)\pi_{\tau}(vc)$.

##### Case 1: $\Delta_{\tau}(v)=1$ and $u\sim_{\tau}v$.

We have

$(k-1)\sum_{x\in\mathcal{C}_{\tau}}\pi_{\tau\cup\left\\{vc\right\\}}(x)B_{\tau\cup\left\\{x\right\\}}(vc,vc)=(\Delta_{\tau}(u)-1)b^{\prime}_{\Delta_{\tau}(u)-1}+(k-\Delta_{\tau}(u)-1)b^{\prime}_{\Delta_{\tau}(u)}.$

Then

$B(vc,vc)=(\Delta_{\tau}(u)-1)(b^{\prime}_{\Delta_{\tau}(u)}-b^{\prime}_{\Delta_{\tau}(u)-1})-4(b^{\prime}_{\Delta_{\tau}(u)})^{2}.$

##### Case 2: $\Delta_{\tau}(v)\geq 2$.

Assume $b^{\prime}_{h}\leq b_{1}$ for any $1\leq h\leq\Delta$. We have

$(k-1)\sum_{x\in\mathcal{C}_{\tau}}\pi_{\tau\cup\left\\{vc\right\\}}(x)B_{\tau\cup\left\\{x\right\\}}(vc,vc)\leq\Delta_{\tau}(v)b_{\Delta_{\tau}(u)-1}+(k-\Delta_{\tau}(v)-1)b_{\Delta_{\tau}(u)}.$

Then

$B(vc,vc)\geq(\Delta_{\tau}(v)-1)b_{\Delta_{\tau}(v)}-\Delta_{\tau}(v)b_{\Delta_{\tau}(v)-1}-4b_{\Delta_{\tau}(v)}^{2}.$

Also for any $v=(i_{1},i_{2})\in V_{\tau}$ where $i_{1},i_{2}\in\widehat{V}$,
$\sum_{i\in\widehat{V}}h_{\tau}^{i}=h_{\tau}^{i_{1}}+h_{\tau}^{i_{2}}\leq\Delta_{\tau}(v)$.
From the analysis in the above two cases, by Lemma 22, eq. 9 is satisfied as
long as

$\frac{96\cdot\iota(\Delta)(1+\iota(\Delta))\exp\left(\iota(\Delta)\right)}{(\beta-1)^{2}}\leq(\Delta_{\tau}(v)-1)(b^{\prime}_{\Delta_{\tau}(v)}-b^{\prime}_{\Delta_{\tau}(v)-1})-4(b^{\prime}_{\Delta_{\tau}(v)})^{2},$
(21)

and

$\frac{96\cdot(1+\iota(\Delta))\iota(\Delta)\exp\left(\iota(\Delta)\right)}{(\beta-1)^{2}}\Delta_{\tau}(v)\leq(\Delta_{\tau}(v)-1)b_{\Delta_{\tau}(v)}-\Delta_{\tau}(v)b_{\Delta_{\tau}(v)-1}-4b_{\Delta_{\tau}(v)}^{2},$
(22)

for any $v\in V_{\tau}$. We remark that the above constraints only appear for
$\Delta_{\tau}(v)\geq 2$ since $\mathtt{codim}(\tau)>2$ and $G_{\tau}$ is
connected. This is crucial since otherwise, the inequality system derived
later has no solution. Assume $\beta\geq 21$. Since

$\displaystyle\begin{split}\Pi_{\tau}^{-1/2}A_{\tau}^{i}\Pi_{\tau}^{-1/2}&=\frac{a_{h_{\tau}^{i}}}{k}\cdot\frac{1}{\absolutevalue{\mathcal{C}_{\tau,k}}}\cdot\Pi_{\tau}^{-1/2}\sum_{\begin{subarray}{c}\omega\in\mathcal{C}_{\tau,k}\colon\\\
\forall w\in V^{i}_{\tau}\colon\omega(w)\neq
c\end{subarray}}A^{i,\omega}_{\tau}\Pi_{\tau}^{-1/2}\\\
&=\frac{a_{h_{\tau}^{i}}}{k\absolutevalue{\mathcal{C}_{\tau,k}}}\Pi_{\tau}^{-1/2}\sum_{\omega\in\mathcal{C}_{\tau,k}^{\prime}}\Xi_{\tau}^{i,\omega}(-\mathtt{Adj}_{\tau}^{i}+\mathcal{R}_{\tau}^{i,\omega})\Xi_{\tau}^{i,\omega}\Pi_{\tau}^{-1/2}\\\
&\preceq\frac{a_{h_{\tau}^{i}}}{2(\beta-1)}\left(1+\frac{5h_{\tau}^{i}}{\beta-1}\right)\mathtt{Id}_{\tau}^{i}\\\
&\preceq\frac{1}{2(\beta-1)}\frac{1+\frac{5h_{\tau}^{i}}{\beta-1}}{1+\frac{8(h_{\tau}^{i}-1)(1+\iota(\Delta))\exp(\iota(\Delta))}{\beta-1}}\mathtt{Id}_{\tau}^{i}\\\
&\preceq\frac{1}{20}\mathtt{Id}_{\tau}^{i},\end{split}$ (23)

we have
$M_{\tau}=\frac{\sum_{i}A_{\tau}^{i}+\Pi_{\tau}B_{\tau}}{k-1}\preceq\frac{k-1}{3k-1}\Pi_{\tau}$
as long as
$B_{\tau}\preceq\left(\frac{(k-1)^{2}}{3k-1}-\frac{1}{10}\right)\mathtt{Id}_{\tau}$.
We strengthen this constraint to
$B_{\tau}\preceq\left(\frac{1}{5}-\frac{1}{10}\right)\mathtt{Id}_{\tau}=\frac{1}{10}\mathtt{Id}_{\tau}$.

For brevity, we denote
$96(1+\iota(\Delta))\iota(\Delta)\exp\left(\iota(\Delta)\right)$ by
$C(\Delta)$ in the following calculation. Therefore, our constraints for
$\left\\{b^{\prime}_{h}\right\\}_{1\leq h\leq\Delta}$ and
$\left\\{b_{h}\right\\}_{1\leq h\leq\Delta}$ are

$\begin{cases}b^{\prime}_{1}=\frac{1}{(\beta-1)^{2}};&\\\
(h-1)(b^{\prime}_{h}-b^{\prime}_{h-1})\geq
4(b^{\prime}_{h})^{2}+\frac{C(\Delta)}{(\beta-1)^{2}}&2\leq h\leq\Delta;\\\
b_{1}\geq b^{\prime}_{h}&1\leq h\leq\Delta;\\\ (h-1)b_{h}-hb_{h-1}\geq
4b_{h}^{2}+\frac{C(\Delta)h}{(\beta-1)^{2}},&2\leq h\leq\Delta;\\\
b_{h}\leq\frac{1}{10},&1\leq h\leq\Delta.\end{cases}$ ($\blacktriangle$)

It follows from Lemma 24 that there exists a feasible solution of
$b^{\prime}_{h}$ such that
$b^{\prime}_{h}\leq\frac{1+\left(4C(\Delta)+32/(\beta-1)^{2}\right)\log\Delta}{(\beta-1)^{2}}$
as long as $\beta\geq
4\sqrt{2\log\Delta\left(\sqrt{1+4C(\Delta)^{2}\log^{2}\Delta}+2C(\Delta)\log\Delta\right)}+1$.
Since $C(\Delta)\geq 96$, the requirement can be strengthened to $\beta\geq
4\sqrt{2(4+\varepsilon_{0})C(\Delta)}\log\Delta+1$, where
$\varepsilon_{0}\approx 10^{-4}$ is a constant, and $b^{\prime}_{h}$ can be
upper bounded by

$b^{\prime}_{h}\leq\frac{5C(\Delta)\log\Delta}{(\beta-1)^{2}}.$

Therefore, we can set $b_{1}=\frac{5C(\Delta)\log\Delta}{(\beta-1)^{2}}$, then
by Lemma 25, $b_{h}=\frac{5C(\Delta)\left(1+(6\log\Delta+\frac{16}{5})\cdot
h\log h\right)}{(\beta-1)^{2}}$ is a feasible solution of the Equation
$\blacktriangle$ if
$\beta\geq(c\sqrt{\Delta}\log^{2}\Delta+2c)\sqrt{5C(\Delta)\log\Delta}+1$
where $c=4\sqrt{2(1+\frac{2}{5\log\Delta})}$. Therefore, our final constraints
for $\beta$ are

$\begin{cases}\beta\geq 21;\\\ \beta\geq\frac{\Delta}{\iota(\Delta)}+1;\\\
\beta\geq 4\sqrt{10\cdot
96(1+\iota(\Delta))\iota(\Delta)\exp(\iota(\Delta))}\log\Delta+1;\\\
\beta\geq(c\sqrt{\Delta}\log^{2}\Delta+2c)\sqrt{5\cdot
96(1+\iota(\Delta))\iota(\Delta)\exp\left(\iota(\Delta)\right)\log\Delta}+1\text{
with }c=4\sqrt{2(1+\frac{2}{5\log\Delta})}.\end{cases}$ ($\heartsuit$)

Taking $\iota(\Delta)=1+0.1\log\Delta$, we obtain the final requirement for
$\beta$:

$\beta\geq\max\left\\{\frac{10\Delta}{\log\Delta},416(\Delta^{0.625}\log^{5/2}\Delta+2\Delta^{0.125}\log^{1/2}\Delta)\right\\}+1.$

###  3.4 Proof of the main theorems

######  Theorem 23.

Let $(\mathcal{C},\pi_{n})$ be a weighted simplicial complex where $\pi_{n}$
is a uniform distribution over proper $\beta$-extra list-colorings over a line
graph $G=(V,E)$ with $|V|=n$ and maximum degree $\Delta$. Then as long as

$\beta\geq\max\left\\{\frac{10\Delta}{\log\Delta},416(\Delta^{0.625}\log^{5/2}\Delta+2\Delta^{0.125}\log^{1/2}\Delta)\right\\}+1=O(\Delta/\log\Delta),$

we have $\lambda_{2}(P_{\tau})\leq\frac{1}{9(k-1)}$ for any
$\tau\in\mathcal{C}$ of co-dimension $k$. Therefore

  1. 1.

$\rho_{\mathtt{LS}}(P_{\mathtt{GL}})=\Omega\left(1/n\right)$, the mixing time
of $P_{\mathtt{GL}}$ is $O_{\Delta}(n\log n)$;

  2. 2.

$\lambda(P_{\mathtt{GL}})=\Omega\left(n^{-10/9}\right)$, the mixing time of
$P_{\mathtt{GL}}$ is $O(n^{19/9}\log q)$,

where $P_{\mathtt{GL}}$ is the transition matrix of Glauber dynamics on
$(\mathcal{C},\pi_{n})$.

###### Proof of Theorem 23.

As we did in Section 3.2 and Section 3.3, we are able to construct a set of
matrices $\left\\{M_{\tau}\right\\}_{\tau\in\mathcal{C}_{\leq
n-2}}$222$\mathcal{C}_{\leq n-2}$ means all faces of dimension at most $n-2$
in $\mathcal{C}$. which are block diagonal with the block $N_{\tau}^{c}$ for
each color $c$. In the following discussion, we fix a color $c$ and drop the
superscript $c$. In our construction,
$N_{\tau}=\frac{1}{k-1}(A_{\tau}+\Pi_{\tau}B_{\tau})=\frac{1}{k-1}\left(\sum_{i\in\widehat{V}}A_{\tau}^{i}+\Pi_{\tau}B_{\tau}\right)$.
By ($\heartsuit$ ‣ 3.3.3), as long as

$\beta\geq\max\left\\{\frac{10\Delta}{\log\Delta},416(\Delta^{0.625}\log^{5/2}\Delta+2\Delta^{0.125}\log^{1/2}\Delta)\right\\}+1,$
(24)

we have $B_{\tau}\preceq\frac{1}{10}\mathtt{Id}_{\tau}$. And by (23), we have
$\Pi_{\tau}^{-1/2}A_{\tau}\Pi_{\tau}^{-1/2}\preceq\frac{1}{\beta-1}\sum_{i\in\widehat{V}}\mathtt{Id}_{\tau}^{i}\preceq\frac{2}{\beta-1}\mathtt{Id}_{\tau}\leq\frac{1}{500}$.
Therefore,
$\lambda_{1}\left(\Pi_{\tau}^{-1}N_{\tau}\right)\leq\frac{1}{9(k-1)}$ and
hence $\left\\{M_{\tau}\right\\}$ satisfy all the conditions in Proposition 9.
So we immediately have $\lambda_{2}\left(P_{\tau}\right)\leq\frac{1}{9(k-1)}$
by Proposition 9.

Calculating the modified log-Sobolev constant by Proposition 6, we get
$\rho_{\mathtt{LS}}(P_{\mathtt{GL}})=O_{\Delta}(1/n)$, therefore the mixing
time is $O_{\Delta}(n\log n)$, proving the first part of the theorem.

Calculating the spectral gap, Proposition 5 implies

$\displaystyle\log\lambda(P_{\mathtt{GL}})$
$\displaystyle\geq\log{\frac{1}{n}}+\sum_{k=2}^{n}\left(\log\left(k-\frac{10}{9}\right)-\log(k-1)\right)$
$\displaystyle\geq\log{\frac{1}{n}}+\log{\frac{8}{9}}+\frac{1}{9}\left(\left(\sum_{k=2}^{n-1}\log(k-1)-\log(k)\right)\right)$
$\displaystyle\geq\log{\frac{8}{9n^{10/9}}},$

so $\lambda(P_{\mathtt{GL}})=\Omega\left(n^{-10/9}\right)$. Since
$\pi_{min}\geq q^{-n}$, by Lemma 4, the mixing time is $O(n^{19/9}\log q)$,
proving the second part of the theorem. ∎

###### Proof of Theorem 1 and Theorem 2.

Here we only need to unify the bound in Equation 24 to the form of $\beta\geq
C\cdot\frac{\Delta}{\log\Delta}$. By calculation, the maximum value of
$416(\Delta^{0.625}\log^{5/2}\Delta+2\Delta^{0.125}\log^{1/2}\Delta)/(\Delta/\log\Delta)$
when $\Delta\geq 1$ is less than $31210$. So the final bound of $\beta$ is
$\beta\geq 31210\cdot\frac{\Delta}{\log\Delta}$. ∎

##  4 Solving the Constraints

######  Lemma 24.

Given positive constants $C_{1},C_{2}$, and $H\in\mathbb{N}_{\geq 1}$,
consider the inductive constraint

$\begin{cases}b^{\prime}_{1}=\frac{1}{p^{2}};&\\\
(h-1)\left(b^{\prime}_{h}-b^{\prime}_{h-1}\right)\geq
C_{1}(b^{\prime}_{h})^{2}+\frac{C_{2}}{p^{2}},&2\leq h\leq H.\end{cases}$
($\blacktriangledown$)

Then eq. $\blacktriangledown$ is solvable when $p\geq 2\sqrt{2C_{1}\log
H\left(\sqrt{1+4C_{2}^{2}\log^{2}H}+2C_{2}\log H\right)}$. Moreover, under
this condition, a feasible solution satisfies
$b^{\prime}_{h}\leq\frac{1}{p^{2}}\left(1+\left(4C_{2}+\frac{8C_{1}}{p^{2}}\right)\log
H\right)$.

###### Proof.

Let

$b^{\prime}_{h}=\frac{1}{p^{2}}\left(1+\eta{}\log h\right),$

We have $b^{\prime}_{1}=1/p^{2}$ so the first constraint is satisfied.

Plugging $b^{\prime}_{h}$ into the second constraint, we have

$\frac{1}{p^{2}}(h-1){\eta{}\log\left(\frac{h}{h-1}\right)}\geq
C_{1}\frac{1}{p^{4}}\left(1+\eta{}\log h\right)^{2}+\frac{1}{p^{2}}C_{2}.$

Since $(h-1)\log\left(\frac{h}{h-1}\right)\geq\frac{1}{2}$,
$\left(1+\eta{}\log h\right)^{2}\leq 2+2\eta^{2}\log^{2}h$, $\log h\leq\log
H$, we can strengthen this constraint to

$\frac{1}{2p^{2}}\eta{}\geq C_{1}\frac{1}{p^{4}}\left(2+2(\eta{}\log
H)^{2}\right)+\frac{1}{p^{2}}C_{2}.$

Multiplying both sides by $2p^{4}$ and moving all terms to the same side, we
have

$4C_{1}(\log^{2}H)\eta{}^{2}-p^{2}\eta{}+2{p^{2}}C_{2}+4C_{1}\leq 0.$ (25)

As long as we can find an $\eta{}$ that satisfies Equation 25, the constraint
Equation $\blacktriangledown$ is satisfied by our $b^{\prime}_{h}$. Since
Equation 25 is nothing but a quadratic equation about $\eta{}$, we can
immediately calculate that the minimum solution of $\eta{}$ is

$\displaystyle\eta{}^{*}$
$\displaystyle=\frac{p^{2}-\sqrt{p^{4}-4\left(16C_{1}^{2}\log^{2}H+8C_{1}C_{2}{\log^{2}H}p^{2}\right)}}{8C_{1}\log^{2}H}$
$\displaystyle\leq\frac{4\left(16C_{1}^{2}\log^{2}H+8C_{1}C_{2}\log^{2}Hp^{2}\right)}{p^{2}\cdot
8C_{1}\log^{2}H}$ $\displaystyle=\frac{8C_{1}}{p^{2}}+4C_{2}.$

Notice that $\eta{}^{*}$ exists as long as
$p\geq\left(64C_{1}^{2}\log^{2}H+\left(32C_{1}C_{2}\log^{2}H\right)p^{2}\right)^{1/4}$,
i.e.,

$p^{2}\geq 8C_{1}\log H\left(\sqrt{1+4C_{2}^{2}\log^{2}H}+2C_{2}\log
H\right).$

So by using $\eta{}^{*}$ as the coefficient $\eta$ in $b^{\prime}_{h}$, we get
a feasible solution of Equation $\blacktriangledown$, and for all $1\leq h\leq
H$,

$b^{\prime}_{h}\leq b^{\prime}_{H}\leq\frac{1}{p^{2}}\left(1+\eta{}\log
H\right)\leq\frac{1}{p^{2}}\left(1+\left(4C_{2}+\frac{8C_{1}}{p^{2}}\right)\log
H\right).$

∎

######  Lemma 25.

Given positive constants $C_{1},C_{2},C_{3}$, $1/2\leq\alpha\leq 1$ and
$H\in\mathbb{N}_{\geq 1}$, consider the inductive constraint

$\begin{cases}b_{1}=\frac{1}{p^{2}};&\\\ (h-1)b_{h}-hb_{h-1}\geq
C_{1}b_{h}^{2}+\frac{C_{2}}{p^{2}}h^{2\alpha},&2\leq h\leq H;\\\ b_{h}\leq
C_{3},&1\leq h\leq H.\end{cases}$ ($\star$)

Then eq. $\star$ is solvable when $p\geq cH^{\alpha}\log^{2}H+2c$, where
$c=\max\left\\{\sqrt{8C_{1}},\sqrt{\frac{2}{C_{3}}}\right\\}\sqrt{1+2C_{2}}$.

###### Proof.

If $H$ = 1, then eq. $\star$ is equivalent to $\frac{1}{p^{2}}\leq C_{3}$, it
is satisfiable as long as
${\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}p\geq\frac{1}{\sqrt{C_{3}}}}$.

Next, we consider the case that $H\geq 2$. Let

$b_{h}=\frac{1}{p^{2}}\left(1+\eta{}\left(H^{2\alpha-1}\log H\right)h\log
h\right),$

where $\eta{}>0$ is a constant to be determined. Since
$b_{1}=\frac{1}{p^{2}}$, the first constraint holds.

The second constraint: Plugging $b_{h}$ into the second constraint, we have

$-\frac{1}{p^{2}}+\eta{}\frac{H^{2\alpha-1}\log
H}{p^{2}}h(h-1)\log\left(\frac{h}{h-1}\right)\geq\frac{C_{1}}{p^{4}}\left(1+\left(\eta{}H^{2\alpha-1}\log
H\right)h\log h\right)^{2}+\frac{C_{2}}{p^{2}}h^{2\alpha}$

Multiplying $p^{4}$ on both sides, we have

$-p^{2}+p^{2}\eta{}\left(H^{2\alpha-1}\log
H\right)h(h-1)\log\left(\frac{h}{h-1}\right)\geq
C_{1}\left(1+\left(\eta{}H^{2\alpha-1}\log H\right)h\log
h\right)^{2}+p^{2}C_{2}h^{2\alpha}$

Since $\log\left(\frac{h}{h-1}\right)\geq\frac{1}{h}$ and
$h(h-1)H^{2\alpha-1}\log H\geq 0$, We can replace
$\log\left(\frac{h}{h-1}\right)$ for $\frac{1}{h}$, strengthening the
constraint.

$p^{2}\left(\eta{}H^{2\alpha-1}\log
H(h-1)-1-C_{2}h^{2\alpha}\right)-C_{1}\left(1+\left(\eta{}H^{2\alpha-1}\log
H\right)h\log h\right)^{2}\geq 0.$ (26)

Next, we simplify the two terms for calculation convenience. By the assumption
$\alpha\geq 1/2$ and $h,H\geq 2$, we have $H^{2\alpha-1}\log H(h-1)\geq\log
2>\frac{1}{2}$. Moreover, $h\geq 2$ implies $h-1\geq\frac{h}{2}$, so for the
first term,

$p^{2}\left(\eta{}H^{2\alpha-1}\log H(h-1)-1-C_{2}h^{2\alpha}\right)\geq
p^{2}\left(\frac{\eta{}-2}{2}\left(H^{2\alpha-1}\log
H\right)h-C_{2}h^{2\alpha}\right).$ (27)

Here we assume $\eta{}-2\geq 0$ so that the above inequality holds.

Similarly, for the second term, using $1<2\left(H^{2\alpha-1}\log
H\right)h\log h$, we have

$C_{1}\left(1+\left(\eta{}H^{2\alpha-1}\log H\right)h\log h\right)^{2}\leq
C_{1}\left(\left(2+\eta{}\right)\left(H^{2\alpha-1}\log H\right)h\log
h\right)^{2}.$ (28)

Now we can strengthen eq. 26 using eq. 27 and eq. 28. The constraint suffices
to

$p^{2}\left(\frac{\eta{}-2}{2}\left(H^{2\alpha-1}\log
H\right)h-C_{2}h^{2\alpha}\right)-C_{1}\left(\left(2+\eta{}\right)\left(H^{2\alpha-1}\log
H\right)h\log h\right)^{2}.\geq 0.$ (29)

Notice that since $\alpha\geq\frac{1}{2}$, the left side is concave with
respect to $h\geq 2$, so in order to prove our $b_{h}$ satisfy eq. 26, it
suffices to prove eq. 29 holds for $h=2$ and $h=H$.

  1. 1.

When $h=2$, eq. 29 is

$p^{2}\left(\left(\eta{}-2\right)\left(H^{2\alpha-1}\log
H\right)-C_{2}2^{2\alpha}\right)-C_{1}\left(\left(2+\eta{}\right)\left(H^{2\alpha-1}\log
H\right)2\log 2\right)^{2}\geq 0.$

Since we have $C_{2}2^{2\alpha}\leq 4C_{2}\leq 8C_{2}H^{2\alpha-1}\log H$, we
can strengthen the constraint to

$\displaystyle p^{2}\left(\left(\eta{}-2-8C_{2}\right)\left(H^{2\alpha-1}\log
H\right)\right)-C_{1}\left(\left(2+\eta{}\right)\left(H^{2\alpha-1}\log
H\right)2\log 2\right)^{2}\geq 0.$

Here we additionally assume $\eta{}-2-8C_{2}>0$. As long as
${\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}p\geq\frac{\sqrt{C_{1}}\left(\eta{}+2\right)2\log
2}{\sqrt{\eta{}-2-8C_{2}}}\left(H^{2\alpha-1}\log H\right)^{1/2}}$, the
constraint holds for all $H\geq 2$.

  2. 2.

When $h=H$, eq. 29 is

$\displaystyle p^{2}\left(\frac{\eta{}-2}{2}H^{2\alpha}\log
H-C_{2}H^{2\alpha}\right)-C_{1}\left(\left(\eta{}+2\right)\left(H^{2\alpha}\log^{2}H\right)\right)^{2}\geq
0.$

Since $C_{2}H^{2\alpha}\leq 4H^{2\alpha}\log H$, we can strengthen the
constraint to

$\displaystyle p^{2}\left(\frac{\eta{}-2-8C_{2}}{2}H^{2\alpha}\log
H\right)-C_{1}\left(\left(\eta{}+2\right)\left(H^{2\alpha}\log^{2}H\right)\right)^{2}\geq
0.$

as long as
${\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}p\geq\frac{\sqrt{C_{1}}\left(\eta{}+2\right)\sqrt{2}}{\sqrt{\eta{}-2-8C_{2}}}\left(H^{2\alpha}\log^{3}H\right)^{1/2}}$,
the constraint holds for all $H\geq 2$.

The third constraint: We have

$b_{h}\leq
b_{H}=\frac{1}{p^{2}}\left(1+\eta{}H^{2\alpha}\log^{2}H\right)\leq\frac{1}{p^{2}}\left(\left(\eta{}+2\right)H^{2\alpha}\log^{2}H\right)$

This constraint holds for all $H\geq 2$ as long as
${\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}p\geq\sqrt{\frac{\left(\eta{}+2\right)}{C_{3}}}H^{\alpha}\log
H}$.

Putting four bounds together: From the above discussion, we get four bounds
for $p$, such that as long as $p$ satisfies all of them, eq. $\star$ holds for
all $H\geq 1$. The four bounds are

$\begin{cases}p\geq\frac{1}{\sqrt{C_{3}}}\\\
p\geq\frac{\sqrt{C_{1}}\left(\eta{}+2\right)2\log
2}{\sqrt{\eta{}-2-8C_{2}}}\left(H^{2\alpha-1}\log H\right)^{1/2}\\\
p\geq\frac{\sqrt{C_{1}}\left(\eta{}+2\right)\sqrt{2}}{\sqrt{\eta{}-2-8C_{2}}}\left(H^{2\alpha}\log^{3}H\right)^{1/2}\\\
p\geq\sqrt{\frac{\left(\eta{}+2\right)}{C_{3}}}H^{\alpha}\log H\end{cases}.$

Letting $\eta{}=6+16C_{2}$, the bounds become

$\begin{cases}p\geq\frac{1}{\sqrt{C_{3}}}\\\ p\geq 2\log 2\cdot
4\sqrt{C_{1}\left(1+2C_{2}\right)}\left(H^{2\alpha-1}\log H\right)^{1/2}\\\
p\geq\sqrt{2}\cdot
4\sqrt{C_{1}\left(1+2C_{2}\right)}\left(H^{2\alpha}\log^{3}H\right)^{1/2}\\\
p\geq\sqrt{\frac{2\left(1+2C_{2}\right)}{C_{3}}}H^{\alpha}\log H\end{cases}.$

When $H\geq 3$, we have $\log H>1$, so the four constraints unify to

$p\geq\max\left\\{\sqrt{8C_{1}},\sqrt{\frac{2}{C_{3}}}\right\\}\sqrt{1+2C_{2}}H^{\alpha}\log^{2}H.$

When $H\leq 2$, we have $H^{\alpha}\leq 2,\log H\leq 1$, so the four
constraints unify to

$p\geq
2\max\left\\{\sqrt{8C_{1}},\sqrt{\frac{2}{C_{3}}}\right\\}\sqrt{1+2C_{2}}.$

Finally, we proved as long as

$p\geq\max\left\\{\sqrt{8C_{1}},\sqrt{\frac{2}{C_{3}}}\right\\}\sqrt{1+2C_{2}}H^{\alpha}\log^{2}H+2\max\left\\{\sqrt{8C_{1}},\sqrt{\frac{2}{C_{3}}}\right\\}\sqrt{1+2C_{2}},$

eq. $\star$ is solvable. ∎

## References

  * [AL20] Vedat Levi Alev and Lap Chi Lau.  Improved analysis of higher order random walks and applications.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1198–1211, 2020.
  * [ALOG21] Dorna Abdolazimi, Kuikui Liu, and Shayan Oveis Gharan.  A matrix trickle-down theorem on simplicial complexes and applications to sampling colorings.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 161–172. IEEE, 2021.
  * [Bha97] Rajendra Bhatia.  Matrix analysis.  Number 169 in Graduate texts in mathematics. Springer, New York, 1997\.
  * [CDM+19] Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle.  Improved bounds for randomly sampling colorings via linear programming.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2216–2234. SIAM, 2019.
  * [CGŠV21] Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda.  Rapid mixing for colorings via spectral independence.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548–1557. SIAM, 2021.
  * [CLMM23] Zongchen Chen, Kuikui Liu, Nitya Mani, and Ankur Moitra.  Strong spatial mixing for colorings on trees and its algorithmic applications, 2023.  To appear in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS).
  * [CLV21] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550, 2021.
  * [DF03] Martin Dyer and Alan Frieze.  Randomly coloring graphs with lower bounds on girth and maximum degree.  Random Structures & Algorithms, 23(2):167–179, 2003.
  * [DFHV13] Martin Dyer, Alan Frieze, Thomas P. Hayes, and Eric Vigoda.  Randomly coloring constant degree graphs.  Random Structures & Algorithms, 43(2):181–200, 2013.
  * [FGYZ20] Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang.  Rapid mixing from spectral independence beyond the boolean domain.  ACM Trans. Algorithms, 18(3), oct 2020.
  * [GKM15] David Gamarnik, Dmitriy Katz, and Sidhant Misra.  Strong spatial mixing of list coloring of graphs.  Random Structures & Algorithms, 46(4):599–613, 2015.
  * [Jer95] Mark Jerrum.  A very simple algorithm for estimating the number of k-colorings of a low-degree graph.  Random Structures & Algorithms, 7(2):157–165, 1995.
  * [LPW17] David A Levin, Yuval Peres, and Elizabeth L. Wilmer.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [Mol04] Michael Molloy.  The glauber dynamics on colorings of a graph with high girth and maximum degree.  SIAM Journal on Computing, 33(3):721–737, 2004.
  * [Opp18] Izhar Oppenheim.  Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps.  Discrete & Computational Geometry, 59(2):293–330, Mar 2018.
  * [SS97] Jesús Salas and Alan D Sokal.  Absence of phase transition for antiferromagnetic potts models via the dobrushin uniqueness theorem.  Journal of Statistical Physics, 86:551–579, 1997.

##  Appendix A The Matrix Trickle-Down Theorem

Let $(\mathcal{C},\pi_{n})$ be a weighted pure $n$-dimensional simplicial
complex.

######  Proposition 26 ( [Opp18]).

The following identities hold.

  1. 1.

$\mathbf{E}_{x\sim\pi_{1}}\left[\Pi_{x}\right]=\Pi$.

  2. 2.

$\mathbf{E}_{x\sim\pi_{1}}\left[\Pi_{x}P_{x}\right]=\Pi P$.

  3. 3.

$\mathbf{E}_{x\sim\pi_{1}}\left[\pi_{x}\pi_{x}^{\top}\right]=\Pi P^{2}$.

###### Proof.

  1. 1.

For any $y\in\mathcal{C}_{1}$, it holds that

$\displaystyle\mathbf{E}_{x\sim\pi_{1}}\left[\Pi_{x}\right](y,y)=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\
x\neq
y\end{subarray}}\pi_{1}(x)\pi_{x}(y)=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\
x\neq
y\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x\in\sigma\right]}{n}\cdot\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y\in\sigma\;\middle|\;x\in\sigma\right]}{n-1}.$

This can be simplified to

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x,y\in\sigma\right]}{n(n-1)}=\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y\in\sigma\right]}{n}=\Pi(y,y).$

  2. 2.

For any $y,z\in\mathcal{C}_{1}$, if $y=z$,
$\mathbf{E}_{x\sim\pi_{1}}\left[\Pi_{x}P_{x}\right](y,z)=\Pi P(y,z)=0$.
Otherwise, direct calculation gives

$\displaystyle\mathbf{E}_{x\sim\pi_{1}}\left[\Pi_{x}P_{x}\right](y,z)$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\pi_{1}(x)\pi_{x}(y)P_{x}(y,z)$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x\in\sigma\right]}{n}\cdot\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y\in\sigma\;\middle|\;x\in\sigma\right]}{n-1}\cdot\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y,z\in\sigma\;\middle|\;x\in\sigma\right]}{(n-2)\cdot\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y\in\sigma\;\middle|\;x\in\sigma\right]}.$

This can be simplified to

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x,y,z\in\sigma\right]}{n(n-1)(n-2)}=\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y,z\in\sigma\right]}{n(n-1)}.$

On the other hand, we have

$\Pi
P(y,z)=\pi_{1}(y)\cdot\frac{\pi_{2}(y,z)}{2\pi_{1}(y)}=\frac{1}{2}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y,z\in\sigma\right]}{\binom{n}{2}}=\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y,z\in\sigma\right]}{n(n-1)}.$

  3. 3.

For every $y,z\in\mathcal{C}_{1}$, it holds that

$\displaystyle\mathbf{E}_{x\sim\pi_{1}}\left[\pi_{x}\pi_{x}^{\top}\right](y,z)$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\pi_{1}(x)\pi_{x}(y)\pi_{x}(z)$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x\in\sigma\right]}{n}\cdot\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y\in\sigma\;\middle|\;x\in\sigma\right]}{n-1}\cdot\pi_{x}(z)$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x,y\in\sigma\right]}{n(n-1)}\cdot\pi_{x}(z).$

On the other hand, note that for every $x\in\mathcal{C}_{1}$, the row of $P$
indexed by $x$ is $\pi_{x}$, we have

$\displaystyle\left(\Pi P^{2}\right)(y,z)=\sum_{x\in\mathcal{C}_{1}}(\Pi
P)(y,x)\cdot
P(x,z)=\sum_{x\in\mathcal{C}_{1}}\pi_{1}(y)\pi_{y}(x)\cdot\pi_{x}(z).$

This can be written as

$\displaystyle\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\ x\neq
y,z\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[y\in\sigma\right]}{n}\cdot\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x\in\sigma\;\middle|\;y\in\sigma\right]}{n-1}\cdot\pi_{x}(z)=\sum_{\begin{subarray}{c}x\in\mathcal{C}_{1}\\\
x\neq
y,z\end{subarray}}\frac{\mathbf{Pr}_{\sigma\sim\pi_{n}}\left[x,y\in\sigma\right]}{n(n-1)}\cdot\pi_{x}(z).$

∎

To prove Proposition 8, we introduce the following property of the Loewner
order.

######  Lemma 27 (Lemma 2.3 in [ALOG21]).

Let $A,B\in\mathbb{R}^{n\times n}$ be two symmetric matrices. If
$A(I-\varepsilon A)\preceq B(I-\varepsilon B)$ for a constant $\varepsilon>0$
and $A,B\preceq\frac{1}{2\varepsilon}I$, then $A\preceq B$.

###### Proof.

Consider the matrix function $f(M)=M(I-M)$ for a symmetric matrix
$M\in\mathbb{R}^{n\times n}$ and $M\preceq\frac{1}{2\varepsilon}I$. If
$M=\sum_{i=1}^{n}\mu_{i}v_{i}v_{i}^{\top}$, then we have
$M(I-M)=\sum_{i=1}^{n}\mu_{i}(1-\varepsilon\mu_{i})v_{i}v_{i}^{\top}$, which
means that $f$ is a matrix function extended from a real bijective function
$x\mapsto x(1-\varepsilon x)$ from $(-\infty,1/2\varepsilon]$ to
$(-\infty,1/4\varepsilon^{2}]$. Therefore, from its inverse function
$x\mapsto\frac{1}{2\varepsilon}-(\frac{1}{4\varepsilon^{2}}-x)^{1/2}$, we give
the inverse function of $f$ on $\left\\{M\in\mathbb{R}^{n\times
n}\,\colon\,M\preceq\frac{1}{4\varepsilon^{2}}I\right\\}$:

$f^{-1}(M)=\frac{1}{2\varepsilon}I-\left(\frac{1}{4\varepsilon^{2}}-M\right)^{1/2}.$

Since $M\mapsto\sqrt{M}$ is monotone under Loewner order (see Theorem V.1.9 in
[Bha97]), it can be obtained by simple calculation that $f^{-1}$ is monotone
under Loewner order. ∎

###### Proof of Proposition 8.

For every $x\in\mathcal{C}_{1}$, eq. 2 is equivalent to

$\Pi_{x}P_{x}-\alpha\pi_{x}\pi_{x}^{\top}\preceq\Pi_{x}N_{x}\preceq\frac{1}{2\alpha+1}\Pi_{x}.$

Taking expectation and applying Proposition 26, we have

$\Pi P-\alpha\Pi
P^{2}\preceq\mathbf{E}_{x\sim\pi}\left[\Pi_{x}N_{x}\right]\preceq\frac{1}{2\alpha+1}\Pi,$

which is equivalent to

$P-\alpha
P^{2}\preceq_{\pi}\Pi^{-1}\mathbf{E}_{x\sim\pi}\left[\Pi_{x}N_{x}\right]\preceq_{\pi}\frac{1}{2\alpha+1}I.$

Therefore, $P-\alpha P^{2}\preceq_{\pi}N-\alpha N^{2}$. Picking
$Q=P-\beta\mathbf{1}\pi^{\top}$ with $\beta=2-\frac{1}{\alpha}$, we
immediately have

$P-\alpha P^{2}=Q-\alpha Q^{2}$

by comparing the spectrum. As a result,

$Q-\alpha Q^{2}\preceq_{\pi}N-\alpha N^{2},$

Since $\lambda_{2}(P_{x})\leq\frac{1}{2\alpha+1}$, by the original trickle-
down theorem (Proposition 7), we have $\lambda_{2}(P)\leq\frac{1}{2\alpha}$.
Combined with $\beta=2-\frac{1}{\alpha}\geq 1-\frac{1}{2\alpha}$ we obtain
that $Q\preceq\frac{1}{2\alpha}I$. It follows from Lemma 27 that
$Q\preceq_{\pi}N$. ∎

##  Appendix B Marginal Probability Bounds in [GKM15]

###### Proof of Lemma 18.

Let $V^{\prime}=V_{\tau}\setminus{u}$. For any proper partial coloring
$\omega$ on $V^{\prime}$ (boundary) when $\tau$ is pinned, let
$p_{G,\mathcal{L}}(uc|\omega)=\mathbf{Pr}_{\sigma\sim\mu}\left[\sigma(u)=c\;\middle|\;\tau\cup\omega\subset\sigma\right]$
where $\mu$ is the uniform distribution over all proper colorings of
$(G,\mathcal{L})$ and $p_{G,\mathcal{L}}(uc)=\mu_{u}^{\tau}(c)$.

For the upper bound of $\mu_{u}^{\tau}(c)$, it holds that

$p_{G,\mathcal{L}}(uc|\omega)\leq\frac{1}{\ell_{u}^{\tau\cup\omega}}\leq\frac{1}{\ell_{u}^{\tau}-\Delta_{\tau}(u)}.$
(30)

Therefore,

$\mu_{u}^{\tau}(c)=p_{G,\mathcal{L}}(uc)=\sum_{\omega}p_{G,\mathcal{L}}(uc|\omega)\mu_{V^{\prime}}^{\tau}(\omega)\leq\frac{1}{\ell_{u}^{\tau}-\Delta_{\tau}(u)}\leq\frac{1}{\beta}.$
(31)

As for the lower bound, assuming the free neighbors of $u$ after pinning
$\tau$ are $v_{1},v_{2},\dots,v_{\Delta_{\tau}(u)}$, recall the recursion on
marginal probabilities:

$p_{G,\mathcal{L}}(uc)=\frac{\prod_{i=1}^{\Delta_{\tau}(u)}(1-p_{G_{u},\mathcal{L}_{i,c}}(v_{i}c))}{\sum_{c^{\prime}\in
L_{u}^{\tau}}\prod_{i=1}^{\Delta_{\tau}(u)}(1-p_{G_{u},\mathcal{L}_{i,c^{\prime}}}(v_{i}c^{\prime}))},$

where $(G_{u},\mathcal{L}_{i,c})$ denote the coloring instance after removing
the vertex $u$ and color $c$ from the color lists of $u$’s neighbors $v_{j}$
for $j<i$. From (31) we have
$\prod_{i=1}^{\Delta_{\tau}(u)}(1-p_{G_{u},\mathcal{L}_{i,c}}(v_{i}c))\geq(1-\frac{1}{\beta})^{\Delta_{\tau}(u)}$.
Also $\sum_{c^{\prime}\in
L_{u}^{\tau}}\prod_{i=1}^{\Delta_{\tau}(u)}(1-p_{G_{u},\mathcal{L}_{i,c^{\prime}}}(v_{i}c^{\prime}))\leq\ell_{u}^{\tau}$.
So we have

$\mu_{u}^{\tau}(c)=p_{G,\mathcal{L}}(uc)\geq\frac{(1-\frac{1}{\beta})^{\Delta_{\tau}(u)}}{\ell_{u}^{\tau}}.$

∎