betaFeedback

WorksMathematics

Rigidity of the moving particle lemma for the interchange process

Abstract

Let G=(V,c)G=(V,c) be a finite connected weighted graph. We establish the exact conditions for attaining equality in the moving particle lemma for the interchange process on GG subject to a unit voltage drop across two terminal vertices x≠y∈Vx\neq y \in V. First, equality can occur only in irreducible representations indexed by partitions with at most two rows. We then show that the equality phenomenon beyond the constant and linear sectors is already visible in the two-particle exclusion process. Such equality occurs in exactly two cases: either the harmonic xx–yy voltage is 12\frac12 on every nonterminal vertex, and the induced nonterminal graph G[V∖{x,y}]G[V\setminus\{x,y\}] is disconnected; or the harmonic voltage is constant on each connected component of G[V∖{x,y}]G[V\setminus \{x,y\}], and both voltage values aa and 1−a1-a, with 0≤a<120\le a<\frac12, occur. In each case we compute the equality kernel in every degree and particle sector. The resulting decomposition gives the complete equality kernel for exclusion and, through the regular representation, for the interchange process.

Introduction and main results

Let G=(V,c)G=(V,c) be a connected undirected weighted graph on nn vertices, with symmetric conductances cuv=cvu≥0c_{uv}=c_{vu}\ge0, cuu=0c_{uu}=0, for all u,v∈Vu,v\in V. We regard {u,v}\{u,v\} as an edge exactly when cuv>0c_{uv}>0. Fix distinct terminals x,y∈Vx,y\in V. The effective conductance between xx and yy is

ceff(x,y):=inf⁡{∑{u,v}cuv[ϕ(u)−ϕ(v)]2 | ϕ:V→R, ϕ(x)=0, ϕ(y)=1}.(1)c_{\mathrm{eff}}(x,y):=\inf\left\{\sum_{\{u,v\}}c_{uv}[\phi(u)-\phi(v)]^2\ \middle|\ \phi:V\to\mathbb{R},\ \phi(x)=0,\ \phi(y)=1\right\}. \tag*{(1)}

The energy functional in (1) has a unique minimizer, which we denote by pp and call the harmonic xx–yy voltage: it satisfies p(x)=0p(x)=0, p(y)=1p(y)=1, and the discrete Laplace’s equation

∑v∈V∖{u}cuv[p(u)−p(v)]=0,u∈V∖{x,y}.(2)\sum_{v\in V\setminus\{u\}}c_{uv}[p(u)-p(v)]=0,\qquad u\in V\setminus\{x,y\}. \tag*{(2)}

The discrete maximum principle gives 0≤p≤10 \le p \le1 on VV. By the homogeneity of the variational characterization in (1), every ϕ:V→R\phi: V \to\mathbb{R} satisfies

ceff(x,y)[ϕ(x)−ϕ(y)]2≤∑{u,v}cuv[ϕ(u)−ϕ(v)]2.(3)c_{\mathrm{eff}}(x,y)[\phi(x)-\phi(y)]^2 \le\sum_{\{u,v\}} c_{uv}[\phi(u)-\phi(v)]^2. \tag*{(3)}

The moving particle lemma (or inequality) is the interacting particle analog of the inequality (3): the scalar edge energy on the right-hand side is replaced by the Dirichlet form of the particle system, while the terminal difference on the left-hand side is replaced by the energy cost of exchanging the configuration at xx and yy.

The moving particle lemma has a long history in the interacting particle systems literature; see, for example, Kipnis and Landim [7, §5.5]. In the classical argument, one chooses a path joining the two sites, writes the distant exchange as a telescoping sequence of nearest-neighbor exchanges along that path, and applies Cauchy–Schwarz. The resulting constants are controlled by path lengths and congestion. Alternatively, one may replace this pathwise comparison by the electrical coefficient (1).

Throughout this paper we work with the interchange process on GG. Let SV\mathfrak{S}_V denote the symmetric group on VV; it acts by left multiplication in its regular representation on R[SV]\mathbb{R}[\mathfrak{S}_V]. For distinct u,v∈Vu,v \in V, denote their transposition by τuv\tau_{uv}. We define the positive semidefinite interchange process generator as

LGIP:=∑{u,v}⊂Vcuv(I−τuv).\mathcal{L}^{\mathrm{IP}}_G := \sum_{\{u,v\}\subset V} c_{uv}(I-\tau_{uv}).

In [5], this author used the octopus inequality of Caputo, Liggett, and Richthammer [3]—the key ingredient towards resolving Aldous’ spectral gap conjecture—to prove the following operator inequality.

Proposition 1.1 (Moving particle lemma, cf. Lemma 3.2 in [5]). On every finite connected weighted graph G=(V,c)G=(V,c), and distinct vertices x,y∈Vx,y \in V,

LGIP≥ceff(x,y)(I−τxy)(4)\mathcal{L}^{\mathrm{IP}}_G \ge c_{\mathrm{eff}}(x,y)(I-\tau_{xy}) \tag*{(4)}

as operators on the regular representation of SV\mathfrak{S}_V.

The proof of Proposition 1.1 proceeds via eliminating vertices successively while preserving the effective conductance between xx and yy, and applying the octopus inequality [3 Theorem 2.3] at each step of the elimination. The argument goes through in only a few lines, but hides the nontrivial nature of the octopus inequality, and does not utilize any algebraic aspect thereof. For a representation theory perspective of the octopus inequality, see e.g. Cesi [4].

Alon and Kozma Alon and Kozma [1] later described [5] as the first application of the octopus inequality for a purpose beyond the proof of Aldous’ spectral gap conjecture. Of course there have been many more developments since then, thanks to our better understanding of the algebraic structure of the operators involved. The main focus of this work is to establish a full characterization of attaining equality in (4).

In order to proceed, let us discuss how to transfer Proposition 1.1 to the symmetric exclusion process on GG. For 0≤r≤n0 \le r \le n, write Ωr=(Vr)\Omega_r=\binom{V}{r} for the space of rr-subsets (or the rr-particle sector in the exclusion process language), and equip RΩr\mathbb{R}^{\Omega_r} with the normalized inner product

⟨f,g⟩r=(nr)−1∑ξ∈Ωrf(ξ)g(ξ),∥f∥r2=⟨f,f⟩r.(5)\langle f,g\rangle_r=\binom{n}{r}^{-1}\sum_{\xi\in\Omega_r}f(\xi)g(\xi), \qquad\|f\|_r^2=\langle f,f\rangle_r. \tag*{(5)}

The positive semidefinite exclusion process generator is

LG(r)=∑{u,v}⊂Vcuv(I−τuv),(6)\mathcal{L}^{(r)}_G=\sum_{\{u,v\}\subset V}c_{uv}(I-\tau_{uv}), \tag*{(6)}

where the transposition τuv\tau_{uv} acts on subsets by interchanging uu and vv, and on functions by pullback. Now apply Proposition 1.1 to the permutation representation on rr-subsets to obtain

LG(r)≥ceff(x,y)(I−τxy).(7)\mathcal{L}^{(r)}_G \ge c_{\mathrm{eff}}(x,y)(I-\tau_{xy}). \tag*{(7)}

It is standard to express (7) as a quadratic form inequality under the inner product (5); in particular at r=1r=1 one recovers (3). There is also a related product Bernoulli formulation of this quadratic form inequality that is recorded as [5 Theorem 1.1]. For most of this paper, we focus on the equality analysis in each fixed rr-particle sector.

This requires us to analyze how the operators act on the irreducible representations of GV\mathcal{G}_V, or the so-called Specht modules. For background and standard facts on Specht modules, Young diagrams, and the branching rule used below, we refer the reader to Sagan [9]. For a given partition λ=(λ1,…,λm)\lambda=(\lambda_1,\ldots,\lambda_m) of nn, write SλS^\lambda for the Specht module (over the field R\mathbb{R}) of GV\mathcal{G}_V indexed by λ\lambda. For r≤n2r\le\frac{n}{2}, Young’s rule [9 §2.11] states that the rr-subset permutation representation decomposes multiplicity-free as

RΩr≅S(n)⊕S(n−1,1)⊕⋯⊕S(n−r,r).(8)\mathbb{R}\Omega^r \cong S^{(n)} \oplus S^{(n-1,1)} \oplus\cdots\oplus S^{(n-r,r)}. \tag*{(8)}

This decomposition agrees with the Hoeffding decomposition to be used from § 4 onwards: the constant sector is S(n)S^{(n)}, the linear sector is S(n−1,1)S^{(n-1,1)}, the quadratic sector is S(n−2,2)S^{(n-2,2)}, and, more generally, the degree-jj Hoeffding layer is the copy of S(n−j,j)S^{(n-j,j)}. Thus symmetric exclusion realizes the interchange generator on the two-row irreducible representations in (8), with exactly the same conductance coefficients.

In [5] this author conjectured that the coefficient ceff(x,y)c_{\mathrm{eff}}(x,y) in (4) should be sharp. Recently Zhu [10] proved the said conjecture on every GG by exhibiting a vector in the linear sector S(n−1,1)S^{(n-1,1)} that realizes equality in (4); see also Proposition 8.5 below. This naturally leads to the next question studied in this work: which vectors outside the sectors S(n)S^{(n)} and S(n−1,1)S^{(n-1,1)} attain equality in (4)? We call any nonzero vector that attains equality in the relevant moving particle inequality an equality vector.

A related but distinct problem concerning the second eigenspace of the interchange process generator LGIP\mathcal{L}^{\mathrm{IP}}_G was studied by Belotserkovskiy and this author [2]; see Remark 2.4 for the precise comparison.

Summary of the main results

The regular representation decomposes orthogonally as

R[GV]≅⨁λ⊢nSλ⊗Rdλ,dλ:=dim⁡Sλ.(9)\mathbb{R}[\mathcal{G}_V] \cong\bigoplus_{\lambda\vdash n} S^\lambda\otimes\mathbb{R}^{d_\lambda}, \qquad d_\lambda:= \dim S^\lambda. \tag*{(9)}

where each Specht module SλS^\lambda occurs with multiplicity dλd_\lambda; see [9 §1.10 and §2.3]. Because the operators on both sides of (4) are built from permutations, the equality problem can be studied on each irreducible summand. Theorem 2.3 shows that no nonzero equality vector can be supported on a partition with three or more rows. Consequently, all equality phenomena for the interchange process are already visible in the two-row representations realized by symmetric exclusion. We name this finding two-row rigidity.

By carrying out the analysis in each rr-particle sector of symmetric exclusion, we obtain a complete graph-theoretic classification, stated formally in Theorem 7.5. Put W:=V∖{x,y}W:=V\setminus\{x,y\}, let G[W]G[W] be the induced graph on WW that retains the edges of positive conductance inside WW, and let pp be the harmonic xx-yy voltage from (2). Then equality in the moving particle lemma outside the constant sector S(n)S^{(n)} and the linear sector S(n−1,1)S^{(n-1,1)} occurs if and only if one of the following alternatives holds:

  • (a) p(u)=12p(u)=\frac{1}{2} for every u∈Wu\in W, and G[W]G[W] has at least two connected components;

  • (b) pp is constant on every connected component of G[W]G[W], and the component values are exactly aa and 1−a1-a for some 0≤a<120\le a<\frac{1}{2}, with both values occurring.

No other weighted graph and terminal pair supports equality beyond the constant and linear sectors. Theorems 8.4 and 8.6 determine the dimension and structure of every surviving equality space, first in each top Hoeffding degree and then in every particle sector. Finally, Theorem 8.8 assembles these spaces into the complete equality kernel for the interchange process.

The rest of the paper is organized as follows. The proof begins with the aforementioned two-row rigidity in § 2, and the equality criterion in symmetric exclusion in § 3. In § 4 we derive interface identities from an equality vector and give conditions for reconstructing one from interface data. We also show that a nonzero equality vector in a top Hoeffding space Hk\mathcal{H}_k, with 3≤k≤⌊n/2⌋3\le k\le\lfloor n/2\rfloor, forces the nonterminal harmonic voltage to take at most two distinct values. We then classify the quadratic kernel in § 5, and reduce higher-degree equality to it in § 6. Finally, § 7 and § 8 transfer and reconstruct the kernels in all particle sectors, first for symmetric exclusion and then for the interchange process.

Interchange equality and two-row rigidity

Let λ⊢n\lambda\vdash n be a partition, let ℓ(λ)\ell(\lambda) denote the number of rows in its Young diagram, and let λi\lambda_i be the number of boxes in row ii. Fix an GV\mathcal{G}_V-invariant inner product on SλS^\lambda, and write ρλ\rho_\lambda for the corresponding orthogonal representation. Set

Quvλ:=Id⁡Sλ−ρλ(τuv),LGλ:=∑{u,v}⊂VcuvQuvλ,KG,xyλ:=LGλ−ceff(x,y)Qxyλ.(10)Q_{uv}^\lambda:= \operatorname{Id}_{S^\lambda}-\rho_\lambda(\tau_{uv}), \qquad\mathcal{L}_G^\lambda:= \sum_{\{u,v\}\subset V} c_{uv}Q_{uv}^\lambda, \qquad\mathcal{K}_{G,xy}^\lambda:= \mathcal{L}_G^\lambda-c_{\mathrm{eff}}(x,y)Q_{xy}^\lambda. \tag*{(10)}

where x≠y∈Vx \ne y \in V. Since the regular representation contains every Specht module, the moving particle lemma for the interchange process, Proposition 1.1, implies KG,xyλ≥0K^\lambda_{G,xy} \ge0.

One-vertex reduction

References

  1. [1]G. Alon and G. Kozma, Comparing with octopi, Ann. Inst. H. Poincaré Probab. Statist. 56 (2020), no. 4, 2672–2685. doi:10.1214/20-AIHP1054; arXiv:1811.10537.DOI
  2. [2]D. Bolshakovskiy and J. P. Chen, Uniqueness of the second eigenspace of the interchange process, preprint (2025), arXiv:2511.03402.
  3. [3]P. Caputo, T. M. Liggett, and T. Richthammer, Proof of Aldous’ spectral gap conjecture, J. Amer. Math. Soc. 23 (2010), no. 3, 831–851. doi:10.1090/S0894-0347-10-00659-4; arXiv:0906.1238.DOI
  4. [4]F. Cesi, A few remarks on the octopus inequality and Aldous’ spectral gap conjecture, Comm. Algebra 44 (2016), no. 1, 279–302. doi:10.1080/00927872.2014.975349; arXiv:1310.6156.DOI
  5. [5]J. P. Chen, The moving particle lemma for the exclusion process on a weighted graph, Electron. Commun. Probab. 22 (2017), paper no. 47, 13 pp. doi:10.1214/17-ECP82; arXiv:1606.01577.DOI
  6. [6]Y. Filmus, An orthogonal basis for functions over a slice of the Boolean hypercube, Electron. J. Combin. 23 (2016), no. 1, paper P1.23. doi:10.37236/4567; arXiv:1406.0142.DOI
  7. [8]G. E. Murphy, A new construction of Young’s seminormal representation of the symmetric groups, J. Algebra 69 (1981), no. 2, 287–297. doi:10.1016/0021-8693(81)90205-2.DOI
  8. [9]B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd ed., Graduate Texts in Mathematics, vol. 203, Springer-Verlag, New York, 2001. doi:10.1007/978-1-4757-6804-6.DOI
  9. [10]H. Zhu, The moving particle lemma and the octopus inequality on a connected weighted graph, preprint (2026).

Paper details

vlnc:W_dg6ej3d9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents