Brendan Nagle

SODA Conference 2016 Conference Paper

An Algorithmic Hypergraph Regularity Lemma

• Brendan Nagle
• Vojtech Rödl
• Mathias Schacht

SODA Conference 2009 Conference Paper

Hypergraph regularity and quasi-randomness

• Brendan Nagle
• Annika Poerschke
• Vojtech Rödl
• Mathias Schacht

FOCS Conference 2005 Conference Paper

An Algorithmic Version of the Hypergraph Regularity Method

• Penny Haxell
• Brendan Nagle
• Vojtech Rödl

Extending the Szemeredi Regularity Lemma for graphs, P. Frank and Rodl [2002] stablished a 3-graph Regularity Lemma guaranteeing that all large triple systems admit partitions of their edge sets into constantly many classes where most classes consist of regularly distributed edges. Many applications of this lemma require a companion Counting Lemma [Nagle and Rodl, 2003] allowing one to estimate the number of copies of K/sub k//sup 3/ in a "dense and regular" environment created by the 3-graph Regularity Lemma. Combined applications of these lemmas are known as the 3-graph Regularity Method. In this paper, we provide an algorithmic version of the 3-graph Regularity Lemma which, as we show, is compatible with a Counting Lemma. We also discuss some applications. For general k-uniform hypergraphs, Regularity and Counting Lemmas were recently established by Gowers [2005] and by Nagle et al. , [2005]. We believe the arguments here provide a basis toward a general algorithmic hypergraph regularity method.