Up: Research Seminars for 2004
Top: Math Department Research Seminars

How Big Does A⊆ {1,...,n} Have To Be Before You Know It Has an Arithmetic Progression of Length Three?

by

William Gasarch

January 9, 2004
12:30 pm
Bailey Hall 102


Abstract:

It is easy to prove that if A⊆ {1,...,n} and |A| ≥ 2n/3 + 1 then A has an arithmetic progression of length 3.

What if |A| ≥ n/3?

What if |A| ≥ n/10?

Roth proved that for any c>0, for large n, if A⊆ {1,...,n} and |A| ≥ cn then A has an arithmetic progression of length 3. His proof used complex analysis.

We will present a purely combinatorial proof, essentially due to Szemeredi. Our treatment is based on the one in Ramsey Theory, by Graham, Rothschild, and Spencer.

(William Gasarch will also give a talk in the Computer Science Department. Check out http://cs.union.edu/seminar/gasarch.html for details.)


For additional information, send e-mail to math@union.edu or call (518) 388-6246.
Up: Research Seminars for 2004
Top: Math Department Research Seminars

[HOME]
Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Sun Sep 23 23:52:16 EDT 2018