### Dependent Random Choice

- Series
- ACO Seminar
- Time
- Friday, October 22, 2010 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Jacob Fox – Mathematics, MIT

We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this talk, which is based on a survey with Benny Sudakov, we discuss some of these applications.