Signatures, lifts, and eigenvalues of graphs

DOI10.1007/978-3-030-44097-8_13zbMATH Open1473.05176arXiv1412.6841OpenAlexW3043880191MaRDI QIDQ5126345FDOQ5126345

Authors: Shiping Liu, Norbert Peyerimhoff, Alina Vdovina 

Publication date: 16 October 2020

Published in: Discrete and Continuous Models in the Theory of Networks (Search for Journal in Brave)

Abstract: We study the spectra of cyclic signatures of finite graphs and the corresponding cyclic lifts. Starting from a bipartite Ramanujan graph, we prove the existence of an infinite tower of $3$-cyclic lifts, each of which is again Ramanujan.

Full work available at URL: https://arxiv.org/abs/1412.6841

Recommendations

• Spectra of lifted Ramanujan graphs
• On the signed graphs with two distinct eigenvalues
• Ramanujan coverings of graphs
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• On the expansion of group-based lifts

zbMATH Keywords

expander graphscyclic groups3-cyclic lifts

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Signed and weighted graphs (05C22) Expander graphs (05C48)

Cites Work

• Signed graphs
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Theory of monomer-dimer systems
• On the notion of balance of a signed graph
• Random graph coverings. I: General theory and graph connectivity
• Expander graphs and their applications
• Lifts, discrepancy and nearly optimal spectral gap
• Title not available (Why is that?)
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Generating all graph coverings by permutation voltage assignments
• Expansion of random graphs: new proofs, new results
• Ramanujan graphs and the solution of the Kadison-Singer problem
• Matchings and walks in graphs
• Voltage graphs
• The topological theory of current graphs
• Title not available (Why is that?)
• Orientable embedding of Cayley graphs
• Relative expanders or weakly relatively Ramanujan graphs.
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• Branched coverings of graph imbeddings
• Discrete magnetic Laplacian
• Quotients of complete graphs: revisiting the Heawood map-coloring problem
• Title not available (Why is that?)
• Ramanujan coverings of graphs
• Shift lifts preserving Ramanujan property
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs

Cited In (4)

• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Spectra and eigenspaces of arbitrary lifts of graphs
• Title not available (Why is that?)
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians

This page was built for publication: Signatures, lifts, and eigenvalues of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5126345)