The acyclic-matrix conjecture for dense zero-submatrices

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.

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.