Exhaustive search for small independent-set targets

Lax263307.ExhaustiveTargets · concepts/Lax263307/ExhaustiveTargets.lean · lax-263307

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Lemma

    For a small target kk, enumerate exactly the kk-element vertex sets and test independence. The first success has size exactly kk. If the search fails, every independent set has size less than kk.

    Concept map
    2 concepts; 2 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 2 statements. Each proof establishes one of them relative to its assumptions.

    Lean source view on GitHub

    1import Lax263307.LinearRelaxation
    2import Mathlib.Data.List.FinRange
    3import Mathlib.Data.List.Sublists
    4
    5/-!
    6---
    7title: Exhaustive search for small independent-set targets
    8type: lemma
    9---
    10For a small target kk, enumerate exactly the kk-element vertex sets and
    11test independence. The first success has size exactly kk. If the search
    12fails, every independent set has size less than kk.
    13
    14# Formalization notes
    15
    16The executable enumeration generates sublists of length kk, without
    17materializing all vertex subsets. The two claims give completeness of
    18the candidate list and correctness of the search.
    19-/
    20
    21namespace Lax263307.ExhaustiveTargets
    22
    23/-- Enumerate the vertex sets of one prescribed cardinality. -/
    24def candidates (n k : ℕ) : List (Finset (Fin n)) :=
    25 ((List.finRange n).sublistsLen k).map List.toFinset
    26
    27/-- Deterministic exact search at target `k`. -/
    28def findIndependentSet {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]
    29 (k : ℕ) : Option (Finset (Fin n)) :=
    30 (candidates n k).find? fun I => decide (G.IsIndepSet (I : Set (Fin n)))
    31
    32/-- Every size-`k` vertex set occurs, and no other cardinality occurs. -/
    33axiom candidate_complete (n k : ℕ) (I : Finset (Fin n)) :
    34 I ∈ candidates n k ↔ I.card = k
    35
    36/-- Search success is exact; search failure excludes every larger independent set. -/
    37axiom search_correct {n : ℕ} (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (k : ℕ) :
    38 match findIndependentSet G k with
    39 | some I => G.IsIndepSet (I : Set (Fin n)) ∧ I.card = k
    40 | none => ∀ J : Finset (Fin n), G.IsIndepSet (J : Set (Fin n)) → J.card < k
    41
    42end Lax263307.ExhaustiveTargets
    43
    Show ProofShow Proof
    Formalization notes

    The executable enumeration generates sublists of length kk, without materializing all vertex subsets. The two claims give completeness of the candidate list and correctness of the search.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…