The acyclic forbidden-matrix conjecture for homogeneous submatrices

A zero-one matrix PP is acyclic if every submatrix of PP has a row or column containing at most one 1-entry; its complement PcP^c is obtained by exchanging 0-entries and 1-entries. A matrix is PP-free if it contains no submatrix equal to PP, and a submatrix is homogeneous if all entries are equal.

Acyclic forbidden-matrix conjecture. Let PP be an acyclic zero-one matrix. Then every n×nn\times n zero-one matrix that is both PP-free and PcP^c-free contains a cn×cncn\times cn homogeneous submatrix, for a suitable constant c>0c>0.

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

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.