Lemma 3.2 (kernels at maximum support rank): if a real matrix has maximum rank among matrices with a given support , then for , and
ProvedOAI.SeymourSecondNeighborhood.Pruning.lemma_3_2combinatoricsgraph-theoryseymour-second-neighborhood
Let be finite index sets and . A real matrix is supported on if its entries outside are zero (entries in may vanish). Suppose is supported on and has maximum rank among all real matrices supported on . Then for every (that is, ), every (that is, ) and every ,
This is Lemma 3.2 of the manuscript. Proof idea: if , the perturbed matrix is still supported on ; shows , and shows ; but annihilates and , so , whence , a contradiction. The lemma is used in the proof of the pruning lemma (Pruning.lemma_3_1) to compare restrictions of kernel vectors of two matrices.
Preamble
import Mathlib import Definitions.Def_SeymourSecondNeighborhood import Definitions.Def_SeymourSecondNeighborhood_Image open Finset
Formal statement
namespace OAI.SeymourSecondNeighborhood.Pruning
theorem lemma_3_2 {I J : Type*} [Fintype I] [Fintype J] [DecidableEq I] [DecidableEq J]
(T : Finset (I × J)) (D : Matrix I J ℝ) (hD : ∀ i j, (i, j) ∉ T → D i j = 0)
(hmax : ∀ D' : Matrix I J ℝ, (∀ i j, (i, j) ∉ T → D' i j = 0) → D'.rank ≤ D.rank)
(x : J → ℝ) (hx : D.mulVec x = 0) (y : I → ℝ) (hy : D.transpose.mulVec y = 0)
(s : I) (j : J) (hsj : (s, j) ∈ T) : x j * y s = 0 := by
sorry
end OAI.SeymourSecondNeighborhood.PruningSource
Statement extracted from OpenAI, *A proof of Seymour's second-neighborhood conjecture*, preprint, September 23, 2026, https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-proof-of-Seymours-second-neighborhood-conjecture-September-23-2026/paper.pdf