An improved bound on Seymour's second neighborhood conjecture

Abstract

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.

arXiv comment13 pages