论文标题
几乎所有排列矩阵都有界限饱和函数
Almost all permutation matrices have bounded saturation functions
论文作者
论文摘要
数十年来，禁止图的饱和问题一直是一个流行的研究领域，最近Brualdi和CAO启动了0-1矩阵饱和问题的研究。我们说，如果$ a $避免$ p $，则0-1矩阵$ a $对于禁止的0-1矩阵$ p $饱和，但是将任何零更改为$ a $中的一个零，会创建$ p $的副本。定义$ sat（n，p）$，是$ n \ times n $ 0-1矩阵中最小数量的数量，该矩阵以$ p $饱和。 Fulek和Keszegh证明，对于每0-1矩阵$ p $，$ sat（n，p）= o（1）$或$ sat（n，p）=θ（n）$。他们发现了两个0-1矩阵$ p $，其中$ sat（n，p）= o（1）$，以及无限的0-1矩阵$ p $，$ sat（n，p）=θ（n）$。他们的结果表明，几乎所有$ k \ times k $ 0-1矩阵$ p $ $ sat（n，p）=θ（n）$。 Fulek和Keszegh猜想，还有更多0-1矩阵$ p $，使得$ sat（n，p）= o（1）$除了他们发现的$（1）$，他们要求对所有置换矩阵$ p $进行表征，使得$ sat（n，p）= o（1）$。我们通过证明几乎所有$ k \ times k $ prabion矩阵$ p $都有$ sat（n，p）= o（1）$来确认他们的猜想。我们还在表征问题上取得了进展，因为我们的主要结果证明表现出具有有界饱和函数的排列矩阵家族。
Saturation problems for forbidden graphs have been a popular area of research for many decades, and recently Brualdi and Cao initiated the study of a saturation problem for 0-1 matrices. We say that 0-1 matrix $A$ is saturating for the forbidden 0-1 matrix $P$ if $A$ avoids $P$ but changing any zero to a one in $A$ creates a copy of $P$. Define $sat(n, P)$ to be the minimum possible number of ones in an $n \times n$ 0-1 matrix that is saturating for $P$. Fulek and Keszegh proved that for every 0-1 matrix $P$, either $sat(n, P) = O(1)$ or $sat(n, P) = Θ(n)$. They found two 0-1 matrices $P$ for which $sat(n, P) = O(1)$, as well as infinite families of 0-1 matrices $P$ for which $sat(n, P) = Θ(n)$. Their results imply that $sat(n, P) = Θ(n)$ for almost all $k \times k$ 0-1 matrices $P$. Fulek and Keszegh conjectured that there are many more 0-1 matrices $P$ such that $sat(n, P) = O(1)$ besides the ones they found, and they asked for a characterization of all permutation matrices $P$ such that $sat(n, P) = O(1)$. We affirm their conjecture by proving that almost all $k \times k$ permutation matrices $P$ have $sat(n, P) = O(1)$. We also make progress on the characterization problem, since our proof of the main result exhibits a family of permutation matrices with bounded saturation functions.
