Abstract. Szemerédi’s regularity lemma guarantees that, for fixed [Formula: see text], every graph [Formula: see text] admits an [Formula: see text]-regular and [Formula: see text]-equitable partition [Formula: see text], where [Formula: see text]. These partitions are constructed by Kohayakawa, Rödl, and Thoma in time [Formula: see text]. Analogous partitions of [Formula: see text]-graphs [Formula: see text] are constructed by Czygrinow and Rödl in time [Formula: see text]. For [Formula: see text], we construct these partitions (and others with slightly stronger regularity) in time [Formula: see text]. We also discuss some applications.

Let ${\cal F}_0$ and ${\cal H}$ be a pair of $k$-graphs (written $F_0$ and $H$, respectively, when k=2). An ${\cal F}_0$-packing of ${\cal H}$ is a family $\mathscr{F}$ of pairwise edge-disjoint copies of ${\cal F}_0$ in ${\cal H}$. Let $\nu_{{\cal F}_0}({\cal H})$ denote the maximum size $|\mathscr{F}|$ of an ${\cal F}_0$-packing $\mathscr{F}$ of ${\cal H}$. Already in the case of graphs (k=2), Dor and Tarsi proved that computing $\nu_{F_0}(H)$ is NP-hard for every fixed graph $F_0$ having a component with three or more edges. On the other hand, Rödl et al. (see primarily [V. Rödl et al. (2007), J. Combin. Theory Ser. B, 97, pp. 245--268]) proved that, for any fixed $k$-graph ${\cal F}_0$, the parameter $\nu_{{\cal F}_0}({\cal H})$ can be approximated within an error of $o(|V({\cal H})|^k)$ in time polynomial in $|V({\cal H})|$. In particular, a foundational result of Haxell and Rödl [P. Haxell and V. Rödl (2001), Combinatorica, 21, pp. 13--38] for graphs ($k=2$) constructs, for every fixed graph $F_0$ and for every given graph $H$, an $F_0$-packing $\mathscr{F}$ of size $|\mathscr{F}| \geq \nu_{F_0}(H) - o(|V(H)|^2)$ in time polynomial in $|V(H)|$. In this paper, we extend the result of Haxell and Rödl to k=3. In particular, for a fixed 3-graph ${\cal F}_0$, we establish an algorithm which, for all $\zeta > 0$ and for every given 3-graph ${\cal H}$, constructs an ${\cal F}_0$-packing $\mathscr{F}$ of ${\cal H}$ of size $|\mathscr{F}| \geq \nu_{{\cal F}_0}({\cal H}) - \zeta |V({\cal H})|^3$ in time polynomial in $|V({\cal H})|$. Our approach is based on that of Haxell and Rödl, and uses hypergraph regularity tools of them and the author from earlier papers, together with some details proven here.

Szemerédi's Regularity Lemma [22, 23] is a powerful tool in graph theory. It asserts that all large graphs G admit a bounded partition of E(G), most classes of which are bipartite subgraphs with uniformly distributed edges. The original proof of this result was non-constructive. A constructive proof was given by Alon, Duke, Lefmann, Rödl and Yuster [1], which allows one to efficiently construct a regular partition for any large graph. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl [3] gave one such extension to 3-uniform hypergraphs, and Rödl and Skokan [19] extended this result to k-uniform hypergraphs. W.T. Gowers [4, 5] gave another such extension. Similarly to the graph case, all of these proofs are non-constructive. We present an efficient algorithmic version of the Hypergraph Regularity Lemma for k-uniform hypergraphs.

Let $\mathcal{F}$ be an r-uniform hypergraph with f vertices, where $f>r\geq3$. In [Inform. Process. Lett., 99 (2006), pp. 130–134], Yuster posed the problem of whether there exists an algorithm which, for a given r-uniform hypergraph $\mathcal{H}$ with n vertices, computes the number of induced copies of $\mathcal{F}$ in $\mathcal{H}$ in time $o(n^f)$. The analogous question for graphs ($r=2$) was known to hold from an $O(n^{f-\varepsilon})$ time algorithm of Nešetřil and Poljak [Comment. Math. Univ. Carolin., 26 (1985), pp. 415–419] (for a constant $\varepsilon=\varepsilon_f>0$ which is independent of n). Here, we present an algorithm for this problem, when $r\geq3$, with running time $O(n^f/\log_2n)$.

Thomason and Chung, Graham, and Wilson were the first to systematically study quasi-random graphs and hypergraphs, and proved that several properties of random graphs imply each other in a deterministic sense. Their concepts of quasi-randomness match the notion of ∊-regularity from the earlier Szemerédi regularity lemma. In contrast, there exists no “natural” hypergraph regularity lemma matching the notions of quasi-random hypergraphs considered by those authors. We study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of Frankl and Rödl, Gowers and Haxell, Nagle and Rödl. We establish an equivalence among the three notions of regularity of these lemmas. Since the regularity lemma of Haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of Frankl–Rödl (a special case thereof) and Gowers as corollaries. As a further corollary, we obtain that the special case of the Frankl–Rödl lemma (which we can make algorithmic) admits a corresponding counting lemma. (This corollary follows by the equivalences and that the regularity lemma of Gowers or that of Haxell et al. admits a counting lemma.)

Extending the Szemerédi regularity lemma for graphs, P. Frankl and V. Rödl [Random Structures Algorithms, 20 (2002), pp. 131–164] established a 3-graph regularity lemma triple systems ${\cal G}_n$ 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. Rödl, 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.

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.