The simple-matrix conjecture on linear homogeneous submatrices

Let PP) be a simple zero-one matrix if both PP and its complement PcP^c are acyclic, meaning that every submatrix has a row or column containing at most one 1-entry. A matrix is PP-free if it contains no submatrix equal to PP. A submatrix is homogeneous if all its entries are equal.

Simple-matrix conjecture. Let PP be a simple zero-one matrix. Then every PP-free n×nn\times n zero-one matrix contains a cn×cncn\times cn homogeneous submatrix, for a suitable constant c>0c>0.

The preceding results establish this type of conclusion for the relevant 2×k2\times k patterns, while nonsimple matrices admit counterexamples with only sublinear homogeneous submatrices. The conjecture concerns the remaining simple patterns, including the finite cases not covered by the proved results.

Sources & referencesView supporting material

Primary source

Dániel Korándi, János Pach and István Tomon, “Large homogeneous submatrices”, arXiv:1903.06608 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.