## How Big Does |

**William Gasarch**

January 9, 2004

12:30 pm

Bailey Hall 102

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

A| ≥n/3?What if |

A| ≥n/10?Roth proved that for any

c>0, for largen, ifA⊆ {1,...,n} and |A| ≥cnthenAhas 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.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Sat Mar 17 08:34:28 EDT 2018 |