Long arithmetic progressions in subsets and Erdos-Folkman conjecture

Van Vu, U.C. San Diego

Thursday , March 13, 4:30 PM, HILL 705 (NOTE NONSTANDARD DAY AND PLACE)

Abstract.

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.


Back to Discrete Math/Theory of Computing seminar