×

zbMATH — the first resource for mathematics

Mixing in high-dimensional expanders. (English) Zbl 1371.05329
Summary: We establish a generalization of the expander mixing lemma for arbitrary (finite) simplicial complexes. The original lemma states that concentration of the Laplace spectrum of a graph implies combinatorial expansion (which is also referred to as mixing, or pseudo-randomness). Recently, an analogue of this lemma was proved for simplicial complexes of arbitrary dimension, provided that the skeleton of the complex is complete. More precisely, it was shown that a concentrated spectrum of the simplicial Hodge Laplacian implies a similar type of pseudo-randomness as in graphs. In this paper we remove the assumption of a complete skeleton, showing that simultaneous concentration of the Laplace spectra in all dimensions implies pseudo-randomness in any complex. We discuss various applications and present some open questions.

MSC:
05E45 Combinatorial aspects of simplicial complexes
55U10 Simplicial sets and complexes in algebraic topology
58A14 Hodge theory in global analysis
58C40 Spectral theory; eigenvalue problems on manifolds
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aharoni, R., Berger, E. and Meshulam, R. (2005) Eigenvalues and homology of flag complexes and vector representations of graphs.Geom. Funct. Anal.15555-566. doi:10.1007/s00039-005-0516-9 · Zbl 1074.05058
[2] Alon, N., Eigenvalues and expanders., Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[3] Alon, N. and Chung, F. R. K. (1988) Explicit construction of linear sized tolerant networks.Discrete Math.7215-19. doi:10.1016/0012-365X(88)90189-6 · Zbl 0657.05068
[4] Alon, N. and Milman, V. D. (1985) λ_{1}, isoperimetric inequalities for graphs, and superconcentrators.J. Combin. Theory Ser. B3873-88. doi:10.1016/0095-8956(85)90092-9 · Zbl 0549.05051
[5] Beigel, R., Margulis, G. and Spielman, D. A. (1993) Fault diagnosis in a small constant number of parallel testing rounds. In Proc. Fifth Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, pp. 21-29.
[6] Bilu, Y. and Linial, N. (2006) Lifts, discrepancy and nearly optimal spectral gap.Combinatorica26495-519. doi:10.1007/s00493-006-0029-7 · Zbl 1121.05054
[7] Cartwright, D. I., Solé, P. and Żuk, A. (2003) Ramanujan geometries of type Ã_{n}.Discrete Math.26935-43. doi:10.1016/S0012-365X(02)00748-3 · Zbl 1021.05068
[8] Cohen, E., Mubayi, D., Ralli, P. and Tetali, P. (2016) Inverse expander mixing for hypergraphs. Electron. J. Combin.23P2.20. · Zbl 1335.05123
[9] Dodziuk, J., Finite-difference approach to the Hodge theory of harmonic forms., Amer. J. Math., 98, 79-104, (1976) · Zbl 0324.58001
[10] Dodziuk, J., Difference equations, isoperimetric inequality and transience of certain random walks., Trans. Amer. Math. Soc., 284, 787-794, (1984) · Zbl 0512.39001
[11] Duval, A., Klivans, C. and Martin, J. (2009) Simplicial matrix-tree theorems.Trans. Amer. Math. Soc.3616073-6114. doi:10.1090/S0002-9947-09-04898-3 · Zbl 1207.05227
[12] Eckmann, B., Harmonische Funktionen und Randwertaufgaben in einem Komplex., Commentarii Mathematici Helvetici, 17, 240-255, (1944) · Zbl 0061.41106
[13] Fox, J., Gromov, M., Lafforgue, V., Naor, A. and Pach, J. (2012) Overlap properties of geometric expanders.J. Reine Angew. Math.67149-83. · Zbl 1306.05171
[14] Friedman, J., Computing Betti numbers via combinatorial Laplacians., Algorithmica, 21, 331-346, (1998) · Zbl 0911.57021
[15] Friedman, J. (2008) A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems, Vol. 908 of Memoirs of the American Mathematical Society, AMS. · Zbl 1177.05070
[16] Friedman, J. and Pippenger, N. (1987) Expanding graphs contain all small trees.Combinatorica771-76. doi:10.1007/BF02579202 · Zbl 0624.05028
[17] Garland, H., p-adic curvature and the cohomology of discrete subgroups of p-adic groups., Ann. of Math., 97, 375-423, (1973) · Zbl 0262.22010
[18] Golubev, K. (2016) On the chromatic number of a simplicial complex. Combinatorica. https://doi.org/10.1007/s00493-016-3137-z
[19] Golubev, K. and Parzanchevski, O. (2014) Spectrum and combinatorics of Ramanujan triangle complexes. arXiv:1406.6666 · Zbl 1410.05126
[20] Gromov, M., Singularities, expanders and topology of maps, part 2: From combinatorics to topology via algebraic isoperimetry., Geom. Funct. Anal., 20, 416-526, (2010) · Zbl 1251.05039
[21] Gundert, A. and Szedlák, M. (2014) Higher dimensional Cheeger inequalities. In SOCG’14: Symposium on Computational Geometry, ACM, pp. 181-188. doi:10.1145/2582112.2582118 · Zbl 1395.05100
[22] Gundert, A. and Wagner, U. (2012) On Laplacians of random complexes. In SOCG’12: Symposium on Computational Geometry, ACM, pp. 151-160. doi:10.1145/2261250.2261272 · Zbl 1293.05210
[23] Gundert, A. and Wagner, U. (2013) On expansion and spectral properties of simplicial complexes. PhD thesis, ETH Zürich, Switzerland. Dissertation ETH no. 21600 of Anna Gundert.
[24] Hoffman, A. J. (1970) On eigenvalues and colorings of graphs. Graph Theory and its Appl. (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), Academic Press, New York, pp. 79-91.
[25] Horak, D. and Jost, J. (2013) Spectra of combinatorial Laplace operators on simplicial complexes.Adv. Math.244303-336. doi:10.1016/j.aim.2013.05.007 · Zbl 1290.05103
[26] Kook, W., Reiner, V. and Stanton, D. (2000) Combinatorial Laplacians of matroid complexes.J. Amer. Math. Soc.13129-148. doi:10.1090/S0894-0347-99-00316-1 · Zbl 0940.05021
[27] Li, W. C. W., Ramanujan hypergraphs., Geom. Funct. Anal., 14, 380-399, (2004) · Zbl 1084.05047
[28] Linial, N. and Meshulam, R. (2006) Homological connectivity of random 2-complexes.Combinatorica26475-487. doi:10.1007/s00493-006-0027-9 · Zbl 1121.55013
[29] Lubotzky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs.Combinatorica8261-277. doi:10.1007/BF02126799 · Zbl 0661.05035
[30] Lubotzky, A., Samuels, B. and Vishne, U. (2005) Ramanujan complexes of type Ã_{d}.Israel J. Math.149267-299. doi:10.1007/BF02772543 · Zbl 1087.05036
[31] Marcus, A., Spielman, D. A. and Srivastava, N. (2015) Interlacing families I: Bipartite Ramanujan graphs of all degrees.Ann. of Math.182307-325. · Zbl 1316.05066
[32] Margulis, G. A., Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators., Problemy Peredachi Informatsii, 24, 51-60, (1988) · Zbl 0708.05030
[33] Matouşek, J. and Wagner, U. (2014) On Gromov’s method of selecting heavily covered points.Discrete Comput. Geom.521-33. doi:10.1007/s00454-014-9584-7 · Zbl 1298.51027
[34] Mukherjee, S. and Steenbergen, J. (2016) Random walks on simplicial complexes and harmonics.Random Struct. Alg.49379-405. doi:10.1002/rsa.20645 · Zbl 1346.05301
[35] Pach, J., A Tverberg-type result on multicolored simplices., Comput. Geom., 10, 71-76, (1998) · Zbl 0896.68143
[36] Parzanchevski, O. and Rosenthal, R. (2017) Simplicial complexes: Spectrum, homology and random walks.Random Struct. Alg.50225-261. doi:10.1002/rsa.20657 · Zbl 1359.05114
[37] Parzanchevski, O., Rosenthal, R. and Tessler, R. J. (2016) Isoperimetric inequalities in simplicial complexes.Combinatorica36195-227. doi:10.1007/s00493-014-3002-x · Zbl 1389.05174
[38] Puder, D., Expansion of random graphs: New proofs, new results., Inventio. Math., 201, 845-908, (2015) · Zbl 1320.05115
[39] Sarveniazi, A., Explicit construction of a Ramanujan (n_{1}, n_{2},. . ., n_{d-1}) -regular hypergraph., Duke Math. J., 139, 141-171, (2007) · Zbl 1180.11016
[40] Spielman, D. A. and Teng, S. H. (2011) Spectral sparsification of graphs.SIAM J. Comput.40981-1025. doi:10.1137/08074489X · Zbl 1228.68040
[41] Tanner, R. M., Explicit concentrators from generalized n-gons, SIAM J. Algebraic Discrete Methods, 5, 287, (1984) · Zbl 0554.05045
[42] Tao, T., (2011)
[43] Żuk, A., La propriété (T) de Kazhdan pour les groupes agissant sur les polyèdres., CR Acad. Sci. Sér. 1 Math., 323, 453-458, (1996) · Zbl 0858.22007
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.