Beijing Institute of Mathematical Sciences and Applications Beijing Institute of Mathematical Sciences and Applications

  • About
    • President
    • Governance
    • Partner Institutions
    • Visit
  • People
    • Management
    • Faculty
    • Postdocs
    • Visiting Scholars
    • Administration
    • Academic Support
  • Research
    • Research Groups
    • Courses
    • Seminars
  • Join Us
    • Faculty
    • Postdocs
    • Students
  • Events
    • Conferences
    • Workshops
    • Forum
  • Life @ BIMSA
    • Accommodation
    • Transportation
    • Facilities
    • Tour
  • News
    • News
    • Announcement
    • Downloads
About
President
Governance
Partner Institutions
Visit
People
Management
Faculty
Postdocs
Visiting Scholars
Administration
Academic Support
Research
Research Groups
Courses
Seminars
Join Us
Faculty
Postdocs
Students
Events
Conferences
Workshops
Forum
Life @ BIMSA
Accommodation
Transportation
Facilities
Tour
News
News
Announcement
Downloads
Qiuzhen College, Tsinghua University
Yau Mathematical Sciences Center, Tsinghua University (YMSC)
Tsinghua Sanya International  Mathematics Forum (TSIMF)
Shanghai Institute for Mathematics and  Interdisciplinary Sciences (SIMIS)
BIMSA > Research seminar in Discrete Mathematics Nearly tight bounds for MaxCut in hypergraphs
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.
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.
Beijing Institute of Mathematical Sciences and Applications
CONTACT

No. 544, Hefangkou Village Huaibei Town, Huairou District Beijing 101408

北京市怀柔区 河防口村544号
北京雁栖湖应用数学研究院 101408

Tel. 010-60661855 Tel. 010-60661855
Email. administration@bimsa.cn

Copyright © Beijing Institute of Mathematical Sciences and Applications

京ICP备2022029550号-1

京公网安备11011602001060 京公网安备11011602001060