Extremal bounds for pattern avoidance in multidimensional 0-1 matrices

arXiv2306.11934MaRDI QIDQ6440929FDOQ6440929

Authors: Jesse Geneson, S. F. Tsai 

Publication date: 20 June 2023

Abstract: A 0-1 matrix $M$ contains another 0-1 matrix $P$ if some submatrix of $M$ can be turned into $P$ by changing any number of $1$-entries to $0$-entries. $M$ is $mathcalP$-saturated where $mathcalP$ is a family of 0-1 matrices if $M$ avoids every element of $mathcalP$ and changing any $0$-entry of $M$ to a $1$-entry introduces a copy of some element of $mathcalP$. The extremal function ex$(n,mathcalP)$ and saturation function sat$(n,mathcalP)$ are the maximum and minimum possible weight of an $nimesn$ $mathcalP$-saturated 0-1 matrix, respectively, and the semisaturation function ssat$(n,P)$ is the minimum possible weight of an $nimesn$ $mathcalP$-semisaturated 0-1 matrix $M$, i.e., changing any $0$-entry in $M$ to a $1$-entry introduces a new copy of some element of $mathcalP$. We study these functions of multidimensional 0-1 matrices. We give upper bounds on parameters of minimally non-$O(n^{d-1})$ $d$-dimensional 0-1 matrices, generalized from minimally nonlinear 0-1 matrices in two dimensions, and we show the existence of infinitely many minimally non-$O(n^{d-1})$ $d$-dimensional 0-1 matrices with all dimensions of length greater than $1$. For any positive integers $k,d$ and integer $rin[0,d-1]$, we construct a family of $d$-dimensional 0-1 matrices with both extremal function and saturation function exactly $k{n}^r$ for sufficiently large $n$. We show that no family of $d$-dimensional 0-1 matrices has saturation function strictly between $O(1)$ and $Theta(n)$ and we construct a family of $d$-dimensional 0-1 matrices with bounded saturation function and extremal function $Omega(n^{d-epsilon})$ for any $epsilon>0$. Up to a constant multiplicative factor, we fully settle the problem of characterizing the semisaturation function of families of $d$-dimensional 0-1 matrices, which we prove to always be $Theta(n^r)$ for some integer $rin[0,d-1]$.

This page was built for publication: Extremal bounds for pattern avoidance in multidimensional 0-1 matrices

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