The system will be going down for regular maintenance. Please save your work and logout.
Graphes expanseurs et crible dans les structures combinatoires
Language
en
Article de revue
This item was published in
Journal of the Australian Mathematical Society. 2018, vol. 105, n° 1, p. 79--102
Cambridge University Press
English Abstract
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 ...Read more >
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.Read less <
English Keywords
Groups
Random Walks
Graphs
Sieve
Origin
Hal imported