Large Cuts in Hypergraphs via Energy

• Published in: arXiv.org 2024-10
• Main Authors: Räty, Eero, Tomon, István
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Eigenvalues; Graph theory; Graphs; Linear algebra; Semidefinite programming
• ISSN: 2331-8422

A simple probabilistic argument shows that every \(r\)-uniform hypergraph with \(m\) edges contains an \(r\)-partite subhypergraph with at least \(\frac{r!}{r^r}m\) edges. The celebrated result of Edwards states that in the case of graphs, that is \(r=2\), the resulting bound \(m/2\) can be improved to \(m/2+\Omega(m^{1/2})\), and this is sharp. We prove that if \(r\geq 3\), then there is an \(r\)-partite subhypergraph with at least \(\frac{r!}{r^r} m+m^{3/5-o(1)}\) edges. Moreover, if the hypergraph is linear, this can be improved to \(\frac{r!}{r^r} m+m^{3/4-o(1)},\) which is tight up to the \(o(1)\) term. These improve results of Conlon, Fox, Kwan, and Sudakov. Our proof is based on a combination of probabilistic, combinatorial, and linear algebraic techniques, and semidefinite programming. A key part of our argument is relating the energy \(\mathcal{E}(G)\) of a graph \(G\) (i.e. the sum of absolute values of eigenvalues of the adjacency matrix) to its maximum cut. We prove that every \(m\) edge multigraph \(G\) has a cut of size at least \(m/2+\Omega(\frac{\mathcal{E}(G)}{\log m})\), which might be of independent interest.