Szemerédi's regularity lemma revisited

Simple item page
dc.creatorTao, Terence
dc.date2005-04-22
dc.date2005-11-16
dc.date.accessioned2026-07-07T06:39:50Z
dc.date.available2026-07-07T06:39:50Z
dc.descriptionSzemeré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.
dc.description21 pages, to appear, Contributions to Discrete Mathematics. This is the final version, incorporating the referee's suggestions
dc.identifierhttps://arxiv.org/abs/math/0504472
dc.identifierhttp://arxiv.org/abs/math/0504472
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/101224
dc.subjectCombinatorics
dc.subject05C75
dc.titleSzemerédi's regularity lemma revisited
dc.typetext

Files

Collections

arXiv