The acyclic forbidden-matrix conjecture for homogeneous submatrices
The acyclic forbidden-matrix conjecture for homogeneous submatrices
A zero-one matrix is acyclic if every submatrix of has a row or column containing at most one 1-entry; its complement is obtained by exchanging 0-entries and 1-entries. A matrix is -free if it contains no submatrix equal to , and a submatrix is homogeneous if all entries are equal.
Acyclic forbidden-matrix conjecture. Let be an acyclic zero-one matrix. Then every zero-one matrix that is both -free and -free contains a homogeneous submatrix, for a suitable constant .
The statement is an immediate corollary proposed from the preceding density conjecture, by applying it to a matrix or its complement. It extends the known linear homogeneous-submatrix results beyond simple matrices and 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.