Large homogeneous submatrices

2019/03/15 by Korándi, Dániel, Pach, János, Tomon, István · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1903.06608

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 an 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 n^1-o(1)× n^1-o(1) homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane-arrangements and string graphs.

Cited by

• C₄-free subgraphs of high degree with geometric applications

Related

• Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
• Saturation problems about forbidden 0-1 submatrices
• On Forbidden Submatrices
• Almost all friendly matrices have many obstructions
• Hypergraphs and hypermatrices with symmetric spectrum