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.
Origine : Fichiers produits par l'(les) auteur(s)