Sieving in graphs and explicit bounds for non-typical elements - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Sieving in graphs and explicit bounds for non-typical elements

Résumé

We study properties of random graphs within families of graphs equipped with a group law. Using the group structure we perform a random walk on the family of graphs. If the generating system is a big enough random subset of graphs, a result of Alon--Roichman provides us with useful expansion properties from which we deduce quantitative estimates for the rarefaction of non-typical elements attained by the random walk. Applying the general setting we show, e.g., that with high probability (in a strong explicit sense) random graphs contain cycles of small length, or that a random colouring of the edges of a graph contains a monochromatic triangle. We also explain how our method gives results towards an effective infinite Ramsey Theorem.
Fichier principal
Vignette du fichier
JoSe14.pdf (193.14 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00693334 , version 1 (02-05-2012)
hal-00693334 , version 2 (16-05-2014)
hal-00693334 , version 3 (06-01-2017)

Identifiants

Citer

Florent Jouve, Jean-Sébastien Sereni. Sieving in graphs and explicit bounds for non-typical elements. 2014. ⟨hal-00693334v2⟩

Collections

LM-ORSAY
551 Consultations
280 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More