OAI/Combinatorics/SecondNeighborhood/Pruning.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.Pruning.pruning Prune two pair families to compatibility with a controlled deletion cost line 10

    L4DEL explanation

    There are subfamilies R′ ⊆ R and C ′ ⊆ C with no conflicts between them

    For any finite binary relation and two families of ordered pairs, the pruning theorem retains every member that was conflict-free initially and removes enough other members to eliminate all conflicts. The total deletions are charged to original conflict corners plus conflict corners left uncovered afterward.

    1. An augmented bipartite matching represents the possible conflicting deletions.
    2. Maximum-support matrix ranks bound that matching, and a matching-to-cover argument converts the bound into compatible retained subfamilies satisfying PruningStatement.

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

    theorem pruning (r : X → X → Prop) : PruningStatement r := by
    …

    Mentions: OAI.SeymourSecondNeighborhood.Pruning.PruningStatement