McKenzie, Theo ;
Mohanty, Sidhanth
HighGirth NearRamanujan Graphs with Lossy Vertex Expansion
Abstract
Kahale proved that linear sized sets in dregular Ramanujan graphs have vertex expansion at least d/2 and complemented this with construction of nearRamanujan 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 highgirth Ramanujan graphs breaks past the d/2 bound. Our results are twofold:
1) For every d = p+1 for prime p ≥ 3 and infinitely many n, we exhibit an nvertex dregular graph with girth Ω(log_{d1} n) and vertex expansion of sublinear sized sets bounded by (d+1)/2 whose nontrivial eigenvalues are bounded in magnitude by 2√{d1}+O(1/(log_{d1} n)).
2) In any Ramanujan graph with girth Clog_{d1} n, all sets of size bounded by n^{0.99C/4} have nearlossless vertex expansion (1o_d(1))d. The tools in analyzing our construction include the nonbacktracking operator of an infinite graph, the IharaBass 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.
BibTeX  Entry
@InProceedings{mckenzie_et_al:LIPIcs.ICALP.2021.96,
author = {McKenzie, Theo and Mohanty, Sidhanth},
title = {{HighGirth NearRamanujan Graphs with Lossy Vertex Expansion}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {96:196:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14165},
URN = {urn:nbn:de:0030drops141655},
doi = {10.4230/LIPIcs.ICALP.2021.96},
annote = {Keywords: expander graphs, Ramanujan graphs, vertex expansion, girth}
}
02.07.2021
Keywords: 

expander graphs, Ramanujan graphs, vertex expansion, girth 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 