Cheeger inequalities for graph limits
Annales de l'Institut Fourier, Volume 74 (2024) no. 1, pp. 257-305.

We introduce notions of Cheeger constants for graphons and graphings. We prove Cheeger and Buser inequalities for these. On the way we prove co-area formulae for graphons and graphings.

Nous introduisons des notions de constantes de Cheeger pour les graphons et graphings. Nous prouvons des inégalites de Cheeger et Buser pour celles-ci. Ce faisant, nous prouvons des formules de la co-aire pour les graphons et graphings.

Received:
Revised:
Accepted:
Online First:
Published online:
DOI: 10.5802/aif.3584
Classification: 05C40, 35P15, 05C75, 05C99, 58J50
Keywords: graph limits, graphon, graphing, Cheeger constant
Mot clés : limites de graphes, graphon, graphing, Constante de Cheeger
Khetan, Abhishek 1; Mj, Mahan 1

1 School of Mathematics, Tata Institute of Fundamental Research. 1, Homi Bhabha Road, Mumbai-400005, India
License: CC-BY-ND 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{AIF_2024__74_1_257_0,
     author = {Khetan, Abhishek and Mj, Mahan},
     title = {Cheeger inequalities for graph limits},
     journal = {Annales de l'Institut Fourier},
     pages = {257--305},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {74},
     number = {1},
     year = {2024},
     doi = {10.5802/aif.3584},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.3584/}
}
TY  - JOUR
AU  - Khetan, Abhishek
AU  - Mj, Mahan
TI  - Cheeger inequalities for graph limits
JO  - Annales de l'Institut Fourier
PY  - 2024
SP  - 257
EP  - 305
VL  - 74
IS  - 1
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.3584/
DO  - 10.5802/aif.3584
LA  - en
ID  - AIF_2024__74_1_257_0
ER  - 
%0 Journal Article
%A Khetan, Abhishek
%A Mj, Mahan
%T Cheeger inequalities for graph limits
%J Annales de l'Institut Fourier
%D 2024
%P 257-305
%V 74
%N 1
%I Association des Annales de l’institut Fourier
%U https://aif.centre-mersenne.org/articles/10.5802/aif.3584/
%R 10.5802/aif.3584
%G en
%F AIF_2024__74_1_257_0
Khetan, Abhishek; Mj, Mahan. Cheeger inequalities for graph limits. Annales de l'Institut Fourier, Volume 74 (2024) no. 1, pp. 257-305. doi : 10.5802/aif.3584. https://aif.centre-mersenne.org/articles/10.5802/aif.3584/

[1] Alon, Noga Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 Theory of computing (Singer Island, Fla., 1984) | DOI | MR | Zbl

[2] Alon, Noga; Milman, Vitali D. λ 1 , isoperimetric inequalities for graphs, and superconcentrators, J. Comb. Theory, Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | DOI | MR | Zbl

[3] Bollobás, Béla; Borgs, Christian; Chayes, Jennifer T.; Riordan, Oliver Percolation on dense graph sequences, Ann. Probab., Volume 38 (2010) no. 1, pp. 150-183 | DOI | MR | Zbl

[4] Borgs, Christian; Chayes, Jennifer T.; Kahn, Jeff; Lovász, László Left and right convergence of graphs with bounded degree, Random Struct. Algorithms, Volume 42 (2013) no. 1, pp. 1-28 | DOI | MR | Zbl

[5] Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T.; Vesztergombi, Katalin Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math., Volume 219 (2008) no. 6, pp. 1801-1851 | DOI | MR

[6] Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T.; Vesztergombi, Katalin Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann. Math., Volume 176 (2012) no. 1, pp. 151-219 | DOI | MR | Zbl

[7] Buser, Peter Geometry and spectra of compact Riemann surfaces, Modern Birkhäuser Classics, Birkhäuser, 2010, xvi+454 pages (reprint of the 1992 edition) | DOI | MR

[8] Chatterjee, Sourav Large deviations for random graphs, Lecture Notes in Mathematics, 2197, Springer, 2017, xi+167 pages (Lecture notes from the 45th Probability Summer School held in Saint-Flour, June 2015, École d’Été de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School]) | DOI | MR

[9] Chavel, Isaac Eigenvalues in Riemannian geometry, Pure and Applied Mathematics, 115, Academic Press Inc., 1984, xiv+362 pages (including a chapter by Burton Randol, with an appendix by Jozef Dodziuk) | MR

[10] Cheeger, Jeff A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Papers dedicated to Salomon Bochner, 1969) (Princeton Mathematical Series), Volume 31, Princeton University Press, 1970, pp. 195-199 | MR | Zbl

[11] Chung, Fan R. K. Spectral graph theory, CBMS Regional Conference Series in Mathematics, 92, American Mathematical Society, 1997, xii+207 pages | MR

[12] Chung, Fan R. K. Four proofs for the Cheeger inequality and graph partition algorithms, Fourth International Congress of Chinese Mathematicians (AMS/IP Studies in Advanced Mathematics), Volume 48, American Mathematical Society, 2010, pp. 331-349 | MR | Zbl

[13] Dodziuk, Jozef Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Am. Math. Soc., Volume 284 (1984) no. 2, pp. 787-794 | DOI | MR | Zbl

[14] Einsiedler, Manfred; Ward, Thomas Ergodic theory with a view towards number theory, Graduate Texts in Mathematics, 259, Springer, 2011, xviii+481 pages | DOI | MR

[15] Elek, Gábor Weak convergence of finite graphs, integrated density of states and a Cheeger type inequality, J. Comb. Theory, Ser. B, Volume 98 (2008) no. 1, pp. 62-68 | DOI | MR | Zbl

[16] Friedland, Shmuel; Nabben, Reinhard On Cheeger-type inequalities for weighted graphs, J. Graph Theory, Volume 41 (2002) no. 1, pp. 1-17 | DOI | MR | Zbl

[17] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi Expander graphs and their applications, Bull. Am. Math. Soc., Volume 43 (2006) no. 4, pp. 439-561 | DOI | MR | Zbl

[18] Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM, Volume 51 (2004) no. 4, pp. 671-697 | DOI | MR | Zbl

[19] Limaye, Balmohan V. Functional analysis, New Age International Publishers Limited, 1996, x+612 pages | MR | Zbl

[20] Lovász, László Large networks and graph limits, Colloquium Publications, 60, American Mathematical Society, 2012, xiv+475 pages | DOI | MR

[21] Mohar, Bojan The Laplacian spectrum of graphs, Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988), John Wiley & Sons, 1991, pp. 871-898 | MR | Zbl

[22] Spielman, Daniel A.; Teng, Shang-Hua Spectral partitioning works: planar graphs and finite element meshes, Linear Algebra Appl., Volume 421 (2007) no. 2-3, pp. 284-305 | DOI | MR | Zbl

[23] Trevisan, Luca Graph Partitioning and Expanders (2011), pp. 331-349 (Course Notes, https://people.eecs.berkeley.edu/~luca/cs359g/lecture04.pdf) | MR

Cited by Sources: