KAIST Discrete Math Seminar

In this talk we deal with extremal results on combinatorial number theory. A typical problem is as follows. We fix a family of linear equations (for example, a+b=2c or a+b=c+d). Then we want to estimate the maximum size of subsets with no solution of the given equations in {1,2,…,n} or a random subset of {1,2,…,n} of size m < n. We consider two important examples:

(1) Sets which contain no arithmetic progression of a fixed size

(2) Sidon sets (without solutions of a+b=c+d)

The first example is about the results of Roth in 1953 and Szemeredi in 1975, and the recent results by Schacht in 2009+, and Conlon-Gowers in 2010+.

Next, the second example is about the results by Erdős, Turán, Chowla, Singer in 1940s and the results by Kohayakawa, Lee, Rödl, and Samotij in 2012+.