Cheeger inequalities for graph limits
[Inégalités de Cheeger pour les limites de graphes]
Khetan, Abhishek1 ; Mj, Mahan1
1 School of Mathematics, Tata Institute of Fundamental Research. 1, Homi Bhabha Road, Mumbai-400005, India
Annales de l'Institut Fourier, Online first, 49 p.

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.

Reçu le :
Révisé le :
Accepté le :
Première publication :
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 
@unpublished{AIF_0__0_0_A36_0,
     author = {Khetan, Abhishek and Mj, Mahan},
     title = {Cheeger inequalities for graph limits},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     year = {2023},
     doi = {10.5802/aif.3584},
     language = {en},
     note = {Online first},
}
TY  - UNPB
AU  - Khetan, Abhishek
AU  - Mj, Mahan
TI  - Cheeger inequalities for graph limits
JO  - Annales de l'Institut Fourier
PY  - 2023
PB  - Association des Annales de l’institut Fourier
N1  - Online first
DO  - 10.5802/aif.3584
LA  - en
ID  - AIF_0__0_0_A36_0
ER  - 
%0 Unpublished Work
%A Khetan, Abhishek
%A Mj, Mahan
%T Cheeger inequalities for graph limits
%J Annales de l'Institut Fourier
%D 2023
%I Association des Annales de l’institut Fourier
%Z Online first
%R 10.5802/aif.3584
%G en
%F AIF_0__0_0_A36_0
Khetan, Abhishek; Mj, Mahan. Cheeger inequalities for graph limits. Annales de l'Institut Fourier, Online first, 49 p.

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

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

Cité par Sources :