论文标题
在程度条件下超图的独立性数量
Independence number of hypergraphs under degree conditions
论文作者
论文摘要
Ajtai等人的众所周知结果。从1982年开始，$ n $顶点上的每一个$ k $ -graph $ h $至少有五个，平均度$ t^{k-1} $包含一组独立的尺寸$ c n（\ log t）^{1/（k-1/（k-1）}/t $，对于某些$ c> 0 $。在本文中，我们表明，在较弱的条件下可以找到一组相同大小的独立集，从而使某些长度为2、3和4的周期。 我们的工作是由Lo和Zhao的问题引起的，他要求$ k \ ge 4 $，当$ n $ vertices上的独立设置$ k $ -graph $ h $中的大小必定会有其最大$（k-2）$（k-2）$ $ $ $ $Δ__{k-2 {k-2}（k-2}（h）\ le dn $。 （关于$（k-1）$ - 学位的相应问题，由Kostochka，Mubayi和Varstraëte[随机结构和算法44，224--239，2014]解决。 （\ frac nd \ log \ log \ frac nd）^{1/（k-1）} $，在其他条件下，一组独立的尺寸$ c（\ frac nd \ log \ frac \ frac nd）^{1/（k-1）} $。前断言为$（k-2）$ - 学位的turán密度提供了全新的上限。
A well-known result of Ajtai et al. from 1982 states that every $k$-graph $H$ on $n$ vertices, with girth at least five, and average degree $t^{k-1}$ contains an independent set of size $c n (\log t)^{1/(k-1)}/t$ for some $c>0$. In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3 and 4. Our work is motivated by a problem of Lo and Zhao, who asked for $k\ge 4$, how large of an independent set a $k$-graph $H$ on $n$ vertices necessarily has when its maximum $(k-2)$-degree $Δ_{k-2}(H)\le dn$. (The corresponding problem with respect to $(k-1)$-degrees was solved by Kostochka, Mubayi, and Varstraëte [Random Structures & Algorithms 44, 224--239, 2014].) In this paper we show that every $k$-graph $H$ on $n$ vertices with $Δ_{k-2}(H)\le dn$ contains an independent set of size $c (\frac nd \log\log \frac nd)^{1/(k-1)}$, and under additional conditions, an independent set of size $c (\frac nd \log \frac nd)^{1/(k-1)}$. The former assertion gives a new upper bound for the $(k-2)$-degree Turán density of complete $k$-graphs.
