## 摘要

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.

原文 | ???core.languages.en_GB??? |
---|---|

頁（從 - 到） | 91-95 |

頁數 | 5 |

期刊 | Discrete Mathematics Letters |

卷 | 11 |

DOIs | |

出版狀態 | 已出版 - 2023 |