CHEEGER INEQUALITIES FOR GRAPH LIMITS

被引：0

作者：

Khetan, Abhishek ^{[1
]}

Mahan, M. J. ^{[1
]}

机构：

[1] Tata Inst Fundamental Res, Sch Math, 1 Homi Bhabha Rd, Mumbai 400005, India

来源：

ANNALES DE L INSTITUT FOURIER | 2024年 / 74卷 / 01期

关键词：

graph limits; graphon; graphing; Cheeger constant; CONVERGENT SEQUENCES;

D O I：

10.5802/aif.3584

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：257 / 305

页数：50

共 23 条

[1] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].

ALON, N ;

MILMAN, VD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88

[2] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

[3] PERCOLATION ON DENSE GRAPH SEQUENCES [J].

Bollobas, Bela ;

Borgs, Christian ;

Chayes, Jennifer ;

Riordan, Oliver .

ANNALS OF PROBABILITY, 2010, 38 (01) :150-183

[4] Convergent sequences of, dense graphs I: Subgraph frequencies, metric properties and testing [J].

Borgs, C. ;

Chayes, J. T. ;

Lovasz, L. ;

Sos, V. T. ;

Vesztergombi, K. .

ADVANCES IN MATHEMATICS, 2008, 219 (06) :1801-1851

[5] Convergent sequences of dense graphs II. Multiway cuts and statistical physics [J].

Borgs, C. ;

Chayes, J. T. ;

Lovasz, L. ;

Sos, V. T. ;

Vesztergombi, K. .

ANNALS OF MATHEMATICS, 2012, 176 (01) :151-219

[6] Left and right convergence of graphs with bounded degree [J].

Borgs, Christian ;

Chayes, Jennifer ;

Kahn, Jeff ;

Lovasz, Laszlo .

RANDOM STRUCTURES & ALGORITHMS, 2013, 42 (01) :1-28

[7]

Buser P., 2010, Geometry and Spectra of Compact Riemann Surfaces, DOI [10.1007/978-0-8176-4992-0, DOI 10.1007/978-0-8176-4992-0]

[8]

CHATTERJEE S., 2017, Large deviations for random graphs, V2197

[9]

Chavel I., 1984, PURE APPL MATH, V115

[10]

Cheeger Jeff, 2015, PROBLEMS ANAL, P195

← 1 2 3 →