Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-07T12:26:14.435Z Has data issue: false hasContentIssue false
  • English
  • Français

Mixing in High-Dimensional Expanders

Published online by Cambridge University Press:  17 May 2017

ORI PARZANCHEVSKI
ORI PARZANCHEVSKI*
Affiliation:
School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: parzan@ias.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Primary 05E45Secondary 55U1058A1458C40

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 746 - 761
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Aharoni, R., Berger, E. and Meshulam, R. (2005) Eigenvalues and homology of flag complexes and vector representations of graphs. Geom. Funct. Anal. 15 555–566.CrossRefGoogle Scholar
[2] Alon, N. (1986) Eigenvalues and expanders. Combinatorica 6 83–96.Google Scholar
[3] Alon, N. and Chung, F. R. K. (1988) Explicit construction of linear sized tolerant networks. Discrete Math. 72 15–19.CrossRefGoogle Scholar
[4] Alon, N. and Milman, V. D. (1985) λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38 73–88.CrossRefGoogle Scholar
[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.Google Scholar
[6] Bilu, Y. and Linial, N. (2006) Lifts, discrepancy and nearly optimal spectral gap. Combinatorica 26 495–519.CrossRefGoogle Scholar
[7] Cartwright, D. I., Solé, P. and Żuk, A. (2003) Ramanujan geometries of type Ãn . Discrete Math. 269 35–43.Google Scholar
[8] Cohen, E., Mubayi, D., Ralli, P. and Tetali, P. (2016) Inverse expander mixing for hypergraphs. Electron. J. Combin. 23 P2.20.Google Scholar
[9] Dodziuk, J. (1976) Finite-difference approach to the Hodge theory of harmonic forms. Amer. J. Math. 98 79–104.Google Scholar
[10] Dodziuk, J. (1984) Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Amer. Math. Soc. 284 787–794.Google Scholar
[11] Duval, A., Klivans, C. and Martin, J. (2009) Simplicial matrix-tree theorems. Trans. Amer. Math. Soc. 361 6073–6114.CrossRefGoogle Scholar
[12] Eckmann, B. (1944) Harmonische Funktionen und Randwertaufgaben in einem Komplex. Commentarii Mathematici Helvetici 17 240–255.CrossRefGoogle Scholar
[13] Fox, J., Gromov, M., Lafforgue, V., Naor, A. and Pach, J. (2012) Overlap properties of geometric expanders. J. Reine Angew. Math. 671 49–83.Google Scholar
[14] Friedman, J. (1998) Computing Betti numbers via combinatorial Laplacians. Algorithmica 21 331–346.CrossRefGoogle Scholar
[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.Google Scholar
[16] Friedman, J. and Pippenger, N. (1987) Expanding graphs contain all small trees. Combinatorica 7 71–76.Google Scholar
[17] Garland, H. (1973) p-adic curvature and the cohomology of discrete subgroups of p-adic groups. Ann. of Math. 97 375–423.Google Scholar
[18] Golubev, K. (2016) On the chromatic number of a simplicial complex. Combinatorica. https://doi.org/10.1007/s00493-016-3137-z CrossRefGoogle Scholar
[19] Golubev, K. and Parzanchevski, O. (2014) Spectrum and combinatorics of Ramanujan triangle complexes. arXiv:1406.6666 Google Scholar
[20] Gromov, M. (2010) Singularities, expanders and topology of maps, part 2: From combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20 416–526.Google Scholar
[21] Gundert, A. and Szedlák, M. (2014) Higher dimensional Cheeger inequalities. In SOCG'14: Symposium on Computational Geometry, ACM, pp. 181–188.Google Scholar
[22] Gundert, A. and Wagner, U. (2012) On Laplacians of random complexes. In SOCG'12: Symposium on Computational Geometry, ACM, pp. 151–160.CrossRefGoogle Scholar
[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.Google Scholar
[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.Google Scholar
[25] Horak, D. and Jost, J. (2013) Spectra of combinatorial Laplace operators on simplicial complexes. Adv. Math. 244 303–336.Google Scholar
[26] Kook, W., Reiner, V. and Stanton, D. (2000) Combinatorial Laplacians of matroid complexes. J. Amer. Math. Soc. 13 129–148.CrossRefGoogle Scholar
[27] Li, W. C. W. (2004) Ramanujan hypergraphs. Geom. Funct. Anal. 14 380–399.Google Scholar
[28] Linial, N. and Meshulam, R. (2006) Homological connectivity of random 2-complexes. Combinatorica 26 475–487.Google Scholar
[29] Lubotzky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs. Combinatorica 8 261–277.Google Scholar
[30] Lubotzky, A., Samuels, B. and Vishne, U. (2005) Ramanujan complexes of type Ãd . Israel J. Math. 149 267–299.Google Scholar
[31] Marcus, A., Spielman, D. A. and Srivastava, N. (2015) Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. 182 307–325.Google Scholar
[32] Margulis, G. A. (1988) Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy Peredachi Informatsii 24 51–60.Google Scholar
[33] Matouşek, J. and Wagner, U. (2014) On Gromov's method of selecting heavily covered points. Discrete Comput. Geom. 52 1–33.Google Scholar
[34] Mukherjee, S. and Steenbergen, J. (2016) Random walks on simplicial complexes and harmonics. Random Struct. Alg. 49 379–405.Google Scholar
[35] Pach, J. (1998) A Tverberg-type result on multicolored simplices. Comput. Geom. 10 71–76.Google Scholar
[36] Parzanchevski, O. and Rosenthal, R. (2017) Simplicial complexes: Spectrum, homology and random walks. Random Struct. Alg. 50 225–261.Google Scholar
[37] Parzanchevski, O., Rosenthal, R. and Tessler, R. J. (2016) Isoperimetric inequalities in simplicial complexes. Combinatorica 36 195–227.Google Scholar
[38] Puder, D. (2015) Expansion of random graphs: New proofs, new results. Inventio. Math. 201 845–908.Google Scholar
[39] Sarveniazi, A. (2007) Explicit construction of a Ramanujan (n 1, n 2,. . ., n d-1) -regular hypergraph. Duke Math. J. 139 141–171.Google Scholar
[40] Spielman, D. A. and Teng, S. H. (2011) Spectral sparsification of graphs. SIAM J. Comput. 40 981–1025.CrossRefGoogle Scholar
[41] Tanner, R. M. (1984) Explicit concentrators from generalized n-gons. SIAM J. Algebraic Discrete Methods 5 287.Google Scholar
[42] Tao, T. (2011) Basic Theory of Expander Graphs. http://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/ Google Scholar
[43] Żuk, A. (1996) La propriété (T) de Kazhdan pour les groupes agissant sur les polyèdres. CR Acad. Sci. Sér. 1 Math. 323 453–458.Google Scholar