我现在卡在Alon和Spencer《概率方法》里的这道习题上了，完全没头绪，想求点思路提示——不知道该用什么技巧来“逼出”偶长度的有向简单环：

Show that there is a finite $n_0$ such that any directed graph on $n>n_0$ vertices in which each outdegree is at least $\log_2(n)-\frac{1}{10}\log_2\log_2n$ contains an even simple directed cycle.

我目前的尝试（卡壳了） #

看了一些相关讨论后我有了个初步想法，但推进不下去：

• 把每个顶点随机分到两个集合A和B中的一个，定义二分有向子图$S$只包含A、B之间的跨集合边
• 计算后发现，$S$中出度为0的顶点的期望数量至多是 $n{\frac{1}{2}}^{\log_2n-\log_2\log_2n} = \log_2n$
• 但这个结果不够强，我试过删掉$S$中出度为0的顶点，但还是没法继续推导，不知道怎么把这个子图和偶环的存在性关联起来

有没有大佬能给点方向？比如是不是要调整随机染色的方式，或者结合其他概率方法的技巧？

备注：内容来源于stack exchange，提问作者ratatouille