Words Maps and Spectra of Random Graph Lifts

Nati Linial, Doron Puder

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 permutat…