Skip to Main content Skip to Navigation
Journal articles

Expander graphs and sieving in combinatorial structures

Florent Jouve 1 Jean-Sébastien Sereni 2
2 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
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 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.
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-00693334
Contributor : Jean-Sébastien Sereni <>
Submitted on : Friday, January 6, 2017 - 12:08:59 PM
Last modification on : Tuesday, April 14, 2020 - 3:12:55 PM
Document(s) archivé(s) le : Friday, April 7, 2017 - 1:25:12 PM

Files

egscs.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Florent Jouve, Jean-Sébastien Sereni. Expander graphs and sieving in combinatorial structures. Journal of the Australian Mathematical Society, Cambridge University Press, 2018, 105 (1), pp.79--102. ⟨10.1017/S1446788717000234⟩. ⟨hal-00693334v3⟩

Share

Metrics

Record views

485

Files downloads

349