Mathematicians solve decades-old graph puzzle with practical computing implications
Researchers have proven a long-standing conjecture about how to find optimal divisions in networks, with applications to chip design, logistics optimization, and communications. The breakthrough provides new theoretical foundations for MaxCut algorithms, a problem central to solving real-world partitioning challenges in industry and infrastructure planning.
Originaltitel: Factorization norms and an inverse theorem for MaxCut
Abstract We prove that Boolean matrices with bounded $$\gamma _2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>γ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> -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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>γ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> -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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mfrac> <mml:mrow> <mml:msqrt> <mml:mrow> <mml:mn>8</mml:mn> <mml:mi>m</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msqrt> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mn>8</mml:mn> </mml:mfrac> </mml:mrow> </mml:math> , 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})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mfrac> <mml:mi>m</mml:mi> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mi>m</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , then G must contain a clique of size $$\Omega (\sqrt{m})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mi>m</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> .