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. The group structure enables one to 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 well suited to give 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 coloring of the edges of a graph contains a monochromatic triangle.
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-00693334
Contributor : Jean-Sébastien Sereni <>
Submitted on : Wednesday, May 2, 2012 - 2:33:57 PM
Last modification on : Thursday, March 26, 2020 - 9:17:48 PM
Document(s) archivé(s) le : Friday, August 3, 2012 - 2:43:53 AM

Files

jose12.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

80

Files downloads

48