On characterizing hypergraph regularity

ABSTRACT: Szemerédi’s Regularity Lemma is a well-known and powerful tool in modern graph theory. This result led to a number of interesting applications, particularly in extremal graph theory. A regularity lemma for 3-uniform hypergraphs developed by Frankl and Rödl [8] allows some of the Szemerédi Regularity Lemma graph applications to be extended to hypergraphs. An important development regarding Szemerédi’s Lemma showed the equivalence between the property of -regularity of a bipartite graph G and an easily verifiable property concerning the neighborhoods of its vertices (Alon et al. [1]; cf. [6]). This characterization of -regularity led to an algorithmic version of Szemerédi’s lemma [1]. Similar problems were also considered for hypergraphs. In [2], [9], [13], and [18], various descriptions of quasi-randomness of k-uniform hypergraphs were given. As in [1], the goal of this paper is to find easily verifiable conditions for the hypergraph regularity provided by [8]. The hypergraph regularity of [8] renders quasi-random “blocks of hyperedges” which are very sparse. This situation leads to technical difficulties in its application. Moreover, as we show in this paper, some easily verifiable conditions analogous to those considered in [2] and [18] fail to be true in the setting of [8]. However, we are able to find some necessary and sufficien