Back to Search
Start Over
EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES.
- Source :
-
Journal of the Australian Mathematical Society . Aug2018, Vol. 105 Issue 1, p79-102. 24p. - Publication Year :
- 2018
-
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 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, for instance, that with high probability (in a strong explicit sense) random coloured subsets of integers contain monochromatic (nonempty) subsets summing to $0$ , and that a random colouring of the edges of a complete graph contains a monochromatic triangle. [ABSTRACT FROM AUTHOR]
- Subjects :
- *ALGEBRA
*MATHEMATICS
*GRAPHIC methods
*ALGORITHMS
*GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 14467887
- Volume :
- 105
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of the Australian Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 130476656
- Full Text :
- https://doi.org/10.1017/S1446788717000234