Saturation of multidimensional 0-1 matrices

DOI10.47443/DML.2022.151MaRDI QIDQ6408928arXivFDO

Authors S. F. Tsai

Publication date 26 August 2022

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Abstract: A 0-1 matrix $M$ is saturating for a 0-1 matrix $P$ if $M$ does not contain a submatrix that can be turned into $P$ by flipping any number of its $1$-entries to $0$-entries, and changing any $0$-entry to $1$-entry of $M$ introduces a copy of $P$. Matrix $M$ is semisaturating for $P$ if changing any $0$-entry to $1$-entry of $M$ introduces a new copy of $P$, regardless of whether $M$ originally contains $P$ or not. The functions $ex(n;P)$ and $sat(n;P)$ are the maximum and minimum possible number of $1$-entries a $nimesn$ 0-1 matrix saturating for $P$ can have, respectively. Function $ssat(n;P)$ is the minimum possible number of $1$-entries a $nimesn$ 0-1 matrix semisaturating for $P$ can have. Function $ex(n;P)$ has been studied for decades, while investigation on $sat(n;P)$ and $ssat(n;P)$ was initiated recently. In this paper, we make nontrivial generalization of results regarding these functions to multidimensional 0-1 matrices. In particular, we find the exact values of $ex(n;P,d)$ and $sat(n;P,d)$ when $P$ is a $d$-dimensional identity matrix. Then we give the necessary and sufficient condition for a multidimensional 0-1 matrix to have bounded semisaturation function.

This page was built for publication: Saturation of multidimensional 0-1 matrices

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