Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

TY - JOUR

T1 - Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

N1 - Publisher Copyright: © 2023 Elsevier Inc.

PY - 2023/7

Y1 - 2023/7

N2 - 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 fH(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 fH(n)≥εnc, 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 fH(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 fH(n)=n1−o(1) for every acyclic matrix H; and indeed there is a 0/1-submatrix that is either Ω(n)×n1−o(1) or n1−o(1)×Ω(n).

AB - 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 fH(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 fH(n)≥εnc, 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 fH(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 fH(n)=n1−o(1) for every acyclic matrix H; and indeed there is a 0/1-submatrix that is either Ω(n)×n1−o(1) or n1−o(1)×Ω(n).

KW - Bipartite graph

KW - Homogeneous matrix

KW - Induced subgraph

KW - Pure pair

UR - http://www.scopus.com/inward/record.url?scp=85151723303&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85151723303&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.03.001

DO - 10.1016/j.jctb.2023.03.001

M3 - Article

SN - 0095-8956

VL - 161

SP - 437

EP - 464

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -