Exhaustive search for small independent-set targets
Lax263307.ExhaustiveTargets · concepts/Lax263307/ExhaustiveTargets.lean · lax-263307
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Lemma
For a small target , enumerate exactly the -element vertex sets and test independence. The first success has size exactly . If the search fails, every independent set has size less than .
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax263307.LinearRelaxation |
| 2 | import Mathlib.Data.List.FinRange |
| 3 | import Mathlib.Data.List.Sublists |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Exhaustive search for small independent-set targets |
| 8 | type: lemma |
| 9 | --- |
| 10 | For a small target , enumerate exactly the -element vertex sets and |
| 11 | test independence. The first success has size exactly . If the search |
| 12 | fails, every independent set has size less than . |
| 13 | |
| 14 | # Formalization notes |
| 15 | |
| 16 | The executable enumeration generates sublists of length , without |
| 17 | materializing all vertex subsets. The two claims give completeness of |
| 18 | the candidate list and correctness of the search. |
| 19 | -/ |
| 20 | |
| 21 | namespace Lax263307.ExhaustiveTargets |
| 22 | |
| 23 | /-- Enumerate the vertex sets of one prescribed cardinality. -/ |
| 24 | def candidates (n k : ℕ) : List (Finset (Fin n)) := |
| 25 | ((List.finRange n).sublistsLen k).map List.toFinset |
| 26 | |
| 27 | /-- Deterministic exact search at target `k`. -/ |
| 28 | def 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. -/ |
| 33 | axiom 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. -/ |
| 37 | axiom 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 | |
| 42 | end Lax263307.ExhaustiveTargets |
| 43 |
Formalization notes
The executable enumeration generates sublists of length , without materializing all vertex subsets. The two claims give completeness of the candidate list and correctness of the search.
Builds on
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments