The simple-matrix conjecture on linear homogeneous submatrices

About 7 years old · traced to

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.

References

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.