Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Sieving in graphs and explicit bounds for non-typical elements

Abstract : 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.
Complete list of metadatas
Contributor : Jean-Sébastien Sereni <>
Submitted on : Friday, May 16, 2014 - 9:46:44 AM
Last modification on : Monday, December 23, 2019 - 3:50:11 PM
Document(s) archivé(s) le : Saturday, August 16, 2014 - 11:11:29 AM


Files produced by the author(s)


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



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



Record views


Files downloads