Korandi, József and Pach, János and Tomon, I. (2020) Large homogeneous submatrices. SIAM JOURNAL ON DISCRETE MATHEMATICS, 34 (4). pp. 2532-2552. ISSN 0895-4801
|
Text
1903.06608.pdf Download (379kB) | Preview |
Abstract
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
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Mathematical techniques; Combinatorial mathematics; String graphs; Forbidden submatrix; Half-planes; Zero-one matrices; Sub-matrices; Submatrix; Intersection patterns; Chordal bipartite graph; Zero-one matrix; Erd\\H os-Hajnal conjecture; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 10 Feb 2023 12:46 |
| Last Modified: | 10 Feb 2023 12:46 |
| URI: | http://real.mtak.hu/id/eprint/158746 |
Actions (login required)
 |
Edit Item |
