License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.55
URN: urn:nbn:de:0030-drops-137000
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13700/
Go to the corresponding LIPIcs Volume Portal

Paredes, Pedro

Spectrum Preserving Short Cycle Removal on Regular Graphs

pdf-format:
LIPIcs-STACS-2021-55.pdf (0.8 MB)

Abstract

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 Ω(log_{d-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 [Mohanty et al., 2020].

BibTeX - Entry

@InProceedings{paredes:LIPIcs.STACS.2021.55,
  author =	{Paredes, Pedro},
  title =	{{Spectrum Preserving Short Cycle Removal on Regular Graphs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{55:1--55:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13700},
  URN =		{urn:nbn:de:0030-drops-137000},
  doi =		{10.4230/LIPIcs.STACS.2021.55},
  annote =	{Keywords: Ramanujan Graphs, High Girth Regular Graphs}
}

Keywords: Ramanujan Graphs, High Girth Regular Graphs
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI