The acyclic-matrix conjecture for dense zero-submatrices
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.
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.