An exponential-type upper bound for Folkman numbers

DOI10.1007/S00493-015-3298-1zbMATH Open1413.05371arXiv1603.00521OpenAlexW3103996987WikidataQ115606572 ScholiaQ115606572MaRDI QIDQ681604FDOQ681604

Authors: Vojtěch Rödl, Andrzej Ruciński, Mathias Schachtz 

Publication date: 12 February 2018

Published in: Combinatorica (Search for Journal in Brave)

Abstract: For given integers $k$ and $r$, the Folkman number $f(k;r)$ is the smallest number of vertices in a graph $G$ which contains no clique on $k+1$ vertices, yet for every partition of its edges into $r$ parts, some part contains a clique of order $k$. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for $r=2$ and by Nev{s}etv{r}il and R"odl (1976) for arbitrary $r$, but these proofs led to very weak upper bounds on $f(k;r)$. Recently, Conlon and Gowers and independently the authors obtained a doubly exponential bound on $f(k;2)$. Here, we establish a further improvement by showing an upper bound on $f(k;r)$ which is exponential in a polynomial function of $k$ and $r$. This is comparable to the known lower bound $2^{Omega(rk)}$. Our proof relies on a recent result of Saxton and Thomason (2015) (or, alternatively, on a recent result of Balogh, Morris, and Samotij (2015)) from which we deduce a quantitative version of Ramsey's theorem in random graphs.

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

Recommendations

• A note on upper bounds for some generalized Folkman numbers
• On generalized Folkman numbers
• Bounds on some edge Folkman numbers
• Bounds on the exponential domination number
• New upper bound for a class of vertex Folkman numbers
• A new exponential upper bound for the Erd\H{o}s-Ginzburg-Ziv constant
• Upper and lower bounds in exponential Tauberian theorems
• Bounds for some generalized vertex Folkman numbers
• Exponential bounds for the Erdős-Ginzburg-Ziv constant
• Bounds for certain exponential sums

zbMATH Keywords

Folkman numbers

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Ramsey theory (05D10)

Cites Work

• Combinatorial theorems in sparse random sets
• Hypergraph containers
• Independent sets in hypergraphs
• The Ramsey property for graphs with forbidden complete subgraphs
• Threshold Functions for Ramsey Properties
• Introduction to Random Graphs
• Ramsey properties of random hypergraphs
• Ramsey properties of random discrete structures
• Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
• On the Folkman Numberf(2, 3, 4)
• Computation of the Folkman numberFe(3, 3; 5)
• On edgewise 2-colored graphs with monochromatic triangles and containing no complete hexagon
• Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring
• An almost quadratic bound on vertex Folkman numbers
• Some remarks on vertex Folkman numbers for hypergraphs
• Ramsey properties of random graphs and folkman numbers
• Title not available (Why is that?)
• Remarks on 15-vertex (3,3)-Ramsey graphs not containing K_5
• Ein kombinatorischer Satz mit Anwendung auf ein logisches Entscheidungsproblem
• Title not available (Why is that?)
• A short proof of the random Ramsey theorem

Cited In (9)

• An improved lower bound for Folkman's theorem
• On the number of points in general position in the plane
• An efficient container lemma
• A note on upper bounds for some generalized Folkman numbers
• Ramsey-type numbers involving graphs and hypergraphs with large girth
• Ramsey properties of random graphs and folkman numbers
• A note on induced Ramsey numbers
• A simple proof for the exponential upper bound for some tenacious patterns
• Symmetric and asymmetric Ramsey properties in random hypergraphs

This page was built for publication: An exponential-type upper bound for Folkman numbers

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