Regularity and counting lemmas for multidimensional matrices

MaRDI QIDQ6325058zbMATH OpenFDO

Authors Anna A. Taranenko

Publication date 11 September 2019

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 $varepsilon$-regularity from graphs to matrices. Next, we state that this $varepsilon$-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 $varepsilon$-regular patterns that allow us to deduce a multidimensional counting lemma.

This page was built for publication: Regularity and counting lemmas for multidimensional matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6325058)