Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders

  • Published:
Geometric and Functional Analysis Aims and scope Submit manuscript

Abstract

Expander graphs have been intensively studied in the last four decades (Hoory et al., Bull Am Math Soc, 43(4):439–562, 2006; Lubotzky, Bull Am Math Soc, 49:113–162, 2012). In recent years a high dimensional theory of expanders has emerged, and several variants have been studied. Among them stand out coboundary expansion and topological expansion. It is known that for every d there are unbounded degree simplicial complexes of dimension d with these properties. However, a major open problem, formulated by Gromov (Geom Funct Anal 20(2):416–526, 2010), is whether bounded degree high dimensional expanders exist for \({d \geq 2}\). We present an explicit construction of bounded degree complexes of dimension \({d = 2}\) which are topological expanders, thus answering Gromov’s question in the affirmative. Conditional on a conjecture of Serre on the congruence subgroup property, infinite sub-family of these give also a family of bounded degree coboundary expanders. The main technical tools are new isoperimetric inequalities for Ramanujan Complexes. We prove linear size bounds on \({\mathbb{F}_2}\) systolic invariants of these complexes, which seem to be the first linear \({\mathbb{F}_2}\) systolic bounds. The expansion results are deduced from these isoperimetric inequalities.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bárány I.: A generalization of Carathéodorys theorem. Discrete Mathematics 40(2), 141–152 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  2. R. Ben Ari and U. Vishne, Homology of 2-dimensional complexes and internal partitions, preprint.

  3. Boros E., Füredi Z.: The number of triangles covering the center of an n-set. Geometriae Dedicata 17(1), 69–77 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cartwright D.I., Steger T.: A family of \({\tilde{A}_n}\)-groups. Israel Journal of Mathematics 103(1), 125–140 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  5. D. Dotterrer, T. Kaufman, and U. Wagner. On Expansion and Topological Overlap. arXiv:1506.04558.

  6. S. Evra, K. Golubev, and A. Lubotzky. Mixing properties and the chromatic number of Ramanujan complexes. International Mathematics Research Notices (IMRN), to appear.

  7. S. Evra and T. Kaufman. Bounded Degree Cosystolic Expanders of Every Dimension (2015). arXiv:1510.00839.

  8. Fox J., Gromov M., Lafforgue V., Naor A., Pach J.: Overlap properties of geometric expanders. Journal fr die reine und angewandte Mathematik 671, 49–83 (2012)

    MathSciNet  MATH  Google Scholar 

  9. Garland H.: p-Adic curvature and the cohomology of discrete subgroups of p-adic groups. The Annals of Mathematics 97(3), 375–423 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  10. M. Gromov. Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geometric and Functional Analysis, (2)20 (2010), 416–526

  11. Guth L., Lubotzky A.: Quantum error-correcting codes and 4-dimensional arithmetic hyperbolic manifolds. Journal of Mathematical Physics 55, 082202 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  12. Hoory S., Linial N., Wigderson A.: Expander graphs and their applications. Bulletin of the American Mathematical Society 43(4), 439–562 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. T. Kaufman, D. Kazhdan, and A. Lubotzky. Ramanujan Complexes and bounded degree topological expanders. FOCS, (2014), 484–493.

  14. Linial N., Meshulam R.: Homological connectivity of random 2-complexes. Combinatorica 26(4), 475–487 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lubotzky A.: Expander graphs in pure and applied mathematics. Bulletin of the American Mathematical Society 49, 113–162 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. A. Lubotzky. Ramanujan Complexes and High Dimensional Expanders. Japanese Journal of Mathematics, (2013), to appear. arXiv:1301.1028.

  17. A. Lubotzky. Discrete Groups, Expanding Graphs and Invariant Measures. Progress in Mathematics, Vol. 125. Birkhäuser, Basel (1994).

  18. Lubotzky A., Meshulam R.: Random Latin squares and 2-dimensional expanders. Advances in Mathematics 272, 743–760 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  19. A. Lubotzky, R. Meshulam, and S. Mozes. Expansion of building-like complexes. Groups, Geometry and Dynamics (GGD), to appear.

  20. Lubotzky A., Samuels B., Vishne U.: Ramanujan complexes of type \({\tilde{A}_d}\). Israel Journal of Mathematics 149(1), 267–299 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  21. A. Lubotzky, B. Samuels, and U. Vishne. Explicit constructions of Ramanujan complexes of type \({\tilde{A}_d}\). European Journal of Combinatorics, (6)26 (2005) 965–993.

  22. Meshulam R., Wallach N.: Homological connectivity of random k-dimensional complexes. Random Structures and Algorithms 34(3), 408–417 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  23. D.A. Meyer, M.H. Freedman, and F. Luo. \({Z_2}\)-systolic freedom and quantum codes. Mathematics of Quantum Computation, (2002), 287–320.

  24. O. Parzanchevsky. Mixing in high-dimensional expanders (2013). arXiv:1310.6477.

  25. G. Prasad and A. Rapinchuk. Computation of the metaplectic kernel. Inst. Hautes Études Sci. Publ. Math., (84) (1997), 91–187.

  26. G. Prasad and A. Rapinchuk. Developments on the congruence subgroup problem after the work of Bass, Milnor and Serre. arXiv:0809.1622.

  27. Raghunathan M.S.: The congruence subgroup problem. The Proceedings of the Indian Academy of Sciences - Mathematical Sciences 114(4), 299–308 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  28. Rapinchuk A., Segev Y.: Valuation-like maps and the congurence subgroup property. Inventiones Mathematicae 144, 571–607 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  29. L. Ribes and P. Zalesskii. Profinite groups. In: Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], Vol. 40. Springer, Berlin, xiv+435 pp. (2000).

  30. Serre J.P.: Le probleme des groupes de congruence pour \({SL_2}\). Annals of Mathematics 92(3), 489–527 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  31. G. Zemor, On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction. Coding and Cryptology, second international workshop IWCC, LNCS, Vol. 5557 (2009), pp. 259–273.

Download references

Author information

Authors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Tali Kaufman

  2. Hebrew University, Jerusalem, Israel

    David Kazhdan & Alexander Lubotzky

Authors
  1. Tali Kaufman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David Kazhdan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alexander Lubotzky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tali Kaufman.

Additional information

The results of this paper were announced in Kaufman et al. (Ramanujan complexes and bounded degree topological expanders FOCS 2014 [KKL14]).

Tali Kaufman’s research was supported in part by the Alon Fellowship, IRG, ERC and BSF. David Kazhdan’s research was supported in part by the NSF, BSF and ERC. Alexander Lubotzky’s research was supported in part by the ERC, NSF and ISF.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kaufman, T., Kazhdan, D. & Lubotzky, A. Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders. Geom. Funct. Anal. 26, 250–287 (2016). https://doi.org/10.1007/s00039-016-0362-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00039-016-0362-y

Keywords

Search

Navigation