Expander graphs and sieving in combinatorial structures

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.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-00693334
Contributeur : Jean-Sébastien Sereni <>
Soumis le : vendredi 6 janvier 2017 - 12:08:59
Dernière modification le : mardi 18 décembre 2018 - 16:38:02
Document(s) archivé(s) le : vendredi 7 avril 2017 - 13:25:12

Fichiers

egscs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00693334, version 3
  • ARXIV : 1205.0631

Citation

Florent Jouve, Jean-Sébastien Sereni. Expander graphs and sieving in combinatorial structures. 2017. 〈hal-00693334v3〉

Partager

Métriques

Consultations de la notice

359

Téléchargements de fichiers

101