Seymour's second neighbourhood conjecture: random graphs and reductions (Q7027489)

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. Seymour's conjecture, which is closely tied to a particular case of the well-known conjecture of \textit{L. Caccetta} and \textit{R. Häggkvist} [in: Proceedings of the ninth southeastern conference on combinatorics, graph theory, and computing. Florida Atlantic University, Boca Raton, 1978. Winnipeg, MB: Utilitas Mathematica Publishing Inc. 181--187 (1978; Zbl 0406.05033)], has attracted a lot of attention due to its simplicity, yet it remains widely open. The statement has only been proved for some special classes of oriented graphs. Of particular interest is the case of tournaments, where the conjecture is known to hold. In this note, the authors focus primarily on the orientations of random graphs. They show that, for any fixed \(p \in [0, 1/2)\), a.a.s. every orientation of \(G(n, p)\) satisfies Seymour's conjecture as well as a related conjecture of \textit{B. D. Sullivan} [``A summary of problems and results related to the Caccetta-Haggkvist conjecture'', Preprint, \url{arXiv:math/0605646}]. This improves on a recent result of \textit{F. Botler} et al. [Discrete Math. 346, No. 12, Article ID 113583, 12 p. (2023; Zbl 1522.05418)], who showed that a.a.s. every orientation of \(G(n, p)\) contains a Seymour vertex whenever \(p<1/4\). The authors provide a first reduction by showing that \(p=1/2\) is a natural barrier for this problem, in the sense that for any fixed \(p\in (1/2, 1)\), Seymour's conjecture is equivalent to saying that, with probability bounded away from \(0\), every orientation of \(G(n, p)\) satisfies Seymour's conjecture. For a second reduction, the authors show that if any counterexamples exist to Seymour's conjecture, then there must exist arbitrarily large strongly-connected counterexamples with bounded minimum outdegree.