2012/05/03 by Florent Jouve, Jouve, Florent, Jean‐Sébastien Sereni +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Limits and Structures in Graph Theory #math.CO #math.GR
paper · pdf · doi:10.48550/arxiv.1205.0631
openalex publication_date 2012/05/03 · arxiv created 2017/01/06 · arxiv updated 2017/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove a general large sieve statement in the context of random walks on subgraphs of a given graph. This can be seen as a generalization of previously known results where one performs a random walk on a group enjoying a strong spectral gap property. In such a context the point is to exhibit a strong uniform expansion property for a suitable family of Cayley graphs on quotients. In our combinatorial approach, this is replaced by a result of Alon--Roichman about expanding properties of random Cayley graphs. Applying the general setting we show e.g., that with high probability (in a strong explicit sense) random coloured subsets of integers contain monochromatic (non-empty) subsets summing to zero, or that a random coloring of the edges of a complete graph contains a monochromatic triangle.