TY - GEN

T1 - Spectrum preserving short cycle removal on regular graphs

AU - Paredes, Pedro

N1 - Funding Information:
Funding Pedro Paredes: Supported by NSF grant CCF-1717606. This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).
Publisher Copyright:
© Pedro Paredes; licensed under Creative Commons License CC-BY 4.0.

PY - 2021/3/1

Y1 - 2021/3/1

N2 - We describe a new method to remove short cycles on regular graphs while maintaining spectral bounds (the nontrivial eigenvalues of the adjacency matrix), as long as the graphs have certain combinatorial properties. These combinatorial properties are related to the number and distance between short cycles and are known to happen with high probability in uniformly random regular graphs. Using this method we can show two results involving high girth spectral expander graphs. First, we show that given d ≥ 3 and n, there exists an explicit distribution of d-regular Θ(n)-vertex graphs where with high probability its samples have girth Ω(logd-1 n) and are ϵ-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√ d - 1 + ϵ (excluding the single trivial eigenvalue of d). Then, for every constant d ≥ 3 and ϵ> 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n)-vertices that is ϵ-near-Ramanujan and has girth Ω(√log n), based on the work of [26].

AB - We describe a new method to remove short cycles on regular graphs while maintaining spectral bounds (the nontrivial eigenvalues of the adjacency matrix), as long as the graphs have certain combinatorial properties. These combinatorial properties are related to the number and distance between short cycles and are known to happen with high probability in uniformly random regular graphs. Using this method we can show two results involving high girth spectral expander graphs. First, we show that given d ≥ 3 and n, there exists an explicit distribution of d-regular Θ(n)-vertex graphs where with high probability its samples have girth Ω(logd-1 n) and are ϵ-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√ d - 1 + ϵ (excluding the single trivial eigenvalue of d). Then, for every constant d ≥ 3 and ϵ> 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n)-vertices that is ϵ-near-Ramanujan and has girth Ω(√log n), based on the work of [26].

KW - High Girth Regular Graphs

KW - Ramanujan Graphs

UR - http://www.scopus.com/inward/record.url?scp=85115269010&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115269010&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2021.55

DO - 10.4230/LIPIcs.STACS.2021.55

M3 - Conference contribution

AN - SCOPUS:85115269010

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021

A2 - Blaser, Markus

A2 - Monmege, Benjamin

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021

Y2 - 16 March 2021 through 19 March 2021

ER -