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\times 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 over all $n\times 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)\ge \epsilon
n^c$, where $c, \epsilon>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 $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
$\Omega(n)\times n^{1-o(1)}$ or $n^{1-o(1)}\times \Omega(n)$.