An algorithmic version of the hypergraph regularity method
Extending the Szemeredi regularity lemma for graphs, P. Frankl and V. Rodl [Random Structures Algorithms, 20 (2002), pp. 131-164] established a 3-graph regularity lemma triple systems Gn admit bounded partitions of their edge sets, most classes of which consist of regularly distributed triples. Many applications of this lemma require a companion counting lemma [B. Nagle and V. Rodl, Random Structures Algorithms, 23 (2003), pp. 264-332] allowing one to find and enumerate subhypergraphs of a given isomorphism type 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.
algorithmic regularity lemma for hypergraphs counting lemma for hypergraphs