Seymour's second neighbourhood conjecture: random graphs and reductions

A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second outneighbourhood is at least as large as its outneighbourhood. In this short note we show that, for any fixed , a.a.s. every orientation of satisfies Seymour's conjecture (as well as a related conjecture of Sullivan). This improves on a recent result of Botler, Moura and Naia. Moreover, we show that is a natural barrier for this problem, in the following sense: for any fixed , Seymour's conjecture is actually equivalent to saying that, with probability bounded away from 0, every orientation of satisfies Seymour's conjecture. This provides a first reduction of the problem. For a second reduction, we consider minimum degrees and show that, if Seymour's conjecture is false, then there must exist arbitrarily large strongly‐connected counterexamples with bounded minimum outdegree. Contrasting this, we show that vertex‐minimal counterexamples must have large minimum outdegree.