Szemerédi's regularity lemma revisited
Abstract
Description
Szemerédi's regularity lemma is a basic tool in graph theory, and also plays an important role in additive combinatorics, most notably in proving Szemerédi's theorem on arithmetic progressions . In this note we revisit this lemma from the perspective of probability theory and information theory instead of graph theory, and observe a variant of this lemma which introduces a new parameter $F$. This stronger version of the regularity lemma was iterated in a recent paper of the author to reprove the analogous regularity lemma for hypergraphs.
21 pages, to appear, Contributions to Discrete Mathematics. This is the final version, incorporating the referee's suggestions
21 pages, to appear, Contributions to Discrete Mathematics. This is the final version, incorporating the referee's suggestions