Search Results

Documents authored by McKenzie, Theo

Track A: Algorithms, Complexity and Games
High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion

Authors: Theo McKenzie and Sidhanth Mohanty

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

  author =	{McKenzie, Theo and Mohanty, Sidhanth},
  title =	{{High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{96:1--96:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-141655},
  doi =		{10.4230/LIPIcs.ICALP.2021.96},
  annote =	{Keywords: expander graphs, Ramanujan graphs, vertex expansion, girth}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail