Nearly tight bounds for MaxCut in hypergraphs
Organizers
Jie Ma
, Benjamin Sudakov
Speaker
Oliver Janzer
Time
Tuesday, September 23, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
An $r$-cut of a $k$-uniform hypergraph is a partition of its vertex set into $r$ parts, and the size of the cut is the number of edges which have at least one vertex in each part. The study of the possible size of the largest $r$-cut in $k$-uniform hypergraphs was initiated by Erd\H{o}s and Kleitman in 1968. Conlon, Fox, Kwan and Sudakov proved that any $k$-uniform hypergraph with $m$ hyperedges has an $r$-cut whose size is $\Omega(m^{5/9})$ larger than the expected size of a random $r$-cut, provided that $k \geq 4$ or $r \geq 3$. They further conjectured that this can be improved to $\Omega(m^{2/3})$. Recently, R{\"a}ty and Tomon improved the bound $m^{5/9}$ to $m^{3/5-o(1)}$ when $r \in \{ k-1,k\}$. Using a novel approach, we prove the following approximate version of the Conlon--Fox--Kwan--Sudakov conjecture: for each $\varepsilon>0$, there is some $k_0=k_0(\varepsilon)$ such that for all $k>k_0$ and $2\leq r\leq k$, in every $k$-uniform hypergraph with $m$ edges there exists an $r$-cut exceeding the random one by $\Omega(m^{2/3-\varepsilon})$. Moreover, we show that (if $k\geq 4$ or $r\geq 3$) every $k$-uniform linear hypergraph has an $r$-cut exceeding the random one by $\Omega(m^{3/4})$, which is tight and proves a conjecture of R\"aty and Tomon.
Joint work with Julien Portier.
Joint work with Julien Portier.
Speaker Intro
Oliver Janzer is a Junior Research Fellow at Trinity College, Cambridge, whose main research interests are Extremal, Probabilistic and Additive Combinatorics. He obtained his PhD in 2020 under the supervision of Timothy Gowers. Between 2020 and 2022 he held an ETH Zurich Postdoctoral Fellowship. In 2022 he won the British Combinatorial Committee’s PhD thesis prize.