Paper detail

More on the phi = beta Conjecture and Eigenvalues of Random Graph Lifts

Let $G$ be a connected graph, and let $λ_1$ and $ρ$ denote the spectral radius of $G$ and the universal cover of $G$, respectively. In \cite{Fri03}, Friedman has shown that almost every $n$-lift of $G$ has all of its new eigenvalues bounded by $O(λ_1^{1/2}ρ^{1/2})$. In \cite{LP10}, Linial and Puder have improved this bound to $O(λ_1^{1/3}ρ^{2/3})$. Friedman had conjectured that this bound can actually be improved to $ρ+ o_n(1)$ (e.g., see \cite{Fri03,HLW06}). In \cite{LP10}, Linial and Puder have formulated two new categorizations of formal words, namely $ϕ$ and $β$, which assign a non-negative integer or infinity to each word. They have shown that for every word $w$, $ϕ(w) = 0$ iff $β(w) = 0$, and $ϕ(w) = 1$ iff $β(w) = 1$. They have conjectured that $ϕ(w) = β(w)$ for every word $w$, and have run extensive numerical simulations that strongly suggest that this conjecture is true. This conjecture, if proven true, gives us a very promising approach to proving a slightly weaker version of Friedman's conjecture, namely the bound $O(ρ)$ on the new eigenvalues (see \cite{LP10}). In this paper, we make further progress towards proving this important conjecture by showing that $ϕ(w) = 2$ iff $β(w) = 2$ for every word $w$.