论文标题
规定大小和超级的子数字
Subdigraphs of prescribed size and outdegree
论文作者
论文摘要
在2006年，Noga Alon提出了以下开放问题：是否存在绝对常数$ c> 0 $，以至于每$ 2N $ -VERTEX DIGRAPH具有最低级别的最低级别的$ n $ n $ vertex子digraph，最低$ n $ vertex subdigraph，至少$ \ frac {s} {s} {2} {2} {2} {2} - c $？在本说明中，我们通过表明$ n $的任意价值为$ 2N $ -VERTEX锦标赛，最低限度$ s = n-1 $，其中每一个$ n $ n $ vertex子最多都包含一个超级级别的顶点$ \ frac {s} {2} - \ left（\ frac {1} {2} {2}+o（1）\ right）\ log_3（s）$。
In 2006, Noga Alon raised the following open problem: Does there exist an absolute constant $c>0$ such that every $2n$-vertex digraph with minimum out-degree at least $s$ contains an $n$-vertex subdigraph with minimum out-degree at least $\frac{s}{2}-c$ ? In this note, we answer this natural question in the negative, by showing that for arbitrarily large values of $n$ there exists a $2n$-vertex tournament with minimum out-degree $s=n-1$, in which every $n$-vertex subdigraph contains a vertex of out-degree at most $\frac{s}{2}-\left(\frac{1}{2}+o(1)\right)\log_3(s)$.
