论文标题
绝对可避免的订单大小对在超图中
Absolutely avoidable order-size pairs in hypergraphs
论文作者
论文摘要
对于固定整数$ r \ ge 2 $，我们称之为一对$（m，f）$的整数，$ m \ geq 1 $，$ 0 \ leq f \ leq f \ leq \ binom {m} {r} {r} $，$ $ $ $ $ $ $ $ $ $ $可避免的$ \ binom {n} {r} $在$ n $ VERTICES上有一个$ r $均匀的超图和$ e $边缘，其中不包含$ m $ pertices和$ f $ edges上的诱导子hypergraph。显然，某些对不可避免，例如$（m，0）$绝对无法避免，因为至少$ m $顶点上的任何足够稀疏的超图包含$ M $ M $顶点的独立集。 Here we show that for any $r\ge 3$ and $m \ge m_0$, either the pair $(m, \lfloor\binom mr/2\rfloor)$ or the pair $(m, \lfloor\binom{m}{r}/2\rfloor-m-1)$ is absolutely avoidable.接下来，按照Erdős，Füredi，Rothschild和Sós的定义，我们将一对$（m，f）$的$密度$定义为$σ_R（m，f）= \ limsup_ {n \ to \ in \ to \ infty} \ infty} \ frac {先生} $。我们表明，对于$ r \ ge 3 $，大多数对$（m，f）$满足$σ_r（m，f）= 0 $，而对于$ m> r $，则没有一对密度1的$（m，f）$ 1。
For fixed integer $r\ge 2$, we call a pair $(m,f)$ of integers, $m\geq 1$, $0\leq f \leq \binom{m}{r}$, $absolutely$ $avoidable$ if there is $n_0$, such that for any pair of integers $(n,e)$ with $n>n_0$ and $0\leq e\leq \binom{n}{r}$ there is an $r$-uniform hypergraph on $n$ vertices and $e$ edges that contains no induced sub-hypergraph on $m$ vertices and $f$ edges. Some pairs are clearly not absolutely avoidable, for example $(m,0)$ is not absolutely avoidable since any sufficiently sparse hypergraph on at least $m$ vertices contains independent sets on $m$ vertices. Here we show that for any $r\ge 3$ and $m \ge m_0$, either the pair $(m, \lfloor\binom mr/2\rfloor)$ or the pair $(m, \lfloor\binom{m}{r}/2\rfloor-m-1)$ is absolutely avoidable. Next, following the definition of Erdős, Füredi, Rothschild and Sós, we define the $density$ of a pair $(m,f)$ as $σ_r(m,f) = \limsup_{n \to \infty} \frac{|\{e : (n,e) \to (m,f)\}|}{\binom mr}$. We show that for $ r\ge 3$ most pairs $(m,f)$ satisfy $σ_r(m,f)=0$, and that for $m > r$, there exists no pair $(m,f)$ of density 1.
