Large cuts in hypergraphs via energy
Eero Räty, István Tomon · Mathematical Proceedings of the Cambridge Philosophical Society · 2025
Abstract A simple probabilistic argument shows that every r -uniform hypergraph with m edges contains an r -partite subhypergraph with at least $({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 $({r!}/{r^r}) m+m^{3/5-o(1)}$ edges. Moreover, if the hypergraph is linear, this can be improved to $({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({\mathcal{E}(G)}/{\log m})$ , which might be of independent interest.