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

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

2009-09-07

arxiv.org/abs/0909.1231v2

Mathematics

Combinatorics

24 pages

Scientific paper

Let $G$ be a connected graph, and let $\lambda_1$ and $\rho$ 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(\lambda_1^{1/2}\rho^{1/2})$. In \cite{LP10}, Linial and Puder have improved this bound to $O(\lambda_1^{1/3}\rho^{2/3})$. Friedman had conjectured that this bound can actually be improved to $\rho + o_n(1)$ (e.g., see \cite{Fri03,HLW06}). In \cite{LP10}, Linial and Puder have formulated two new categorizations of formal words, namely $\phi$ and $\beta$, which assign a non-negative integer or infinity to each word. They have shown that for every word $w$, $\phi(w) = 0$ iff $\beta(w) = 0$, and $\phi(w) = 1$ iff $\beta(w) = 1$. They have conjectured that $\phi(w) = \beta(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(\rho)$ on the new eigenvalues (see \cite{LP10}). In this paper, we make further progress towards proving this important conjecture by showing that $\phi(w) = 2$ iff $\beta(w) = 2$ for every word $w$.

Affiliated with

Also associated with

No associations

Rating

More on the phi = beta Conjecture and Eigenvalues of Random Graph Lifts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with More on the phi = beta Conjecture and Eigenvalues of Random Graph Lifts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and More on the phi = beta Conjecture and Eigenvalues of Random Graph Lifts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-295937