* Förster Schreiber et al. (2018) Förster Schreiber N. M., Renzini A., Mancini C., Genzel R., Bouché N., Cresci G., Hicks E. K. S., et al., 2018, ApJS, 238, 21
  * Freundlich et al. (2013) Freundlich J. et al., 2013, A&A, 553, A130
  * Genel et al. (2012) Genel S. et al., 2012, ApJ, 745, 11
  * Gentry et al. (2017) Gentry E. S., Krumholz M. R., Dekel A., Madau P., 2017, MNRAS, 465, 2471
  * Genzel et al. (2008) Genzel R. et al., 2008, ApJ, 687, 59
  * Genzel et al. (2014) Genzel R., Förster Schreiber N. M., Lang P., Tacchella S., Tacconi L. J., Wuyts S., et al., 2014, ApJ, 785, 75
  * Genzel et al. (2011) Genzel R., Newman S., Jones T., Förster Schreiber N. M., Shapiro K., Genel S., Lilly S. J., et al., 2011, ApJ, 733, 101
  * Genzel et al. (2006) Genzel R., Tacconi L. J., Eisenhauer F., Förster Schreiber N. M., Cimatti A., Daddi E., Bouché N., et al., 2006, Nature, 442, 786
  * Ginzburg et al. (2021) Ginzburg O., Huertas-Company M., Dekel A., Mandelker N., Snyder G., Ceverino D., Primack J., 2021, MNRAS, 501, 730
  * Guo et al. (2015) Guo Y. et al., 2015, ApJ, 800, 39
  * Guo et al. (2012) Guo Y., Giavalisco M., Ferguson H. C., Cassata P., Koekemoer A. M., 2012, ApJ, 757, 120
  * Guo et al. (2018) Guo Y. et al., 2018, ApJ, 853, 108
  * Hopkins, Quataert & Murray (2012a) Hopkins P. F., Quataert E., Murray N., 2012a, MNRAS, 421, 3522
  * Hopkins, Quataert & Murray (2012b) Hopkins P. F., Quataert E., Murray N., 2012b, MNRAS, 421, 3522
  * Huertas-Company et al. (2020) Huertas-Company M. et al., 2020, MNRAS, 499, 814
  * Immeli et al. (2004a) Immeli A., Samland M., Gerhard O., Westera P., 2004a, A&A, 413, 547
  * Immeli et al. (2004b) Immeli A., Samland M., Westera P., Gerhard O., 2004b, ApJ, 611, 20
  * Inoue et al. (2016) Inoue S., Dekel A., Mandelker N., Ceverino D., Bournaud F., Primack J., 2016, MNRAS, 456, 2052
  * Kim & Ostriker (2015) Kim C.-G., Ostriker E. C., 2015, ApJ, 802, 99
  * Kravtsov (2003) Kravtsov A. V., 2003, ApJ, 590, L1
  * Kravtsov, Klypin & Khokhlov (1997) Kravtsov A. V., Klypin A. A., Khokhlov A. M., 1997, ApJS, 111, 73
  * Kretschmer et al. (2021) Kretschmer M., Dekel A., Freundlich J., Lapiner S., Ceverino D., Primack J., 2021, MNRAS, 503, 5238
  * Krumholz & Burkert (2010) Krumholz M. R., Burkert A., 2010, ApJ, 724, 895
  * Krumholz et al. (2018) Krumholz M. R., Burkhart B., Forbes J. C., Crocker R. M., 2018, MNRAS, 477, 2716
  * Krumholz & Dekel (2010) Krumholz M. R., Dekel A., 2010, MNRAS, 406, 112
  * Krumholz, Dekel & McKee (2012) Krumholz M. R., Dekel A., McKee C. F., 2012, ApJ, 745, 69
  * Krumholz & Thompson (2012) Krumholz M. R., Thompson T. A., 2012, ApJ, 760, 155
  * Krumholz & Thompson (2013) Krumholz M. R., Thompson T. A., 2013, MNRAS, 434, 2329
  * Mandelker et al. (2017) Mandelker N., Dekel A., Ceverino D., DeGraf C., Guo Y., Primack J., 2017, MNRAS, 464, 635
  * Mandelker et al. (2014) Mandelker N., Dekel A., Ceverino D., Tweed D., Moody C. E., Primack J., 2014, MNRAS, 443, 3675
  * Moody et al. (2014) Moody C. E., Guo Y., Mandelker N., Ceverino D., Mozena M., Koo D. C., Dekel A., Primack J., 2014, MNRAS, 444, 1389
  * Moster, Naab & White (2018) Moster B. P., Naab T., White S. D. M., 2018, MNRAS, 477, 1822
  * Murray, Quataert & Thompson (2010) Murray N., Quataert E., Thompson T. A., 2010, ApJ, 709, 191
  * Newman et al. (2012) Newman S. F. et al., 2012, ApJ, 752, 111
  * Noguchi (1999) Noguchi M., 1999, ApJ, 514, 77
  * Oklopčić et al. (2017) Oklopčić A., Hopkins P. F., Feldmann R., Kereš D., Faucher-Giguère C.-A., Murray N., 2017, MNRAS, 465, 952
  * Ostriker & Shetty (2011) Ostriker E. C., Shetty R., 2011, ApJ, 731, 41
  * Renaud, Romeo & Agertz (2021) Renaud F., Romeo A. B., Agertz O., 2021, arXiv e-prints, arXiv:2106.00020
  * Rodríguez-Puebla et al. (2017) Rodríguez-Puebla A., Primack J. R., Avila-Reese V., Faber S. M., 2017, MNRAS, 470, 651
  * Sarkar, Gnat & Sternberg (2021) Sarkar K. C., Gnat O., Sternberg A., 2021, MNRAS, 504, 583
  * Tacchella et al. (2016a) Tacchella S., Dekel A., Carollo C. M., Ceverino D., DeGraf C., Lapiner S., Mandelker N., Primack J. R., 2016a, MNRAS, 458, 242
  * Tacchella et al. (2016b) Tacchella S., Dekel A., Carollo C. M., Ceverino D., DeGraf C., Lapiner S., Mandelker N., Primack Joel R., 2016b, MNRAS, 457, 2790
  * Tacconi et al. (2010) Tacconi L. J. et al., 2010, Nature, 463, 781
  * Tacconi et al. (2018) Tacconi L. J. et al., 2018, ApJ, 853, 179
  * Tacconi et al. (2013) Tacconi L. J., Neri R., Genzel R., Combes F., Bolatto A., Cooper M. C., Wuyts S., et al., 2013, ApJ, 768, 74
  * Tomassetti et al. (2016) Tomassetti M. et al., 2016, MNRAS, 458, 4477
  * Toomre (1964) Toomre A., 1964, ApJ, 139, 1217
  * Zolotov et al. (2015) Zolotov A. et al., 2015, MNRAS, 450, 2327


# The Analogue of Aldous’ spectral gap conjecture for the generalized
exclusion process

Kazuna Kanegae  and  Hidetada Wachi  Department of Mathematics, Faculty of
Science and Technology, Keio University, 3-14-1 Hiyoshi, Kouhoku-ku, Yokohama
223-8522, Japan<EMAIL_ADDRESS>Department of Mathematics, Faculty of
Science and Technology, Keio University, 3-14-1 Hiyoshi, Kouhoku-ku, Yokohama
223-8522, Japan<EMAIL_ADDRESS>
###### Abstract.

The spectral gap is an important value to evaluate the mixing time of the
continuous time Markov processes. Caputo, Ligget and Richthammer, in their
seminal paper [CLR10], proved Aldous’ spectral gap conjecture which asserts
that spectral gaps of the random walk and the interchange process on the
common weighted graph are equal. In this paper, we introduce a general
framework to compare the spectral gaps of two processes, and to prove an
analogue of Aldous’ spectral gap conjecture. In our framework, to sort out the
problem, we will define the functor from the category of the weighted group to
category of the weighted complete directed graph, and construct the weighted
complete directed graph associated with the generalized exclusion process by
the quotient of the weighted complete directed graph associated with the
interchange process on extended graph by the weighted subgroup. Moreover, as
an application of our framework, we prove the analogue of Aldous’ spectral gap
conjecture for the generalized exclusion process under appropriate assumptions
which show that the spectral gap of the generalized exclusion process is equal
to that of the random walk.

This work was supported in JST CREST Grant Number JPMJCR1913 including AIP
challenge program and RIKEN Junior Research Associate Program.

###### Contents

  1. 1 Introduction
    1. 1.1 The spectral gap
    2. 1.2 Strategy and Construction of this paper
    3. 1.3 Acknowledgements
  2. 2 Categories and the spectral gap
    1. 2.1 The category of weighted complete directed graph
    2. 2.2 The category of weighted group
  3. 3 Various processes
    1. 3.1 Interchange Process
    2. 3.2 Generalized Exclusion Process
    3. 3.3 Evaluation of spectral gaps
    4. 3.4 Some Remarks

##  1\. Introduction

###  1.1. The spectral gap

Spectral gaps play important roles in the study of the relaxation time of the
continuous time Markov processes. Consider the continuous time Markov chain
$X=\\{X_{t}\\}_{t\geq 0}$ with finite state space $S$ and transition rate
$q_{x,y}\geq 0$ for $x,y\in S$, $x\neq y$. We assume that the continuous time
Markov chain is irreducible. Then the generator $\mathcal{L}$ of this
continuous time Markov chain is given by

$\mathcal{L}f(x)=\sum_{y\in S}q_{x,y}(f(y)-f(x)).$

A stationally distribution of this continuous time Markov chain is a map
$\mu:S\rightarrow\mathbb{R}_{\geq 0}$ such that $\mathcal{L}\mu=\mu$. If $\mu$
is reversible (i.e. $q_{x,y}\mu(x)=q_{y,x}\mu(y)$), all eigenvalues of
$-\mathcal{L}$ are real and non-negative. Since such continuous time Markov
chain is irreducible, eigenvalues $\lambda_{i}$ of $-\mathcal{L}$ for
$i=0,\dots,\sharp S-1$ satisfies

$0=\lambda_{0}<\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{\sharp S-1},$

and we call $\lambda_{1}$ the spectral gap of this continuous time Markov
chain. Then, we have

$P(X_{t}=y\mid
X_{0}=x)=\mu(x)+a_{x,y}e^{-\lambda_{1}t}+o(e^{-\lambda_{1}t}),\quad
t\rightarrow\infty$

for some $a_{x,y}\neq 0$. We often refer to $1/\lambda_{1}$ as the relaxation
time of this continuous time Markov chain, and evaluating $\lambda_{1}$ is an
important problem. However, in general, it is difficult to evaluate the
spectral gap, and an effective method to evaluate it is not generally known.
Therefore we study the following problem.

######  Question 1.1.

When is the spectral gap of the process larger than or especially equal to
that of another process whose spectral gap can be easily found?

In this paper we will evaluate the spectral gap of the following process. Let
$X=(V,r)$ be a symmetric weighted complete directed graph of size $n$, where
$V$ is the set of vertices such that $|V|=n$, and $r:V\times
V\rightarrow\mathbb{R}_{\geq 0}$ is a weight function on edges such that
$r(u,w)=r(w,u)$, $r(u,u)=0$ for any $u,w\in V$. We fix $k\in\mathbb{Z}_{\geq
0}$, which we call the maximal occupacy, and $l\in\mathbb{Z}_{\geq 1}$, which
we call the number of particles. We assume that $l<N$ where $N=kn$. We define
the set $S_{GEP}=S_{GEP}(X,l,k)$ as the set of the assignments of $l$
indistinguishable particles to $n$ vertices such that for any $v\in V$ has at
most $k$ particles, that is

$\begin{split}S_{GEP}:=\left\\{\pi:V\rightarrow\\{0,\dots,l\\}\,\middle|\,\pi(v)\leq
k,\sum_{v\in V}x(v)=l\right\\}.\end{split}$

For any state $\pi\in S_{GEP}$ and $u,w\in V$, if $\pi(u)>0$ and $\pi(w)<k$,
we define $\pi^{uw}$ as the transition of the particles of $\pi$ from $u$ to
$w$, that is

$\pi^{uw}(v)=\left\\{\begin{array}[]{cc}\pi(u)-1&v=u\\\ \pi(w)+1&v=w\\\
\pi(v)&\mbox{otherwise.}\end{array}\right.$

For any $u,w\in V$, we assume the transition from a state $\pi\in S_{GEP}$ to
$\pi^{uw}\in S_{GEP}$ occurs with rate $\mu(\pi,u,w)r(u,w)$ where
$\mu:S_{GEP}\times V\times V\rightarrow\mathbb{R}_{\geq 0}$. Then, we define
the generalized exclusion process (GEP) as the Markov chain with state space
$S_{GEP}$ and generator

$\mathcal{L}^{GEP}f(\pi)=\sum_{u,w\in
V}\mu(\pi,u,w)r(u,w)(f(\pi^{uw})-f(\pi)),\quad\mbox{where
}f:S_{GEP}\rightarrow\mathbb{R},\pi\in S_{GEP}.$

In this paper, we consider the spectral gap of the generalized exclusion
process when $\mu(\pi,u,w)=\pi(u)(k-\pi(w))$ for $u,w\in V$, $\pi\in S_{GEP}$.
We call the generalized exclusion process with this transition rate $\mu$ the
normal generalized exclusion process.

Figure 1. GEP on $V=\\{1,2,3,4,5\\}$ with $l=2$, $k=2$. This picture shows the
underlying graph and the transition of the jump on edge $(1,2)$.

The transition rate of the normal generalized exclusion process implies how
vertices with more particles are more likely to spit them out and vertices
with more empty space are more likely to accept particles. Moreover, the
normal generalized exclusion process is an example of the generalized
exclusion process which satisfies the gradient condition in some sense (c.f
§3.2). The normal generalized exclusion process is a special case of the
process studied in [FGJS] and [JS] called $\mathrm{SEP}(k)$, but without a
reservoir.

Caputo [C04] gives a lower bound on a spectral gap of the generalized
exclusion process whisch is not necessarily normal. In this paper, we only
consider the normal generalized exclusion process, however we will give an
equation for the spectral gap of the normal generalized exclusion process and
that of the random walk on the common graph. A random walk is the continuous
time Markov chain, which is defined as follows.

######  Definition 1.2.

A random walk on $V$ with rate $r:V\times V\rightarrow\mathbb{R}_{\geq 0}$ is
a continuous time Markov chain in which a single particle jumps from $u$ to
$w$, $u,w\in V$ with rate $r(u,w)$. A state space is $S_{RW}=V$ and its
generator is given by

$\mathcal{L}^{RW}f(v)=\sum_{v\in V}r(v,w)(f(w)-f(v)),$

for any $v\in V$.

The main theorem of this paper states that the spectral gap of normal random
walk is equal to $k$-times of that of the random walk on the common graph.

######  Theorem 1.3 (Theorem 3.10).

Let $\lambda_{1}^{RW}$ be the spectral gap of the random walk on $X=(V,r)$.
Then the spectral gap of the normal generalized exclusion process on $X$ with
maximal occupancy $k$ and $l$ particles is equal to that of the random walk on
$X$;

$\lambda_{1}^{GEP}=k\lambda_{1}^{RW}.$

In particular, the spectral gap of the normal generalized exclusion process
does not depend on the number of particles $l$.

######  Remark 1.4.

Jara and Salvador study the $\mathrm{SEP}(k)$ independently prove Theorem 1.3
for $\mathrm{SEP}(k)$ with reservoirs. We think that their proof is very
different from ours, and the purpose of this paper is to introduce a new
framework for studying spectral gaps.

To prove this theorem we apply Aldous’ spectral gap conjecture. Aldous’
spectral gap conjecture is a theorem which implies that the spectral gap of
interchange process is equal to that of the corresponding random walk.

######  Definition 1.5.

An interchange process on $V$ with rate $r:V\times
V\rightarrow\mathbb{R}_{\geq 0}$ is a continuous time Markov chain with state
space $S_{IP}$ which gives the assignments of $n$ labeled particles to $V$
such that each vertex is occupied by exactly one particle. The transition form
a state $\eta\in S$ to a state $\eta^{uw}$ interchanges the particles at $u$
and $w$ which occurs with rate $r(u,w)$. Then, the generator of the
interchange process is defined by

$\mathcal{L}^{IP}f(\eta)=\sum_{uv\in E}r(uv)(f(\eta^{uv})-f(\eta)).$

The statement of Aldous’ spectral gap conjecture is follows.

######  Theorem 1.6 ([CLR10]*Theorem 1.1).

Let $\lambda_{1}^{IP}$ (resp. $\lambda_{1}^{RW}$) be the spectral gap of the
interchange process (resp. random walk) on $X$. Then, we have

$\lambda_{1}^{IP}=\lambda_{1}^{RW}.$

This theorem was firstly conjectured by Aldous [DA] for an unweighted graph,
and finally proved by Caputo, Ligget and Richthammer [CLR10] in 2009 for
arbitrarily weighted graphs. Moreover, in [CLR10], they also proved that the
spectral gap of the colored exclusion process, which is the process of multi-
particles, equal to that of random walk as the corollary of the Aldou’s
spectral gap conjecture. After their study, there are some generalization or
analogue of the Aldous’ spectral gap conjecture. Piras [P10] gave the
generalization for simple block shuffle. Kim-Sau [KS23] gave the analogues for
the simple inclusion process which does not have the symmetry like the
interchange process or the colored exclusion process discussed in [CLR10]. We
note that Theorem 1.3 is an analogue of Aldous’ spectral gap conjecture.

###  1.2. Strategy and Construction of this paper

One of the most surprising points of Aldous’ spectral gap conjecture is that,
even though the state space of the random walk is much ”simpler” than that of
the interchange process, they both have equal spectral gaps. Hence, if one can
find the suitable continuous time Markov chain $P$ whose state space is more
”complex” than that of the random walk, but ”simpler” than that of the
interchange process, Aldous’ spectral gap conjecture finds an equality

$\lambda_{1}^{RW}=\lambda_{1}^{P}=\lambda_{1}^{IP}.$

This is the strategy to prove Theorem 1.3. To carry out this strategy, first,
we need to compare the different continuous time Markov chains. We will use
the concept of the sub-process to do this. In §2.1, we define this concept in
the category $\mathrm{CompGrp}_{\mathcal{L}}$ of weighted complete directed
graph with Laplacian operator. A continuous time Markov chain with finite
state space $S$ can be seen as an object of $\mathrm{CompGrp}_{\mathcal{L}}$
with a set of vertices $S$ and its weight given by the transition rates.
Therefore, $\mathrm{CompGrp}_{\mathcal{L}}$ is the suitable setting for
evaluating the spectral gap of the continuous time Markov chains.

Unfortunately, it often fails such strategy at the first step. For example,
the normal generalized exclusion process is not the sub-process of the
interchange process on a common graph, and the random walk is also not the
sub-process of the generalized exclusion process. To overcome this problem, we
will compare the spectral gap of $P$ and that of some weighted graph between
the random walk and the interchange process. To find such a weihgted graph, we
use the symmetry of the random walk and the generalized exclusion process
induced by the symmetry of the interchange process. The state space of the
interchange process can be seen as the symmetic group, and the changing of the
state can be described as the action of permutation element on itself. In
[CLR10], Caputo et. al. proved Aldous’ spectral gap cojecture by using this
fact and the representation theory of the regular representation of the
symmetric group. Moreover, Cesi [Ces10] reformulates Aldous’ spectral gap with
the Cayley graph, and the generalization and analogue of Aldous’ spectral gap
conjecture in the context of Cayley graph is studied by Parazanchevski and
Puder [PP20], Li, Xia and Zhou [LXZ23]. A weighted Caylay graph is weighted
complete directed graph constructed from finite graph $G$ and weight function
$C_{G}:G\rightarrow\mathbb{R}_{\geq 0}$. In §2.2, we define the subcategory of
$\mathrm{CompGrp}_{\mathcal{L}}$ spanned by the weighted Cayley graph. It
contains the interchange process. Moreover, we take the quotient of the
weighted Cayley graph by the subgroup of $G$. This quotient is not a Caylay
graph of some finite graph. We prove two key propositions Proposition 2.24,
and Proposition 2.26, which give partial answers of Question 1.1.

In §3, as the application of above strategy, we will prove Theorem 1.3. To
compare the normal generalized exclusion process with a weighted graph between
the random walk and the interchange process, we consider the interchange
process on a certain graph, which is constructed by changing each vertex to a
complete graph of size $k$. Finally, we note the relation between our main
theorem and Aldous’ spectral gap conjecture for the block shuffle process.

###  1.3. Acknowledgements

The authors express gratitude to Kenichi Bannai and Makiko Sasada for
suggesting the topic and discussion. We thanks Ryokichi Tanaka, who gave us
important references. The first author was supported by JST CREST Grant Number
JPMJCR1913 including AIP challenge program. The Second author is supported by
RIKEN Junior Research Associate Program.

##  2\. Categories and the spectral gap

Caputo-Liggett-Richthammer [CLR10] proves that the spectral gap of the random
walk is equal to that of the interchange process. It is easily proved the
random walk is a sub-process of the interchange process. Since the spectral
gap of random walk is always larger than that of the interchange process, the
most difficult point is to prove the reverse inequality. In this section, we
define the category of weighted complete directed graph and restate some
definitions and properties for continuous time Markov processes in our
category. See [AF] for detail concerning the classical theory of continuous
time Markov process. Moreover, we will define the functor from the category of
weighted group to the category of weighted complete directed graph and
introduce one of the methods to solve Question 1.1.

###  2.1. The category of weighted complete directed graph

We define a weighted complete directed graph $P=(S,C)$ to be a pair consistig
of a set $S$ of vertices and weight function on edges $C:S\times
S\rightarrow\mathbb{R}_{\geq 0}$ such that $C(x,x)=0$ for any $x\in S$. Then
we define the generator on $P$, which is a type of Laplacian.

######  Definition 2.1.

We define the linear operator $\mathcal{L}^{P}$ on
$M^{P}:={\mathrm{Map}}(S,\mathbb{R})$ by

$\mathcal{L}^{P}f(x)=\sum_{y\in S}C(x,y)(f(y)-f(x)),\quad f\in M^{P},$

which we call the generator of $P$.

In this paper, we will consider eigenvalues of the generator of $P$. Next, we
define a morphism of weighted complete graph , which is important to compare
eigenvalues of generators of two complete weighted graphs.

######  Definition 2.2.

We define the category $\mathrm{CompGrp}_{\mathcal{L}}$ as follows;

  * •

The object is a non-trivial weighted complete directed graph $P$.

  * •

The morphism from $P_{1}$ to $P_{2}$ is a map of set $\varphi:S_{1}\rightarrow
S_{2}$ such that

$\mathcal{L}^{P_{1}}(f\circ\varphi)=(\mathcal{L}^{P_{2}}f)\circ\varphi$

for any $f\in M^{P_{2}}$.

Now we will show that the relationship between the continuous time Markov
chains and $\mathrm{CompGrp}_{\mathcal{L}}$. Let $\\{X_{t}\\}_{t\geq 0}$ be a
continuous time Markov chain with finite set of states $S$ and transition
rates $q_{x,y}$, $x\neq y\in S$. We define
$P=(S,C)\in\mathrm{CompGrp}_{\mathcal{L}}$ by

$C(x,y)=\left\\{\begin{array}[]{cc}q_{x,y}&\mbox{if }x\neq y\\\
0&\mbox{otherwise.}\end{array}\right.$

Therefore we can construct the object $\mathrm{CompGrp}_{\mathcal{L}}$
associated with a continuous time Markov chain. This shows that the object
$P\in\mathrm{CompGrp}_{\mathcal{L}}$ is a nice setting to discuss the spectral
gap of continuous time Markov chains. In following, we will restate some
definitions and properties of continuous time Markov chains in terms of
$\mathrm{CompGrp}_{\mathcal{L}}$.

######  Definition 2.3.

Let $P_{1},P_{2}\in\mathrm{CompGrp}_{\mathcal{L}}$. We say that a morphism
$\varphi:P_{1}\rightarrow P_{2}$ is surjective (resp. injective) if $\varphi$
is surjective (resp. injective) as a map of sets. By definition of a morphism
in $\mathrm{CompGrp}_{\mathcal{L}}$, if $\varphi$ is surjective and injective,
then $\varphi$ is an isomorphism, that is $\varphi$ has an inverse morphism.

For any $P_{1},P_{2}\in\mathrm{CompGrp}_{\mathcal{L}}$ associated with some
continuous time Markov chains, if there exists a morphism
$\varphi:P_{1}\rightarrow P_{2}$ which is surjective, we often call $P_{2}$ a
sub-process of $P_{1}$. The following lemma gives a condition for a map
$S_{1}\rightarrow S_{2}$ to be a morphism in $\mathrm{CompGrp}_{\mathcal{L}}$.

######  Lemma 2.4.

Let
$P_{1}=(S_{1},C_{1}),P_{2}=(S_{2},C_{2})\in\mathrm{CompGrp}_{\mathcal{L}}$. A
map $\varphi:S_{1}\rightarrow S_{2}$ is a morphism in
$\mathrm{CompGrp}_{\mathcal{L}}$ if and only if $\varphi$ satisfies

$C_{2}(\varphi(x),y)=\sum_{y^{\prime}\in\varphi^{-1}(y)}C_{1}(x,y^{\prime})$

for any $x\in S_{1}$, $y\in S_{2}$ such that $\varphi(x)\neq y$.

###### Proof.

For the sufficiency, it suffices to prove the commutativity of $\varphi$ with
the generator. We assume

$C_{2}(\varphi(x),y_{2})=\sum_{y_{1}\in\varphi^{-1}(y_{2})}C_{1}(x,y_{1})$

for any $x\in S_{1}$, $y_{1}\in S_{2}$. For any $f\in M^{P_{2}}$ and $x\in
S_{1}$, we have

$\begin{split}\mathcal{L}^{P_{1}}(f\circ\varphi)(x)&=\sum_{y\in
S_{1}}C_{1}(x,y)(f\circ\varphi(y)-f\circ\varphi(x))\\\
&=\sum_{y_{2}\in\varphi(S_{1})}\sum_{y_{1}\in\varphi^{-1}(y_{2})}C_{1}(x,y_{1})(f\circ\varphi(y_{1})-f\circ\varphi(x))\\\
&=\sum_{y_{2}\in
S_{2}}\sum_{y_{1}\in\varphi^{-1}(y_{2})}C_{1}(x,y_{1})(f(y_{2})-f\circ\varphi(x))\\\
&=(\mathcal{L}^{P_{2}}f)\circ\varphi(x).\end{split}$

It follows that $\varphi:S_{1}\rightarrow S_{2}$ is a morphism of
$\mathrm{CompGrp}_{\mathcal{L}}$.

For the necessity, we fix $z\in S_{2}$ and define $f_{z}$ by

$f_{z}(z^{\prime})=\left\\{\begin{array}[]{cc}1&z^{\prime}=z\\\
0&\mbox{otherwise}.\end{array}\right.$

For any $x\in S_{1}$ such that $\varphi(x)\neq z$, we have

$\mathcal{L}^{P_{1}}(f_{z}\circ\varphi)(x)=\sum_{y_{1}\in\varphi^{-1}(z)}C_{1}(x,y_{1}).$

If $\varphi:S_{1}\rightarrow S_{2}$ is a morphism of
$\mathrm{CompGrp}_{\mathcal{L}}$, we have

$(\mathcal{L}^{P_{2}}f_{z})\circ\varphi(x)=\sum_{y_{2}\in
S_{2}}C_{2}(\varphi(x),y_{2})(f_{z}(y_{2})-f_{z}\circ\varphi(x))=C_{2}(\varphi(x),z)$

and this shows

$C_{2}(\varphi(x),z)=\sum_{y_{1}\in\varphi^{-1}(z)}C_{1}(x,y_{1}).$

Since this holds for arbitrary $z\in S_{2}$, this imples the porposition. ∎

Next, we define the irreducibility and reversibility of weighted complete
directed graphs. These are well-knowm results for continuous time Markov
chain.

######  Definition 2.5.

Let $P\in\mathrm{CompGrp}_{\mathcal{L}}$. We say that $P$ is irreducible if
there exists a finite sequence $x=x_{0},\dots,x_{k}=y$ of elements of $S$ such
that $C(x_{0},x_{1})\cdots C(x_{n-1},x_{n})\neq 0$ for any $x,y\in S$ .

We let $\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr}}$ denote the full
subcategory of $\mathrm{CompGrp}_{\mathcal{L}}$ of irreducible object. The
following lemma shows that all morphisms in
$\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr}}$ are surjective.

######  Lemma 2.6.

Let $P_{1},P_{2}\in\mathrm{CompGrp}_{\mathcal{L}}$. If $P_{2}$ is irreducible,
a morphism $\varphi:S_{1}\rightarrow S_{2}$ is always surjective.

###### Proof.

If there exists $y_{2}\in S_{2}$ such that $y_{2}\not\in\varphi(S_{1})$, by
Lemma 2.4, we have

$C_{2}(\varphi(x),y_{2})=\sum_{y_{1}\in\varphi^{-1}(y_{2})}C_{1}(x,y_{1})$

for any $x\in S_{1}$ such that $\varphi(x)\neq y_{2}$. However, since
$\varphi^{-1}(y_{2})=\emptyset$, it follows that $C_{2}(\varphi(x),y)=0$ for
any $y\not\in\varphi(S_{1})$. This contradicts to the fact that $P_{2}$ is
irreducible, and hence $\varphi$ is surjective. ∎

Next definition is the analogue of reversible continuous time Markov chain.

######  Definition 2.7.

Let $P\in\mathrm{CompGrp}_{\mathcal{L}}$. We say that P is reversible if there
exist a function $\mu\in{\mathrm{Map}}(S,\mathbb{R})$ such that

$C(y,x)\mu(x)=C(x,y)\mu(y)$

for any $x,y\in S$.

######  Lemma 2.8.

Let
$P_{1}=(S_{1},C_{1}),P_{2}=(S_{2},C_{2})\in\mathrm{CompGrp}_{\mathcal{L}}$. If
we assume that a morphism $\varphi:S_{1}\rightarrow S_{2}$ is surjective, then

  1. (1)

If $P_{1}$ is irreducible, then $P_{2}$ is also irreducible.

  2. (2)

If $P_{1}$ is reversible, then $P_{2}$ is also reversible.

###### Proof.

(1) Since a morphism $\varphi:S_{1}\rightarrow S_{2}$ is surjective, there
exist $x,y\in S_{1}$ for any $x^{\prime},y^{\prime}\in S_{2}$ such that
$\varphi(x)=x^{\prime}$, $\varphi(y)=y^{\prime}$. Therefore, there exists
$x=x_{0},x_{1},\dots,x_{n}=y\in S_{1}$ such that

$C_{1}(x_{0},x_{1})\cdots C_{1}(x_{n-1},x_{n})\neq 0,$

and we have

$C_{2}(\varphi(x_{i}),\varphi(x_{i+1}))=\left\\{\begin{array}[]{cc}\sum_{\varphi(z)=\varphi(x_{i+1})}C_{1}(x_{i},z)\geq
C_{1}(x_{i},x_{i+1})&\mbox{ if }\varphi(x_{i})\neq\varphi(x_{i+1})\\\ 0&\mbox{
if }\varphi(x_{i})=\varphi(x_{i+1}).\end{array}\right.$

We define a sequence of elements $x^{\prime}=z_{0},\dots,z_{m}=y^{\prime}$ by
removing elements $\varphi(x_{i+1})$ such that
$\varphi(x_{i+1})=\varphi(x_{i})$ from the original sequence
$\varphi(x_{0}),\varphi(x_{1}),\dots,\varphi(x_{n})$. Then, we have

$C_{2}(z_{0},z_{1})\cdots C_{2}(z_{m-1},z_{m})\neq 0,$

and $P_{2}$ is irreducible.

(2) Since $P_{1}$ is reversible, there exists
$\mu_{1}\in\mathrm{Map}(S_{1},\mathbb{R})$ which satisfies
$C_{1}(x,y)\mu_{1}(x)=C_{1}(y,x)\mu_{1}(y)$. We define
$\mu_{2}\in\mathrm{Map}(S_{2},\mathbb{R})$ to be

$\mu_{2}(x)=\sum_{x^{\prime}\in\varphi^{-1}(x)}\mu_{1}(x^{\prime}),\quad x\in
S_{2}.$

We take $x,y\in S_{2}$ and fix $x_{1}\in\varphi^{-1}(x)$ and
$y_{1}\in\varphi^{-1}(y)$. Then, since
$C_{2}(x,y)=\sum_{y^{\prime}\in\varphi^{-1}(y)}C_{1}(x_{1},y^{\prime})$
regardless of the choice of $x_{1}$, we have

$\begin{split}C_{2}(x,y)\mu_{2}(x)&=\sum_{y^{\prime}\in\varphi^{-1}(y)}C_{1}(x_{1},y^{\prime})\sum_{x^{\prime}\in\varphi^{-1}(x)}\mu_{1}(x^{\prime})\\\
&=\sum_{x^{\prime}\in\varphi^{-1}(x)}\sum_{y^{\prime}\in\varphi^{-1}(y)}C_{1}(x^{\prime},y^{\prime})\mu_{1}(x^{\prime})\\\
&=\sum_{x^{\prime}\in\varphi^{-1}(x)}\sum_{y^{\prime}\in\varphi^{-1}(y)}C_{1}(y^{\prime},x^{\prime})\mu_{1}(y^{\prime})\\\
&=\sum_{x^{\prime}\in\varphi^{-1}(x)}C_{1}(y_{1},x^{\prime})\sum_{y^{\prime}\in\varphi^{-1}(y)}\mu_{1}(y^{\prime})\\\
&=C_{2}(y,x)\mu_{2}(y).\end{split}$

Hence, $P_{2}$ is also reversible. ∎

Next lemma is also well known in the context of continuous time Markov chains.

######  Lemma 2.9.

If $P\in\mathrm{CompGrp}_{\mathcal{L}}$ is reversible with respect to $\mu$,
then all eigenvalues of $-\mathcal{L}^{P}$ are non-negative.

###### Proof.

Since $-\mathcal{L}^{P}$ is a linear operator on $M^{P}$, we have
$A_{P}\in\mathrm{Mat}(\sharp S,\mathbb{R})$ such that
$-\mathcal{L}^{P}f=A_{P}f$ for any $f\in M^{P}$. Fix a bijection
$\xi:\\{1,\dots,n\\}\rightarrow S$ where $n=\sharp S$. We define $B$ by

$B=\left(\begin{array}[]{ccc}\mu(\xi(1))&&\\\ &\ddots&\\\
&&\mu(\xi(n))\end{array}\right),\quad\sqrt{B}=\left(\begin{array}[]{ccc}\sqrt{\mu(\xi(1))}&&\\\
&\ddots&\\\ &&\sqrt{\mu(\xi(n))}\end{array}\right),$

and we put

$\tilde{A}_{P}:=\sqrt{B}^{-1}A_{P}\sqrt{B}=\sqrt{B}^{-1}A_{P}B\sqrt{B}^{-1}.$

Then $A_{P}B$ is a symmetric matrix, thus $\tilde{A}_{P}$ is also a symmetric
matrix. Since we can diagonalize $\tilde{A}_{P}$ by a real orthogonal matrix
$R$, $A_{P}$ is also diagonalizable as

$R^{-1}\tilde{A}_{P}R=R^{-1}\sqrt{B}^{-1}A_{P}\sqrt{B}R.$

This shows $-\mathcal{L}^{P}$ has only real eigenvalues and
$\lambda\in\mathbb{R}$ is an eigenvalue of $-\mathcal{L}^{P}$ if and only if
$\lambda$ is an eigenvalue of $\tilde{A}_{P}$. It follows that we may reduce
to the case that $C(x,y)=C(y,x)$ for any $x,y\in S$. Then we have

$\begin{split}-f\cdot\mathcal{L}^{P}f&=-\sum_{x,y\in
S}f(x)C(x,y)(f(y)-f(x))\\\ &=\frac{1}{2}\sum_{x,y\in
S}C(x,y)(f(y)-f(x))^{2}\geq 0,\end{split}$

that is, $-\mathcal{L}^{P}$ has only non-negative real eigenvalues. ∎

If $P\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr}}$ is reversible and
irreducible, by Perrin-Frobenius theorem and Lemma 2.9, the eigenvalues
$\lambda_{0},\lambda_{1},\dots,\lambda_{n}$ of $-\mathcal{L}^{P}$ satisfies

$0=\lambda_{0}<\lambda_{1}<\cdots<\lambda_{n}.$

Then we can define the spectral gap as follows.

######  Definition 2.10.

If $P\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr}}$ is reversible, then we
define the spectral gap $\lambda_{1}^{P}$ of $P$ to be the second smallest
eigenvalue of $-\mathcal{L}^{P}$.

We let $\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ denote the full
subcategory of $\mathrm{CompGrp}_{\mathcal{L}}$ consisting of irreducible and
reversible objects. In this paper, we will mainly focus on objects in
$\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ and its spectral gap. As
well know, we can characterize the spectral gap as the solution of a certain
minimization problem.

######  Lemma 2.11.

Let $P\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$. We assume that
$P$ is reversible with $\mu:M^{P}\rightarrow\mathbb{R}_{\geq 0}$. If we define
$\langle f,g\rangle_{\mu}=\sum_{x\in S}f(x)g(x)\mu(x)$, then we have

$\lambda_{1}^{P}=\min\left\\{-\frac{\langle
f,\mathcal{L}^{P}f\rangle_{\mu}}{\langle f,f\rangle_{\mu}}\,\middle|\,\langle
f,1\rangle_{\mu}=0\right\\}.$

The main goal of this paper is introducing the method of how to apply the
Aldous’ spectral gap conjecture (Theorem 1.6) and estimate the spectral gap of
$P\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$. As in [CLR10], if a
Markov chain $P_{2}$ is the sub-process of another Markov chain $P_{1}$,
spectral gaps $\lambda_{1}^{P_{1}}$, $\lambda_{1}^{P_{2}}$ hold
$\lambda_{1}^{P_{1}}\leq\lambda_{1}^{P_{2}}$. This property is restate in
terms of $\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ as follows.

######  Proposition 2.12.

Let
$P_{1}=(S_{1},C_{1}),P_{2}=(S_{2},C_{2})\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$.
If there exists a morphism $\varphi:P_{1}\rightarrow P_{2}$, all eigenvalues
of $\mathcal{L}^{P_{2}}$ are also eigenvalues of $\mathcal{L}^{P_{1}}$. In
particular, we have

$\lambda^{P_{1}}_{1}\leq\lambda^{P_{2}}_{1}.$

###### Proof.

By Lemma 2.6, $\varphi$ is surjective. We define
$\varphi_{M}:{\mathrm{Map}}(S_{2},\mathbb{R})\rightarrow{\mathrm{Map}}(S_{1},\mathbb{R})$
by $f\mapsto f\circ\varphi$. Since $\varphi_{M}$ is injective, the
${\mathrm{Map}}(S_{2},\mathbb{R})$ can be seen as the vector subspace of
${\mathrm{Map}}(S_{1},\mathbb{R})$. For any eigenfunction
$f\in{\mathrm{Map}}(S_{2},\mathbb{R})$ of $\mathcal{L}^{P_{2}}$ with an
eigenvalue $\lambda\in\mathbb{R}$, we have

$\begin{split}\mathcal{L}^{P_{1}}(f\circ\varphi)(x)&=(\mathcal{L}^{P_{2}}f)\circ\varphi(x)\\\
&=\lambda(f\circ\varphi)(x)\end{split}$

for any $x\in S_{1}$ since $\varphi$ is a morphism of
$\mathrm{CompGrp}_{\mathcal{L}}$. Therefore, $\lambda$ is also an eigenvalue
of $\mathcal{L}^{P_{1}}$. ∎

Let $P_{1}\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ and consider
its spectral gap $\lambda_{1}^{P}$. We often want to evaluate
$\lambda_{1}^{P_{1}}$ by the lower bound to give the upper bound of the
relaxation time of the continuous time Markov chain. If we find a morphism
$\varphi:P_{2}\rightarrow P_{1}$ in
$\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$, then, by Proposition
2.12, we have the evaluation of lower bound of $\lambda_{1}^{P_{1}}$

$\lambda^{P_{2}}_{1}\leq\lambda^{P_{1}}_{1}.$

However, this does not mean we can easily calculate a lower bound of
$\lambda_{1}^{P_{1}}$ since the problem of finding the spectral gap is easier
in $P_{1}$ than $P_{2}$ because $\sharp S_{1}\leq\sharp S_{2}$. Therefore, to
answer Question 1.1, we need to find a morphism $\varphi:P_{1}\rightarrow
P_{2}$ in $\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr}}$ and, moreover, prove
that these spectral gaps are equal;

$\lambda^{P_{2}}_{1}=\lambda^{P_{1}}_{1}.$

We will apply the Aldous’ spectral gap conjecture to overcome the second part
of this strategy. In the next subsection, we introduce how to reduce the
problem of equality to the Aldous’ spectral gap conjecture.

###  2.2. The category of weighted group

In this subsection, we will consider weighted groups and define the key
functor $\hat{P}$ from the category of weighted groups to
$\mathrm{CompGrp}_{\mathcal{L}}$. After that, we construct a morphism in
$\mathrm{CompGrp}_{\mathcal{L}}$ by taking a quotient of $\hat{P}(G)$ by a
weighted subgroup of $G$. Firstly we define a weighted group.

######  Definition 2.13.

We define a weighted group $(G,C_{G})$ to be pair consisting of a finite group
$G$ and a map $C_{G}:G\rightarrow\mathbb{R}_{\geq 0}$ such that
$C_{G}(1_{G})=0$. For any subgroup $H\subset G$, we define a weighted subgroup
$(H,C_{H})$ to be pair of a finite group $H$ and a map
$C_{H}:H\rightarrow\mathbb{R}_{\geq 0}$ such that $C_{H}=C_{G}|_{H}$. By abuse
of notation, we will denote by $G$ a weighted group $(G,C_{G})$. We define the
category $\mathrm{WGp}$ of weighted group so that a morphism
$\varphi:(G_{1},C_{G_{1}})\rightarrow(G_{2},C_{G_{2}})$ is a group morphism
$\varphi:G_{1}\rightarrow G_{2}$ such that

$C_{G_{2}}(g)=\sum_{g^{\prime}\in\varphi^{-1}(g)}C_{G_{1}}(g^{\prime}).$

Next, we define the irreducibility and reversibility for the object of
$\mathrm{WGp}$. It is very similar to that for weighted complete directed
graphs.

######  Definition 2.14.

  1. (1)

We say that a weighted group $G$ is irreducible if for any $x,y\in G$ there
exists a sequence $x=x_{0},x_{1},\dots,x_{k}=y$ in $G$ such that
$C_{G}(x_{1}x_{0}^{-1})\cdots C_{G}(x_{n}x_{n-1}^{-1})\neq 0$. We will denote
by $\mathrm{WGp}^{\mathrm{Irr}}$ the full subcategory of the irreducible
weighted group.

  2. (2)

We say that a weighted group $G$ is reversible if there exists a map
$\mu:G\rightarrow\mathbb{R}_{\geq 0}$ such that

$C_{G}(h)\mu(g)=C_{G}(h^{-1})\mu(hg)$

for any $g,h\in G$.

We will denote by $\mathrm{WGp}^{\mathrm{Irr,rev}}$ the full subcategory of
irreducible and reversible weighted group.

######  Lemma 2.15.

Let $G\in\mathrm{WGp}^{\mathrm{Irr}}$. If $G$ is reversible, then we have
$C_{G}(g)=C_{G}(g^{-1})$ for any $g\in G$. In particular, we can take $\mu$ to
be a constant function.

###### Proof.

Fix $\mu:G\rightarrow\mathbb{R}_{\geq 0}$ such that
$C_{G}(h)\mu(g)=C_{G}(h^{-1})\mu(hg)$ for any $g,h\in G$. Since $G$ is
irreducible, we have $\mu(g)>0$ for any $g\in G$. Therefore, we have
$C_{G}(g)=0$ if and only if $C_{G}(g^{-1})=0$. Moreover, if $C_{G}(g)\neq 0$,
we have

$\mu(h)=\frac{C_{G}(g^{-1})}{C_{G}(g)}\mu(gh)=\frac{C_{G}(g^{-1})^{n}}{C_{G}(g)^{n}}\mu(g^{n}h),$

for any $n\in\mathbb{Z}_{\geq 1}$. Since $G$ is a finite group, there exists
$m\in\mathbb{Z}_{>0}$ such that $g^{m}h=h$. It implies that
$C_{G}(g)^{m}=C_{G}(g^{-1})^{m}$, and we have $C_{G}(g)=C_{G}(g^{-1})$. ∎

Next, we define a weighted complete directed graph over a weighted group.

######  Definition 2.16.

Let $G$ be a weighted group. We define a weighted complete directed graph
$\hat{P}(G)=(\hat{S},\hat{C})$ by $\hat{S}=G$ and

$\hat{C}(x,y)=\left\\{\begin{array}[]{cc}C_{G}(g)&\mbox{if }y=gx,\\\
0&\mbox{otherwise, }\end{array}\right.$

for every $x,y\in\hat{S}$.

######  Proposition 2.17.

The correspondence $G\mapsto\hat{P}(G)$ gives a functor
$\hat{P}:\mathrm{WGp}\rightarrow\mathrm{CompGrp}_{\mathcal{L}}$.

###### Proof.

It suffices to show that every morphism of $\mathrm{WGp}$ induces a morphism
of $\mathrm{CompGrp}_{\mathcal{L}}$ via $\hat{P}$. For $G_{1},G_{2}$ in
$\mathrm{WGp}$, we set $\hat{P}(G_{1})=(\hat{S}_{1},\hat{C}_{1})$,
$\hat{P}(G_{2})=(\hat{S}_{2},\hat{C}_{2})$. Every morphism
$\varphi:G_{1}\rightarrow G_{2}$ induces a map
$\varphi:\hat{S}_{1}\rightarrow\hat{S}_{2}$ and

$\begin{split}\hat{C}_{2}(\varphi(x),y)&=C_{G_{2}}(y\varphi(x)^{-1})\\\
&=\sum_{g\in\varphi^{-1}(y\varphi(x)^{-1})}C_{G_{1}}(g)\\\
&=\sum_{g\in\varphi^{-1}(y)x^{-1}}C_{G_{1}}(g)\\\
&=\sum_{y^{\prime}\in\varphi^{-1}(y)}\hat{C}_{1}(x,y^{\prime})\end{split}$

holds for any $x\in\hat{S}_{1}$ and $y\in\hat{S}_{2}$ such that
$\varphi(x)\neq y$. Therefore, $\varphi$ is a morphism of
$\mathrm{CompGrp}_{\mathcal{L}}$. ∎

The following lemma immediately follows from by the definition and the
construction of $\hat{P}$.

######  Lemma 2.18.

Let $G$ be a weighted group.

  1. (1)

$\hat{P}(G)$ is irreducible if and only if $G$ is irreducible.

  2. (2)

$\hat{P}(G)$ is reversible if and only if $G$ is reversible

######  Corollary 2.19.

The functor $\hat{P}$ induces a functor
$\mathrm{WGp}^{\mathrm{Irr}}\rightarrow\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr}}$
and
$\mathrm{WGp}^{\mathrm{Irr,rev}}\rightarrow\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$.
In particular, for any $G\in\mathrm{WGp}^{\mathrm{Irr}}$, if $G$ is
reversible, then $\hat{P}(G)=(\hat{S},\hat{C})$ is a symmetric weighted graph,
that is $\hat{C}(u,v)=\hat{C}(v,u)$ for any $u,v\in\hat{S}$.

###### Proof.

The first part immediately follows from Lemma 2.18, and the second part
follows from Lemma 2.15. ∎

As noted at the end of §2.1, finding the morphism between two complete
weighted graphs is the first step to compare their spectral gaps. In the
category $\mathrm{WGp}$, we can easily construct the morphism by taking the
quotient of subgroup action. Next, We define the quotient of weighted groups.

######  Definition 2.20.

Let $G\in\mathrm{WGp}$ and $H,H^{\prime}\subset G$ be a weighted subgroup. We
say a pair $(H,H^{\prime})$ is regular if

$\sum_{y^{\prime}\in HyH^{\prime}}C_{G}(y^{\prime}x^{-1})=\sum_{y^{\prime}\in
HyH^{\prime}}C_{G}(y^{\prime}x^{-1}h^{-1}),\,h\in H$

for any $x,y\in G$ such that $HxH^{\prime}\neq HyH^{\prime}$. For
$\hat{P}(G)=(\hat{S},\hat{C})$ and regular pair $(H,H^{\prime})$, we define a
weighted complete directed graph
$\bar{P}=H\backslash\hat{P}/H^{\prime}=(\bar{S},\bar{C})\in\mathrm{CompGrp}_{\mathcal{L}}$
by $\bar{S}:=H\backslash\hat{S}/H^{\prime}$ and

$\bar{C}([x],[y])=\sum_{y^{\prime}\in[y]}\hat{C}(x,y^{\prime}),\,x,y\in\hat{S},$

where $[z]=HzH^{\prime}$ for any $z\in\hat{S}$. For any regular pair
$(\\{1_{G}\\},H)$ and $(H,\\{1_{G}\\})$, we set
$\\{1_{G}\\}\backslash\hat{P}(G)/H=\hat{P}(G)/H$ and
$H\backslash\hat{P}(G)/\\{1_{G}\\}=H\backslash\hat{P}(G)$.

We note $\bar{C}$ in Definition 2.20 does not depend on the choice of
representative elements. Indeed, if $x,y\in\hat{S}$, $[x]\neq[y]$ and we set
$x^{\prime}:=hxh^{\prime}$, $h\in H$, $h^{\prime}\in H^{\prime}$, then we have

$\begin{split}\sum_{y^{\prime}\in[y]}\hat{C}(x,y^{\prime})&=\sum_{y^{\prime}\in[y]}C_{G}(y^{\prime}x^{-1})\\\
&=\sum_{y^{\prime}\in[y]}C_{G}(y^{\prime}h^{\prime}h^{\prime-1}x^{-1}h^{-1})\\\
&=\sum_{y^{\prime}\in[y]}\hat{C}(x^{\prime},y^{\prime}h^{\prime})\\\
&=\sum_{y^{\prime}\in[y]}\hat{C}(x^{\prime},y^{\prime}).\end{split}$

This show that $\bar{C}$ does not depend on the choice of a representative of
$[x]$.

Now, we show that a quotient of weighted group induces a morphism of complete
weighted graphs.

######  Lemma 2.21.

Let $G\in\mathrm{WGp}$ and $\hat{P}(G)=(\hat{S},\hat{C})$. For any regular
pair $(H_{i},H_{i}^{\prime})$ of $G$ for $i=1,2$, if $H_{1}\subset H_{2}$ and
$H_{1}^{\prime}\subset H_{2}^{\prime}$, then there exists a natural morphism
$\varphi:\bar{P}_{1}\rightarrow\bar{P}_{2}$ where
$\bar{P}_{1}:=H_{1}\backslash\hat{P}(G)/H_{1}^{\prime}$,
$\bar{P}_{2}:=H_{2}\backslash\hat{P}(G)/H_{2}^{\prime}$.

###### Proof.

Let $\bar{P}_{i}=(\bar{S}_{i},\bar{C}_{i})$ for $i=1,2$. For any
$x\in\hat{S}$, we set $[x]_{1}:=H_{1}xH^{\prime}_{1}$,
$[x]_{2}:=H_{2}xH^{\prime}_{2}$. We note that $[x]_{1}\subset[x]_{2}$. For any
$x,y\in\hat{S}$, we have

$\begin{split}\bar{C}_{2}([x]_{2},[y]_{2})&=\sum_{y_{2}\in[y]_{2}}\hat{C}(x,y_{2})\\\
&=\sum_{h\in H_{2}}\sum_{h^{\prime}\in
H_{2}^{\prime}}\hat{C}(x,hyh^{\prime})\\\ &=\sum_{h_{2}\in
H_{2}/H_{1}}\sum_{h_{1}\in H_{1}}\sum_{h_{2}^{\prime}\in
H_{1}^{\prime}\backslash H_{2}^{\prime}}\sum_{h_{1}^{\prime}\in
H_{1}^{\prime}}\hat{C}(x,h_{2}h_{1}yh_{1}^{\prime}h_{2}^{\prime})\\\
&=\sum_{h_{2}\in H_{2}/H_{1}}\sum_{h_{2}^{\prime}\in H_{1}^{\prime}\backslash
H_{2}^{\prime}}\sum_{y_{1}\in[y]_{1}}\hat{C}(x,h_{2}y_{1}h_{2}^{\prime})\\\
&=\sum_{h_{2}\in H_{2}/H_{1}}\sum_{h_{2}^{\prime}\in H_{1}^{\prime}\backslash
H_{2}^{\prime}}\bar{C}_{1}([x]_{1},h_{2}[y]_{1}h_{2}^{\prime})\quad(\because\mbox{
Definition of }\bar{C}_{1}).\end{split}$

We take a natural map $\varphi:\hat{S}_{1}\rightarrow\hat{S}_{2}$, then we
have

$\bar{C}_{2}(\varphi([x]_{1}),[y]_{2})=\sum_{y^{\prime}\in\varphi^{-1}([y]_{2})}\bar{C}_{1}(x,y^{\prime})$

for any $x,y\in\hat{S}$ such that $[x]_{2}\neq[y]_{2}$. It follows from Lemma
2.4 $\varphi$ is a morphism in $\mathrm{CompGrp}_{\mathcal{L}}$. ∎

######  Corollary 2.22.

In the setting of Lemma 2.21, if $G\in\mathrm{WGp}^{\mathrm{Irr,rev}}$,

$\lambda_{1}^{\bar{P}_{1}}\leq\lambda_{1}^{\bar{P}_{2}}.$

holds.

###### Proof.

It follows form Proposition 2.12 and Lemma 2.21. ∎

######  Corollary 2.23.

Let $G\in\mathrm{WGp}$ and $(H,H^{\prime})$ be regular.

  1. (1)

If $G$ is irreducible, then $\bar{P}=H\backslash\hat{P}(G)/H^{\prime}$ is also
irreducible.

  2. (2)

If $G$ is reversible, $\bar{P}=H\backslash\hat{P}(G)/H^{\prime}$ is also
reversible.

###### Proof.

This follows from Lemma 2.8, Proposition 2.17, and Lemma 2.21. ∎

In §3, we will see the generalized exclusion process as a quotient of the
interchange process. However, it does not immediately give a good answer for
Question 1.1, as the comment at last of §2.1. In the rest of this subsection,
we will prove key propositions to solve this problem. Firstly, we give the
equation of spectral gaps related to a quotient by a left action, which is the
generalization of [P10]*Proposition 3.1.

######  Proposition 2.24.

Let $G\in\mathrm{WGp}^{\mathrm{Irr,rev}}$ and $\hat{P}(G)=(\hat{S},\hat{C})$.
For any regular pairs $(H_{1},H^{\prime})$, $(H_{2},H^{\prime})$ such that
$H_{1}\subset H_{2}$ and $H_{2}xH^{\prime}\neq\hat{S}$ for every
$x\in\hat{S}$, we put
$\bar{P}_{1}=H_{1}\backslash\hat{P}(G)/H^{\prime}=(\bar{S}_{1},\bar{C}_{1})$,
$\bar{P}_{2}=H_{2}\backslash\hat{P}(G)/H^{\prime}=(\bar{S}_{2},\bar{C}_{2})$,
and we define $[x]_{1}:=H_{1}xH^{\prime}$, $[x]_{2}:=H_{2}xH^{\prime}$. We
assume following condition;

  1. (1)

For every $x,y\in\hat{S}$ and $h_{2}\in H_{2}$, if $y,h_{2}y\not\in[x]_{1}$
holds, then

$\sum_{y^{\prime}\in[y]_{1}}C_{G}(y^{\prime}x^{-1})=\sum_{y^{\prime}\in[h_{2}y]_{1}}C_{G}(y^{\prime}x^{-1}).$

  2. (2)

The weight $C_{G}$ satisfies

$\sharp(H_{1}\backslash[x]_{2})\sum_{w\in[h_{2}x]_{1}}C_{G}(wx^{-1})\geq\min_{z\in\hat{S}}\sum_{y\not\in[z]_{2}}C_{G}(yz^{-1}),$

for every $h_{2}\in H_{2}$ such that $h_{2}x\not\in[x]_{1}$.

Then we have

$\lambda_{1}^{\bar{P}_{1}}=\lambda_{1}^{\bar{P}_{2}}.$

######  Remark 2.25.

If assumption (1) holds, the left hand side of the inequarity in assumption
(2) does not depend on the choice of $h_{2}\in H_{2}$. Indeed, if we take
$h_{2},h_{2}^{\prime}\in H_{2}$ such that $h_{2},h_{2}^{\prime}\not\in H_{1}$
and $h_{2}x,h_{2}^{\prime}x\not\in[x]_{1}$, then we have

$\sum_{w\in[h_{2}x]_{1}}C_{G}(wx^{-1})=\sum_{w^{\prime}\in[h_{2}^{\prime}h_{2}^{-1}h_{2}x]_{1}}C_{G}(w^{\prime}x^{-1})=\sum_{w^{\prime}\in[h_{2}^{\prime}x]_{1}}C_{G}(wx^{-1}).$

This is the key point of the proof.

###### Proof of Proposition 2.24.

By Corollary 2.22, it sufficies to show that
$\lambda_{1}^{\bar{P}_{2}}\leq\lambda_{1}^{\bar{P}_{1}}$. For $x\in\hat{S}$,
we take $f_{x}^{2}\in M^{\hat{P}}$ such that $f_{x}^{2}(y)=0$ for any
$y\not\in[x]_{2}$ and $f_{x}^{2}(y)=1$ for any $y\in[x]_{2}$. Then we can
regard $f^{2}_{x}\in M^{\bar{P}_{2}}$. We let $M^{\bar{P}_{2},\perp_{1}}$
denote the orthogonal complement of $M^{\bar{P}_{2}}$ in $M^{\bar{P}_{1}}$.
Then, we have

$f\cdot
f^{2}_{x}=\sum_{y\in\hat{S}}f(y)f^{2}_{x}(y)=\sum_{x^{\prime}\in[x]_{2}}f(x^{\prime})=0$

for any $f\in M^{\bar{P}_{2},\perp_{1}}$. Since $f(hx)=f(x)$ for any
$x\in\hat{S}$ and $h\in H_{1}$, we have

$\sum_{x^{\prime}\in[x]_{2}}f(x^{\prime})=\sum_{[x^{\prime}]_{1}\in
H_{1}\backslash[x]_{2}}\sum_{x^{\prime\prime}\in[x^{\prime}]_{1}}f(x^{\prime})=0,$

for any $x\in\hat{S}$.

Now we fix an arbitrary function $f\in M^{\bar{P}_{2},\perp_{1}}$, and we see
$f$ as an element of $M^{\hat{P}}$. Then, we have

$\begin{split}-\mathcal{L}^{\bar{P}_{1}}f([x]_{1})&=-\mathcal{L}^{\hat{P}}f(x)\\\
&=-\sum_{y\in\hat{S}}C_{G}(yx^{-1})(f(y)-f(x))\\\ &=-\sum_{[y]_{2}\in
H_{2}\backslash\hat{S}/H^{\prime}}\sum_{[z]_{1}\in
H_{1}\backslash[y]_{2}}\sum_{w\in[z]_{1}}C_{G}(wx^{-1})(f(w)-f(x))\\\
\end{split}$

In above equation, for any $[z]_{1},[z^{\prime}]_{1}\in
H_{1}\backslash[y]_{2}$ such that $z,z^{\prime}\not\in[x]_{1}$, we have
$\sum_{w\in[z]_{1}}C_{G}(wx^{-1})=\sum_{w^{\prime}\in[z^{\prime}]_{1}}C_{G}(w^{\prime}x^{-1})$
by assumption (1). Moreover, since $f\in M^{\bar{P}_{1}}$, we have $f(w)=f(z)$
for any $w\in[z]_{1}$. Thus, by equation (2.2), we have

$\begin{split}&-\sum_{[y]_{2}\in
H_{2}\backslash\hat{S}/H^{\prime}}\sum_{[z]_{1}\in
H_{1}\backslash[y]_{2}}\sum_{w\in[z]_{1}}C_{G}(wx^{-1})(f(w)-f(x))\\\
&=-\sum_{\begin{subarray}{c}[y]_{2}\in H_{2}\backslash\hat{S}/H^{\prime}\\\
[y]_{2}\neq[x]_{2}\end{subarray}}\sum_{[z]_{1}\in
H_{1}\backslash[y]_{2}}\sum_{w\in[z]_{1}}C_{G}(wx^{-1})(f(z)-f(x))-\sum_{[z]_{1}\in
H_{1}\backslash[x]_{2}}\sum_{w\in[z]_{1}}C_{G}(wx^{-1})(f(z)-f(x))\\\
&=\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1})f(x)-\sum_{\begin{subarray}{c}[z]_{1}\in
H_{1}\backslash[x]_{2}\\\
[z]_{1}\neq[x]_{1}\end{subarray}}\sum_{w\in[z]_{1}}C_{G}(wx^{-1})(f(z)-f(x))-\sum_{w\in[x]_{1}}C_{G}(wx^{-1})(f(x)-f(x)).\\\
\end{split}$

Now, by applying assumption (1) and equation (2.2) to the second term, we
observe that

$\begin{split}&\sum_{\begin{subarray}{c}[z]_{1}\in H_{1}\backslash[x]_{2}\\\
[z]_{1}\neq[x]_{1}\end{subarray}}\sum_{w\in[z]_{1}}C_{G}(wx^{-1})(f(z)-f(x))\\\
&=\sum_{\begin{subarray}{c}[z]_{1}\in H_{1}\backslash[x]_{2}\\\
[z]_{1}\neq[x]_{1}\end{subarray}}\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})(f(z)-f(x))\\\
&=-\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})f(x)-(\sharp(H_{1}\backslash[x]_{2})-1)\cdot\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})f(x)\\\
&=-\sharp(H_{1}\backslash[x]_{2})\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})f(x),\end{split}$

where $\tilde{h}_{2}\in H_{2}$ such that $\tilde{h_{2}}x\not\in[x]_{1}$ by
Remrak 2.25. Thus, we have

$-\mathcal{L}^{\bar{P}_{1}}f([x]_{1})=\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1})f(x)+\sharp(H_{1}\backslash[x]_{2})\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})f(x)$

for any $x\in\hat{S}$, and this induces that the eigenvalue
$\lambda_{1}^{P_{2},\perp_{1}}$ of $-\mathcal{L}^{\bar{P}_{2}}$ with
eigenvectors in $M^{\bar{P}_{2},\perp_{1}}$ satisfies

$\lambda_{1}^{P_{2},\perp_{1}}\geq\min_{x\in\hat{S}}\left(\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1})+\sharp(H_{1}\backslash[x]_{2})\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})\right),\quad
x\in\hat{S},$

by Lemma 2.11. Therefore, it is sufficient to show that

$\lambda_{1}^{\bar{P}_{1}}\leq\min_{x\in\hat{S}}\left(\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1})+\sharp(H_{1}\backslash[x]_{2})\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})\right).$

By assumption (2), we will show that

$\lambda_{1}^{\bar{P}_{1}}\leq
2\cdot\min_{x\in\hat{S}}\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1})\leq\min_{x\in\hat{S}}\left(\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1})+\sharp(H_{1}\backslash[x]_{2})\sum_{w\in[\tilde{h}_{2}x]_{1}}C_{G}(wx^{-1})\right).$

For any $x\in\hat{S}$, we define $\mathbbm{1}_{x}\in M^{\hat{P}}$ by

$\mathbbm{1}_{x}(y)=\left\\{\begin{array}[]{cc}1/\sharp[x]_{2}&\mbox{if
}y\in[x]_{2}\\\ 0&\mbox{otherwise.}\end{array}\right.$

Then $\mathbbm{1}_{x}\in M^{\bar{P}_{2}}$, and since
$\sum_{y\in\hat{S}}(\mathbbm{1}_{x}(y)-1/\sharp\hat{S})=0$, we have

$\lambda_{1}^{\bar{P}_{1}}\leq-\frac{(\mathbbm{1}_{x}-1/\sharp\hat{S})\cdot\mathcal{L}^{\hat{P}}(\mathbbm{1}_{x}-1/\sharp\hat{S})}{(\mathbbm{1}_{x}-1/\sharp\hat{S})\cdot(\mathbbm{1}_{x}-1/\sharp\hat{S})}.$

Moreover, we have

$\begin{split}-\frac{(\mathbbm{1}_{x}-1/\sharp\hat{S})\cdot\mathcal{L}^{\hat{P}}(\mathbbm{1}_{x}-1/\sharp\hat{S})}{(\mathbbm{1}_{x}-1/\sharp\hat{S})\cdot(\mathbbm{1}_{x}-1/\sharp\hat{S})}&=\frac{\sum_{y\in[x]_{2}}\sum_{z\not\in[x]_{2}}C_{G}(zy^{-1})/(\sharp[x]_{2})^{2}}{1/\sharp[x]_{2}-2/\sharp\hat{S}+1/\sharp\hat{S}}\\\
&=\frac{\sum_{z\not\in[x]_{2}}C_{G}(zx^{-1})}{1-\sharp[x]_{2}/\sharp\hat{S}}\\\
&=\frac{\sharp\hat{S}}{\sharp\hat{S}-\sharp[x]_{2}}\sum_{z\not\in[x]_{2}}C_{G}(zx^{-1})\end{split}$

Since $\hat{S}\neq H_{2}xH^{\prime}$, we have $[x]_{2}\leq\sharp\hat{S}$ and
$2\geq\frac{\sharp\hat{S}}{\sharp\hat{S}-\sharp[x]_{2}}$. It follows that

$\lambda_{1}^{\bar{P}_{1}}\leq 2\cdot\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1}).$

∎

Proposition 2.24 gives an inequality of spectral gaps about a quotient by a
left group action. On the other hand, the next proposition is about a quotient
by a right group action. This is a generalization of the discussion in
[CLR10]*§4.1.1.

######  Proposition 2.26.

Let $G\in\mathrm{WGp}^{\mathrm{Irr,rev}}$ and $\hat{P}(G)=(\hat{S},\hat{C})$.
For any regular pairs $(H,H^{\prime})$, $(H,H_{a})$, let
$\bar{P}=H\backslash\hat{P}/H^{\prime}$ and
$\bar{P}_{a}=H\backslash\hat{P}/H_{a}$. We define
$H^{a}:=\\{hH^{\prime}h^{-1}\mid h\in H_{a}\\}$. We assume $H$ and $H_{a}$
satisfy following two conditions;

  1. (1)

$H_{b}=\cap_{H_{\alpha}\in H^{a}}H_{\alpha}\subset H_{a}$,

  2. (2)

For every $H_{\alpha}\subset H^{a}$, $\langle H_{\alpha},\cap_{H_{\beta}\in
H^{a}\backslash\\{H_{\alpha}\\}}H_{\beta}\rangle=G$.

Then we have

$\lambda_{1}^{\bar{P}_{a}}\leq\lambda_{1}^{\bar{P}}.$

To prove Proposition 2.26, we firstly prove next lemma.

######  Lemma 2.27.

Let $G\in\mathrm{WGp}$ and $\hat{P}(G)=(\hat{S},\hat{C})$. For regular pair
$(H_{1},H_{2})$, let $\bar{P}=H_{1}\backslash\hat{P}/H_{2}=(\bar{S},\bar{C})$.
Then $(H_{1},h_{0}H_{2}h_{0}^{-1})$ is regular for every $h_{0}\in G$.
Moreover,
$\bar{P}^{\prime}=H_{1}\backslash\hat{P}/h_{0}H_{2}h_{0}^{-1}=(\bar{S}^{\prime},\bar{C}^{\prime})$
is isomorphic to $\bar{P}$.

###### Proof.

Firstly, we will prove $(H_{1},h_{0}H_{2}h_{0}^{-1})$ is regular for every
$h_{0}\in G$. For every $x\in\hat{S}$, we let $[x]$ and $[x]^{\prime}$ denote
an equivalence class of $x$ in $\bar{S}$ and $\bar{S}^{\prime}$, respectively.
Take $x,y\in\hat{S}$ such that $[x]^{\prime}\neq[y]^{\prime}$. Then we have

$\begin{split}\sum_{y^{\prime}\in[y]^{\prime}}C_{G}(y^{\prime}x^{-1})&=\sum_{h\in
H_{1},h^{\prime}\in
H_{2}}C_{G}(hyh_{0}h^{\prime}h_{0}^{-1}x^{-1})=\sum_{y^{\prime}\in[yh_{0}]}C_{G}(y^{\prime}h_{0}^{-1}x^{-1}).\end{split}$

If $[yh_{0}]=[xh_{0}]$, there exists $h\in H_{1}$, $h^{\prime}\in H_{2}$ such
that $hyh_{0}h^{\prime}=xh_{0}$, and we have $[y]^{\prime}=[x]^{\prime}$.
Since this contradicts the assumption $[y]^{\prime}\neq[x]^{\prime}$, we have
$[yh_{0}]\neq[xh_{0}]$. Thus, we have

$\sum_{y^{\prime}\in[y]^{\prime}}C_{G}(y^{\prime}x^{-1})=\sum_{y^{\prime}\in[yh_{0}]}C_{G}(y^{\prime}h_{0}^{-1}x^{-1})=\sum_{y^{\prime}\in[yh_{0}]}C_{G}(y^{\prime}h_{0}^{-1}x^{-1}h_{1})=\sum_{y^{\prime}\in[y]^{\prime}}C_{G}(y^{\prime}x^{-1}h_{1})$

for every $h_{1}\in H_{1}$ since $(H_{1},H_{2})$ is regular. This means that
$(H_{1},h_{0}H_{2}h_{0}^{-1})$ is also regular.

For the second assertion, we define a map
$\varphi:\bar{S}\rightarrow\bar{S}^{\prime}$ by
$[x]\mapsto[xh_{0}^{-1}]^{\prime}$. This morphism is well defined and
bijective since

$x^{\prime}h_{0}^{-1}\in
H_{1}xH_{2}h_{0}^{-1}=H_{1}xh_{0}^{-1}(h_{0}H_{2}h_{0}^{-1})=[xh_{0}^{-1}]^{\prime}$

for any $x^{\prime}\in[x]=H_{1}xH_{2}$. Then, for $g\in G$ such that $y=gx$
and $[y]\neq[x]$, we have

$\begin{split}\bar{C}([x],[y])&=\sum_{y^{\prime}\in[y]}\hat{C}(x,y^{\prime})\\\
&=\sum_{h_{1}\in H_{1},\,h_{2}\in H_{2}}\hat{C}(h_{1}gxh_{2}x^{-1})\\\
&=\sum_{h_{1}\in H_{1},\,h_{2}\in
H_{2}}\hat{C}(h_{1}gxh_{0}^{-1}h_{0}h_{2}h_{0}^{-1}h_{0}x^{-1})\\\
&=\sum_{h_{1}\in H_{1},\,h_{2}^{\prime}\in
h_{0}H_{2}h_{0}^{-1}}\hat{C}(h_{1}gxh_{0}^{-1}h_{2}^{\prime}h_{0}x^{-1})\\\
&=\sum_{y^{\prime\prime}\in[yh_{0}^{-1}]^{\prime}}\hat{C}(xh_{0}^{-1},y^{\prime\prime})=\bar{C}^{\prime}(\varphi([x]),\varphi([y]))\end{split}$

for any $x,y\in\hat{S}$. Therefore, $\varphi$ be a morphism, and we have
$\bar{P}\cong\bar{P}^{\prime}$. ∎

###### Proof of Proposition 2.26.

Let $\bar{P}_{b}=H\backslash\hat{P}(G)/H_{b}=(\bar{S}_{b},\bar{C}_{b})$. Let
$H_{1_{G}}\in H^{a}$ be an equivalence class of $H^{\prime}$. We consider an
eigenfunction $f=f_{1_{G}}$ of $-\mathcal{L}^{\bar{P}}$ with an eigenvalue
$\lambda_{1}^{\bar{P}}$. It is suffices to show that
$\lambda_{1}^{\bar{P}_{a}}$ is also an eigenvalue of $-\mathcal{L}^{\bar{P}}$.
We chose $h_{\alpha}\in H_{a}$ such that
$h_{\alpha}Hh_{\alpha}^{-1}=H_{\alpha}$ for $H_{\alpha}\in H^{a}$ and
$H_{\alpha}\neq H^{\prime}$. By Lemma 2.27,
$f_{\alpha}(x_{\alpha})=f(x_{\alpha}h_{\alpha})$ for
$x_{\alpha}\in\bar{S}_{\alpha}$ is an eigenfunction with an eigenvalue
$\lambda_{1}^{\bar{P}_{\alpha}}=\lambda_{1}^{\bar{P}}$. Then we define
$f_{b}\in M^{\bar{P}_{b}}$ as

$f_{b}:=\sum_{H_{\alpha}\in H^{a}}f_{\alpha}\circ\varphi_{\alpha}$

where $\varphi_{\alpha}$ is a natural morphism of process
$\bar{P}_{b}\rightarrow\bar{P}_{\alpha}$.

We will prove that $f_{b}\neq 0$. Let
$\bar{P}_{\check{\alpha}}=H\backslash\hat{P}(G)/\cap_{H_{\beta}\in
H^{a}\backslash{H_{\alpha}}}H_{\beta}$. If $f_{b}=0$, we have
$f_{\alpha}\circ\varphi_{\alpha}\in{\mathrm{Map}}(\bar{P}_{\check{\alpha}},\mathbb{R})$
for any $H_{\alpha}\in H^{a}$. Since $\langle H_{\alpha},\cap_{H_{\beta}\in
H^{a}\backslash{H_{\alpha}}}H_{\beta}\rangle=G$, this means that
$f_{\alpha}\circ\varphi_{\alpha}$ is invariant under the action of $G$.
Therefore, $f_{\alpha}\circ\varphi_{\alpha}$ is a constant function. However,
this contradicts the assumption that $f_{\alpha}$ is an eigenfunction of
$-\mathcal{L}^{\bar{P}_{\alpha}}$ with an eigenvalue
$\lambda_{1}^{\bar{P}}>0$. Therefore, we have $f\neq 0$. Moreover, $f_{b}$ is
an eigenfunction of $-\mathcal{L}^{\bar{P}_{a}}$ with an eigenvalue
$\lambda_{1}^{\bar{P}}$ since

$\begin{split}(-\mathcal{L}^{\bar{P}_{b}}f_{b})(x)&=-\sum_{y\in\bar{S}_{b}}\sum_{H_{\alpha}\in
H^{a}}\bar{C}_{b}(x,y)(f_{\alpha}\circ\varphi_{\alpha}(y)-f_{\alpha}\circ\varphi_{\alpha}(x))\\\
&=-\sum_{H_{\alpha}\in
H^{a}}\sum_{y^{\prime}\in\bar{S}_{\alpha}}\sum_{y\in\varphi_{\alpha}^{-1}(y^{\prime})}\bar{C}_{b}(x,y)(f_{\alpha}\circ\varphi_{\alpha}(y)-f_{\alpha}\circ\varphi_{\alpha}(x))\\\
&=-\sum_{H_{\alpha}\in
H^{a}}\sum_{y^{\prime}\in\bar{S}_{\alpha}}\bar{C}_{\alpha}(\varphi_{\alpha}(x),y^{\prime})(f_{\alpha}(y^{\prime})-f_{\alpha}\circ\varphi_{\alpha}(x))\\\
&=-\sum_{H_{\alpha}\in
H^{a}}(\mathcal{L}^{\bar{P}_{\alpha}}f_{\alpha})\circ\varphi_{\alpha}(x)\\\
&=\lambda_{1}^{\bar{P}}f_{b}\end{split}$

for any $x\in\bar{S}_{b}$.

Finally, we will prove that $f_{a}:=f_{b}\circ\varphi_{a}$ is an eigenfunction
of $-\mathcal{L}^{\bar{P}_{a}}$ with an eigenvalue $\lambda_{1}^{\bar{P}}$. It
is sufficies to show that $f_{a}$ is invariant under the action of $H_{a}$.
This follows from

$\begin{split}f_{a}(xh_{a})&=\sum_{H_{\alpha}\in
H^{a}}f_{\alpha}(xh_{a}H_{\alpha})\\\ &=\sum_{H_{\alpha}\in
H^{a}}f_{1_{G}}(xh_{a}h_{\alpha}Hh_{\alpha}^{-1}h_{\alpha}),\quad(\because
H_{\alpha}=h_{\alpha}Hh_{\alpha}^{-1}\mbox{ and
}f_{\alpha}(\cdot)=f_{1_{G}}(\cdot h_{\alpha}))\\\ &=\sum_{H_{\alpha}\in
H^{a}}f_{1_{G}}\circ\varphi_{1_{G}}(xh_{a}h_{\alpha})\\\
&=\sum_{H_{\alpha^{\prime}}\in
H^{a}}f_{\alpha^{\prime}}\circ\varphi_{\alpha^{\prime}}(x),\quad(\mbox{where
}H_{\alpha^{\prime}}=h_{a}h_{\alpha}H(h_{a}h_{\alpha})^{-1})\\\
&=\sum_{H_{\alpha}\in
H^{a}}f_{\alpha}\circ\varphi_{\alpha}(x)=f_{a}(x)\end{split}$

for any $x\in S$ and $h_{a}\in H_{a}$. Therefore, we have

$\lambda_{1}^{\bar{P}_{a}}\leq\lambda_{1}^{\bar{P}}.$

∎

##  3\. Various processes

In this section, we will evaluate the spectral gap of the normal generalized
exclusion process by that of the random walk by applying Aldous’ spectral gap
conjecture to our framework. In the following, we assume that any process is
irreducible.

######  Remark 3.1.

The irreducibility assumption is minor. If one wants to consider non-
irreducible processes, one may apply our result to each irreducible component.

In this section, we will consider a continuous time Markov chain on a
symmetric weighted complete directed graph $X=(V,r)$, where $V$ is a set of
vertices and $r:V\times V\rightarrow\mathbb{R}_{\geq 0}$ is a weight function
on edges such that $r(u,w)=r(w,u)$, $r(u,u)=0$ for any $u,w\in V$. We note $X$
is just the basis graph of the continuous time Markov chain and we do not
consider $X$ to be an object of $\mathrm{CompGrp}_{\mathcal{L}}$. If one want
to consider a continuous time Markov chain on an incomplete graph, set
$r(u,w)=0$ for any unnecessary edge $(u,w)\in V\times V$.

###  3.1. Interchange Process

The interchange process is the basic example of a revesible continuous time
Markov chain. In this subsection, we define the interchange process and the
weighted group associated with it.

######  Definition 3.2 ([CLR10]*1.2.2).

Let $X=(V,r)$ be a symmetric weighted complete directed graph of order $n$. We
define a set $S_{IP}$ of states is a set of assignments of $n$ labeled
particles to the vertices of $X$, that is

$S_{IP}:=\mathrm{Bij}(V,\\{1,\dots,n\\}).$

For any state $\eta\in S_{IP}$ and $u,w\in V$, we define $\eta^{uw}$ as
interchanging the labels of $\eta$ at vertices $u$ and $w$, that is

$\eta^{uw}(v)\left\\{\begin{array}[]{cc}\eta(w)&v=u\\\ \eta(u)&v=w\\\
\eta(v)&\mbox{otherwise.}\end{array}\right.$

For any $u,w\in V$, we assume that a transition from a state $\eta\in S_{IP}$
to $\eta^{uw}\in S_{IP}$ occurs with rate $r(u,w)$. Then we define the
interchange process on $X$ to be a continuous time Markov chain with state
space $S_{IP}$ and generator

$\mathcal{L}^{IP}f(\eta)=\sum_{u,w\in
V}r(u,w)(f(\eta^{uw})-f(\eta)),\quad\mbox{where
}f:S_{IP}\rightarrow\mathbb{R},\eta\in S_{IP}.$

Figure 2. IP on $V=\\{1,2,3,4,5\\}$. This picture shows the underlying graph
and a transition of interchanging particles on vertices $1$ and $5$.

For interchange process $(S_{IP},\mathcal{L}^{IP})$ on $X$, we let
$P_{IP}=(S_{IP},C_{IP})$ denote an object of
$\mathrm{CompGrp}_{\mathcal{L}}^{\textrm{Irr,rev}}$ associated with the
interchange process, that is we define $C_{IP}$ by

$C_{IP}(\eta,\eta^{\prime})=\left\\{\begin{array}[]{cc}r(u,w)&\mbox{if
}\exists u,w\in V\mbox{ s.t. }\eta^{\prime}=\eta^{uw}\\\
0&\mbox{otherwise.}\end{array}\right.$

The goal of this subsection is to prove that $P_{IP}$ lies in the essential
image of the functor
$\hat{P}:\mathrm{WGp}^{\mathrm{Irr,rev}}\rightarrow\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$.
The group process associated with the interchange process is given by;

######  Lemma 3.3.

Let $X=(V,r)$ be a symmetric weighted complete graph of order $n$ and
$P_{IP}=(S_{IP},C_{IP})\in\mathrm{CompGrp}_{\mathcal{L}}^{Irr,rev}$ associated
with the interchange process on $X$. We fix $\xi:\\{1,\dots,n\\}\rightarrow
V$. Let $G=\mathfrak{S}_{n}$ be a weighted group such that

$C_{G}(g)=\left\\{\begin{array}[]{cc}r((\xi^{-1}(i),\xi^{-1}(j)))&\mbox{if
}g=(ij)\\\ 0&\mbox{otherwise.}\end{array}\right.$

Then $\hat{P}_{IP}=(\hat{S}_{IP},\hat{C}_{IP}):=\hat{P}(G)$ is isomorphic to
$P_{IP}$.

###### Proof.

We define a bijection $\varphi:S_{IP}\rightarrow\hat{S}_{IP}$ by
$\varphi(\eta)\cdot i=\eta\circ\xi(i),i\in\\{1,\dots,n\\}$. This bijection
induces a bijection $M^{\hat{P}_{IP}}\rightarrow M^{P_{IP}}$, and we have

$\begin{split}\mathcal{L}^{IP}(f\circ\varphi)(\eta)&=\sum_{u,w\in
V}r(u,w)(f\circ\varphi(\eta^{uw}))-f\circ\varphi(\eta))\\\ &=\sum_{(ij)\in
G}r(\xi^{-1}(i),\xi^{-1}(j))(f((ij)\varphi(\eta))-f(\varphi(\eta)))\\\ \
&=\sum_{g\in G}C_{G}(g)(f(g\varphi(\eta))-f(\varphi(\eta)))\\\
&=\mathcal{L}^{\hat{P}_{IP}}f(\varphi(x))\end{split}$

for any $f\in M^{\hat{P}_{IP}}$ and $\eta\in S_{IP}$. Therefore,
$\hat{P}_{IP}$ is isomorphic to $P_{IP}$. ∎

By Lemma 3.3, we identify the interchange process on $X$ and $\hat{P}(G)$ for
the rest of this paper.

###  3.2. Generalized Exclusion Process

In this subsection, we define the generalized exclusion process, and prove
that the weighted complete directed graph associated with the generalized
exclusion process is isomorphic to a quotient of a weighted complete directed
graph associated with the interchange process on a certain graph. The
generalized exclusion process is a continuous time Markov chain, which is
defined as follows.

######  Definition 3.4.

Let $X=(V,r)$ be a symmetric weighted complete graph of order $n$. For $v\in
V$, we fix $k_{v}$, which we call the maximal occupancy at $v$, and we put
$N=\sum_{v\in V}k_{v}$. We fix $l\in\mathbb{Z}_{\geq 1}$, which we call the
number of particles, such that $l<N$. We define a set
$S_{GEP}=S_{GEP}(X,l,(k_{v})_{v})$ as a set of a assignments of $l$
indistinguishable particles to $n$ vertices such that for any $v\in V$ has at
most $k_{v}$ particles, that is

$\begin{split}S_{GEP}:=\left\\{\pi:V\rightarrow\\{0,\dots,l\\}\,\middle|\,\pi(v)\leq
k_{v},\sum_{v\in V}x(v)=l\right\\}.\end{split}$

For any state $\pi\in S_{GEP}$ and $u,w\in V$, if $\pi(u)>0$ and
$\pi(w)<k_{w}$, we define $\pi^{uw}$ to be a transition of the particles of
$\pi$ from $u$ to $w$, that is

$\pi^{uw}(v)\left\\{\begin{array}[]{cc}\pi(u)-1&v=u\\\ \pi(w)+1&v=w\\\
\pi(v)&\mbox{otherwise.}\end{array}\right.$

For any $u,w\in V$, we assume a transition from a state $\pi\in S_{GEP}$ to
$\pi^{uw}\in S_{GEP}$ occurs with rate $\mu(\pi,u,w)r(u,w)$ where
$\mu:S_{GEP}\times V\times V\rightarrow\mathbb{R}_{\geq 0}$. Then, we define
the generalized exclusion process is a continuous time Markov chain with state
space $S_{GEP}$ and generator

$\mathcal{L}^{GEP}f(\pi)=\sum_{u,w\in
V}\mu(\pi,u,w)r(u,w)(f(\pi^{uw})-f(\pi)),\quad\mbox{where
}f:S_{GEP}\rightarrow\mathbb{R},\pi\in S_{GEP}.$

In this paper, we consider the spectral gap of the generalized exclusion
process with the special transition rate $\mu$ such that
$\mu(\pi,u,w)=\pi(u)(k_{w}-\pi(w))$ for $u,w\in V$, $\pi\in S$. We call the
generalized exclusion process with this transition rate $\mu$ as the normal
generalized exclusion process.

Figure 3. GEP on $V=\\{1,2,3,4,5\\}$ with $l=2$, $k_{v}=2$. This picture shows
an underlying graph and a transition of the jump on edge $(1,2)$.

######  Remark 3.5.

The normal generalized exclusion process satisfies a gradient condition in
following sense (c.f. [KL]*Remark 2.4). Let $V=\\{u,v\\}$, and a weight
function $r:V\times V\rightarrow\mathbb{R}_{\geq 0}$ satisfy
$r(u,v)=r(v,u)=1$. We assume $k_{v}=k$ for any $v\in V$ for some
$k\in\mathbb{Z}_{>0}$. We define $f_{i}:M^{P_{GEP}}\rightarrow\mathbb{R}$,
$i=0,1$ by $f_{i}(x)=x_{i}=x(i)$. Then $f_{i}$ is conserved quontity of the
generalized exclusion process. Moreover, we have

$\begin{split}-\mathcal{L}^{P_{GEP}}f_{u}(x)&=-\sum_{y\in
S_{GEP}}C_{GEP}(x,y)(y_{u}-x_{u})\\\
&=-C_{GEP}(x,x^{uv})(x^{uv}_{u}-x_{u})-C_{GEP}(x,x^{vu})(x^{vu}_{u}-x_{u})\\\
&=-x_{u}(k-x_{v})((x_{u}-1)-x_{u})-x_{v}(k-x_{u})((x_{u}+1)-x_{u})\\\
&=k(x_{u}-x_{v})\end{split}$

Thus, it can be said $P_{GEP}$ satisfies the gradient condition.

Our main result of this paper is to prove an analogue of Aldous’ spectral gap
conjecture for the normal generalized exclusion process. More precisely, we
prove that the spectral gap of the normal generalized exclusion process is
equal to that of a random walk on a complete graph of same order. To prove the
main theorem, we will apply our framework and Aldous’ spectral gap conjecture.
Firstly, we will write the normal generalized exclusion process as the
quotient of the interchange process on the extended graph.

We define a symmetric weighted complete directed graph
$\tilde{X}=(\tilde{V},\tilde{r})$ on $X=(V,E)$ by

$\begin{split}\tilde{V}&=\\{(v,m)\mid v\in V,\,m=1,\dots,k_{v}\\},\\\
\tilde{r}(\tilde{u},\tilde{w})&=\left\\{\begin{array}[]{cc}r(\varphi_{V}(\tilde{u}),\varphi_{V}(\tilde{w}))&\mbox{if
}\varphi_{V}(\tilde{u})\neq\varphi_{V}(\tilde{w})\\\
\sum_{v\neq\varphi_{V}(\tilde{u})}r(\varphi_{V}(\tilde{u}),v)&\mbox{if
}\varphi_{V}(\tilde{u})=\varphi_{V}(\tilde{w}),\\\
\end{array}\right.\end{split}$

where a map $\varphi_{V}:\tilde{V}\rightarrow V$ is $\varphi_{V}((v,i))=v$ for
any $(v,i)\in\tilde{V}$. Then $\tilde{X}=(\tilde{V},\tilde{E})$ is a symmetric
weighted complete directed graph of order $N$. (cf. Figure 4.)

Figure 4. The upper row of this picture shows underlying graph and the
generalized exclusion process on it, and lower row shows the extended graph
and the interchange process on it. In the picture of IP, we regard particles
$1$ and $2$ as the particles of GEP.

Let $\tilde{P}_{IP}\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$
associated with the interchange process on $\tilde{X}$. By Lemma 3.3, we can
take $\tilde{G}\cong\mathfrak{S}_{N}\in\mathrm{WGp}^{\mathrm{Irr,rev}}$ such
that $\tilde{P}_{IP}\cong\hat{P}(\tilde{G})$. In following, we will prove that
the normal generalized exclusion process on $(X,r)$ is isomorphic to a
quotient process of $\tilde{P}_{IP}$. For any $n\in\mathbb{Z}_{\geq 1}$, let
$H_{n}$ be a weighted subgroup of $\tilde{G}$ with respect to a permutation
group of $\\{1,\dots,n\\}$, and let $H_{n,N}$ be a weighted subgroup of
$\tilde{G}$ with respect to a permutation group of $\\{n+1,\dots,N\\}$. We fix
a bijection $\tilde{\xi}:\\{1,\dots,N\\}\rightarrow\tilde{V}$. For any $v\in
V$, we let $H^{v}$ denote the weighted subgroup of $\tilde{G}$ with respect to
a permutation group of $(\varphi_{V}\circ\tilde{\xi})^{-1}(v)$. Then, a pair
$(\prod_{v\in V}H^{v},H_{l}H_{l,N})$ is a regular weighted subgroup of $G$.

######  Remark 3.6.

We note that if we put $H^{\prime}=H_{N-1}$, $H_{a}=H_{l}H_{l,N}$, then
$H^{\prime}$ and $H_{a}$ satisfies the condition in Proposition 2.26.

######  Lemma 3.7.

Let $P_{GEP}\in\mathrm{CompGrp}_{\mathcal{L}}^{Irr}$ associated with the
normal generalized exclusion process on $X=(V,r)$. Then,
$\bar{P}_{GEP}=\prod_{v\in V}H^{v}\backslash\tilde{P}_{IP}/H_{l}H_{l,N}$ is
isomorphic to $P_{GEP}$.

###### Proof.

We define $\rho_{GEP}:\\{1,\dots,n\\}\rightarrow\\{0,1\\}$ by

$\rho_{GEP}(i)=\left\\{\begin{array}[]{cc}1&i\leq l\\\
0&i>l\end{array}\right.$

for $i\in\\{1,\dots,n\\}$. We have a bijection
$\varphi_{GEP}:\bar{S}_{GEP}\rightarrow S_{GEP}$ by

$\varphi_{GEP}([g])(v)=\sum_{a\in(\varphi_{V}\circ\tilde{\xi})^{-1}(v)}\rho_{GEP}(ga),\quad
v\in V$

for $[g]\in\bar{S}_{GEP}$. Thus, it sufficies to show that $\varphi_{GEP}$ is
a morphism in $\mathrm{CompGrp}_{\mathcal{L}}$.

Let take $[g],[h]\in\bar{S}_{GEP}$ such that $[g]\neq[h]$. Firstly we assume
there exits a transposition $\sigma=(ij)\in\mathfrak{S}_{N}$ such that
$[h]=[\sigma g]$. We may assume $\rho_{GEP}(i)=1$, $\rho_{GEP}(j)=0$ since
$[x]\neq[y]$. We put
$u=\varphi_{V}\circ\tilde{\xi}(i),w=\varphi_{V}\circ\tilde{\xi}(j)\in V$ and
we have

$\begin{split}\varphi_{GEP}([g])=\varphi_{GEP}([h])^{uw}.\end{split}$

A transposition $\sigma^{\prime}=(i^{\prime}j^{\prime})\in\mathfrak{S}_{N}$
satisfies $[h]=[\sigma^{\prime}g]$ if and only if there exist $\sigma_{1}$
(resp. $\sigma_{2}$), which is an element of a permutation group of
$(\varphi_{V}\circ\tilde{\xi})^{-1}(u)$ (resp.
$(\varphi_{V}\circ\tilde{\xi})^{-1}(w)$), such that
$\sigma^{\prime}=\sigma_{1}^{-1}\sigma_{2}^{-1}\sigma\sigma_{2}\sigma_{1}$.
Therefore, we have

$\begin{split}&\bar{C}_{GEP}([g],[h])\\\
=&\left\\{\begin{array}[]{cc}\varphi_{GEP}([g])(u)\cdot(k_{w}-\varphi_{GEP}([g])(w))r(u,w)&\mbox{if
}\exists u,w\in V\mbox{ s.t. }\varphi_{GEP}([g])^{uw}=\varphi_{GEP}([g])\\\
0&\mbox{otherwise}\end{array}\right.\\\
=&C_{GEP}(\varphi_{GEP}([g]),\varphi_{GEP}([h])).\end{split}$

Hence, $\varphi_{GEP}$ is a morphism in $\mathrm{CompGrp}_{\mathcal{L}}$ ∎

By Lemma 2.23 and Lemma 3.7, $P_{GEP}$ is irreducible and reversible.
Therefore, we can consider the spectral gap of $P_{GEP}$, and we immediately
have an inequality $\lambda_{1}^{\tilde{P}_{IP}}\leq\lambda_{1}^{P_{GEP}}$.

######  Remark 3.8.

The quotient by the left action of $\prod_{v}H^{v}$ identifies the elements of
the pre-image of the surjection $\tilde{V}\twoheadrightarrow V$ with each
other. Moreover, quotient by the right action of $H_{l}$ identifies the
labeles with particles and quotient of the right action of $H_{l,N}$
identifies labeles with empty vertex.

###  3.3. Evaluation of spectral gaps

In this subsection, by using our framework, we will prove that the spectral
gap of the normal generalized exclusion process and that of the random walk
are equal. Firstly, we recall the Aldous’ spectral gap conjecture. This
conjecture can be reformulated in our framework as follows.

######  Proposition 3.9 ([CLR10]*Theorem 1.1).

Let $X=(V,r)$ be a symmetric weighted complete directed graph and $P_{IP}$ be
the interchange process on $X$. Let $G$ be a weighted group such that
$P_{IP}=\hat{P}_{IP}(G)$. For any weighted subgroup $H\subset H_{n-1}\subset
G$, we have

$\lambda_{1}^{\bar{P}}=\lambda_{1}^{\hat{P}_{IP}}$

where $\bar{P}=\hat{P}_{IP}/H$.

###### Proof.

This follows from [CLR10]*Theorem 1.1 and Lemma 2.22. ∎

Next, we prove our main theorem.

######  Theorem 3.10.

Let $X=(V,r)$ be a symmetric weighted complete directed graph and $P_{GEP}$ be
the normal generalized exclusion process on $X$ with maximal occupancies
$(k_{v})_{v\in V}$ and $l$ particles. Let $G$ be a weighted group as in Lemma
3.7 such that
$\bar{P}_{GEP}=\prod_{i}H^{i}\backslash\tilde{P}_{IP}/H_{l}H_{l,N}$ where
$\tilde{P}_{IP}=\hat{P}(G)$. Then, we have

$\lambda_{1}^{\bar{P}_{GEP}}=\lambda_{1}^{\bar{P}}.$

###### Proof.

We prove this theorem by a following diagram. In the diagram, arrows are drawn
from smaller value of the spectral gap to larger.

$\textstyle{\tilde{P}_{IP}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$quotientProposition
3.9$\textstyle{\tilde{P}_{IP}/H_{N-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$Proposition
2.24$\textstyle{\bar{P}_{1}=\tilde{P}_{IP}/H_{l}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$quotientquotient$\textstyle{P_{GEP}\cong\prod_{v}H^{v}\backslash\tilde{P}_{IP}/H_{l}H_{l,N}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Proposition
2.26$\textstyle{\bar{P}=\prod_{v}H^{v}\backslash\tilde{P}_{IP}/H_{N-1}}$$\textstyle{\bar{P}_{2}=\prod_{v}H^{v}\backslash\tilde{P}_{IP}/H_{l}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$quotientquotient

By Proposition 3.9, we have

$\lambda_{1}^{\tilde{P}_{IP}}=\lambda_{1}^{\tilde{P}_{IP}/H_{N-1}}.$

If we put $\bar{P}_{1}=\tilde{P}_{IP}/H_{l}$,
$\bar{P}_{2}=\prod_{v}H^{v}\backslash\tilde{P}_{IP}/H_{l}$, then $\bar{P}_{1}$
and $\bar{P}_{2}$ satisfies the condition in Proposition 2.24. Indeed, for
every $[y]_{1}\neq[x]_{1}$, a summation
$\sum_{y^{\prime}\in[y]_{1}}C_{G}(y^{\prime}x^{-1})$ is determined by
$v_{y},v_{x}\in V$ such that $(\varphi_{V}\circ\xi)^{-1}(v_{y})=y(N)$ and
$(\varphi_{V}\circ\xi)^{-1}(v_{x})=x(N)$, which is same for $[h_{2}y]$ for any
$h_{2}\in\prod_{v}H^{v}$ such that $h_{2}y\not\in[x]_{1}$. This implies that
$\bar{P}_{1}$ and $\bar{P}_{2}$ satisfies the condition (1) in Proposition
2.24. For the condition (2), by the definition of $\tilde{r}$ in §3.2, for any
$h_{2}\in H_{2}$ and $x\in\hat{S}$ and $h_{2}x\not\in[x]_{1}$ we have

$\sum_{w\in[h_{2}x]_{1}}C_{G}(wx^{-1})=\sum_{v^{\prime}\in
V\backslash\\{v\\}}r(v,v^{\prime}),$

where $v\in V$ such that there exist $u,w\in\varphi_{V}^{-1}(v)$ and
$[h_{2}x]_{1}=[(\tilde{\xi}^{-1}(u)\tilde{\xi}^{-1}(w))x]_{1}$. Therefore, we
have

$\begin{split}\left(\sum_{v\in
V}\sharp(\varphi^{-1}_{V}(v))\right)\cdot\sum_{w\in[h_{2}x]_{1}}C_{G}(wx^{-1})&\geq\min_{v\in
V}\sum_{v^{\prime}\in V\backslash\\{v\\}}\sharp(\varphi_{V}^{-1}(v))\cdot
r(v,v^{\prime})\\\
&=\min_{x\in\hat{S}}\sum_{y\not\in[x]_{2}}C_{G}(yx^{-1}),\end{split}$

which implies that $\bar{P}_{1}$ and $\bar{P}_{2}$ satisfies condition (2) of
Proposition 2.24. Therefore, we have

$\lambda_{1}^{\tilde{P}_{IP}}\leq\lambda_{1}^{\bar{P}_{1}}\leq\lambda_{1}^{\bar{P}_{2}}\leq\lambda_{1}^{\bar{P}}=\lambda_{1}^{\tilde{P}_{IP}}.$

by Lemma 2.22 and Proposition 2.24. Thus, we have
$\lambda_{1}^{\tilde{P}_{IP}}=\lambda_{1}^{\bar{P}_{1}}=\lambda_{1}^{\bar{P}_{2}}=\lambda_{1}^{\bar{P}}$.

Finally, if we put $H^{\prime}=H_{N-1}$ and $H_{a}=H_{l,N}$, we have
$\lambda_{1}^{\bar{P}}\leq\lambda_{1}^{P_{GEP}}$ by Proposition 2.26 with
$H_{b}=H_{l}$. Therefore, we have
$\lambda_{1}^{P_{GEP}}=\lambda_{1}^{\bar{P}}$ by ($\heartsuit$). ∎

######  Corollary 3.11.

If $k_{v}=k$ for any $v\in V$ for some $k\in\mathbb{Z}_{\geq 1}$, we have

$\lambda_{1}^{\bar{P}_{GEP}}=k\lambda_{1}^{P_{RW}}.$

In particular, $\lambda_{1}^{\bar{P}_{GEP}}$ does not depend on the choice of
$l$.

###### Proof.

Let $P_{kRW}$ be the random walk on a symmetric weighted complete directeed
graph $(V,kr)$. Since the spectral gap $\lambda_{1}^{P_{RW}}$ is equal to $k$
times of $\lambda_{1}^{RW}$, it sufficies to show the quotient process
$\bar{P}:=\prod_{i=1}^{n}H^{i}\backslash\tilde{P}_{IP}/H_{n-1}$ is isomorphic
to $P_{kRW}$. We define a bijection $\varphi_{kRW}:\bar{S}\rightarrow S_{kRW}$
by

$\varphi_{kRW}([x])=\tilde{\xi}\circ x(N).$

We will show that $\varphi_{kRW}$ is a morphism in
$\mathrm{CompGrp}_{\mathcal{L}}$. For any $[x],[y]\in\bar{S}$, if we put
$i=x(N)$, $j=y(N)$, then we have

$\begin{split}\bar{C}([x],[y])&=\sum_{y^{\prime}\in[y]}\tilde{C}_{G}(y^{\prime}x^{-1})\\\
&=kr(\varphi_{kRW}([x]),\varphi_{kRW}([y]))\\\
&=C_{kRW}(\varphi_{kRW}([x]),\varphi_{kRW}([y])).\end{split}$

Thus, we see that $\varphi_{kRW}$ is a morphism in
$\mathrm{CompGrp}_{\mathcal{L}}$. ∎

###  3.4. Some Remarks

In §3.1 and §3.2, we consider a weighted group whose weight has support only
on transpositions. However, we can easily consider examples of weighted groups
whose weights have larger support. The block shuffle process, which is the
generalization fo the interchange process, is an example of such weighted
group.

######  Definition 3.12.

Let $X$ be a complete directed graph of order $n$, and we fix a map
$\alpha_{X}:2^{V}\rightarrow\mathbb{R}_{\geq 0}$. We define a set $S_{BS}$ of
states is a set of a assignments of $n$ labeled particles to vertices of $X$,
that is

$S_{BS}:=\mathrm{Bij}(V,\\{1,\dots,n\\}).$

For any state $\eta,\eta^{\prime}\in S_{BS}$, we assume a transition from a
state $\eta$ to $\eta^{\prime}$ occurs with rate

$C_{\eta\eta^{\prime}}:=\sum_{\\{v\in
V\mid\eta(v)\neq\eta^{\prime}(v)\\}\subset A}\alpha_{X}(A).$

Then we define the block shuffle process on $(X,\alpha_{X})$ is a continuous
time Markov chain with state space $S_{BS}$ and generator

$\mathcal{L}^{BS}f(\eta)=\sum_{\eta^{\prime}\in
S_{BS}}C_{\eta\eta^{\prime}}(f(\eta^{\prime})-f(\eta)),\quad\mbox{where
}f:S_{BS}\rightarrow\mathbb{R},\eta\in S_{BS}.$

If $\alpha_{X}(A)=0$ for any $\sharp A>2$, the block shuffle process is
isomorphic to the interchange process on $(X,r)$ where
$r(e)=\alpha_{x}(\\{e_{o},e_{t}\\})$, where $e_{o}$ and $e_{t}$ are the
endpoints of the edge $e$. Then, we can state a generalization of Lemma 3.3.

######  Lemma 3.13.

Let $X$ be a complete directed graph of order $n$ with a map
$\alpha_{X}:2^{V}\rightarrow\mathbb{R}_{\geq 0}$ and
$P_{BS}\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ associated with
the block shuffle process on $X$. Let $(G,C_{G})$ be a weighted group such
that $G$ is a symmetric group of order $n$ and

$C_{G}(g)=\sum_{\\{i\in\\{1,\dots,n\\}\mid g(i)\neq i\\}\subset
B}\alpha_{X}\circ\xi(B),\quad g\in G.$

for some fixed bijection $\xi:\\{1,\dots,n\\}\rightarrow V$. Then
$\hat{P}_{BS}=(\hat{S}_{BS},\hat{C}_{BS})$ is isomorphic to $P_{BS}$.

###### Proof.

We define a bijection $\varphi_{BS}:\hat{S}_{BS}\rightarrow S_{BS}$ by
$\varphi_{BS}(x)(v)=x\xi^{-1}(v),v\in V$. Then $\varphi_{BS}$ induces a
bijection $M^{\hat{P}_{BS}}\rightarrow M^{P_{BS}}$, and we have

$\begin{split}\mathcal{L}^{\hat{P}_{BS}}(f\circ\varphi_{BS})(x)&=\sum_{g\in
G}C_{G}(g)(f\circ\varphi_{BS}(gx)-f\circ\varphi_{BS}(x))\\\ &=\sum_{g\in
G}\sum_{\\{i\in\\{1,\dots,n\\}\mid g(i)\neq i\\}\subset
B}(\alpha_{X}\circ\xi(B))(f\circ\varphi_{BS}(gx)-f\circ\varphi_{BS}(x))\\\
&=\sum_{\eta^{\prime}\in S_{BS}}\sum_{\\{v\in
V\mid\varphi_{BS}(x)(v)\neq\eta^{\prime}(v)\\}\subset
A}\alpha_{X}(A)(f(\eta^{\prime})-f\circ\varphi_{BS}(x))\\\
&=\mathcal{L}^{BS}f\circ\varphi_{BS}(x)\end{split}$

for any $f\in M^{P_{BS}}$. Therefore, $\hat{P}_{BS}$ is isomorphic to
$P_{BS}$. ∎

Aldous’ spetral gap conjecture can be generalized to the case of the block
shuffle process as follows. This is still an open problem. This conjecture is
formulated in our framework as follows.

######  Conjecture 1 ([P10]*Conjecture 3).

Let $X$ be a complete graph and
$P_{BS}\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ associated with
the block shuffle on $X$ with $\alpha:S^{V}\rightarrow\mathbb{R}_{\geq 0}$. By
Lemma 3.13, let $G$ be a weighted group such that $\hat{P}_{BS}=\tilde{P}(G)$
is isomorphic to $P_{BS}$. For any weighted subgroup $H\subset H_{n-1}\subset
G$, we have

$\lambda_{1}^{\bar{P}}=\lambda_{1}^{\hat{P}_{BS}}.$

where $\bar{P}=\hat{P}_{BS}/H$ where $H\subset H_{n-1}$.

Finally, we remark that Conjecture 1 implies the generalization of Theorem
3.10. Let $(X,r)$ be a symmetric weighted complete directed graph. We fix
$(k_{v})_{\in V}$, $k_{v}\geq 1$ and $1\leq l<\sum_{v\in V}k_{v}$ and set
$v_{i}=v_{\xi(i)}$, $k_{i}=k_{v_{i}}$. Take a extended graph $\tilde{X}$ of
$X$ as in §3.2 and define $\alpha_{\tilde{X}}$ by

$\alpha_{\tilde{X}}(A)=\left\\{\begin{array}[]{cc}r(v_{i},v_{j})&\mbox{if
}A=S_{j}\bigcup\\{\tilde{v}_{i}\\}\mbox{ where }v_{i}\in\tilde{V}\mbox{ s.t.
}\varphi_{V}(\tilde{v}_{i})=v_{i},\\\ M(r,(k_{v}))&A=S_{i},\\\
0&\mbox{otherwise,}\end{array}\right.$

where $M(r,(k_{v}))>0$ is depending on the rate $r$ and the maximal occupacies
$(k_{v})_{v}$ which is large enogh to satisfy condition (2) in Proposition
2.24. We let
$\tilde{P}_{BS}\in\mathrm{CompGrp}_{\mathcal{L}}^{\mathrm{Irr,rev}}$ denote a
weighted complete graph associated with the block shuffle process on
$\tilde{X}$ with $\alpha_{\tilde{X}}$. Then, we can conjecture a
generalization of Theorem 3.10.

######  Conjecture 2.

If we define
$\bar{P}_{GEP}:=\prod_{i=1}^{n}H^{i}\backslash\tilde{P}(G)/H_{l}H_{l,N}$ and
$\bar{P}:=\prod_{i=1}^{n}H^{i}\backslash\tilde{P}(G)/H_{N-1}$, the weighted
complete graph $\bar{P}_{GEP}$ and $\bar{P}$ do not depend on the choice of
$M(r,(k_{v}))$. Moreover, if Conjecture 1 holds, we have

$\lambda_{1}^{\bar{P}_{GEP}}=\lambda_{1}^{\bar{P}}.$

######  Remark 3.14.

If we assume Conjecture 1, it follows from same proof as that of Theorem 3.10.

######  Remark 3.15.

We note that $\bar{P}_{GEP}$ has a more complicated transition rate than the
normal generalized exclusion process.

## References

  * from-IP-to-GEP