Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T06:40:52.376Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 746 - 761
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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