Signing a graph to have small magnitude eigenvalues

Importance: Medium ✭✭
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: mdevos
on: March 24th, 2013

\begin{conjecture} If $A$ is the adjacency matrix of a $d$-regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$) so that the resulting matrix has all eigenvalues of magnitude at most $2 \sqrt{d-1}$. \end{conjecture}

A graph $H$ is a $k$-\emph{lift} of a graph $G$ if there is a $k$-to-$1$ map $f : V(H) \rightarrow V(G)$ which is locally injective in the sense that the restriction of $f$ to the neighbourhood of every vertex is an injection. We can construct a random $k$-lift of $G$ with vertex set $V(G) \times \{1,\ldots,k\}$ by adding a (uniformly chosen) random matching between $\{v\} \times \{1,\ldots,k\}$ and $\{w\} \times \{1,\ldots,k\}$ whenever $vw \in E(G)$. If $H$ is a $k$-lift of $G$, then every eigenvalue of $G$ will also be an eigenvalue of $H$, but in addition $H$ will have $(k-1) |V(G)|$ new eigenvalues. There has been considerable interest and investigation into the behaviour of these new eigenvalues for a random $k$-lift, since it is expected that they should generally be small in magnitude. In particular, if $G$ is a Ramanujan graph (a $d$-regular graph for which all nontrivial eigenvalues are at most $2 \sqrt{d-1}$) it may be possible to construct a new Ramanujan graph by taking a suitable $k$-lift of $G$. A series of increasingly strong results have shown that a random $k$-lift of a $d$-regular Ramanujan graph will have all new eigenvalues at most $O(d^{3/4})$ (Friedman [F]), $O(d^{2/3})$ (Linial and Pruder [LP]) and $O(\sqrt{d} \log d)$ (Lubetzky, Sudakov, and Vu [LSV]).

An interesting paper of Bilu and Linial [BL] investigates 2-lifts of graphs. Let $G$ be a graph and let $H$ be a 2-lift of $G$ with vertex set $V(G) \times \{1,2\}$ as above. Every eigenvector of $G$ extends naturally to an eigenvector of $H$ which is constant on each fiber (set of the form $\{u\} \times \{1,2\}$). 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 $V(G) \times \{1\}$. Now we assign a signature $\pm 1$ to each edge of $G$ to form a signed graph $G^*$ by assigning each edge $uv \in E(G)$ for which $(u,1)(v,1) \in E(H)$ a sign of $1$ and every other edge of $G$ sign $-1$. It is straightforward to verify that the restriction of any new eigenvector of $H$ to $V(G) \times \{1\}$ will then be an eigenvector of $G^*$. Thus, the above conjecture is equivalent to the conjecture that every $d$-regular graph has a $2$-lift so that all new eigenvalues have magnitude at most $2 \sqrt{d-1}$. Furthermore, a positive solution to this conjecture for $d$-regular Ramanujan graphs would yield families of $d$-regular expanders.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

*[BL] Y. Bilu, N. Linial, Lifts, discrepancy and nearly optimal spectral gap, Combinatorica 26 (5) (2006) 495–519. \MRhref{MR2279667}

[F] J. Friedman, Relative expanders or weakly relatively Ramanujan graphs, Duke Math. J. 118 (1) (2003) 19–35. \MRhref{MR1978881}

[LP] N. Linial, D. Puder, Word maps and spectra of random graph lifts, Random Structures Algorithms 37 (1) (2010) 100–135. \MRhref{MR2674623}

[LSV] E. Lubetzky, B. Sudakov, V Vu, Spectra of lifted Ramanujan graphs. Adv. Math. 227 (2011), no. 4, 1612–1645. \MRhref{MR2799807}

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.