Ramsey properties of random graphs and folkman numbers

DOI10.7151/DMGT.1971MaRDI QIDQ2364094zbMATH OpenOpenAlexFDO

Authors Vojtěch Rödl, Andrzej Ruciński, M. Schacht

Publication date 17 July 2017

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1603.00517

zbMATH Keywords

random graphRamsey propertyFolkman number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55)

Abstract: For two graphs, $G$ and $F$, and an integer $rge2$ we write $Gightarrow(F{)}_r$ if every $r$-coloring of the edges of $G$ results in a monochromatic copy of $F$. In 1995, the first two authors established a threshold edge probability for the Ramsey property $G(n,p)o(F{)}_r$, where $G(n,p)$ is a random graph obtained by including each edge of the complete graph on $n$ vertices, independently, with probability $p$. The original proof was based on the regularity lemma of Szemer'edi and this led to tower-type dependencies between the involved parameters. Here, for $r=2$, we provide a self-contained proof of a quantitative version of the Ramsey threshold theorem with only double exponential dependencies between the constants. As a corollary we obtain a double exponential upper bound on the 2-color Folkman numbers. By a different proof technique, a similar result was obtained independently by Conlon and Gowers.

Recommendations

• Threshold Functions for Ramsey Properties
• An exponential-type upper bound for Folkman numbers
• A randomized version of Ramsey's theorem
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
• Ramsey games near the critical threshold

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A short proof of the random Ramsey theorem
• Hypergraph containers
• Independent sets in hypergraphs
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• Ramsey properties of random discrete structures
• Threshold Functions for Ramsey Properties

Cited in

(10)

• A randomized version of Ramsey's theorem
• scientific article; zbMATH DE number 2196516 (Why is no real title available?)
• An efficient container lemma
• A short proof of the random Ramsey theorem
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
• Ramsey properties of random subgraphs of pseudo-random graphs
• Ramsey properties of random graphs
• Some recent results on Ramsey-type numbers
• Ramsey goodness of clique versus paths in random graphs
• An exponential-type upper bound for Folkman numbers

This page was built for publication: Ramsey properties of random graphs and folkman numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364094)