An improved lower bound for Folkman's theorem

Abstract

Folkman's Theorem asserts that for each $k\in \mathbb{N}$, there exists a natural number $n=F(k)$ such that whenever the elements of $[n]$ are two-coloured, there exists a set $A\subset [n]$ of size $k$ with the property that all the sums of the form ${\sum }_{x\in B}x$, where $B$ is a nonempty subset of $A$, are contained in $[n]$ and have the same colour. In 1989, Erdős and Spencer showed that $F(k)\ge 2^{c{k}^2/\log k}$, where $c>0$ is an absolute constant; here, we improve this bound significantly by showing that $F(k)\ge 2^{2^{k-1}/k}$ for all $k\in \mathbb{N}$.

5 pages, Bulletin of the LMS