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

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).