论文标题
用多项式边界去除超图
Hypergraph removal with polynomial bounds
论文作者
论文摘要
鉴于固定的$ k $均匀的超图$ f $，$ f $ elemoval Lemma指出，每个副本的$ f $都可以通过删除几个边缘来制成$ f $ $ f $。不幸的是，对于一般$ f $，所涉及的常数是由不可思议的快速增长的Ackermann型功能提供的。因此，很自然地询问哪种$ f $可以证明具有多项式界限的去除诱饵。可以获得此类界限的一种微不足道的情况是$ f $是$ k $ - 分支机构。 Alon证明，当$ k = 2 $（即在处理图时）时，只有两分图具有多项式删除引理。 Kohayakawa，Nagle和Rödl于2002年提出，Alon的结果可以扩展到所有$ k> 2 $，即，唯一的$ k $ -graphs $ f $是当$ f $ f $ k $ k $ -partite时，HyperGraph emoval Lemma具有多项式界限是微不足道的情况。在本文中，我们证明了这个猜想。
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.
