| Description |
Szemeredi's Regularity lemma is key result in extremal graph theory, that roughly states the following: For any ϵ>0, the vertex set of a graph G=(V,E) can be partitioned into k=C(ϵ) (i.e. a constant number of) parts V1,...,Vk of equal size, such that the induced subgraph on most pairs (Vi,Vj) is 'ϵ-close' to being a regular bipartite graph. Besides many combinatorial applications, it can also be used to get polynomial time approximation schemes for various problems on dense graphs. We will look at a proof of a weakened version of the Regularity Lemma, and discuss a couple of it's applications.
|