First and second out-neighborhoods in oriented graphs

Source and verification

This article explains family 173 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ First and second out-neighborhoods

An oriented graph is a finite directed graph with no loops and no pair of opposite arcs. It need not have an arc between every pair of vertices. For a vertex $v$, let $N_1^{+}(v)$ be its out-neighbors, and let $N_2^{+}(v)$ consist of vertices at directed distance exactly two from $v$.

Thus $N_2^{+}(v)$ excludes both $v$ and the first out-neighbors. A vertex reached by several two-step paths is counted only once.

Manuscript claim

Every nonempty finite oriented graph has a vertex $v$ with $|N_2^{+}(v)|\ge |N_1^{+}(v)|$. No connectivity or degree assumption is required. (OpenAI, 2026)

This is Seymour’s second-neighborhood conjecture. A sink satisfies it immediately, with both sides zero. The nontrivial case has positive outdegree everywhere. A directed triangle also gives equality at each vertex: one first neighbor and one distinct second neighbor.

Counting directed paths instead of distinct second neighbors would miss the issue. Many paths can merge at the same endpoint, and some endpoints may already be first neighbors.

🏷️ A set-image formulation

For a vertex set $S$, define its forward image

$$\begin{array}{c}F(S)\\ =\{y:x\to y\text{ for some }x\in S\}.\end{array}$$

This operation does not subtract $S$. Because an oriented graph has no two-step return to its starting vertex,

$$N_2^{+}(v)=F^2(\{v\})\setminus F(\{v\}).$$

Suppose a counterexample exists, and choose one first with minimum vertex count and then with minimum arc count. The source’s edge-deletion reduction gives, for every nonempty proper $S$,

$$|F^2(S)\setminus F(S)|<|F(S)\setminus S|.$$

This is stronger than simply applying the supposed failure at individual vertices. It controls arbitrary subsets and uses both minimality choices.

The manuscript next replaces each vertex by a sufficiently large transitive tournament, an orientation of a complete graph induced by a linear order. The resulting graph $G$ has positive indegree at every vertex and satisfies

$$|U|+|F_G^2(U)|<2|F_G(U)|$$

for every nonempty proper $U$. The rest of the argument proves that no finite graph arising in this way can have this strict concavity property for all subsets.

🏷️ Compatible families of ordered pairs

Work in $V(G)\times V(G)$. Advancing the first coordinate of a pair means following an arc of $G$ in that coordinate and keeping the second fixed; advancing the second coordinate is defined similarly.

Take two families of pairs, a left family and a right family. Call them compatible if the first-coordinate image of the left family is disjoint from the second-coordinate image of the right family. Require both families to contain the diagonal pairs $(v,v)$. The absence of opposite arcs makes the diagonal families compatible, so admissible choices exist.

A point outside both coordinate images is uncovered. Write $M$ for the sum of the sizes of the two families and $d$ for the number of uncovered points. Among all compatible choices containing the diagonal, maximize

$$M+d.$$

The diagonal and positive indegree conditions ensure that the columns of the left family and the rows of the right family are nonempty proper subsets. The strict concavity inequality therefore applies to each. Taking complements of second iterated images produces prospective new families whose combined size exceeds $M+2d$.

These larger families need not be compatible. Repairing that failure without spending the entire gain is the central problem.

🏷️ A pruning cost paid by uncovered points

The source proves a pruning lemma for arbitrary finite binary relations. It deletes conflicting members while preserving specified conflict-free members, which here include the diagonal. Let $d^{\prime }$ be the number of points uncovered by the retained families after pruning.

In the application, the deletion cost is at most $d+d^{\prime }$. Thus the new objective is strictly greater than

$$M+2d-(d+d^{\prime })+d^{\prime }=M+d,$$

contradicting maximality. The cancellation shows why the lemma must use the number of points uncovered after deletion. A bound expressed only in terms of the old uncovered set need not support this argument.

The pruning proof represents conflicts by an augmented bipartite graph and bounds a matching in it. Advancing the two coordinates in opposite orders yields two factorizations of the same matrix through different index sets. A simultaneous maximum-rank choice makes the corresponding kernels control the matching size. This is the new finite-dimensional ingredient; the extremal calculation alone would be incomplete without it.

🏷️ Scope of the conclusion

The paper also derives weighted versions through established equivalences. Two different quantifier orders arise: for every nonnegative vertex weighting there exists a suitable vertex, and there exists a probability weighting for which every vertex is suitable. They should not be conflated.

The unweighted theorem already follows from the chain described above: a minimal counterexample yields strict subset concavity; that concavity enlarges a compatible pair of families; the pruning estimate converts the enlargement into a strict improvement of a finite extremal objective. Each reduction is necessary to make the final contradiction apply to general oriented graphs rather than only tournaments.

🏷️ Key steps and proof outlines

The pruning problem needs an augmented graph

For left pairs $(p,j)$ and right pairs $(i,s)$, a conflict means $p\to i$ and $s\to j$. Let $Z$ contain the output corners $(i,j)$ of conflicts and $H$ their opposite corners $(p,s)$. The pruning lemma seeks conflict-free subfamilies with deletion cost at most $|H|$ plus the number of points of $Z$ left uncovered afterward. (OpenAI, 2026)

Build a bipartite graph with original left and right members and two separate copies $Z_L,Z_R$ of $Z$. Join conflicting original members, and join each original member to the opposite copy of every point it covers. One conflict contributes the path below; distinct conflicts may share vertices.

flowchart TB
  ZL["output corner in Z left"] --- C["right member (i,s)"]
  C --- R["left member (p,j)"]
  R --- ZR["output corner in Z right"]

Suppose this graph has a vertex cover $K$ of size at most $|Z|+|H|$. Delete its original members. If $q$ output corners become uncovered, each of the remaining $|Z|-q$ corners has a surviving covering member, so the opposite copy of that corner must belong to $K$. Hence at most

$$|K|-(|Z|-q)\le |H|+q$$

original members were deleted. Initially conflict-free members are isolated even in the augmented graph and can be retained. Thus the exact desired deletion bound reduces to bounding a maximum matching.

Two coordinate orders give the same matrix

Choose a maximum matching with as few original-original edges as possible. Let $k$ count those edges, and let $\ell ,t$ count its original-to-copy edges on the two sides. The latter matchings are individually maximum in their respective subgraphs: an augmenting path would either enlarge the whole matching or replace an original-original edge and decrease $k$.

Using coefficients $a_{pi}$ and $b_{sj}$ on allowed arrows, define linear maps along the two routes

$${\mathbb{R}}^{\mathcal{R}}\stackrel{L}{\to }{\mathbb{R}}^Z\stackrel{N}{\to }{\mathbb{R}}^{\mathcal{C}},{\mathbb{R}}^{\mathcal{R}}\stackrel{B}{\to }{\mathbb{R}}^H\stackrel{A}{\to }{\mathbb{R}}^{\mathcal{C}}.$$

The first route changes the first coordinate forward and then the second backward; the second reverses that order. For each conflicting input-output pair, both matrix products have the single contribution $a_{pi}{b}_{sj}$. Thus $NL=AB$ exactly.

The source chooses one coefficient assignment with $\mathrm{rank}L=\ell$, $\mathrm{rank}N=t$, and the needed local support ranks maximal simultaneously. For each requirement choose a minor that is a nonzero polynomial in the coefficients. Their finite product is still nonzero, even when variables are shared, so one real assignment makes all requirements hold.

A maximum-rank support forces complementary kernel zeros

Kernel lemma

If $D$ has maximum rank among matrices with a prescribed support, then $x_j{y}_s=0$ at every allowed entry whenever $Dx=0$ and $D^{\mathsf{T}}y=0$.

If $x_j{y}_s\ne 0$, perturb only that entry: $D_{\tau }=D+\tau e_s{e}_j^{\mathsf{T}}$. Then $D_{\tau }x=\tau x_j{e}_s$, so $e_s$ belongs to the new image. Every old image vector also belongs to it because $Dw=D_{\tau }w-\tau w_j{e}_s$. Yet $e_s$ is outside the old image, since the left-kernel vector $y$ has $y_s\ne 0$. Rank would increase, a contradiction.

Apply this lemma to the source’s coordinate blocks. It implies that a vector in $\ker B$ must vanish at each of the $k$ original left endpoints, by pairing it with a suitable vector in $\ker N^{\mathsf{T}}$ equal to one at the matched right endpoint. Meanwhile the basis columns of $L$ allow each original left endpoint to be lifted to a vector $u^r\in \ker L$ with its own endpoint coordinate one and the others zero. The vectors $B{u}^r$ are independent: a linear relation would put their corresponding linear combination in $\ker B$, forcing every coefficient to vanish.

Since $AB{u}^r=NL{u}^r=0$, these $k$ vectors lie in $\ker A$. Rank-nullity now gives

$$|H|\ge k+\mathrm{rank}(NL)\ge k+\ell +t-|Z|.$$

The matching has size $k+\ell +t\le |Z|+|H|$. The alternating-path proof of the bipartite matching-cover theorem supplies the required cover and hence the pruning.

The extremal objective absorbs the final uncovered set

In the graph reduction, take compatible pair families containing the diagonal and maximizing $M+d$, where $M$ is their total size and $d$ counts uncovered points. Positive indegrees ensure that each relevant row and column is nonempty and proper, so strict subset concavity applies. Complements of the second coordinate images then have total size greater than $M+2d$.

The diagonal remains conflict-free in these larger families, and their opposite conflict corners lie in the old uncovered set, so $|H|\le d$. Pruning costs at most $d+d^{\prime }$, where $d^{\prime }$ is the new uncovered count. The new objective therefore exceeds $M+2d-(d+d^{\prime })+d^{\prime }=M+d$, contradicting maximality. This is why the pruning lemma must charge the uncovered points after deletion: their cost cancels exactly in the extremal objective.

See Also

• Crossing-number formulas uses matrix rank and subspace dimensions for another global graph inequality.
• Strong thin trees also depends on preserving structural constraints during deletion of graph data.

🏷️ Manuscripts and verification scope

• A proof of Seymour’s second-neighborhood conjecture — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The selected statement is the unweighted second-neighborhood theorem, including sinks and excluding first neighbors from the second count. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A proof of Seymour’s second-neighborhood conjecture.