2022/02/15 by Lior Gishboliner, A. Shapira, Gishboliner, Lior +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2202.07567
openalex publication_date 2022/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a fixed k-uniform hypergraph F, the F-removal lemma states that every hypergraph with few copies of F can be made F-free by the removal of few edges. Unfortunately, for general F, the constants involved are given by incredibly fast-growing Ackermann-type functions. It is thus natural to ask for which F one can prove removal lemmas with polynomial bounds. One trivial case where such bounds can be obtained is when F is k-partite. Alon proved that when k=2 (i.e. when dealing with graphs), only bipartite graphs have a polynomial removal lemma. Kohayakawa, Nagle and Rödl conjectured in 2002 that Alon's result can be extended to all k>2, namely, that the only k-graphs F for which the hypergraph removal lemma has polynomial bounds are the trivial cases when F is k-partite. In this paper we prove this conjecture.