The acyclic-matrix conjecture for dense zero-submatrices
A zero-one matrix is acyclic if every submatrix of has a row or column containing at most one 1-entry. A matrix is -free if it contains no submatrix equal to .
Acyclic-matrix conjecture. For every acyclic zero-one matrix and every , there is a such that every -free zero-one matrix with at least 0-entries contains a all-0 submatrix.
This is presented as a strengthening of the simple-matrix conjecture. The proved results use the density of zero-entries to obtain large homogeneous submatrices in several special cases, but the asserted statement for arbitrary acyclic forbidden matrices remains open.
References
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
No solutions have been posted yet.