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

Random Steiner systems and bounded degree coboundary expanders of every dimension

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We introduce a new model of random d-dimensional simplicial complexes, for \(d\ge 2\), whose \((d-1)\)-cells have bounded degrees. We show that with high probability, complexes sampled according to this model are coboundary expanders. The construction relies on Keevash’s recent result on designs (The existence of designs; arXiv:1401.3665, 2014), and the proof of the expansion uses techniques developed by Evra and Kaufman in (Bounded degree cosystolic expanders of every dimension; arXiv:1510.00839, 2015). This gives a full solution to a question raised in Dotterrer and Kahle (J Topol Anal 4(4): 499–514, 2012), which was solved in the two-dimensional case by Lubotzky and Meshulam (Adv Math 272: 743–760, 2015).

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

Notes

  1. Not necessarily with a complete \((d-1)\)-skeleton.

  2. Although this property is not explicitly stated in [22, 23] one can note that the algorithm is invariant under permutations. Indeed in the greedy stage the name of the vertices is not used while in the second stage the names for the vertices are chosen uniformly at random (see Template 2.3).

References

  1. Alon, N., Milman, V.D.: \(\lambda _1\), isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory Ser. B 38(1), 73–88 (1985)

    Google Scholar 

  2. Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol. 92. American Mathematical Society, Providence (1997)

  3. Cohen, E., Mubayi, D., Ralli, P., Tetali, P.: Inverse expander mixing for hypergraphs. Electron. J. Comb. 23(2) (2016)

  4. Dodziuk, J.: Difference equations, isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc. 284(2), 787–794 (1984)

    Article  MathSciNet  Google Scholar 

  5. Dotterrer, D., Kahle, M.: Coboundary expanders. J. Topol. Anal. 4(4), 499–514 (2012)

    Article  MathSciNet  Google Scholar 

  6. Dotterrer, D., Kaufman, T., Wagner, U.: On expansion and topological overlap. In: Fekete, S., Lubiw, A. (eds.) Proceedings of the 32nd International Symposium on Computational Geometry (SoCG’16). Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, pp. 35:1–35:10. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl (2016)

  7. Eckmann, B.: Harmonische Funktionen und Randwertaufgaben in einem Komplex. Comment. Math. Helv. 17, 240–255 (1945)

    Article  MathSciNet  Google Scholar 

  8. Evra, S.: Finite quotients of Bruhat–Tits buildings as geometric expanders. J. Topol. Anal. 9(1), 51–66 (2017)

    Article  MathSciNet  Google Scholar 

  9. Evra, S., Golubev, K., Lubotzky, A.: Mixing properties and the chromatic number of Ramanujan complexes. Int. Math. Res. Not. IMRN 2015(22), 11520–11548 (2015)

    MathSciNet  MATH  Google Scholar 

  10. Evra, S., Kaufman, T.: Bounded degree cosystolic expanders of every dimension (2015). arXiv:1510.00839

  11. Fox, J., Gromov, M., Lafforgue, V., Naor, A., Pach, J.: Overlap properties of geometric expanders. J. Reine Angew. Math. 671, 49–83 (2012)

    MathSciNet  MATH  Google Scholar 

  12. Friedman, J.: On the second eigenvalue and random walks in random \(d\)-regular graphs. Combinatorica 11(4), 331–362 (1991)

    Google Scholar 

  13. Friedman, J.: A proof of Alon’s second eigenvalue conjecture and related problems. Memoirs of the American Mathematical Society, vol. 195 (910). American Mathematical Society, Providence (2008)

  14. Garland, H.: \(p\)-Adic curvature and the cohomology of discrete subgroups of \(p\)-adic groups. Ann. Math. 97, 375–423 (1973)

    Google Scholar 

  15. Golubev, K.: On the chromatic number of a simplicial complex. Combinatorica 37(5), 953–964 (2017)

    Article  MathSciNet  Google Scholar 

  16. Gromov, M.: Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry. Geom. Funct. Anal. 20(2), 416–526 (2010)

    Article  MathSciNet  Google Scholar 

  17. Gundert, A., Szedlák, M.: Higher dimensional Cheeger inequalities. In: Proceedings of the 13th Annual Symposium on Computational Geometry (SoCG’14), pp. 181–188. ACM, New York (2014)

  18. Gundert, A., Wagner, U.: On eigenvalues of random complexes. Isr. J. Math. 216(2), 545–582 (2016)

    Article  MathSciNet  Google Scholar 

  19. Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. 43(4), 439–561 (2006)

    Article  MathSciNet  Google Scholar 

  20. Horak, D., Jost, J.: Spectra of combinatorial Laplace operators on simplicial complexes. Adv. Math. 244, 303–336 (2013)

    Article  MathSciNet  Google Scholar 

  21. Kaufman, T., Kazhdan, D., Lubotzky, A.: Isoperimetric inequalities for Ramanujan complexes and topological expanders. Geom. Funct. Anal. 26(1), 250–287 (2016)

    Article  MathSciNet  Google Scholar 

  22. Keevash, P.: The existence of designs (2014). arXiv:1401.3665

  23. Keevash, P.: Counting designs (2015). arXiv:1504.02909

  24. Knowles, A., Rosenthal, R.: Eigenvalue confinement and spectral gap for random simplicial complexes. Rand. Struct. Algorithms 51(3), 506–537 (2017)

    Article  MathSciNet  Google Scholar 

  25. Li, W.C.W.: Ramanujan hypergraphs. Geom. Funct. Anal. 14(2), 380–399 (2004)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  27. Lubotzky, A.: Discrete groups, expanding graphs and invariant measures. Modern Birkhäuser Classics. Birkhäuser, Basel (2010). With an appendix by Jonathan D. Rogawski, Reprint of the 1994 edition

  28. Lubotzky, A.: Ramanujan complexes and high dimensional expanders. Jpn. J. Math. 9(2), 137–169 (2014)

    Article  MathSciNet  Google Scholar 

  29. Lubotzky, A., Meshulam, R.: Random Latin squares and 2-dimensional expanders. Adv. Math. 272, 743–760 (2015)

    Article  MathSciNet  Google Scholar 

  30. Lubotzky, A., Meshulam, R., Mozes, S.: Expansion of building-like complexes. Groups Geom. Dyn. 10(1), 155–175 (2016)

    Article  MathSciNet  Google Scholar 

  31. Lubotzky, A., Samuels, B., Vishne, U.: Ramanujan complexes of type \(\widetilde{A}_d\). Isr. J. Math. 149, 267–299 (2005)

    Google Scholar 

  32. Matoušek, J., Wagner, U.: On Gromov’s method of selecting heavily covered points. Discrete Comput. Geom. 52(1), 1–33 (2014)

    Article  MathSciNet  Google Scholar 

  33. Meshulam, R., Wallach, N.: Homological connectivity of random \(k\)-dimensional complexes. Rand. Struct. Algorithms 34(3), 408–417 (2009)

    Google Scholar 

  34. Mukherjee, S., Steenbergen, J.: Random walks on simplicial complexes and harmonics. Rand. Struct. Algorithms 49(2), 379–405 (2016)

    Article  MathSciNet  Google Scholar 

  35. Oppenheim, I.: Local spectral expansion approach to high dimensional expanders (2014). arXiv:1407.8517

  36. Oppenheim, I.: Local spectral expansion approach to high dimensional expanders. Part I: descent of spectral gaps. Discrete Comput. Geom. 59(2), 293–330 (2018)

    Article  MathSciNet  Google Scholar 

  37. Parzanchevski, O.: Mixing in high-dimensional expanders. Comb. Probab. Comput. 26(5), 746–761 (2017)

    Article  MathSciNet  Google Scholar 

  38. Parzanchevski, O., Rosenthal, R.: Simplicial complexes: spectrum, homology and random walks. Rand. Struct. Algorithms 50(2), 225–261 (2017)

    Article  MathSciNet  Google Scholar 

  39. Parzanchevski, O., Rosenthal, R., Tessler, R.J.: Isoperimetric inequalities in simplicial complexes. Combinatorica 36(2), 195–227 (2016)

    Article  MathSciNet  Google Scholar 

  40. Puder, D.: Expansion of random graphs: new proofs, new results. Invent. Math. 201(3), 845–908 (2015)

    Article  MathSciNet  Google Scholar 

  41. Rosenthal, R.: Simplicial branching random walks and their applications (2014). arXiv:1412.5406

  42. Steenbergen, J., Klivans, C., Mukherjee, S.: A Cheeger-type inequality on simplicial complexes. Adv. Appl. Math. 56, 56–77 (2014)

    Article  MathSciNet  Google Scholar 

  43. Wagner, U.: Minors in random and expanding hypergraphs. In: Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG’11), pp. 351–360. ACM, New York (2011)

Download references

Acknowledgements

The authors would like to thank the anonymous referees for their suggestions which helped to improve this manuscript.

Author information

Authors and Affiliations

  1. Einstein Institute of Mathematics, Hebrew University, Jerusalem, 91904, Israel

    Alexander Lubotzky

  2. Institute of Theoretical Studies, ETH Zürich, 8092, Zürich, Switzerland

    Zur Luria

  3. Israel Institute for Advanced Studies, Hebrew University of Jerusalem, Givat Ram, Jerusalem, 91904, Israel

    Zur Luria

  4. Departement Mathematik, ETH Zürich, 8092, Zürich, Switzerland

    Ron Rosenthal

  5. Technion - Israel Institute of Technology, Haifa, 3200003, Israel

    Ron Rosenthal

Authors
  1. Alexander Lubotzky
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zur Luria
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ron Rosenthal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zur Luria.

Additional information

Editor in Charge: János Pach

A. Lubotzky: Research supported in part by the ERC, ISF and NSF; Z. Luria and A. Lubotzky: Supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Foundation; R. Rosenthal: Partially supported by an ETH fellowship.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lubotzky, A., Luria, Z. & Rosenthal, R. Random Steiner systems and bounded degree coboundary expanders of every dimension. Discrete Comput Geom 62, 813–831 (2019). https://doi.org/10.1007/s00454-018-9991-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-018-9991-2

Keywords

Search

Navigation