The simple-matrix conjecture on linear homogeneous submatrices
The simple-matrix conjecture on linear homogeneous submatrices
Let ) be a simple zero-one matrix if both and its complement are acyclic, meaning that every submatrix has a row or column containing at most one 1-entry. A matrix is -free if it contains no submatrix equal to . A submatrix is homogeneous if all its entries are equal.
Simple-matrix conjecture. Let be a simple zero-one matrix. Then every -free zero-one matrix contains a homogeneous submatrix, for a suitable constant .
The preceding results establish this type of conclusion for the relevant 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.