Saturation of multidimensional 0-1 matrices

Research output: Contribution to journalArticlepeer-review


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 flipping any 0-entry of M to 1-entry introduces a copy of P . Matrix M is semisaturating for P if flipping any 0-entry of M to 1-entry 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 n×n 0-1 matrix saturating for P can have, respectively. The function ssat(n; P) is the minimum possible number of 1-entries an n × n 0-1 matrix semisaturating for P can have. The 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, a nontrivial generalization of results regarding these functions to multidimensional 0-1 matrices is made. In particular, the exact values of ex(n; P, d) and sat(n; P, d) are found when P is a d-dimensional identity matrix. Finally, a necessary and sufficient condition for a multidimensional 0-1 matrix to have a bounded semisaturation function is given.

Original languageEnglish
Pages (from-to)91-95
Number of pages5
JournalDiscrete Mathematics Letters
StatePublished - 2023


  • 0-1 matrix
  • excluded submatrix
  • forbidden pattern
  • multidimensional matrix
  • saturation


Dive into the research topics of 'Saturation of multidimensional 0-1 matrices'. Together they form a unique fingerprint.

Cite this