Name
Abstract | ||
|---|---|---|
A matrix is homogeneous if all of its entries are equal. Let P be a 2 x 2 zero-one matrix that is not homogeneous. We prove that if an n x n zero-one matrix A does not contain P as a submatrix, then A has a cn x 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 n(1-o(1)) x n(1-o(1)) homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane arrangements, and string graphs. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/19M125786X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
zero-one matrices, forbidden submatrix, intersection patterns, Erdos-Hajnal conjecture | Journal | 34 |
Issue | ISSN | Citations |
4 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Korándi | 1 | 2 | 3.45 |
| János Pach | 2 | 2366 | 292.28 |
| István Tomon | 3 | 6 | 6.70 |