Word maps and spectra of random graph lifts

DOI10.1002/rsa.20304zbMath1242.60011arXiv0806.1993OpenAlexW2950282402MaRDI QIDQ3057070

Doron Puder, Nathan Linial

Publication date: 24 November 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0806.1993

zbMATH Keywords

random graphsspectrum of graphsgraph liftsword mapAlon's conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Algebraic theory of languages and automata (68Q70)

Related Items

Tight products and graph expansion, Orthogonal labeling for some different infinite graph classes, Functional limit theorems for random regular graphs, Some orbits of free words that are determined by measures on finite groups, Unseparated pairs and fixed points in random permutations, Cycles and eigenvalues of sequentially growing random regular graphs, Spectrum of random d‐regular graphs up to the edge, Matrix group integrals, surfaces, and mapping class groups. II: \( \mathrm{O}\left( n\right)\) and \(\mathrm{Sp}\left( n\right) \), Word measures on symmetric groups, Primitive words, free factors and measure preservation., Formal Zeta function expansions and the frequency of Ramanujan graphs, Expansion of random graphs: new proofs, new results, Spectra of lifted Ramanujan graphs, Surface words are determined by word measures on groups, The random transposition dynamics on random regular graphs and the Gaussian free field, The spectral norm of random lifts of matrices, On the Expansion of Group-Based Lifts, Measure preserving words are primitive, Eigenvalues of random lifts and polynomials of random permutation matrices, On the Expansion of Group-Based Lifts, Interlacing families. I: Bipartite Ramanujan graphs of all degrees, Random unitary representations of surface groups. I: Asymptotic expansions

Cites Work

• Unnamed Item
• Unnamed Item
• Characteristic vectors of bordered matrices with infinite dimensions
• Lifts, discrepancy and nearly optimal spectral gap
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• On the second eigenvalue of a graph
• Relative expanders or weakly relatively Ramanujan graphs.
• Random lifts of graphs: perfect matchings
• Word maps and Waring type problems
• Some Probabilistic Aspects of Set Partitions
• On the probability of satisfying a word in a group
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• On the number of cycles of given length of a free word in several random permutations
• Random lifts of graphs: Independence and chromatic number
• Random Lifts of Graphs: Edge Expansion