Factorization norms and an inverse theorem for MaxCut

Abstract We prove that Boolean matrices with bounded $$\gamma _2$$ γ 2 -norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $$\gamma _2$$ γ 2 -norm and discuss applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics. As a key application, we establish an inverse theorem for MaxCut. A celebrated result of Edwards states that every graph G with m edges has a cut of size at least $$\frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}$$ m 2 + 8 m + 1 - 1 8 , with equality achieved by complete graphs with an odd number of vertices. To contrast this, we prove that if the MaxCut of G is at most $$\frac{m}{2}+O(\sqrt{m})$$ m 2 + O ( m ) , then G must contain a clique of size $$\Omega (\sqrt{m})$$ Ω ( m ) .