OAI/Combinatorics/SecondNeighborhood/SubsetDeficit.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.deficitPotential_terminal line 10
  2. theorem OAI.SeymourSecondNeighborhood.subsetDeficit_of_minimal Minimal counterexamples satisfy the strengthened subset deficit line 44

    L4DEL explanation

    Minimality first gives a strict deficit for subsets of a counterexample.

    The following lemma says, starting with a counterexample to the SNC, one can remove edges

    In an oriented counterexample minimal by arcs and equipped with a nonempty boundary, every nonempty proper set S has fewer newly reached second-image vertices than first-image vertices lying outside S. This strengthens the earlier subset perspective by using |F(S)\S| on the right.

    1. The proof repeatedly augments a subset of the boundary while an arc-deletion argument makes the deficit potential grow by less than the number of added vertices.
    2. At the full boundary, the terminal potential is exactly |F²(S)\F(S)|, yielding the strict subset inequality.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f), OpenAI Seymour second-neighborhood manuscript, Tyler Seacrest, Seymour's Second Neighborhood Conjecture for Subsets of Vertices (2019)

    theorem subsetDeficit_of_minimal {r : V → V → Prop}
        (hr : IsOriented r) (hcounter : Counterexample r)
        (hminimal : ArcMinimal r) (hboundary : NonemptyBoundary r) :
        SubsetDeficit r := by
    …

    Mentions: OAI.SeymourSecondNeighborhood.IsOriented, OAI.SeymourSecondNeighborhood.Counterexample, OAI.SeymourSecondNeighborhood.ArcMinimal, OAI.SeymourSecondNeighborhood.NonemptyBoundary, OAI.SeymourSecondNeighborhood.SubsetDeficit