Factorization norms and an inverse theorem for MaxCut
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912458072915968 |
|---|---|
| author | Balla, Igor Hambardzumyan, Lianna Tomon, István |
| author_facet | Balla, Igor Hambardzumyan, Lianna Tomon, István |
| contents | We prove that Boolean matrices with bounded $γ_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 $γ_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 $Ω(\sqrt{m})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23989 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Factorization norms and an inverse theorem for MaxCut Balla, Igor Hambardzumyan, Lianna Tomon, István Combinatorics Computational Complexity Discrete Mathematics We prove that Boolean matrices with bounded $γ_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 $γ_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 $Ω(\sqrt{m})$. |
| title | Factorization norms and an inverse theorem for MaxCut |
| topic | Combinatorics Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2506.23989 |