Graphes expanseurs et crible dans les structures combinatoires

JOUVE, Florent; SERENI, Jean-Sébastien

doi:10.1017/S1446788717000234

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

JOUVE, Florent
Institut de Mathématiques de Bordeaux [IMB]

SERENI, Jean-Sébastien
Knowledge representation, reasonning [ORPAILLEUR]

Langue

Article de revue

Ce document a été publié dans

Journal of the Australian Mathematical Society. 2018, vol. 105, n° 1, p. 79--102

Cambridge University Press

Résumé en anglais

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.< Réduire

Mots clés en anglais

Groups

Random Walks

Graphs

Sieve

Métadonnées

Partager cette publication !

Licence d’utilisation du document