OctoInformBeta

OpenAI preprint, September 2026 · §2. From a counterexample to a strict subset inequality

Proposition 2.1: A nonempty oriented graph with no good vertex yields one on [n]×[n+1][n]\times[n+1] with positive indegree and |S|+|F2(S)|<2|F(S)||S|+|F^2(S)|<2|F(S)| for nonempty proper SS

A counterexample yields an oriented graph with strict growth.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A digraph DD on a finite vertex set VV, with an arc written u→wu \to w, is oriented when it has no loop v→vv \to v and no pair of opposite arcs u→wu \to w and w→uw \to u.✦ The first out-neighborhood N1+(v)N_1^+(v) of a vertex vv of DD is the set of its out-neighbors✦, and its second out-neighborhood N2+(v)N_2^+(v) is the set of vertices at directed distance exactly two from vv, each counted once: N1+(v)={u:v→u},N2+(v)={w:w≠v,v↛w,v→u→w for some u}.N_1^+(v) = \{u : v \to u\}, \qquad N_2^+(v) = \{w : w \ne v,\ v \not\to w,\ v \to u \to w \text{ for some } u\}.(1)✦

A vertex vv is good when |N1+(v)|≤|N2+(v)||N_1^+(v)| \le |N_2^+(v)|, and Seymour’s second-neighborhood conjecture asserts that every oriented graph on a nonempty finite vertex set has a good vertex. A counterexample to the conjecture is an oriented graph DD on VV in which no vertex is good: |N2+(v)|<|N1+(v)|for every v∈V.|N_2^+(v)| < |N_1^+(v)| \quad \text{for every } v \in V.(2)✦

Images of Vertex Sets

The claim below carries the failure (2) from single vertices to sets of vertices, measured by their images. The image F(S)F(S) of a set SS of vertices of a digraph on VV is the set of vertices that receive an arc from some vertex of SS, and the second image of SS is F2(S)=F(F(S))F^2(S) = F(F(S)): F(S)={y:x→y for some x∈S},F2(S)=F(F(S)).F(S) = \{y : x \to y \text{ for some } x \in S\}, \qquad F^2(S) = F(F(S)).(3)✦ The image may meet SS, and FGF_G is written for the image in a digraph GG when more than one digraph is in play.

A set SS of vertices is proper when S≠VS \ne V. A digraph on VV has positive indegree when every vertex vv has an in-neighbor, a vertex uu with u→vu \to v.✦

The Claim

Theorem 1. Let DD be a counterexample to Seymour’s second-neighborhood conjecture, an oriented graph on a nonempty finite vertex set VV satisfying (2). For a positive integer mm write [m]={1,…,m}[m] = \{1, \dots, m\}. Then there are a positive integer nn and an oriented graph GG on the vertex set [n]×[n+1][n] \times [n+1] that has positive indegree and strict growth: every nonempty proper set SS of vertices of GG satisfies |S|+|FG2(S)|<2|FG(S)|.|S| + |F_G^2(S)| < 2\,|F_G(S)|.(4)✦

In the paper, the result reads: if the paper’s Theorem 1.1 has a counterexample, then there is a finite nonempty oriented graph GG in which every vertex has positive indegree and |U|+|FG2(U)|<2|FG(U)||U| + |F_G^2(U)| < 2\,|F_G(U)| for every nonempty proper vertex set UU of GG.

What Is Checked

The claim is stated over oriented graphs on finite vertex sets, the out-neighborhoods (1) and the counterexample condition (2) built from them, the image (3), positive indegree and strict growth (4).