Szemerédi's Regularity Lemma via Martingales

  • Pandelis Dodos
  • Vassilis Kanellopoulos
  • Thodoris Karageorgos
DOI: https://doi.org/10.37236/5585
Keywords: Szemerédi's regularity lemma, Semiring, Norm, Martingale difference sequences

Abstract

We prove a variant of the abstract probabilistic version of Szemerédi's regularity lemma, due to Tao, which applies to a number of structures (including graphs, hypergraphs, hypercubes, graphons, and many more) and works for random variables in $L_p$ for any $p>1$. Our approach is based on martingale difference sequences.
Published
2016-07-22
How to Cite
Dodos, P., Kanellopoulos, V., & Karageorgos, T. (2016). Szemerédi’s Regularity Lemma via Martingales. The Electronic Journal of Combinatorics, 23(3), P3.11. https://doi.org/10.37236/5585
Issue
Volume 23, Issue 3 (2016)
Article Number
P3.11