## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 437-464 |

Number of pages | 28 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 161 |

DOIs | |

State | Published - Jul 2023 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Bipartite graph
- Homogeneous matrix
- Induced subgraph
- Pure pair