Large Cuts in Hypergraphs via Energy

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...

Full description

Saved in:
Bibliographic Details
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
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422