op_193_avoidance_forces_nonanchor
If every family of q sets of at most k cycle vertices admits a stable k-set meeting each set in at most one point, every q-coloring of the stable k-sets has a nonanchored color class.
Statement
theorem op_193_avoidance_forces_nonanchor (m k q : ℕ)
(c : {S : Finset (Fin m) // S.card = k ∧
(SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))} → Fin q)
(havoid : ∀ A : Fin q → Finset (Fin m), (∀ j, (A j).card ≤ k) →
∃ S : {S : Finset (Fin m) // S.card = k ∧
(SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))},
∀ j, (S.1 ∩ A j).card ≤ 1) :
∃ j : Fin q, ∀ U, c U = j → ∃ W, c W = j ∧ (U.1 ∩ W.1).card < 2- Source
- Anchor-avoidance reduction for OP-193.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_193_cubic_noncolorable_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), if the cycle-stable k-set graph is not (m-2k+1)-colorable, then adding an isolated vertex…
The proof, explained
The proof is by contradiction. Assuming every color class has an anchor—a member that meets every other member of the same color in at least two vertices—we choose one anchor for each of the q colors. The avoidance hypothesis then guarantees a stable k-set S meeting each of these q anchors in at most one vertex. Considering the anchor sharing the color of S, its anchor property demands an intersection of size at least 2, while avoidance bounds it by 1, yielding a contradiction.
If every color class were anchored, there would exist an anchor A(j) for each color j that intersects every stable k-set of color j in at least 2 vertices.
We proceed by contradiction and negate the conclusion (`by_contra hn`, `push_neg at hn`). The negated statement says that for every color j, there is a stable k-set A(j) of color j such that every stable k-set W of color j satisfies |A(j) ∩ W| ≥ 2. We choose such an anchor A(j) for each color (`choose A hcolor hanchor using hn`).
classical by_contra hn push_neg at hn choose A hcolor hanchor using hn
There exists a stable k-set S intersecting each anchor A(j) in at most one vertex.
Since each A(j) is a stable k-set, its size is k. Applying the avoidance hypothesis `havoid` to the family of q sets {A(j)} produces a stable k-set S satisfying |S ∩ A(j)| ≤ 1 for every color j.
obtain ⟨S, hS⟩ := havoid (fun j => (A j).1) (by intro j; rw [(A j).2.1])
The stable k-set S yields a contradiction, completing the proof.
Specializing to the color j = c(S) of S: because S has color c(S), the anchoring property of A(c(S)) requires |A(c(S)) ∩ S| ≥ 2. Meanwhile, the avoidance guarantee for S gives |S ∩ A(c(S))| ≤ 1. Since intersection of finite sets is commutative (`Finset.inter_comm`), the cardinality must simultaneously be at least 2 and at most 1, an arithmetic contradiction resolved by `omega`.
uses
Finset.inter_commhave hlarge := hanchor (c S) S rfl have hsmall := hS (c S) rw [Finset.inter_comm] at hlarge omega
Finset.inter_comm- Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem op_193_avoidance_forces_nonanchor (m k q : ℕ) (c : {S : Finset (Fin m) // S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))} → Fin q) (havoid : ∀ A : Fin q → Finset (Fin m), (∀ j, (A j).card ≤ k) → ∃ S : {S : Finset (Fin m) // S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))}, ∀ j, (S.1 ∩ A j).card ≤ 1) : ∃ j : Fin q, ∀ U, c U = j → ∃ W, c W = j ∧ (U.1 ∩ W.1).card < 2 := by classical by_contra hn push_neg at hn choose A hcolor hanchor using hn obtain ⟨S, hS⟩ := havoid (fun j => (A j).1) (by intro j; rw [(A j).2.1]) have hlarge := hanchor (c S) S rfl have hsmall := hS (c S) rw [Finset.inter_comm] at hlarge omega