The large constant submatrix conjecture for bounded max-norm matrices

Let MM be an m×nm\times n binary matrix, with entries in {0,1}\{0,1\}, and let γ2(M)\gamma_2(M) denote its factorization max-norm. A submatrix is obtained by restricting MM to selected sets of rows and columns. The large constant submatrix conjecture. For every C>0C>0 there exists c>0c>0 such that the following holds: if γ2(M)C\gamma_2(M)\leq C, then MM contains a cm×cncm\times cn submatrix that is either all ones or all zeros. The source presents this as an easier consequence to pursue independently of the bounded blocky-matrix conjecture; its resolution status is not specified.

Sources & referencesView supporting material

Primary source

István Tomon, “Factorization norms and Zarankiewicz problems”, arXiv:2502.18429 (2025).

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.