We prove that Boolean matrices with bounded $\gamma_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$-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}$, 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})$, then $G$ must contain a clique of size $\Omega(\sqrt{ m})$.
Categories: math.CO cs.CC cs.DM