Back to Search
Start Over
Large Homogeneous Submatrices
- Source :
- SIAM Journal on Discrete Mathematics, 34 (4)
- Publication Year :
- 2020
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2020.
-
Abstract
- A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2\times 2$ zero-one matrix that is not homogeneous. We prove that if an $n\times n$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has an $cn\times 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)}\times n^{1-o(1)}$ homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane-arrangements and string graphs.<br />21 pages, 2 figures. Revised version, a tabular overview of results added at the end
- Subjects :
- Combinatorics
Matrix (mathematics)
010201 computation theory & mathematics
Homogeneous
General Mathematics
FOS: Mathematics
Mathematics - Combinatorics
Block matrix
Combinatorics (math.CO)
0102 computer and information sciences
Zero-one matrices
Forbidden submatrix
Intersection patterns
Erdos-Hajnal conjecture
01 natural sciences
Mathematics
Subjects
Details
- ISSN :
- 10957146 and 08954801
- Volume :
- 34
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....2af3766825b1c183bbc83dea10c14e1d
- Full Text :
- https://doi.org/10.1137/19m125786x