Szemerédi's Regularity Lemma via Martingales

Pandelis Dodos, Vassilis Kanellopoulos, Thodoris Karageorgos

Type: Article

Publication Date: 2016-07-22

Citations: 4

DOI: https://doi.org/10.37236/5585

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.

Locations

The Electronic Journal of Combinatorics - View - PDF
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Szemerédi's regularity lemma via martingales	2014	Pandelis Dodos Vassilis Kanellopoulos Thodoris Karageorgos
+	Szemer\'edi's regularity lemma via martingales	2014	Pandelis Dodos Vassilis Kanellopoulos Thodoris Karageorgos
+	Szemerédi’s Regularity Lemma and Quasi-randomness	2003	Yoshiharu Kohayakawa V. Rödl
+	Szemerédi's regularity lemma revisited	2005	Terence Tao
+	Szemeredi''s Regularity Lemma and its applications in graph theory	1995	János Komlós Miklós Simonovits
+	Szemer'edi's regularity lemma revisited	2006	Terence Tao
+	The Szemerédi Regularity Lemma	2017	Emma Everett
+	The Regularity Lemma and Its Applications in Graph Theory	2002	János Komlós Ali Shokoufandeh Miklós Simonovits Endre Szemerédi
+	Szémeredi's regularity lemma and its applications in combinatorics	2006	Jonas Hägglund
+	Szemerédi's partition and quasirandomness	1991	Miklós Simonovits Vera T. Sós
+	Randomness and regularity	2007	Tomasz Łuczak
+	Random Discrete Structures	1996	David Aldous Robin Pemantle
+	The sparse regularity lemma and its applications	2005	Stefanie Gerke Angelika Steger
+ PDF Chat	A tight lower bound for Szemerédi’s regularity lemma	2017	Jacob Fox László Lovász
+ PDF Chat	MARTINGALES OF RANDOM DISTRIBUTIONS	1981	Itaru Mitoma
+	Hypergraph regularity and quasi-randomness	2009	Brendan Nagle Annika Poerschket Vojtěch Rödl Mathias Schacht
+ PDF Chat	Random differences in Szemerédi’s theorem and related results	2016	Nikos Frantzikinakis Emmanuel Lesigne Μáté Wierdl
+	Szemerédi’s Regularity Lemma for Sparse Graphs	1997	Yoshiharu Kohayakawa
+	Randomness and regularity	2006	Tomasz Łuczak
+	Hypergraphs, Quasi-randomness, and Conditions for Regularity	2002	Yoshiharu Kohayakawa Vojtěch Rödl Jozef Skokan

Works That Cite This (4)

Action	Title	Year	Authors
+ PDF Chat	Concentration estimates for functions of finite high‐dimensional random arrays	2023	Pandelis Dodos Konstantinos Tyros Petros Valettas
+ PDF Chat	An Algorithmic Regularity Lemma for $L_p$ Regular Sparse Matrices	2017	Silouanos Brazitikos Thodoris Karageorgos
+	An algorithmic regularity lemma for $L_p$ regular sparse matrices	2016	Thodoris Karageorgos Silouanos Brazitikos
+	$L_p$ regular sparse hypergraphs	2015	Pandelis Dodos Vassilis Kanellopoulos Thodoris Karageorgos

Works Cited by This (22)

Action	Title	Year	Authors
+	An Abstract Regularity Lemma	2007	Béla Bollobás Vladimir Nikiforov
+	Sharp uniform convexity and smoothness inequalities for trace norms	1994	Keith Ball Eric A. Carlen Élliott H. Lieb
+	Szemer'edi's regularity lemma revisited	2006	Terence Tao
+	Primitive recursive bounds for van der Waerden numbers	1988	Saharon Shelah
+	A variant of the hypergraph removal lemma	2006	Terence Tao
+ PDF Chat	Szemerédi’s Lemma for the Analyst	2007	László Lovász Balázs Szegedy
+	Quick Approximation to Matrices and Applications	1999	Alan Frieze Ravi Kannan
+ PDF Chat	A Simple Proof of the Density Hales–Jewett Theorem	2013	Pandelis Dodos Vassilis Kanellopoulos Konstantinos Tyros
+ PDF Chat	Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing	2008	Christian Borgs Jennifer Chayes L. Lovász Vera T. Sós K. Vesztergombi
+	REGULAR PARTITIONS OF GRAPHS	1975	Endre Szemerédi