Saturation of multidimensional 0-1 matrices

研究成果: 雜誌貢獻期刊論文同行評審


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.

頁(從 - 到)91-95
期刊Discrete Mathematics Letters
出版狀態已出版 - 2023


深入研究「Saturation of multidimensional 0-1 matrices」主題。共同形成了獨特的指紋。