OctoInformBeta

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

The arc-deletion step: Each proper subset TT of E=F(S)\SE = F(S) \setminus S has a nonempty Q⊆E\TQ \subseteq E \setminus T with g(T∪Q)<g(T)+|Q|g(T \cup Q) < g(T) + |Q|, and g(E)=|F2(S)\F(S)|g(E) = |F^2(S) \setminus F(S)|

Steps toward the subset deficit in an arc-minimal oriented counterexample.

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

Take a digraph DD on a finite vertex set VV, written with arrows, u→wu \to w for an arc. The image F(S)F(S) of a set SS of vertices is the set of vertices that receive an arc from some vertex of SS, F(S)={y:x→y for some x∈S};F(S) = \{y : x \to y \text{ for some } x \in S\};(1)✦ The image F(S)F(S) may meet SS. The second image is the map F2=F∘FF^2 = F \circ F.

Fix a set SS of vertices. Its image splits into I=F(S)∩SI = F(S) \cap S, the part inside SS, and E=F(S)\SE = F(S) \setminus S, the vertices that SS reaches outside itself; the vertices reached from SS in two steps but not in one form F2(S)\F(S)F^2(S) \setminus F(S). The subset deficit is the statement that |F2(S)\F(S)|<|F(S)\S||F^2(S) \setminus F(S)| < |F(S) \setminus S|(2) holds for every nonempty proper vertex set SS, a vertex set being proper when it is not all of VV.

The deficit potential of SS is the function gg on vertex sets that counts, for a set TT, the vertices receiving an arc from TT and lying neither in TT nor in II: g(T)=|F(T)\(I∪T)|.g(T) = |F(T) \setminus (I \cup T)|.(3)✦

The arc-deletion step follows gg along subsets TT of EE, adding at each step a nonempty set of vertices of EE not yet in TT.

Counterexamples

The first neighborhood N1+(v)N_1^+(v) of a vertex vv of DD is the set of its out-neighbors✦, and the second neighborhood N2+(v)N_2^+(v) of vv is the set of vertices at directed distance exactly two from vv: 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\}.(4)✦

A vertex vv is good when |N1+(v)|≤|N2+(v)||N_1^+(v)| \le |N_2^+(v)|. A digraph DD on VV is a counterexample to Seymour’s second-neighborhood conjecture when it has no good vertex: |N2+(v)|<|N1+(v)|for every v∈V.|N_2^+(v)| < |N_1^+(v)| \quad \text{for every } v \in V.(5)✦

A digraph DD on VV 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 arc set A(D)A(D) of DD is the set of ordered pairs (u,w)(u, w) of vertices with u→wu \to w.✦ A digraph DD on VV is arc-minimal when no oriented counterexample on VV has fewer arcs: |A(D)|≤|A(D′)||A(D)| \le |A(D')| for every oriented counterexample D′D' on VV.✦

The subdigraph D[S]D[S] induced on a vertex set SS is the digraph on SS whose arcs are the arcs x→yx \to y of DD with xx and yy in SS.✦

The Claim

Theorem 1. Let DD be a digraph on a finite vertex set VV and SS a set of vertices, with II, EE and the deficit potential gg of SS as above.

  1. If DD is an oriented, arc-minimal counterexample, then every proper subset TT of EE has a nonempty subset QQ of E\TE \setminus T with g(T∪Q)<g(T)+|Q|.g(T \cup Q) < g(T) + |Q|.(6)✦

  2. For vertex sets JJ, TT and QQ with QQ disjoint from J∪TJ \cup T, |F(T∪Q)\(J∪T∪Q)|+|Q∩F(T)|=|F(T)\(J∪T)|+|F(Q)\(J∪T∪Q∪F(T))|;\begin{split} &|F(T \cup Q) \setminus (J \cup T \cup Q)| + |Q \cap F(T)| \\ &\qquad = |F(T) \setminus (J \cup T)| + |F(Q) \setminus (J \cup T \cup Q \cup F(T))|; \end{split}(7)✦ for J=IJ = I, the first terms of the two sides are g(T∪Q)g(T \cup Q) and g(T)g(T).

  3. If WW is a nonempty vertex set and hh a function from vertex sets to the nonnegative integers with h(∅)=0h(\emptyset) = 0 such that every proper subset TT of WW has a nonempty subset QQ of W\TW \setminus T with h(T∪Q)<h(T)+|Q|h(T \cup Q) < h(T) + |Q|, then h(W)<|W|.h(W) < |W|.(8)✦

  4. At EE, the deficit potential takes the value g(E)=|F2(S)\F(S)|.g(E) = |F^2(S) \setminus F(S)|.(9)✦

  5. If DD is a counterexample and F(S)⊆SF(S) \subseteq S, then the induced subdigraph D[S]D[S] is a counterexample: with the neighborhoods taken in D[S]D[S], |N2+(v)|<|N1+(v)|for every v∈S.|N_2^+(v)| < |N_1^+(v)| \quad \text{for every } v \in S.(10)✦

In the paper, the result reads: for T⊊E=F(S)\ST \subsetneq E = F(S) \setminus S, deleting the arcs from SS to E\TE \setminus T yields a nonempty Q⊆E\TQ \subseteq E \setminus T with g(T∪Q)−g(T)<|Q|g(T \cup Q) - g(T) < |Q|, where g(T)=|F(T)\(I∪T)|g(T) = |F(T) \setminus (I \cup T)| and I=F(S)∩SI = F(S) \cap S; summing from T=∅T = \emptyset gives g(E)<|E|g(E) < |E|, and g(E)=|F2(S)\F(S)|g(E) = |F^2(S) \setminus F(S)|; strong connectivity is argued with a terminal strongly connected component, which carries a smaller counterexample.

What Is Checked

The claim is stated over finite digraphs and the images F(S)F(S) of their vertex sets, the first and second neighborhoods and the counterexamples they define, oriented graphs, arc-minimality through the arc set, the deficit potential gg and the induced subdigraph D[S]D[S].