Szemerédi regularity lemma

From Wikipedia, the free encyclopedia

In mathematics, Szemerédi's regularity lemma states that for every ε > 0 and every positive integer t there is an integer

T = T(ε,t)

such that every graph with n > T vertices has an ε-regular partition into k + 1 classes, .

This lemma was introduced by Szemerédi in 1975 in order to prove what is now known as Szemerédi's theorem. It has since proven to have many applications in graph theory and computer science.