Bounded cgamma2cgamma_2-norm decomposition conjecture for Boolean matrices

About 1 year old · traced to

Let MM be an m×nm\times n Boolean matrix, and let γ2(M)\gamma_2(M) denote its γ2\gamma_2-norm. A blocky matrix is a blow-up of a permutation matrix. Bounded γ2\gamma_2-norm decomposition conjecture. If

γ2(M)≤γ,\gamma_2(M)\leq \gamma,

then there exists a constant cγc_{\gamma} depending only on γ\gamma such that MM is a ±1\pm1-linear combination of at most cγc_{\gamma} blocky matrices.

The conjecture is equivalent, according to the source, to a structural characterization of matrices with bounded γ2\gamma_2-norm and to an open question about characterizing idempotent Schur multipliers in terms of contractive idempotents.

References

Primary source

Igor Balla, Lianna Hambardzumyan and István Tomon, “Factorization norms and an inverse theorem for MaxCut”, arXiv:2506.23989 (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.