Disputation Marcus Kühn The Random Greedy Hypergraph Matching Process

Fix a uniform hypergraph H. Consider the random graph process that, starting with a complete uniform hypergraph on n vertices, iteratively proceeds as follows. In every iteration, all edges of a copy of H chosen uniformly at random among all remaining copies are removed and once no copies of H remain, the process terminates. What can we say about the number R(n,H) of edges left after termination? While this process, which corresponds to the random greedy hypergraph matching process in an auxiliary hypergraph, is easy to formulate, showing that asymptotic estimates of the correct order of magnitude for R(n,H) hold with high probability turns out to be challenging. So far, ignoring the cases where H has at most one edge, such estimates were available for only a single choice of H, namely when H is a triangle. We extend this by proving analogous estimates for all cases where H comes from a large natural class of hypergraphs. As this class in particular includes all complete uniform hypergraphs, this confirms a major folklore conjecture in the area in a very strong form.