  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.
