The acyclic-matrix conjecture for dense zero-submatrices

About 7 years old · traced to

A zero-one matrix PP is acyclic if every submatrix of PP has a row or column containing at most one 1-entry. A matrix is PP-free if it contains no submatrix equal to PP.

Acyclic-matrix conjecture. For every acyclic zero-one matrix PP and every ε>0\varepsilon>0, there is a δ>0\delta>0 such that every PP-free n×nn\times n zero-one matrix with at least εn2\varepsilon n^2 0-entries contains a δn×δn\delta n\times\delta n 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

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.