Signing a graph to have small magnitude eigenvalues
A graph is a -lift of a graph if there is a -to- map which is locally injective in the sense that the restriction of to the neighbourhood of every vertex is an injection. We can construct a random -lift of with vertex set by adding a (uniformly chosen) random matching between and whenever . If is a -lift of , then every eigenvalue of will also be an eigenvalue of , but in addition will have new eigenvalues. There has been considerable interest and investigation into the behaviour of these new eigenvalues for a random -lift, since it is expected that they should generally be small in magnitude. In particular, if is a Ramanujan graph (a -regular graph for which all nontrivial eigenvalues are at most ) it may be possible to construct a new Ramanujan graph by taking a suitable -lift of . A series of increasingly strong results have shown that a random -lift of a -regular Ramanujan graph will have all new eigenvalues at most (Friedman [F]), (Linial and Pruder [LP]) and (Lubetzky, Sudakov, and Vu [LSV]).
An interesting paper of Bilu and Linial [BL] investigates 2-lifts of graphs. Let be a graph and let be a 2-lift of with vertex set as above. Every eigenvector of extends naturally to an eigenvector of which is constant on each fiber (set of the form ). Thus, we may assume that all of the new eigenvalues are associated with eigenvectors which sum to zero on each fiber. So, each of these new eigenvectors is completely determined by its behaviour on . Now we assign a signature to each edge of to form a signed graph by assigning each edge for which a sign of and every other edge of sign . It is straightforward to verify that the restriction of any new eigenvector of to will then be an eigenvector of . Thus, the above conjecture is equivalent to the conjecture that every -regular graph has a -lift so that all new eigenvalues have magnitude at most . Furthermore, a positive solution to this conjecture for -regular Ramanujan graphs would yield families of -regular expanders.
Bibliography
*[BL] Y. Bilu, N. Linial, Lifts, discrepancy and nearly optimal spectral gap, Combinatorica 26 (5) (2006) 495–519. MathSciNet
[F] J. Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (1) (2003) 19–35. MathSciNet
[LP] N. Linial, D. Puder, Word maps and spectra of random graph lifts, Random Structures Algorithms 37 (1) (2010) 100–135. MathSciNet
[LSV] E. Lubetzky, B. Sudakov, V Vu, Spectra of lifted Ramanujan graphs. Adv. Math. 227 (2011), no. 4, 1612–1645. MathSciNet
* indicates original appearance(s) of problem.