Hypergraph shuffles and the one-particle spectral gap
Let $n \ge 2$ and give each subset $B \subseteq [n]$ with $|B| \ge 2$ a weight $w_B \ge 0$, such that the graph joining two vertices whenever they lie in a common subset of positive weight is connected. Place one distinct label at each vertex; independently, each $B$ rings at rate $w_B$ and then permutes the labels it carries uniformly at random. Let $L_{\mathrm{IP}}$ be the generator of this interchange process on $S_n$. The position of a single label is the random walk with generator $$L_{\mathrm{RW}} f(x) = \sum_{B \ni x} w_B \left( \frac{1}{|B|} \sum_{y \in B} f(y) - f(x) \right).$$ Both chains are reversible; let $\lambda_{\mathrm{IP}}$ and $\lambda_{\mathrm{RW}}$ be the smallest positive eigenvalues of $-L_{\mathrm{IP}}$ and $-L_{\mathrm{RW}}$, so that $\lambda_{\mathrm{IP}} \le \lambda_{\mathrm{RW}}$. When only sets of size two have positive weight, $\lambda_{\mathrm{IP}} = \lambda_{\mathrm{RW}}$: this is Aldous' spectral gap conjecture, proved by Caputo, Liggett and Richthammer. Bristiel and Caputo proved the equality when $w_B$ depends only on $|B|$, and Alon, Kozma and Puder proved it for further classes of hypergraphs.
Problem. Is $\lambda_{\mathrm{IP}} = \lambda_{\mathrm{RW}}$ for every $n \ge 2$ and every choice of weights as above?
Source: Caputo (by 2010; recorded in Piras (2010), Conjecture 3, according to Alon and Puder); see Cesi (2016), Aldous, Caputo, Durrett, Holroyd, Jung and Puha (2021), Bristiel and Caputo (2024), Conjecture 1.7, and Alon and Puder (2026), Conjecture 1.2 ("Caputo's hypergraph conjecture"), in this form.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO, RT
- Keywords
- AIM Open Applied Problems, hypergraphs, interchange process, spectral gaps
References
@article{cesi2016,
author = {Cesi, Filippo},
title = {A few remarks on the octopus inequality and {A}ldous' spectral gap conjecture},
journal = {Comm. Algebra},
volume = {44},
number = {1},
year = {2016},
pages = {279--302},
doi = {10.1080/00927872.2014.975349},
}
@article{aldous2021,
author = {Aldous, David and Caputo, Pietro and Durrett, Rick and Holroyd, Alexander E. and Jung, Paul and Puha, Amber},
title = {The life and mathematical legacy of {T}homas {M}. {L}iggett},
journal = {Notices Amer. Math. Soc.},
volume = {68},
number = {1},
year = {2021},
doi = {10.1090/noti2203},
}
@article{bristiel2024,
author = {Bristiel, Alexandre and Caputo, Pietro},
title = {Entropy inequalities for random walks and permutations},
journal = {Ann. Inst. Henri Poincar\'e Probab. Stat.},
volume = {60},
number = {1},
year = {2024},
pages = {54--81},
doi = {10.1214/22-AIHP1267},
eprint = {2109.06009},
archivePrefix = {arXiv},
}
@misc{alon2026,
author = {Alon, Gil and Puder, Doron},
title = {Aldous-type spectral gaps in unitary groups},
year = {2026},
eprint = {2603.00353},
archivePrefix = {arXiv},
}
@article{caputo2010,
author = {Caputo, Pietro and Liggett, Thomas M. and Richthammer, Thomas},
title = {Proof of {A}ldous' spectral gap conjecture},
journal = {J. Amer. Math. Soc.},
volume = {23},
number = {3},
year = {2010},
pages = {831--851},
doi = {10.1090/S0894-0347-10-00659-4},
eprint = {0906.1238},
archivePrefix = {arXiv},
}
@article{alon2025,
author = {Alon, Gil and Kozma, Gady and Puder, Doron},
title = {On the {A}ldous--{C}aputo spectral gap conjecture for hypergraphs},
journal = {Math. Proc. Cambridge Philos. Soc.},
volume = {179},
number = {2},
year = {2025},
pages = {259--298},
doi = {10.1017/S0305004125000179},
eprint = {2311.02505},
archivePrefix = {arXiv},
}
@misc{aim-caputo-hypergraph-gap,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Hypergraph shuffles and the one-particle spectral gap}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/607-caputo-hypergraph-gap.md},
note = {Entry 607 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00282, "Hypergraph shuffles and the one-particle spectral gap", clopen.solutions.