The hypergraph removal process

2024/12/19 by Felix Joos, Joos, Felix, Marcus Kühn +1
Computer Science · #Algorithms and Data Compression #Web Data Mining and Analysis

paper · pdf · doi:10.48550/arxiv.2412.15039

Abstract

Let k≥ 2 and fix a k-uniform hypergraph F. Consider the random process that, starting from a k-uniform hypergraph H on n vertices, repeatedly deletes the edges of a copy of F chosen uniformly at random and terminates when no copies of F remain. Let R(H,F) denote the number of edges that are left after termination. We show that R(H,F)=n^{k-1/ρ± o(1)}, where ρ:=(| E(F)|-1)/(| V(F)| -k), holds with high probability provided that F is strictly k-balanced and H is sufficiently dense with pseudorandom properties. Since we may in particular choose F and H to be complete graphs, this confirms the major folklore conjecture in the area in a very strong form.

Related

• On the random greedy F-free hypergraph process
• The stripping process can be slow: part I
• Random K_k-removal algorithm
• On the decomposition of random hypergraphs
• Dense Peelable Random Uniform Hypergraphs