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 - Funding Information:
Supported by AFOSR grants A9550-19-1-0187 and FA9550-22-1-0234, and NSF grants DMS-1800053 and DMS-2154169.Current address: University of Waterloo, Ontario, Canada N2L3G1. This material is based upon work supported by the National Science Foundation under Award No. DMS-1802201.
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(logn). 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(logn). 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
AN - SCOPUS:85151723303
SN - 0095-8956
VL - 161
SP - 437
EP - 464
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
ER -