[Inégalités de Cheeger pour les limites de graphes]
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.
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.
Révisé le :
Accepté le :
Première publication :
Publié le :
Keywords: graph limits, graphon, graphing, Cheeger constant
Mot clés : limites de graphes, graphon, graphing, Constante de Cheeger
Khetan, Abhishek 1 ; Mj, Mahan 1
CC-BY-ND 4.0
@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, Tome 74 (2024) no. 1, pp. 257-305. doi : 10.5802/aif.3584. https://aif.centre-mersenne.org/articles/10.5802/aif.3584/
[1] Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 Theory of computing (Singer Island, Fla., 1984) | DOI | MR | Zbl
[2] isoperimetric inequalities for graphs, and superconcentrators, J. Comb. Theory, Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | DOI | MR | Zbl
[3] Percolation on dense graph sequences, Ann. Probab., Volume 38 (2010) no. 1, pp. 150-183 | DOI | MR | Zbl
[4] Left and right convergence of graphs with bounded degree, Random Struct. Algorithms, Volume 42 (2013) no. 1, pp. 1-28 | DOI | MR | Zbl
[5] 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] 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] 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] 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] 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] 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] Spectral graph theory, CBMS Regional Conference Series in Mathematics, 92, American Mathematical Society, 1997, xii+207 pages | MR
[12] 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] 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] Ergodic theory with a view towards number theory, Graduate Texts in Mathematics, 259, Springer, 2011, xviii+481 pages | DOI | MR
[15] 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] On Cheeger-type inequalities for weighted graphs, J. Graph Theory, Volume 41 (2002) no. 1, pp. 1-17 | DOI | MR | Zbl
[17] Expander graphs and their applications, Bull. Am. Math. Soc., Volume 43 (2006) no. 4, pp. 439-561 | DOI | MR | Zbl
[18] 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] Functional analysis, New Age International Publishers Limited, 1996, x+612 pages | MR | Zbl
[20] Large networks and graph limits, Colloquium Publications, 60, American Mathematical Society, 2012, xiv+475 pages | DOI | MR
[21] 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] 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] Graph Partitioning and Expanders (2011), pp. 331-349 (Course Notes, https://people.eecs.berkeley.edu/~luca/cs359g/lecture04.pdf) | MR
Cité par Sources :
