Heat kernels are not uniform expanders
[Les noyaux de la chaleur ne forment pas une famille d’expanseurs]
Frączyk, Mikołaj1 ; van Limbeek, Wouter2
1Faculty of Mathematics and Computer Science, Jagiellonian University, ul. Łojasiewicza 6, 30-348 Kraków, Poland
2Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL 60607, USA
Annales Henri Lebesgue, Tome 7 (2024), pp. 1301-1321

We study infinite analogues of expander graphs, namely graphs whose subgraphs weighted by heat kernels form an expander family. Our main result is that there does not exist any infinite expander in this sense. This proves the analogue for random walks of Benjamini’s conjecture that there is no infinite graph whose metric balls are uniformly expanders. The proof relies on a study of stationary random graphs, in particular proving non-expansion of heat kernels in that setting. A key result is that any stationary random graph is stationary hyperfinite, which is a new property of independent interest.

Notre résultat principal est qu’il n’existe aucun graphe infini dont l’ensemble des sous-graphes pondérés par des noyaux de la chaleur forment une famille d’expanseurs. Cela prouve une analogue, pour les marches aléatoires, de la conjecture de Benjamini selon laquelle il n’existe pas de graphe infini dont les boules métriques sont une famille d’expanseurs. La démonstration repose sur l’étude de graphes aléatoires stationnaires, en particulier la démonstration de la non-expansion des noyaux de la chaleur dans ce cadre. Un résultat clé est que tout graphe aléatoire stationnaire est stationnaire hyperfini, ce qui est une notion nouvelle, d’un intérêt indépendant.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/ahl.220
Classification : 53C28, 53C26, 32Q45
Keywords: Stationary random graphs, random walks, expander graphs

Frączyk, Mikołaj  1   ; van Limbeek, Wouter  2

1 Faculty of Mathematics and Computer Science, Jagiellonian University, ul. Łojasiewicza 6, 30-348 Kraków, Poland
2 Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL 60607, USA
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{AHL_2024__7__1301_0,
     author = {Fr\k{a}czyk, Miko{\l}aj and van Limbeek, Wouter},
     title = {Heat kernels are not uniform expanders},
     journal = {Annales Henri Lebesgue},
     pages = {1301--1321},
     year = {2024},
     publisher = {\'ENS Rennes},
     volume = {7},
     doi = {10.5802/ahl.220},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/ahl.220/}
}
TY  - JOUR
AU  - Frączyk, Mikołaj
AU  - van Limbeek, Wouter
TI  - Heat kernels are not uniform expanders
JO  - Annales Henri Lebesgue
PY  - 2024
SP  - 1301
EP  - 1321
VL  - 7
PB  - ÉNS Rennes
UR  - https://www.numdam.org/articles/10.5802/ahl.220/
DO  - 10.5802/ahl.220
LA  - en
ID  - AHL_2024__7__1301_0
ER  - 
%0 Journal Article
%A Frączyk, Mikołaj
%A van Limbeek, Wouter
%T Heat kernels are not uniform expanders
%J Annales Henri Lebesgue
%D 2024
%P 1301-1321
%V 7
%I ÉNS Rennes
%U https://www.numdam.org/articles/10.5802/ahl.220/
%R 10.5802/ahl.220
%G en
%F AHL_2024__7__1301_0
Frączyk, Mikołaj; van Limbeek, Wouter. Heat kernels are not uniform expanders. Annales Henri Lebesgue, Tome 7 (2024), pp. 1301-1321. doi: 10.5802/ahl.220

[Ada90] Adams, Scot Trees and amenable equivalence relations, Ergodic Theory Dyn. Syst., Volume 10 (1990) no. 1, pp. 1-14 | DOI | Zbl | MR

[AGV14] Abert, Miklós; Glasner, Yair; Virag, Balint Kesten’s theorem for Invariant Random Subgroups, Duke Math. J., Volume 163 (2014) no. 3, pp. 465-488 | DOI | Zbl | MR

[AL07] Aldous, David; Lyons, Russell Processes on unimodular random networks, Electron. J. Probab., Volume 12 (2007) no. 54, pp. 1454-1508 | DOI | MR | Zbl

[BC12] Benjamini, Itai; Curien, Nicolas Ergodic theory on stationary random graphs, Electron. J. Probab., Volume 17 (2012), 93 | DOI | MR | Zbl

[Ben98] Benjamini, Itai Expanders are not hyperbolic, Isr. J. Math., Volume 108 (1998), pp. 33-36 | DOI | MR | Zbl

[Ben04] Benjamini, Itai Note on personal website, http://www.wisdom.weizmann.ac.il/~itai/infexp.ps, 2004

[Ben13] Benjamini, Itai Euclidean vs. graph metric, Erdős centennial (Bolyai Society Mathematical Studies), Volume 25, János Bolyai Mathematical Society; Springer, 2013, pp. 35-57 | DOI | MR | Zbl

[CFW81] Connes, Alain; Feldman, Jacob; Weiss, Benjamin An amenable equivalence relation is generated by a single transformation, Ergodic Theory Dyn. Syst., Volume 1 (1981) no. 4, pp. 431-450 | DOI | Zbl | MR

[Ele07] Elek, Gábor The combinatorial cost, Enseign. Math., Volume 53 (2007) no. 3-4, pp. 225-235 | MR | Zbl

[ET11] Elek, Gábor; Timár, Ádám Quasi-invariant means and Zimmer amenability (2011) (preprint) | arXiv

[Gro03] Gromov, Mikhail Random walk in random groups, Geom. Funct. Anal., Volume 13 (2003) no. 1, pp. 73-146 | Zbl | DOI | MR

[JS87] Jones, Vaughan F. R.; Schmidt, Klaus Asymptotically invariant sequences and approximate finiteness, Am. J. Math., Volume 109 (1987) no. 1, pp. 91-114 | DOI | MR | Zbl

[Kai05] Kaimanovich, Vadim A Amenability and the Liouville property, Isr. J. Math., Volume 149 (2005) no. 1, pp. 45-85 | Zbl | DOI | MR

[Kec93] Kechris, Alexander S. Amenable versus hyperfinite Borel equivalence relations, J. Symb. Log., Volume 58 (1993) no. 3, pp. 894-907 | DOI | MR | Zbl

[Lee22] Leemann, Paul-Henry Up to a double cover, every regular connected graph is isomorphic to a Schreier graph, Bull. Belg. Math. Soc. Simon Stevin, Volume 28 (2022) no. 3, pp. 373-379 | DOI | Zbl | MR

[Lov12] Lovász, László Large networks and graph limits, Colloquium Publications, 60, American Mathematical Society, 2012 | MR | DOI | Zbl

[Mac62] Mackey, George W. Point realizations of transformation groups, Ill. J. Math., Volume 6 (1962), pp. 327-335 | MR | Zbl

[Mar73] Margulis, Grigoriĭ A. Explicit constructions of expanders, Probl. Peredachi Inf., Volume 9 (1973) no. 4, pp. 71-80 | MR | Zbl

[NY08] Nowak, Piotr; Yu, Guoliang What is ⋯ property A?, Notices Am. Math. Soc., Volume 55 (2008) no. 4, pp. 474-475 | MR | Zbl

[Oza06] Ozawa, Narutaka Amenable actions and applications, Proceedings of the International Congress of Mathematicians. Vol. II: Invited lectures, European Mathematical Society, 2006, pp. 1563-1580 | MR | Zbl

[PT22] Pete, Gábor; Timár, Ádám The Free Uniform Spanning Forest is disconnected in some virtually free groups, depending on the generator set, Ann. Probab., Volume 50 (2022) no. 6, pp. 2218-2243 | DOI | Zbl | MR

[Sch11] Schramm, Oded Hyperfinite Graph Limits, Selected Works of Oded Schramm (Benjamini, Itai; Häggström, Olle, eds.), Springer, 2011, pp. 639-645 | DOI | Zbl

[Yu00] Yu, Guoliang The coarse Baum–Connes conjecture for spaces which admit a uniform embedding into Hilbert space, Invent. Math., Volume 139 (2000) no. 1, pp. 201-240 | DOI | MR | Zbl

[Zim78] Zimmer, Robert J. Amenable ergodic group actions and an application to Poisson boundaries of random walks, J. Funct. Anal., Volume 27 (1978) no. 3, pp. 350-372 | DOI | MR | Zbl

[Zim84] Zimmer, Robert J. Ergodic theory and semisimple groups, Monographs in Mathematics, 81, Birkhäuser, 1984 | DOI | Zbl | MR

Cité par Sources :