Hypergraph removal with polynomial bounds

The hypergraph removal lemma is one of the pertinent results of extremal combinatorics. It states that for every fixed integer \(k\), \(k\)-uniform hypergraph \(F\) and positive \(\varepsilon\), there is \(\delta=\delta(F,\varepsilon)>0\) so that if \(G\) is an \(n\)-vertex \(k\)-graph with at least \(\varepsilon^nk\) edge disjoint 1 copies of \(F\), then \(G\) contains \(\delta^nv(F)\) copies of \(F\). The main drawback of the hypergraph removal lemma is that it supplies very weak quantitative bounds. That is, for a general \(k\) graph \(F\), the function \(1/\delta(F,\varepsilon)\) grows like the \(k\)th Ackermann function. So it is natural to ask for which \(k\)-graphs \(F\) one can obtain more sensible bounds. The authors of this paper completely prove a conjecture raised by \textit{Y. Kohayakawa} et al. [Lect. Notes Comput. Sci. 2380, 1017--1028 (2002; Zbl 1057.68649)] that \textit{N. Alon}'s result [Random Struct. Algorithms 21, No. 3--4, 359--370 (2002; Zbl 1027.68095)] 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.

Cites work

Cited in

(1)

Posets are easily testable

This page was built for publication: Hypergraph removal with polynomial bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6973315)