2024/10/02 by Eero Räty, Räty, Eero, István Tomon +1 · 5 citations
Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Graph Theory and Algorithms #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2410.01682
openalex publication_date 2024/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A simple probabilistic argument shows that every r-uniform hypergraph with m edges contains an r-partite subhypergraph with at least (r!)/(rr)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+Ω(m1/2), and this is sharp. We prove that if r≥ 3, then there is an r-partite subhypergraph with at least (r!)/(rr) m+m3/5-o(1) edges. Moreover, if the hypergraph is linear, this can be improved to (r!)/(rr) m+m3/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 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+Ω((E(G))/(log m)), which might be of independent interest.