Hanno Lefmann

(Department of Computer Science, Chemnitz University of Technology)

The Regularity Lemma and Some Of Its Applications

Date Friday, July 27, 2018

The regularity lemma proved by Szemerédi turned out to be a fruitful tool in mathematics, for example in combinatorics and graph theory, and theoretical computer science. It asserts that for every large enough graph \(G=(V,E)\) its vertex set \(V\) can be partitioned into a constant number of classes \(V_1, \ldots , V_k\) such that the set of edges between two different classes (for most pairs of classes) behaves 'pseudorandomly'. For example, this result was successfully used by Green and Tao to show that the set of primes contain arbitrary long finite arithmetic progressions.

In this talk we will give some non-algorithmic and algorithmic applications of this lemma. These include edge coloring problems in graphs related to the Turan problem, polynomial time approximation algorithms and property testing.