论文标题
多维0-1矩阵的饱和
Saturation of multidimensional 0-1 matrices
论文作者
论文摘要
如果$ m $不包含可以通过将其$ 1 $ 1 $ 1 $ 0 $ 0 $ entries的任何数字转换为$ 0 $ - 输入到$ 1 $ $ m $的$ m $ prives $ p $ p $ p $ p $ p $ p $ p $ p $，则a 0-1矩阵$ m $对于0-1矩阵$ p $ p $ p $如果不包含可以将其变成$ p $的子元素。如果将任何$ 0 $ - 输入到$ 1 $ m $的$ 0 $ entry将$ p $的新副本更改为$ p $，则矩阵$ m $对于$ p $的半饱和度，无论$ m $最初包含$ p $。功能$ ex（n; p）$和$ sat（n; p）$是$ 1 $ -Entries a $ n \ times n $ 0-1矩阵饱和的最大和最小数量。函数$ ssat（n; p）$是$ 1 $ - 输入a $ n \ times n $ 0-1矩阵半饱和的最低数量。 函数$ ex（n; p）$数十年来已经研究了，而最近启动了对$ sat（n; p）$和$ ssat（n; p）$的调查。在本文中，我们将有关这些功能的结果对多维0-1矩阵进行了非平凡的概括。特别是，当$ p $为$ d $二维身份矩阵时，我们发现$ ex（n; p，d）$和$ sat（n; p，d）$的确切值（n; p，d）$。然后，我们为多维0-1矩阵提供了必要的条件，以具有有界的半饱和函数。
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 $n\times n$ 0-1 matrix saturating for $P$ can have, respectively. Function $ssat(n;P)$ is the minimum possible number of $1$-entries a $n\times n$ 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.
