Description
The "entropy compression" is a term coined by Terrence Tao to describe algorithmic version of the Lovasz Local Lemma discovered recently by Robin Moser and Gabor Tardos. A basic idea is surprisingly simple and can be described as a random greedy procedure: color a given structure randomly, fixing eventual local errors by random recoloring (of just a small part of the structure where the error occurs). This looks like a naive idea since recoloring may cause occurrence of new errors in neighboring substructures. Do not worry and keep on fixing these new errors in the same way. The surprising result of Moser and Tardos asserts that, under certain conditions, this procedure gives a desired coloring with non-zero probability in expected polynomial time. In the talk I will present some spectacular applications of the entropy compression method in graph coloring and combinatorics on words.
Primary author
Dr
Jarek Grytczuk
(Jagiellonian University)
