Regularity and counting lemmas for multidimensional matrices

Abstract

In the present paper we propose generalizations of the regularity and counting lemmas for multidimensional matrices under a finite alphabet. Firstly, we prove a variant of a multidimensional regularity lemma with the help of a translation of $\epsilon$-regularity from graphs to matrices. Next, we state that this $\epsilon$-regularity is sufficient for obtaining a matrix analogue of the counting lemma for $2$-dimensional matrices but not for higher-dimensional cases. Finally, we introduce $\epsilon$-regular patterns that allow us to deduce a multidimensional counting lemma.