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+.

A dynamic coloring of a graph G is a proper coloring of the vertex set V(G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. A dynamic k-coloring of a graph is a dynamic coloring with k colors. Note that the gap χ_d(G) – χ(G) could be arbitrarily large for some graphs. An interesting problem is to study which graphs have small values of χ_d(G) – χ(G).
One of the most interesting problems about dynamic chromatic numbers is to find upper bounds of χ_d(G)$ for planar graphs G. Lin and Zhao (2010) and Fan, Lai, and Chen (recently) showed that for every planar graph G, we have χ_d(G)≤5, and it was conjectured that χ_d(G)≤4 if G is a planar graph other than C₅. (Note that χ_d(C₅)=5.)
As a partial answer, Meng, Miao, Su, and Li (2006) showed that the dynamic chromatic number of Pseudo-Halin graphs, which are planar graphs, are at most 4, and Kim and Park (2011) showed that χ_d(G)≤4 if G is a planar graph with girth at least 7.
In this talk we settle the above conjecture that χ_d≤4 if G is a planar graph other than C₅. We also study the corresponding list coloring called a list dynamic coloring.
This is joint work with Seog-Jin Kim and Won-Jin Park.

A set A of integers is a Sidon set if all the sums a₁+a₂, with a₁≤a₂ and a₁, a₂∈A, are distinct. In the 1940s, Chowla, Erdős and Turán showed that the maximum possible size of a Sidon set contained in [n]={0,1,…,n-1} is √n (1+o(1)). We study Sidon sets contained in sparse random sets of integers, replacing the ‘dense environment’ [n] by a sparse, random subset R of [n].

Let R=[n]_m be a uniformly chosen, random m-element subset of [n]. Let F([n]_m)=max {|S| : S⊆[n]_m Sidon}. An abridged version of our results states as follows. Fix a constant 0≤a≤1 and suppose m=m(n)=(1+o(1))n^a. Then there is a constant b=b(a) for which F([n]_m)=n^b+o(1) almost surely. The function b=b(a) is a continuous, piecewise linear function of a, not differentiable at two points: a=1/3 and a=2/3; between those two points, the function b=b(a) is constant. This is joint work with Yoshiharu Kohayakawa and Vojtech Rödl.