Ramanujan coverings of graphs

DOI10.1145/2897518.2897574zbMath1376.05096OpenAlexW2962849104MaRDI QIDQ5361859

William F. Sawin, Doron Puder, Chris Hall

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897574

zbMATH Keywords

matching polynomialgraph coveringsexpander graphsgraph liftsRamanujan graphsinterlacing polynomials

Mathematics Subject Classification ID

Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Shift lifts preserving Ramanujan property, Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes, On the Expansion of Group-Based Lifts, On the Expansion of Group-Based Lifts