2009/09/07 by Edward Lui, Doron Puder, Lui, Edward +1
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.0909.1231
Let G be a connected graph, and let λ1 and ρ denote the spectral radius of G and the universal cover of G, respectively. In \citeFri03, Friedman has shown that almost every n-lift of G has all of its new eigenvalues bounded by O(λ11/2ρ1/2). In \citeLP10, Linial and Puder have improved this bound to O(λ11/3ρ2/3). Friedman had conjectured that this bound can actually be improved to ρ+ on(1) (e.g., see \citeFri03,HLW06). In \citeLP10, 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 \citeLP10). In this paper, we make further progress towards proving this important conjecture by showing that ϕ(w) = 2 iff β(w) = 2 for every word w.