Felix Joos (Universität Heidelberg): The hypergraph removal process

Abstract:

Fix some graph or uniform hypergraph F and then consider the following simple process: start
with a large complete (hyper)graph Kn on n vertices and iteratively remove (the edge set of) co-
pies 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 termi-
nation 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 fa-
mously proved in 2015 that the triangle-removal process (F is a triangle) typically terminates with
n3/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.

Before this talk, from 4:45 p.m., there will be coffee and tea again in room 1404.

Everyone is warmly invited to attend.

gez. Prof. Dr. Torsten Mütze