The hypergraph removal process
Organizers
Jie Ma
, Benjamin Sudakov
Speaker
Felix Joos
Time
Tuesday, December 16, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
Fix some graph or uniform hypergraph $F$ and then consider the following simple process: start with a large complete (hyper)graph $K_n$ on $n$ vertices and iteratively remove (the edge set of) copies of $F$ as long as possible; each selection is made uniformly among all present copies of $F$ at that time. This process is known as the $F$-removal process. The determination of the termination time (how many edges are left when the process terminates) is the key question regarding this process. This question has proven to be highly challenging. Bohman, Frieze and Lubetzky famously proved in 2015 that the triangle-removal process ($F$ is a triangle) typically terminates with $n^{3/2+o(1)}$ edges. For no other (hyper)graph $F$ has the termination of the $F$-removal process been established. We determine when the $F$-removal process ends for all "sensible" choices of $F$; this includes cliques, for which a major folklore conjecture in this area predicts the termination time.
This is joint work with Marcus Kühn.
This is joint work with Marcus Kühn.