Ramsey properties of random graphs and folkman numbers

DOI10.7151/DMGT.1971zbMATH Open1366.05099arXiv1603.00517OpenAlexW3102934840MaRDI QIDQ2364094FDOQ2364094

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)

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.

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

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

zbMATH Keywords

random graphRamsey propertyFolkman number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Hypergraph containers
• Independent sets in hypergraphs
• Threshold Functions for Ramsey Properties
• Ramsey properties of random discrete structures
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• A short proof of the random Ramsey theorem

Cited In (10)

• A randomized version of Ramsey's theorem
• Title not available (Why is that?)
• 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
• Ramsey goodness of clique versus paths in random graphs
• Some recent results on Ramsey-type numbers
• 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)