×

zbMATH — the first resource for mathematics

Isoperimetric inequalities in simplicial complexes. (English) Zbl 1389.05174
Authors’ abstract: In graph theory there are intimate connections between the expansion properties of a graph and the spectrum of its Laplacian. In this paper we define a notion of combinatorial expansion for simplicial complexes of general dimension, and prove that similar connections exist between the combinatorial expansion of a complex, and the spectrum of the high dimensional Laplacian defined by Eckmann. In particular, we present a Cheeger-type inequality, and a high-dimensional expander mixing lemma. As a corollary, using the work of J. Pach [Comput. Geom. 10, No. 2, 71–76 (1998; Zbl 0896.68143)], we obtain a connection between spectral properties of complexes and Gromov’s notion of geometric overlap. Using the work of A. Gundert and U. Wagner [in: Proceedings of the 28th annual symposium on computational geometry, SoCG 2012, Chapel Hill, NC, USA, June 17–20, 2012. New York, NY: Association for Computing Machinery (ACM). 151–160 (2012; Zbl 1293.05210)], we give an estimate for the combinatorial expansion and geometric overlap of random Linial-Meshulam complexes.
Reviewer’s remark: Finally, five open questions are proposed.

MSC:
05E45 Combinatorial aspects of simplicial complexes
05C80 Random graphs (graph-theoretic aspects)
55U10 Simplicial sets and complexes in algebraic topology
35P05 General topics in linear spectral theory for PDEs
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] R. Aharoni, E. Berger and R. Meshulam: Eigenvalues and homology of ag complexes and vector representations of graphs, Geometric and functional analysis 15 (2005), 555–566. · Zbl 1074.05058
[2] N. Alon and F. R. K. Chung: Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), 15–19. · Zbl 0657.05068
[3] N. Alon: Eigenvalues and expanders, Combinatorica 6 (1986), 83–96. · Zbl 0661.05053
[4] N. Alon and V. D. Milman: {\(\lambda\)}1, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, Ser. B 38 (1985), 73–88. · Zbl 0549.05051
[5] M. Blum, R. M. Karp, O. Vorneberger, C. H. Papadimitriou and M. Yan-nakakis: Complexity of testing whether a graph is a superconcentrator, Information Processing Letters 13 (1981), 164–167. · Zbl 0482.05059
[6] Y. Bilu and N. Linial: Lifts, discrepancy and nearly optimal spectral gap, Combinatorica 26 (2006), 495–519. · Zbl 1121.05054
[7] R. Beigel, G. Margulis and D. A. Spielman: Fault diagnosis in a small constant number of parallel testing rounds, in: Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, ACM, 1993, 21–29.
[8] P. Buser: A note on the isoperimetric constant, Ann. Sci. École Norm. Sup. 15 (1982), 213–230. · Zbl 0501.53030
[9] J. Cheeger: A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis 195 (1970), 199. · Zbl 0212.44903
[10] F. Chung: The Laplacian of a hypergraph, Expanding Graphs (Joel Friedman, ed.), DIMACS, 10, AMS, 1993, 21–36. · Zbl 0790.05061
[11] F. R. K. Chung: Spectral graph theory, CBMS, Amer Mathematical Society, 1997.
[12] D. Dotterrer and M. Kahle: Coboundary expanders, Journal of Topology and Analysis 4 (2012), 499–514. · Zbl 1259.05151
[13] A. Duval, C. Klivans and J. Martin: Simplicial matrix-tree theorems, Transactions of the American Mathematical Society 361 (2009), 6073–6114. · Zbl 1207.05227
[14] J. Dodziuk: Finite-difference approach to the Hodge theory of harmonic forms, American Journal of Mathematics 98 (1976), 79–104. · Zbl 0324.58001
[15] J. Dodziuk: Difference equations, isoperimetric inequality and transience of certain random walks, Trans. Amer. Math. Soc. 284 (1984). · Zbl 0512.39001
[16] B. Eckmann: Harmonische funktionen und randwertaufgaben in einem komplex, Commentarii Mathematici Helvetici 17 (1944), 240–255. · Zbl 0061.41106
[17] P. Erdos and A. Rényi: On random graphs, Publicationes Mathematicae Debrecen 6 (1959), 290–297.
[18] P. Erdos and A. Rényi: On the evolution of random graphs, Bull. Inst. Internat. Statist 38 (1961), 343–347.
[19] J. Fox, M. Gromov, V. Lafforgue, A. Naor and J. Pach: Overlap properties of geometric expanders, J. Reine Angew. Math. 671 (2012), 49–83. · Zbl 1306.05171
[20] J. Friedman and N. Pippenger: Expanding graphs contain all small trees, Combinatorica 7 (1987), 71–76. · Zbl 0624.05028
[21] J. Friedman: Computing Betti numbers via combinatorial Laplacians, Algorithmica 21 (1998), 331–346. · Zbl 0911.57021
[22] J. Friedman: A proof of Alon’s second eigenvalue conjecture and related problems, Mem. Amer. Math. Soc. 195 (2008). · Zbl 1177.05070
[23] J. Friedman and A. Wigderson: On the second eigenvalue of hypergraphs, Combinatorica 15 (1995), 43–65. · Zbl 0843.05075
[24] H. Garland: p-adic curvature and the cohomology of discrete subgroups of p-adic groups, The Annals of Mathematics 97 (1973), 375–423. · Zbl 0262.22010
[25] M. Gromov: Singularities, expanders and topology of maps. Part 2: from combinatorics to topology via algebraic isoperimetry, Geometric And Functional Analysis 20 (2010), 416–526. · Zbl 1251.05039
[26] A. Gundert and M. Szedlák: Higher dimensional discrete Cheeger inequalities, Annual Symposium on Computational Geometry (New York, NY, USA), SOCG14, ACM, 2014. · Zbl 1405.05101
[27] A. Gundert and U. Wagner: On Laplacians of random complexes, in: Proceedings of the 2012 symposuim on Computational Geometry, ACM, 2012, 151–160. · Zbl 1293.05210
[28] S. Hoory, N. Linial and A. Wigderson: Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (2006), 439–562. · Zbl 1147.68608
[29] S. Janson: On concentration of probability, Contemporary combinatorics 10 (2002), 1–9.
[30] W. Kook, V. Reiner and D. Stanton: Combinatorial Laplacians of matroid complexes, Journal of the American Mathematical Society 13 (2000), 129–148. · Zbl 0940.05021
[31] N. Linial and R. Meshulam: Homological connectivity of random 2-complexes, Combinatorica 26 (2006), 475–487. · Zbl 1121.55013
[32] A. Lubotzky, R. Phillips and P. Sarnak: Ramanujan graphs, Combinatorica 8 (1988), 261–277. · Zbl 0661.05035
[33] A. Lubotzky, B. Samuels and U. Vishne: Ramanujan complexes of type Ãd, Israel Journal of Mathematics 149 (2005), 267–299. · Zbl 1087.05036
[34] A. Lubotzky: Discrete groups, expanding graphs and invariant measures, vol. 125, Birkhauser, 2010. · Zbl 1183.22001
[35] A. Lubotzky: Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. 49 (2012), 113–162. · Zbl 1232.05194
[36] D. W. Matula and F. Shahrokhi: Sparsest cuts and bottlenecks in graphs, Discrete Applied Mathematics 27 (1990), 113–123. · Zbl 0733.05056
[37] A. Marcus, D. A. Spielman and N. Srivastava: Interlacing families I: Bipartite Ramanujan graphs of all degrees, arXiv preprint arXiv:1304.4132, (2013). · Zbl 1316.05066
[38] R. Meshulam and N. Wallach: Homological connectivity of random k-dimensional complexes, Random Structures & Algorithms 34 (2009), 408–417. · Zbl 1177.55011
[39] J. Matoušsek and U. Wagner: On Gromov’s method of selecting heavily covered points, Discrete & Computational Geometry 52 (2014), 1–33. · Zbl 1298.51027
[40] A. Nilli: On the second eigenvalue of a graph, Discrete Mathematics 91 (1991), 207–210. · Zbl 0771.05064
[41] I. Newman and Y. Rabinovich: On multiplicative {\(\lambda\)}-approximations and some geometric applications, in: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, SIAM, 2012, 51–67. · Zbl 1281.28006
[42] R. I. Oliveira: Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges, Arxiv preprint ArXiv:0911.0600v2 (2010).
[43] J. Pach: A Tverberg-type result on multicolored simplices, Computational Geometry 10 (1998), 71–76. · Zbl 0896.68143
[44] O. Parzanchevski and R. Rosenthal: Simplicial complexes: spectrum, homology and random walks, arXiv preprint arXiv:1211.6775 (2012).
[45] D. Puder: Expansion of random graphs: New proofs, new results, Inventiones mathematicae (2014), 1–64.
[46] J. Steenbergen, C. Klivans and S. Mukherjee: A Cheeger-type inequality on simplicial complexes, Advances in Applied Mathematics 56 (2014), 56–77. · Zbl 1305.55010
[47] R. M. Tanner: Explicit concentrators from generalized n-gons, SIAM Journal on Algebraic and Discrete Methods 5 (1984), 287. · Zbl 0554.05045
[48] T. Tao: Basic theory of expander graphs, http://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/, 2011.
[49] A. \.Zuk: La propriété (T) de Kazhdan pour les groupes agissant sur les polyedres, in: Comptes rendus de l’Académie des sciences, Série 1, Mathématique 323 (1996), 453–458.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.