DIMACS Discrete Math/Theory of Computing Seminar

Title: Long arithmetic progressions in subsets and Erdos-Folkman conjecture

Speaker: Van Vu, U.C. San Diego

Date: Thursday , March 13, 4:30 PM

Location: Hill Center, room 705, (Note room change) Rutgers University, Busch Campus, Piscataway, NJ


Let A be a (finite or infinite) set of positive integers, S(A) denotes the collection of finite subset sums of A. For instance, if A={1,2, 9}, then S(A)={1,2,3, 9, 10,11, 12}. Recently, we proved

Theorem 1: There is a constant c such that for any set A containing cn^{1/2} different integers between 1 and n, S(A) contains an arithmetic progression of length n.

Using this theorem, we confirmed a long standing conjecture of Erdos and Folkman, posed in the sixties.

Conjecture 2: There is a constant c such that for any increasing sequence A of density cn^{1/2}, S(A) contains an infinite arithmetic progression.

The proof of Theorem 1 introduces a new method for proving the existence of long arithmetic progressions. In this talk we shall discuss some essential points of this proof.

Joint work with E. Szemeredi.