Regular Partitions of Hypergraphs: Regularity Lemmas

Vojtěch Rödl, Mathias Schacht

Type: Article

Publication Date: 2007-07-31

Citations: 123

DOI: https://doi.org/10.1017/s0963548307008553

Abstract

Szemerédi's regularity lemma for graphs has proved to be a powerful tool with many subsequent applications. The objective of this paper is to extend the techniques developed by Nagle, Skokan, and the authors and obtain a stronger and more ‘user-friendly’ regularity lemma for hypergraphs.

Locations

edoc Publication server (Humboldt University of Berlin) - View - PDF
Combinatorics Probability Computing - View

Similar Works

Action	Title	Year	Authors
+	Regular Partitions of Hypergraphs	2007	RödlVojtěch SchachtMathias
+ PDF Chat	Regular Partitions of Hypergraphs: Counting Lemmas	2007	Vojtěch Rödl Mathias Schacht
+	Regularity Lemmas for Graphs	2010	Vojtěch Rödl Mathias Schacht
+	A Tight Bound for Hypergraph Regularity II	2018	Guy Moshkovitz A. Shapira
+	A Tight Bound for Hypergraph Regularity II	2018	Guy Moshkovitz A. Shapira
+ PDF Chat	A Tight Bound for Hyperaph Regularity	2019	Guy Moshkovitz A. Shapira
+	A Tight Bound for Hypergraph Regularity I	2018	Guy Moshkovitz A. Shapira
+	A Tight Bound for Hyperaph Regularity	2019	Guy Moshkovitz A. Shapira
+	Regularity lemmas for hypergraphs and quasi‐randomness	1991	Fan Chung
+	Extremal Hypergraph Theory and Algorithmic Regularity Lemma for Sparse Graphs	2010	Rerum Naturalium Mathematisch-Naturwissenschaftlichen Fakultät
+	The Regularity Lemma and Its Applications in Graph Theory	2002	János Komlós Ali Shokoufandeh Miklós Simonovits Endre Szemerédi
+	Equivalent regular partitions of three‐uniform hypergraphs	2024	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	Regular partitions of gentle graphs	2020	Yiting Jiang Jaroslav Nešetřil Patrice Ossona de Mendez Sebastian Siebertz
+ PDF Chat	Regular partitions of gentle graphs	2020	Yiting Jiang Jaroslav Nešetřil Patrice Ossona de Mendez Sebastian Siebertz
+	Regularity inheritance in hypergraphs	2019	Peter Allen Ewan Davies Jozef Skokan
+	Regularity inheritance in hypergraphs	2019	Peter J. Allen Ewan Davies Jozef Skokan
+	An Algorithmic Hypergraph Regularity Lemma	2015	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	An algorithmic hypergraph regularity lemma	2016	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	Szemerédi’s Regularity Lemma for Sparse Graphs	1997	Yoshiharu Kohayakawa
+ PDF Chat	An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs	2025	Natan Rubin

Works That Cite This (119)

Action	Title	Year	Authors
+	A sparse regular approximation lemma	2017	Guy Moshkovitz A. Shapira
+	Monochromatic loose path partitions in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="mml4" display="inline" overflow="scroll" altimg="si4.gif"><mml:mi>k</mml:mi></mml:math>-uniform hypergraphs	2017	Changhong Lü Bing Wang Ping Zhang
+ PDF Chat	A new proof of the density Hales-Jewett theorem	2012	NULL AUTHOR_ID
+	A measure-theoretic approach to the theory of dense hypergraphs	2012	Gábor Elek Balázs Szegedy
+	Weak hypergraph regularity and linear hypergraphs	2009	Yoshiharu Kohayakawa Brendan Nagle Vojtěch Rödl Mathias Schacht
+ PDF Chat	Recent advances on Dirac-type problems for hypergraphs	2016	Yi Zhao
+	On the testability and repair of hereditary hypergraph properties	2008	Tim Austin Terence Tao
+	Linear Ramsey Numbers for Bounded-Degree Hypergrahps	2007	Yoshiyasu Ishigami
+	Multiple recurrence in quasirandom groups	2012	Vitaly Bergelson Terence Tao
+	Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets	2015	Terence Tao

Works Cited by This (38)

Action	Title	Year	Authors
+ PDF Chat	On sets of integers containing k elements in arithmetic progression	1975	Endre Szemerédi
+	Szemerédi’s Regularity Lemma for Sparse Graphs	1997	Yoshiharu Kohayakawa
+	Szemeredi''s Regularity Lemma and its applications in graph theory	1995	János Komlós Miklós Simonovits
+	The Regularity Lemma and Its Applications in Graph Theory	2002	János Komlós Ali Shokoufandeh Miklós Simonovits Endre Szemerédi
+	Extremal Hypergraph Problems and the Regularity Method	2007	Brendan Nagle Vojtěch Rödl Mathias Schacht
+	A Szemeredi-type regularity lemma in abelian groups	2003	Ben Green
+	Integer and fractional packings of hypergraphs	2006	V. Rödl Mathias Schacht Mark Siggers Norihide Tokushige
+	An ergodic Szemerédi theorem for IP-systems and combinatorial theory	1985	Hillel Fürstenberg Yitzhak Katznelson
+	Regularity Lemma for k‐uniform hypergraphs	2004	Vojtěch Rödl Jozef Skokan
+	Applications of the regularity lemma for uniform hypergraphs	2006	Vojtěch Rödl Jozef Skokan