The unresolved density regimes for Seymour's second neighbourhood conjecture on $G(n,p)$: the critical case $p=1/2$ and the $p\to 1$ regime

Seymour's second neighbourhood conjecture (SNC) asserts that every oriented graph has a vertex whose second outneighbourhood is at least as large as its outneighbourhood. Espuny Díaz, Girão, Granet and Kronenberg (2024) proved that, for every fixed $p<1/2$, asymptotically almost surely every orientation of the binomial random graph $G(n,p)$ contains such a vertex, and showed that $p=1/2$ is a natural barrier: for fixed $p\in(1/2,1)$ the statement that all orientations of $G(n,p)$ a.a.s. contain a Seymour vertex is equivalent to the full conjecture. The problems the authors explicitly posed in their concluding section remain open: whether a.a.s. every orientation of $G(n,1/2)$ contains a Seymour vertex; the behaviour for densities $p=1-o(1)$ approaching the (resolved) tournament case; and whether the reduction for $p>1/2$ provides a useful avenue for tackling the full conjecture.

Background

An oriented graph is a directed graph obtained by orienting each edge of a simple undirected graph, so that between any two vertices there is at most one arc. For a vertex $v$, its outneighbourhood $N_1(v)$ (also written $N^+(v)$) is the set of vertices $w$ with an arc from $v$ to $w$, and its second outneighbourhood $N_2(v)$ (also written $N^{++}(v)$) is the set of vertices outside $\{v\}\cup N_1(v)$ that receive an arc from some vertex of $N_1(v)$. A Seymour vertex is a vertex with $|N_2(v)|\ge|N_1(v)|$. Around 1990, Seymour conjectured that every oriented graph has a Seymour vertex; the conjecture was popularized through Sullivan's 2006 survey of problems related to the Caccetta–Häggkvist conjecture (the assertion that every digraph on $n$ vertices with minimum outdegree at least $r$ contains a directed cycle of length at most $\lceil n/r\rceil$), to which it is closely tied. The conjecture is notorious for its simplicity and remains open; it is known for tournaments (orientations of complete graphs), first proved by Fisher (1996) via Dean's conjecture and reproved by Havet and Thomassé (2000) using median orders (vertex orderings that maximize the number of arcs pointing forward), and for various special classes and low minimum outdegree (Kaneko and Locke in 2001 settled minimum outdegree at most 6; a 2026 computer-assisted preprint of Sadhukhan, Sandeep and Sen handles minimum outdegree 7).

Sullivan also proposed variants and strengthenings; the variant treated here (Conjecture 6.6 of the survey) asserts that every oriented graph has a Sullivan vertex, i.e. a vertex $v$ with $|N_2^+(v)|\ge|N^-(v)|$, where $N^-(v)$ is the inneighbourhood of $v$ (note $N_2^+(v)$ and $N^-(v)$ may intersect).

For random inputs, one distinguishes a random orientation of $G(n,p)$ — where the binomial random graph $G(n,p)$ has each edge present independently with probability $p$ and each present edge oriented uniformly at random — from the much stronger all-orientations property, requiring every orientation of the random graph to contain the desired vertex. Cohn, Godbole, Wright Harkness and Zhang showed that a random orientation of $G(n,p)$ a.a.s. contains a Seymour vertex for a wide range of $p$; here a.a.s. (asymptotically almost surely) means with probability tending to 1 as $n\to\infty$. Botler, Moura and Naia (2023) proved the all-orientations property for fixed $p<1/4$, and for $p\in[1/2,2/3)$ for orientations with minimum outdegree $\Omega(\sqrt n)$.

Espuny Díaz, Girão, Granet and Kronenberg improved this to every fixed $p<1/2$ (for both Seymour's and Sullivan's variants), and established two reductions showing that $p=1/2$ is a genuine barrier. First (their Theorem 3), for any fixed $p\in(1/2,1)$: if SNC is false, then a.a.s. there is an orientation of $G(n,p)$ with no Seymour vertex; hence proving the all-orientations property a.a.s. for any single fixed $p>1/2$ would prove SNC in full, so the random-graph statement above $1/2$ is exactly as hard as the conjecture itself. Second, on counterexample structure: if SNC is false, then for every function $d(n)=\omega(1)$ there are arbitrarily large strongly-connected counterexamples with minimum outdegree below $d$ (their Proposition 5), while on the other hand every vertex-minimal counterexample (a counterexample that is minimal under deletion of vertices) must satisfy $\delta^+(D)>\sqrt{|V(D)|}$, where $\delta^+(D)$ denotes the minimum outdegree (their Proposition 4). The paper's concluding section explicitly poses what its methods leave open, and the threads below record exactly those questions.

Problem Statement

Resolve the open regimes of the all-orientations version of Seymour's second neighbourhood conjecture on the binomial random graph $G(n,p)$, as posed in the concluding section of Espuny Díaz–Girão–Granet–Kronenberg (2024). The common objective is to complete the density landscape of the property that every orientation of $G(n,p)$ contains a Seymour vertex — recall that a Seymour vertex is a vertex $v$ with $|N_2(v)|\ge|N_1(v)|$, where $N_1(v)$ and $N_2(v)$ are the outneighbourhood and second outneighbourhood of $v$. The threads below are the pieces of that landscape the source paper's reductions leave undetermined. The threads are not independent — thread (3) is equivalent to Seymour's conjecture in full, so a proof of that conjecture settles all three at once, while a refutation settles thread (3) alone. Each thread is posed as an open question in the paper's concluding section. Concretely:

(1) The critical density $p=1/2$. Determine whether a.a.s. (i.e. with probability tending to 1 as $n\to\infty$) every orientation of $G(n,1/2)$ contains a Seymour vertex. Neither the $p<1/2$ results nor the $p>1/2$ reduction applies at $p=(1\pm o(1))/2$.

(2) The regime approaching tournaments. For sequences $p(n)=1-o(1)$ with $p(n)<1$, determine whether a.a.s. every orientation of $G(n,p(n))$ contains a Seymour vertex. The endpoint $p=1$ (tournaments) is resolved by Fisher and by Havet–Thomassé; the paper's methods do not treat $p\to 1$.

(3) Any fixed density above the barrier. Determine whether, for at least one fixed $p\in(1/2,1)$, the unconditional statement holds that a.a.s. every orientation of $G(n,p)$ contains a Seymour vertex — that is, whether the paper's reduction provides a useful avenue for tackling the full conjecture, as its concluding section asks. By Theorem 3 of the source paper this is equivalent to Seymour's second neighbourhood conjecture in full generality, so this thread is exactly as hard as the conjecture itself; an answer here either proves Seymour's conjecture or refutes it, in which case a.a.s. counterexample orientations exist throughout $(1/2,1)$.

References

1. Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg, 'Seymour's second neighbourhood conjecture: random graphs and reductions', Random Structures & Algorithms 66(1) (2024/2025), DOI: 10.1002/rsa.21251; arXiv:2403.02842, https://arxiv.org/abs/2403.02842
2. Fábio Botler, Phablo F. S. Moura, Tássio Naia, 'Seymour's second neighborhood conjecture for orientations of (pseudo)random graphs', Discrete Mathematics 346(12) (2023), 113583, DOI: 10.1016/j.disc.2023.113583; arXiv:2211.06540, https://arxiv.org/abs/2211.06540
3. Blair Dowling Sullivan, 'A Summary of Problems and Results related to the Caccetta-Häggkvist Conjecture' (2006), arXiv:math/0605646, https://arxiv.org/abs/math/0605646
4. David C. Fisher, 'Squaring a tournament: A proof of Dean's conjecture', Journal of Graph Theory 23(1) (1996), 43–48, DOI: 10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K, https://doi.org/10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K
5. Frédéric Havet, Stéphan Thomassé, 'Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture', Journal of Graph Theory 35(4) (2000), 244–256, DOI: 10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H, https://doi.org/10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H
6. Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Shujing Wang, Anders Yeo, Yacong Zhou, 'On Seymour's and Sullivan's Second Neighbourhood Conjectures' (2023), arXiv:2306.03493, https://arxiv.org/abs/2306.03493
7. Hao Huang, Fei Peng, 'An improved bound on Seymour's second neighborhood conjecture' (2024), arXiv:2412.20234, https://arxiv.org/abs/2412.20234
8. Yilun Shang, 'Asymptotic confirmation of the second neighborhood conjecture on inhomogeneous random graphs', Periodica Mathematica Hungarica (2026), DOI: 10.1007/s10998-026-00736-7, https://doi.org/10.1007/s10998-026-00736-7
9. Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen, 'A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7' (2026), arXiv:2606.30588, https://arxiv.org/abs/2606.30588
10. Yandong Bai, Binlong Li, Boram Park, 'Towards a strengthening of the second neighborhood conjecture' (2026), arXiv:2607.18047, https://arxiv.org/abs/2607.18047
11. Jake Brukhman, 'A dense-case theorem for Seymour's second neighborhood conjecture' (2026), arXiv:2608.11530, https://arxiv.org/abs/2608.11530
12. Krystal Guo, Ross J. Kang, Gabriëlle Zwaneveld, 'Seymour-tight orientations' (2026), arXiv:2603.29626, https://arxiv.org/abs/2603.29626
13. Stanisław M. S. Halkiewicz, 'Split-Twin Extensions Preserving Seymour Vertices' (2026), arXiv:2601.21563, https://arxiv.org/abs/2601.21563
14. Ayman El Zein, 'A Note on Sullivan's Second Neighborhood Conjecture', Graphs and Combinatorics 41 (2025), DOI: 10.1007/s00373-025-02908-7, https://doi.org/10.1007/s00373-025-02908-7
15. Charles N. Glover, 'A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order' (2024/2025), arXiv:2501.00614, https://arxiv.org/abs/2501.00614
16. Zachary Cohn, Anant Godbole, Elizabeth Wright Harkness, Yiguang Zhang, 'The number of Seymour vertices in random tournaments and digraphs', Graphs and Combinatorics 32(5) (2016), 1805–1816, DOI: 10.1007/s00373-015-1672-9, https://doi.org/10.1007/s00373-015-1672-9
17. Yoshihiro Kaneko, Stephen C. Locke, 'The minimum degree approach for Paul Seymour's distance 2 conjecture', Congressus Numerantium 148 (2001), 201–206, Zbl 0996.05042, https://zbmath.org/?q=an%3A0996.05042