Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
复制标题
纯对。
DOI：
10.1016/j.jctb.2023.03.001
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Spirkl, Sophie
中科院分区：
文献类型：
--
作者：
Scott, Alex;Seymour, Paul;Spirkl, Sophie
对于整数n> 0，设f（n）是M的最大全0或全1子方阵的行数，它在所有n× n 0/1-矩阵M上最小化.因此f（n）= O（log n）。但让我们固定一个矩阵H，并定义f H（n）是相同的，在所有n× n 0/1-矩阵M上最小化，使得M和它的补矩阵（也就是说，将所有的0变为1，反之亦然）都不包含H作为子矩阵。已知f H（n）≥ ε nc，其中c，ε> 0是依赖于H的常数.什么时候可以取c= 1？如果是，则H和它的补图中的一个一定是无圈矩阵（即对应的二部图是森林）。Korándi，Pach，and Tomon [6]证明了匡威的情况，即对于每个非循环矩阵H，f H（n）在n中是线性的;并且他们对某些只有两行的矩阵H证明了这一点。他们的猜想仍然是公开的，但我们证明了对每个非循环矩阵H，f H（n）= n 1− o（1）;并且确实存在一个0/1-子矩阵，它或者是Ω（n）× n 1− o（1），或者是n 1− o（1）× Ω（n）。
For integer n> 0, let f (n) be the number of rows of the largest all-0 or all-1 square submatrix of M, minimized over all n× n 0/1-matrices M. Thus f (n)= O (log n). But let us fix a matrix H, and define f H (n) to be the same, minimized over all n× n 0/1-matrices M such that neither M nor its complement (that is, change all 0's to 1's and vice versa) contains H as a submatrix. It is known that f H (n)≥ ε n c, where c, ε> 0 are constants depending on H. When can we take c= 1? If so, then one of H and its complement must be an acyclic matrix (that is, the corresponding bipartite graph is a forest). Korándi, Pach, and Tomon [6] conjectured the converse, that f H (n) is linear in n for every acyclic matrix H; and they proved it for certain matrices H with only two rows. Their conjecture remains open, but we show f H (n)= n 1− o (1) for every acyclic matrix H; and indeed there is a 0/1-submatrix that is either Ω (n)× n 1− o (1) or n 1− o (1)× Ω (n).