The Hypergraph Removal Process

Let k≥ 2 and fix a k-uniform hypergraph F. Consider the random greedy algorithm for generating a hypergraph without copies of F that, starting from a complete k-uniform hypergraph on n vertices, repeatedly deletes the edges of a copy of F chosen uniformly at random and terminates when no copies of F remain. This algorithm is a special case of the random greedy hypergraph matching algorithm and with an interest in the performance of this special case, we use Rn(F) to denote the number of edges that are left after termination. We show that Rn(F)=nk−1/ρ± o(1), where ρ:=(|E(F)|−1)/(|V(F)|−k), holds with high probability provided that F is strictly k-balanced. Since we may in particular choose F to be a complete hypergraph, this confirms the major folklore conjecture in the area in a very strong form and establishes new precise bounds characterizing the performance of this special case of the random greedy hypergraph matching algorithm.