Large homogeneous submatrices
Korandi, József, János Pach, István Tomon · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2020
A matrix is homogeneous if all of its entries are equal. Let P be a 2 × 2 zero-one matrix that is not homogeneous. We prove that if an n × n zero-one matrix A does not contain P as a submatrix, then A has a cn × cn homogeneous submatrix for a suitable constant c > 0. We further provide an almost complete characterization of the matrices P (missing only finitely many cases) such that forbidding P in A guarantees an n1 - o(1) × n1 - o(1) homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs. © 2020 authors