Szemerédi's regularity lemma revisited TeX Export

@misc{citeulike:2424251, abstract = {Szemer\'edi's regularity lemma is a basic tool in graph theory, and also plays an important role in additive combinatorics, most notably in proving Szemer\'edi'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.}, archivePrefix = {arXiv}, author = {Tao, Terence}, citeulike-article-id = {2424251}, citeulike-linkout-0 = {http://arxiv.org/abs/math/0504472}, citeulike-linkout-1 = {http://arxiv.org/pdf/math/0504472}, comment = {Lemma 4.4 gives an inequality relating conditional expectation to conditional information that is similar to Pinsker's inequality. See also: Rudolf Ahlswede's "The final form of Tao's inequality relating conditional expectation and conditional mutual information" in which Tao's bound of 2 is reduced to (2 ln 2)^(1/2).}, day = {16}, eprint = {math/0504472}, keywords = {combinatorics, conditional\_expectation, graph, inequality, information, probability, theory}, month = {Nov}, posted-at = {2008-02-25 05:02:51}, priority = {3}, title = {Szemer\'edi's regularity lemma revisited}, url = {http://arxiv.org/abs/math/0504472}, year = {2005} }

TY - ELEC ID - citeulike:2424251 L3 - citeulike-article-id:2424251 N2 - Szemer\'edi's regularity lemma is a basic tool in graph theory, and also plays an important role in additive combinatorics, most notably in proving Szemer\'edi'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. TI - Szemer\'edi's regularity lemma revisited KW - combinatorics KW - conditional_expectation KW - graph KW - inequality KW - information KW - probability KW - theory N1 - Lemma 4.4 gives an inequality relating conditional expectation to conditional information that is similar to Pinsker's inequality. See also: Rudolf Ahlswede's "The final form of Tao’s inequality relating conditional expectation and conditional mutual information" in which Tao's bound of 2 is reduced to (2 ln 2)^(1/2). AU - Tao, Terence PY - 2005/Nov/16/ UR - http://arxiv.org/abs/math/0504472 ER -