OAI/Combinatorics/SecondNeighborhood/Main.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

1 declarations, 0 contain sorry, 0 declared as axioms

  1. theorem OAI.SeymourSecondNeighborhood.exists_goodVertex Proof-bearing solution of Seymour's second-neighborhood conjecture line 11

    L4DEL explanation

    every nonempty finite oriented graph has a vertex with at least as many vertices at directed distance two as at directed distance one

    Every nonempty finite oriented graph has a good vertex. Unlike the comparator declaration with the same fully qualified name, this declaration imports the reduction, pruning theorem, and extremal contradiction and contains the checked proof term that composes them.

    1. Assuming no good vertex produces Counterexample r, which counterexample_reduction converts into an oriented positive-indegree graph with strict subset growth.
    2. The general pruning theorem applies to that graph, while the extremal theorem proves pruning and strict subset growth incompatible; the contradiction discharges the original assumption.

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

    Distinct definitions of this name: ComparatorChallenges/SeymourSecondNeighborhood.lean:34 (same statement text; different proof or body). Qualify references as OAI.SeymourSecondNeighborhood.exists_goodVertex@path.

    theorem exists_goodVertex (r : V → V → Prop) (hr : IsOriented r) :
        ∃ v, GoodVertex r v := by
    …

    Mentions: OAI.SeymourSecondNeighborhood.IsOriented, OAI.SeymourSecondNeighborhood.GoodVertex