-

The hypergraph removal process

组织者

马杰 , 本杰明·苏达科夫

演讲者

Felix Joos

时间

2025年12月16日 17:05 至 18:15

地点

Online

线上

Zoom 787 662 9899 (BIMSA)

摘要

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.