## 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 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 language | English |
---|---|

Pages (from-to) | 91-95 |

Number of pages | 5 |

Journal | Discrete Mathematics Letters |

Volume | 11 |

DOIs | |

State | Published - 2023 |

## Keywords

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