Title: Saturation of 0-1 Matrices Show Chinese title

Title: 0-1矩阵的饱和度

Abstract: A 0-1 matrix $M$ contains a 0-1 matrix $P$ if $M$ has a submatrix $P'$ which can be turned into $P$ by changing some of the ones to zeroes. Matrix $M$ is $P$-saturated if $M$ does not contain $P$, but any matrix $M'$ derived from $M$ by changing a zero to a one must contain $P$. The saturation function $sat(n,P)$ is defined as the minimum number of ones of an $n \times n$ $P$-saturated 0-1 matrix. Fulek and Keszegh showed that each pattern $P$ has $sat(n,P) = O(1)$ or $sat(n,P) = \Theta(n)$. This leads to the natural problem of classifying forbidden 0-1 matrices according to whether they have linear or bounded saturation functions. Some progress has been made on this problem: multiple infinite families of matrices with bounded saturation function and other families with linear saturation function have been identified. We answer this question for all patterns with at most four ones, as well as several specific patterns with more ones, including multiple new infinite families. We also consider the effects of certain matrix operations, including the Kronecker product and insertion of empty rows and columns. Additionally, we consider the simpler case of fixing one dimension, extending results of (Fulek and Keszegh, 2021) and (Berendsohn, 2021). We also generalize some results to $d$-dimensional saturation. Show Chinese abstract

Abstract: 一个0-1矩阵$M$包含一个0-1矩阵$P$，如果$M$有一个子矩阵$P'$，可以通过将一些1变为0来变成$P$。 矩阵$M$是$P$-饱和的，如果$M$不包含$P$，但任何由将$M$中的一个零改为一得到的矩阵$M'$必须包含$P$。 饱和函数$sat(n,P)$定义为一个$n \times n$$P$-饱和的 0-1 矩阵中 1 的最小数量。 Fulek 和 Keszegh 表明每个模式$P$都有$sat(n,P) = O(1)$或$sat(n,P) = \Theta(n)$。 这导致了一个自然的问题，即根据它们是否具有线性或有界饱和函数来对禁止的 0-1 矩阵进行分类。 在这个问题上已经取得了一些进展：已经识别出多个具有有界饱和函数的无限矩阵族和其他具有线性饱和函数的族。 我们针对最多四个 1 的所有模式以及一些具有更多 1 的特定模式回答了这个问题，包括多个新的无限族。 我们还考虑了某些矩阵操作的影响，包括克罗内克积以及插入空行和列。 此外，我们考虑了固定一个维度的更简单情况，扩展了 (Fulek 和 Keszegh, 2021) 和 (Berendsohn, 2021) 的结果。 我们还将一些结果推广到$d$维度的饱和。