论文标题
具有有界饱和函数的矩阵模式
Matrix patterns with bounded saturation function
论文作者
论文摘要
如果我们可以通过删除行和/或列并将任意的1个输入转换为0s，则0-1矩阵$ m $包含一个0-1矩阵模式$ p $，如果我们可以从$ m $中获得$ p $。 0-1矩阵模式$ p $的饱和函数$ \ mathrm {sat}（p，n）$表示不包含$ p $的$ n \ times n $ 0-1矩阵中的最小数量，但将任何0个输入更改为1-输入会产生$ p $ $ p $。 Fulek和Keszegh最近表明，饱和函数是有界的，要么是$θ（n）$。在其结果的基础上，我们发现了具有有界饱和功能的大型模式，包括无限的许多排列矩阵和无限的许多非渗透矩阵。
A 0-1 matrix $M$ contains a 0-1 matrix pattern $P$ if we can obtain $P$ from $M$ by deleting rows and/or columns and turning arbitrary 1-entries into 0s. The saturation function $\mathrm{sat}(P,n)$ for a 0-1 matrix pattern $P$ indicates the minimum number of 1s in a $n \times n$ 0-1 matrix that does not contain $P$, but changing any 0-entry into a 1-entry creates an occurrence of $P$. Fulek and Keszegh recently showed that the saturation function is either bounded or in $Θ(n)$. Building on their results, we find a large class of patterns with bounded saturation function, including both infinitely many permutation matrices and infinitely many non-permutation matrices.
