## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, June 27, 2017, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: József Balogh (University of Illinois)

## An improved lower bound for Folkman's theorem

Folkman's Theorem asserts that for each k in N, there exists a natural number n=F(k) such that whenever the elements of [n] are two-coloured, there exists a subset A of [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\H{o}s and Spencer showed that F(k) >= 2^{ck^2/log k}, where c>0 is an absolute constant; here, we improve this bound significantly by showing that F(k)>= 2^{2^{k-1}/k} for all k in N. Joint with Sean Eberhard, Bhargav Narayanan, Andrew Treglown, Adam Zsolt Wagner.

Information for students and suggested topics for student talks