PUB - Publikationen an der Universität Bielefeld

Recently Terence Tao approached Szemeredi's Regularity Lemma from the perspectives of Probability Theory and Information Theory instead of Graph Theory and found a stronger variant of this lemma, which involves a new parameter. To pass from an entropy formulation to an expectation formulation he found the following: Let Y, and X, X' be discrete random variables taking values in Y and X, respectively, where Y subset of [-1, 1], and with X' = f(X) for a (deterministic) function f. Then we have E(vertical bar E(Y vertical bar X') - E(Y vertical bar X)vertical bar) <= 2I(X Lambda Y vertical bar X')1/2. We show that the constant 2 can be improved to (2ln2)1/2 and that this is the best possible constant.