Words Maps and Spectra of Random Graph Lifts

Details Words Maps and Spectra of Random Graph Lifts Words Maps and Spectra of Random Graph Lifts

2008-06-12

arxiv.org/abs/0806.1993v3

Random Structures and Algorithms, 2010(37) 100--135

Mathematics

Combinatorics

46 pages, 10 figures. For associated pdf file, see http://www.cs.huji.ac.il/~nati/PAPERS/puder.pdf . Accepted for publication

Scientific paper

10.1002/rsa.20304

We begin with a new analysis of formal words. Let w be a formal word in letters g_1,...,g_k. The word map associated with w maps the permutations s_1,...,s_k in S_n to the permutation obtained by replacing for each i, every occurrence of g_i in w by s_i. We investigate the random variable X_w^n that counts the fixed points in this permutation when the s_i are selected uniformly at random. A major ingredient of our work is a new categorization of words which considerably extends the dichotomy of primitive vs. imprimitive words. We establish some results and make a few conjectures about the relation between the expectation E(X_w^n) and this new categorization. This analysis contributes deeply to our study of the spectra of random lifts of graphs. Let G be a connected graph, and let the infinite tree T be its universal cover space. If L and R are the spectral radii of G and T respectively, then, as shown by J. Friedman, for almost every n-lift H of G, all "new" eigenvalues of H are < O(L^(1/2)R^(1/2)). We improve this upper bound to O(L^(1/3)R^(2/3)), and our aforementioned conjectures suggest a possible approach to proving an upper bound of O(R). This is a generalization of the problem of bounding the second eigenvalue in a random 2d-regular graph. As an aside, we obtain a new conceptual and relatively simple proof of a theorem of A. Nica, which determines, for every fixed w, the limit distribution (as n \to \infty) of X_w^n. A surprising aspect of this theorem is that the answer depends only on the largest integer d so that w=u^d for some word u.

Affiliated with

Also associated with

No associations

Rating

Words Maps and Spectra 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 Words Maps and Spectra of Random Graph Lifts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Words Maps and Spectra of Random Graph Lifts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-690124