OAI/Combinatorics/SecondNeighborhood/ExtremalContradiction.lean

GitHub source file

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL
Lean4 Domain Explanation Language

Credit: OpenAI's pinned repository says an unreleased internal model produced the manuscripts and supporting proof artifacts. The collection builds on the mathematics community's accumulated problems, results, language, and formal libraries; each manuscript's BibTeX and bibliography are the authority for individual scholarly credit.

Project sources: Pinned openai/math documentation, Pinned formalization catalogue

2 declarations, 0 contain sorry, 0 declared as axioms

  1. theorem OAI.SeymourSecondNeighborhood.Extremal.complement_gain line 12
  2. theorem OAI.SeymourSecondNeighborhood.Extremal.no_strictSubsetGrowth_of_pruning Pruning contradicts the existence of a positive-indegree strict-growth graph line 29

    L4DEL explanation

    There is no nonempty finite oriented graph G in which every vertex has an in-neighbor

    No nonempty finite oriented graph can simultaneously have positive indegree, satisfy the pruning statement, and obey StrictSubsetGrowth. An extremal compatible pair of ordered-pair families can always be replaced by a strictly better one, contradicting maximality.

    1. Complementing second iterated coordinate images creates candidate families whose combined size beats the current objective by more than twice the uncovered count.
    2. Pruning restores compatibility while charging deletions to old and new uncovered points; the latter cancel in the objective, leaving a strict improvement.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f), OpenAI Seymour second-neighborhood manuscript

    theorem no_strictSubsetGrowth_of_pruning {r : V → V → Prop}
        (hr : IsOriented r) (hpos : PositiveIndegree r)
        (hprune : PruningStatement r) : ¬ StrictSubsetGrowth r := by
    …

    Mentions: OAI.SeymourSecondNeighborhood.IsOriented, OAI.SeymourSecondNeighborhood.PositiveIndegree, OAI.SeymourSecondNeighborhood.StrictSubsetGrowth