Document Open Access Logo

High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion

Authors Theo McKenzie, Sidhanth Mohanty

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.96.pdf
  • Filesize: 0.74 MB
  • 15 pages

Document Identifiers

Author Details

Theo McKenzie
  • Department of Mathematics, University of California, Berkeley, CA, USA
Sidhanth Mohanty
  • Department of Computer Science, University of California, Berkeley, CA, USA

Funding

  • McKenzie, Theo: This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGE-1752814.
  • Mohanty, Sidhanth: Supported by NSF grant CCF-1718695.

Acknowledgements

We would like to thank Shirshendu Ganguly and Nikhil Srivastava for their highly valuable insights, intuition, and comments. We would also like to thank Amitay Kamber for helpful comments on the initial version of the preprint.

Cite As Get BibTex

Theo McKenzie and Sidhanth Mohanty. High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 96:1-96:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.96

Abstract

Kahale proved that linear sized sets in d-regular Ramanujan graphs have vertex expansion at least d/2 and complemented this with construction of near-Ramanujan graphs with vertex expansion no better than d/2. However, the construction of Kahale encounters highly local obstructions to better vertex expansion. In particular, the poorly expanding sets are associated with short cycles in the graph. Thus, it is natural to ask whether the vertex expansion of high-girth Ramanujan graphs breaks past the d/2 bound. Our results are two-fold:  
1) For every d = p+1 for prime p ≥ 3 and infinitely many n, we exhibit an n-vertex d-regular graph with girth Ω(log_{d-1} n) and vertex expansion of sublinear sized sets bounded by (d+1)/2 whose nontrivial eigenvalues are bounded in magnitude by 2√{d-1}+O(1/(log_{d-1} n)). 
2) In any Ramanujan graph with girth Clog_{d-1} n, all sets of size bounded by n^{0.99C/4} have near-lossless vertex expansion (1-o_d(1))d.  The tools in analyzing our construction include the nonbacktracking operator of an infinite graph, the Ihara-Bass formula, a trace moment method inspired by Bordenave’s proof of Friedman’s theorem [Bordenave, 2019], and a method of Kahale [Kahale, 1995] to study dispersion of eigenvalues of perturbed graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Spectra of graphs
  • Theory of computation → Expander graphs and randomness extractors
Keywords
  • expander graphs
  • Ramanujan graphs
  • vertex expansion
  • girth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon. Eigenvalues and expanders. Combinatorica, 6:83-96, 1986. Google Scholar
  2. Noga Alon. Explicit expanders of every degree and size. Combinatorica, pages 1-17, 2021. Google Scholar
  3. Noga Alon, Shirshendu Ganguly, and Nikhil Srivastava. High-girth near-Ramanujan graphs with localized eigenvectors. arXiv preprint, 2019. URL: http://arxiv.org/abs/1908.03694.
  4. Noga Alon, Shlomo Hoory, and Nathan Linial. The Moore bound for irregular graphs. Graphs and Combinatorics, 18(1):53-57, 2002. Google Scholar
  5. Nalini Anantharaman. Quantum ergodicity on regular graphs. Communications in Mathematical Physics, 353(2):633-690, 2017. Google Scholar
  6. Nalini Anantharaman and Etienne Le Masson. Quantum ergodicity on large regular graphs. Duke Math. J., 164(4):723-765, 2015. Google Scholar
  7. Omer Angel, Joel Friedman, and Shlomo Hoory. The non-backtracking spectrum of the universal cover of a graph. Transactions of the American Mathematical Society, 367(6):4287-4318, 2015. Google Scholar
  8. Charles Bordenave. A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. In Annales scientifiques de l'Ecole normale supérieure, 2019. Google Scholar
  9. Shimon Brooks, Etienne Le Masson, and Elon Lindenstrauss. Quantum ergodicity and averaging operators on the sphere. International Mathematics Research Notices, 19:6034-6064, 2016. Google Scholar
  10. Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 659-668, 2002. Google Scholar
  11. Joel Friedman. A proof of Alon’s second eigenvalue conjecture. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 720-724, 2003. Google Scholar
  12. Shirshendu Ganguly and Nikhil Srivastava. On non-localization of eigenvectors of high girth graphs. International Mathematics Research Notices, 2018. Google Scholar
  13. Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1-2):613-622, 2001. Google Scholar
  14. Venkatesan Guruswami, James Lee, and Alexander Razborov. Almost euclidean subspaces of 𝓁ⁿ₁ via expander codes. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 353-362, 2008. Google Scholar
  15. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc., 43(4):439–561, 2018. Google Scholar
  16. Nabil Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM (JACM), 42(5):1091-1106, 1995. Google Scholar
  17. Nati Linial and Michael Simkin. A randomized construction of high girth regular graphs. Random Structures & Algorithms, 58(2):345-369, 2021. Google Scholar
  18. Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8:261-277, 1988. Google Scholar
  19. Michael Luby, Michael Mitzenmacher, M. Amin Shokrollahi, and Daniel Spielman. Improved low-density parity-check codes using irregular graphs. IEEE Trans. Inform. Theory, 42(2):585-598, 2001. Google Scholar
  20. Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii, 24(1):51-60, 1988. Google Scholar
  21. Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. Explicit near-ramanujan graphs of every degree. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 510-523, 2020. Google Scholar
  22. Moshe Morgenstern. Existence and explicit constructions of q+ 1 regular ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B, 62(1):44-62, 1994. Google Scholar
  23. Pedro Paredes. Spectrum preserving short cycle removal on regular graphs. In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 55:1-55:19, 2021. Google Scholar
  24. Gregory Quenell. Notes on an example of McLaughlin, 1996. Google Scholar
  25. Grant Schoenebeck. Linear level lasserre lower bounds for certain k-csps. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593-602. IEEE, 2008. Google Scholar
  26. Michael Sipser and Daniel Spielman. Expander codes. IEEE Trans. Inform. Theory, 42(6, part 1):1710-1722, 1996. Google Scholar
  27. Daniel Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6, part 1):1723-1731, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact