2021/01/10 by Alex Scott, Scott, Alex, Paul Seymour +3
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2101.03537
openalex publication_date 2021/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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). Korandi, Pach, and Tomon 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).