北京雁栖湖应用数学研究院

马杰 , 本杰明·苏达科夫

Oliver Janzer

2025年09月23日 17:05 至 18:15

Online

Zoom 787 662 9899 (BIMSA)

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.

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.