2012/08/27 by Amir Yehudayoff · 1 citation
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #graph theory and CDMA systems
paper · doi:10.1145/2421096.2421115
openalex publication_date 2012/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
This text is meant to be an introduction to a recent strategy introduced by Bourgain and Gamburd (following a work of Helfgott) for proving graph-expansion. The strategy is designed for graphs H that are defined using some underlying group G. The strategy consists of three steps, which, in Sarnak's terminology, correspond to the three steps of a chess game: opening, middle-game and endgame. In the opening, the objective is to prove that the girth of H is logarithmic. In the middle-game, the goal is to prove a productgrowth theorem for subsets of G. The endgame consists of establishing a "mixing property" for G. There are two methods for proving a mixing property: using pairwise independence and using basic representation theory.