Szemeredi's Regularity Lemma Revisited
| COMPUTER SCIENCE/DISCRETE MATH, I | |
| Topic: | Szemeredi's Regularity Lemma Revisited |
| Speaker: | Terry Tao |
| Affiliation: | University of California, Los Angeles |
| Date: | Monday, October 3 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
Szemeredi's regularity lemma asserts, roughly speaking, that any large dense graph can be approximated to any specified accuracy by a much simpler "finite complexity" object; it has had many applications in graph theory, combinatorial number theory, and property testing. Here we revisit the lemma from an information-theoretic perspective, and discuss a recent strengthening of the lemma in which the approximation becomes dramatically improved after adding or deleting a small number of edges to the graph. Using this stronger version one obtains a corresponding lemma for hypergraphs, which has a number of deep consequences which we will discuss.