Seymour's celebrated second neighborhood conjecture, now more than thirty years old, states that in every oriented digraph, there is a vertex $u$ such that the size of its second out-neighborhood $N^{ ++}(u)$ is at least as large as that of its first out-neighborhood $N^+(u)$. In this paper, we prove the existence of $u$ for which $|N^{ ++}(u)| \ge 0.715538 |N^+(u)|$. This result provides the first improvement to the best known constant factor in over two decades.
Categories: math.CO