Seymour's second neighborhood conjecture: pushing the universal constant beyond 0.715538 and the limit of the nested weighted-minimizer/CSP method

Seymour's second neighborhood conjecture (SSNC), posed in the early 1990s, asserts that every oriented digraph contains a vertex $u$ whose second out-neighborhood $N^{++}(u)$ is at least as large as its first out-neighborhood $N^{+}(u)$ (a 1-Seymour vertex). A quantitative relaxation asks for the largest constant $\gamma^*$ such that every oriented digraph contains a $\gamma^*$-Seymour vertex, where $d^{++}(u) \ge \gamma^* d^{+}(u)$. After two decades at the constant $\lambda = 0.657298\ldots$ of Chen–Shen–Yuster, Huang and Peng (2024) proved $\gamma^* \ge 0.715538\ldots$ by deriving, from a hypothetical counterexample, a finite quadratic constraint satisfaction problem over distance-class counts — built with a weighted out-degree minimizer and third-neighborhood bounds — and certifying its unsatisfiability; they further report that a nested three-minimizer variant of the CSP is already unsatisfiable at $\mu = 0.74530$ (Gurobi-certified), and ask whether the method can in principle reach $\mu = 1$. This problem asks: (a) rigorously establish that every oriented digraph has a $\mu$-Seymour vertex for some explicit $\mu > 0.715538$; and (b) determine whether the nested weighted-minimizer/finite-CSP framework can reach $\mu = 1$ — which would prove SSNC — or whether it has an intrinsic ceiling below 1.

Background

An oriented digraph is a directed graph without loops and without digons (at most one of the arcs $(u,v)$, $(v,u)$ is present). For a vertex $u$, the first out-neighborhood $N^{+}(u)$ is the set of out-neighbors of $u$, and the second out-neighborhood $N^{++}(u)$ is the set of vertices at directed distance exactly 2 from $u$; write $d^{+}(u)=|N^{+}(u)|$ and $d^{++}(u)=|N^{++}(u)|$. A vertex $u$ is a $\mu$-Seymour vertex if $d^{++}(u) \ge \mu\, d^{+}(u)$. Seymour's second neighborhood conjecture (SSNC), posed in the early 1990s and first recorded in print by Dean and Latka, asserts that every oriented digraph has a 1-Seymour vertex. The tournament case (edge-maximal oriented digraphs) was known as Dean's conjecture and was proved by Fisher via Farkas' lemma (a fundamental criterion from linear-programming duality), with a different proof by Havet and Thomassé using median orders (an ordering of tournament vertices that locally maximizes forward arcs); the conjecture is also known for oriented digraphs of minimum out-degree at most 6 (Kaneko and Locke, 2001) and, by a 2026 computer-assisted preprint of Sadhukhan, Sandeep, and Sen, for minimum out-degree exactly 7. Extremal constructions (sparse powers, disjoint unions, and iterative blow-ups of directed cycles) show that the constant 1 cannot be improved if SSNC holds, so the natural quantitative parameter is $\gamma^* = \inf_D \max_{u \in V(D)} d^{++}(u)/d^{+}(u)$ taken over oriented digraphs $D$ with minimum out-degree at least $1$ (a vertex of out-degree $0$ satisfies the inequality $d^{++}(u) \ge \mu\, d^{+}(u)$ vacuously for every $\mu$, so digraphs containing such a vertex impose no constraint on $\gamma^*$); SSNC is exactly the claim $\gamma^* \ge 1$. A vertex of minimum out-degree is always a $\frac{1}{2}$-Seymour vertex. Chen, Shen, and Yuster (2003) improved this: every oriented digraph has a $\lambda$-Seymour vertex with $\lambda = 0.657298\ldots$, the unique real root of $2x^3 + x^2 - 1 = 0$, and they indicate $0.67815\ldots$ by refined arguments. This stood as the best constant for over two decades until Huang and Peng (2024) proved that every oriented digraph has a $\gamma$-Seymour vertex with $\gamma = 0.715538\ldots$, the unique real root in $[0,1]$ of $8x^5 + 4x^4 - 12x^3 - 7x^2 + 2x + 4 = 0$. Their method works by contradiction: in an edge-minimal $\mu$-counterexample (a digraph with no $\mu$-Seymour vertex, minimal under edge deletion) they first bound the third neighborhood, $d^{+++}(u) \le \mu\, d^{++}(u)$, then select two vertices — $u$ of globally minimum out-degree, and $v$ a weighted out-degree minimizer in $X_1 = N^{+}(u)$, i.e. a vertex of $X_1$ minimizing $w\, d^{+}_{X_1}(v) + d^{+}_{X_2}(v)$ for a weight $w \ge 1$, where $X_2 = N^{++}(u)$ — and partition the reachable vertices into cells $X_{ij} = \{y : \mathrm{dist}^+(u,y)=i, \mathrm{dist}^+(v,y)=j\}$. The cell counts $x_{ij} = |X_{ij}|$ must then satisfy a finite quadratic constraint satisfaction problem (CSP) combining the Seymour violations at $u$ and $v$, the minimum-degree conditions, and a double count of the arcs leaving the low cells; for $\mu = \gamma$ and a suitable $w$, Huang and Peng show this CSP unsatisfiable through an explicit polynomial identity with positive coefficients and a negative discriminant. They also show $\gamma$ is optimal within the constraints their analysis uses. In the concluding remarks they observe that nesting the construction one level deeper — selecting a further weighted out-degree minimizer $v_2$ inside $X_{11}$ and refining to cells $X_{ijk}$ — yields a CSP that is already unsatisfiable at $\mu = 0.74530$ with optimally chosen weights, as certified by rigorous bounds from the Gurobi optimization software, but they judge a fully self-contained, human-checkable written proof of this 'excessively laborious'. They then pose the two questions considered here: whether such longer sequences of nested weighted minimizers can push the constant further in a rigorous proof, and whether this extremal-sequence/finite-CSP strategy can in principle reach $\mu = 1$ — which would prove SSNC, since it would exclude a hypothetical $1$-counterexample whose cell counts must satisfy the derived constraints — or faces a theoretical limit below 1. The authors note that the median-order proof of Dean's conjecture can also be loosely placed under this framework, so the source's 'approach' is broader than the specific nested weighted-minimizer CSP family. (A third, looser suggestion — applying the same toolkit directly to the Caccetta–Häggkvist conjecture on directed triangles in digraphs of large minimum degree, where their constant already yields a corollary at minimum degree $n/(2+\gamma) \approx 0.3683n$, short of the standing $0.3465n$ record — concerns a different conjecture and is recorded as a related direction, not part of this problem.)

Problem Statement

Let $\gamma^* = \inf_D \max_{u \in V(D)} d^{++}(u)/d^{+}(u)$ over all finite oriented digraphs $D$ with minimum out-degree at least $1$ (equivalently, the supremum of $\mu$ such that every oriented digraph contains a $\mu$-Seymour vertex; a vertex of out-degree $0$ satisfies the defining inequality vacuously, so only sink-free digraphs constrain $\gamma^*$). Seymour's second neighborhood conjecture asserts $\gamma^* \ge 1$, and extremal blow-up constructions give $\gamma^* \le 1$; currently $0.715538\ldots \le \gamma^*$ (Huang–Peng, 2024). Resolve the open questions posed in the concluding remarks of that work, whose common objective is to determine how far the constant, and the extremal-sequence/finite-CSP method behind it, can be pushed:

(a) Prove rigorously that $\gamma^* > 0.715538\ldots$; in particular, decide whether the nested three-minimizer constraint system — obtained by selecting, in an edge-minimal counterexample, a minimum out-degree vertex $u$, a weighted out-degree minimizer $v \in N^{+}(u)$, a further weighted minimizer $v_2 \in X_{11}$, and deriving the quadratic constraints satisfied by the refined cell counts $x_{ijk} = |X_{ijk}|$ — is unsatisfiable at $\mu = 0.74530$ (as the source's Gurobi computation indicates) or beyond.

(b) Determine whether the nested weighted-minimizer/finite-CSP framework can, in principle, reach $\mu = 1$ — which would prove Seymour's second neighborhood conjecture for oriented digraphs — or whether there is an intrinsic ceiling $\mu_c < 1$ imposed by the method's structure (i.e., for every finite nesting depth and every choice of weighting factors, the derivable constraint system admits a feasible real solution whenever $\mu > \mu_c$); if such a ceiling exists, bound or identify it. The source poses this limit question more broadly, for any approach that 'chooses a sequence of vertices that altogether satisfies some extremal properties' and derives a contradiction provided all vertices in the sequence violate the $\mu$-Seymour condition; the parenthetical above describes the ceiling for the concrete nested weighted-minimizer/CSP family, the instance in which the question is currently posed. The reach-or-ceiling claim is made relative to a fixed framework — a family of constraint systems derivable at each nesting depth, with a nesting rule by which each successive weighted out-degree minimizer and the resulting refined cell-count constraints are derived, and with an admissible family of weighting factors — that contains the source's system for $\gamma = 0.715538\ldots$ and its nested three-minimizer refinement as instances.

A finite oriented digraph $D$ with minimum out-degree at least $1$, given together with a single constant $\mu < 1$ such that every vertex $v$ of $D$ satisfies $d^{++}(v) < \mu\, d^{+}(v)$, would refute SSNC and cap $\gamma^*$ from above, resolving the ceiling question in the negative direction.

References

1. Hao Huang and Fei Peng. An improved bound on Seymour's second neighborhood conjecture. arXiv:2412.20234, 2024. https://arxiv.org/abs/2412.20234
2. Guantao Chen, Jian Shen, and Raphael Yuster. Second neighborhood via first neighborhood in digraphs. Annals of Combinatorics 7 (2003) 15–20. DOI 10.1007/s000260300001. https://doi.org/10.1007/s000260300001
3. 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%3C43::aid-jgt4%3E3.0.co;2-k
4. Frédéric Havet and 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%3C244::aid-jgt2%3E3.0.co;2-h
5. Yoshihiro Kaneko and Stephen C. Locke. The minimum degree approach for Paul Seymour's distance 2 conjecture. Congressus Numerantium 148 (2001) 201–206. zbMATH 1743979. https://zbmath.org/?q=an%3A1743979
6. Nathaniel Dean and Brenda J. Latka. Squaring the tournament — an open problem. Congressus Numerantium 109 (1995) 73–80. zbMATH 1185310. https://zbmath.org/?q=an%3A1185310
7. Arpan Sadhukhan, R. B. Sandeep, and Sagnik Sen. A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7. arXiv:2606.30588, 2026. https://arxiv.org/abs/2606.30588
8. Yandong Bai, Binlong Li, and Boram Park. Towards a strengthening of the second neighborhood conjecture. arXiv:2607.18047, 2026. https://arxiv.org/abs/2607.18047
9. Jake Brukhman. A dense-case theorem for Seymour's second neighborhood conjecture. arXiv:2608.11530, 2026. https://arxiv.org/abs/2608.11530
10. Charles N. Glover. A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order. arXiv:2501.00614, 2024 (revised through v14, May 2026). https://arxiv.org/abs/2501.00614