Let w be a formal word with k distinct letters and let X be a finite group. Associated with w is a map from X^k into X which is obtained by substituting, for each formal letter in w, a random member in X. We introduce some new ideas to the study of formal words which yield, in turn, several interesting insights about words maps over X=S_n. These are then used to study the spectrum in random lifts of graphs. Joel Friedman had shown that if G is a (finite connected) graph of spectral radius lambda and if T, the universal cover of G has spectral radius rho, then in almost every lift of G, all ``new" eigenvalues are at most sqrt(lambda rho) + o(1). He also suggested that the same might hold with the better (in fact optimal) bound rho + o(1). Our new methods allow us to improve his bound to O(lambda^{1/3} rho^{2/3}). Several intriguing open problems and conjectures suggest themselves which, if true, would yield the nearly optimal bound of O(rho). As an aside, our methods yield also a new simplified proof for a theorem of Nica on the limit distribution of word maps in S_n.
(Joint work with Doron Puder)
Copyright. All Rights Reserved.