op_193_stable_anchor_avoidance_forces_nonanchor
If every family of q stable k-sets can be met in at most one point by a stable k-set, every q-coloring has a nonanchored color class.
Statement
theorem op_193_stable_anchor_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 → {S : Finset (Fin m) // S.card = k ∧
(SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))},
∃ S : {S : Finset (Fin m) // S.card = k ∧
(SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))},
∀ j, (S.1 ∩ (A j).1).card ≤ 1) :
∃ j : Fin q, ∀ U, c U = j → ∃ W, c W = j ∧ (U.1 ∩ W.1).card < 2- Source
- Stable-anchor refinement of the coloring argument in arXiv:2610.17884 Section 3.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_193_noncolorable_if_stable_anchor_avoidanceIf the cycle-only stable k-set graph is not (m-2k+1)-colorable and every family of m-2k+2 stable k-sets can be met in at most one point by…
The proof, explained
The theorem is proved by contradiction. If every color class had an anchor—a set intersecting every other set of that color in at least two vertices—we could select one such anchor for each of the q colors. The avoidance hypothesis then provides a stable k-set S intersecting every chosen anchor in at most one vertex. Comparing the anchor condition and the avoidance condition on the anchor belonging to S's own color yields the contradiction 2 ≤ |S ∩ A(c(S))| ≤ 1.
Suppose for contradiction that every color class has an anchor, and choose one anchor for each color.
Assuming the negation of the theorem and pushing negations through the quantifiers, we suppose that every color class j has an "anchor": a stable k-set U of color j such that every stable k-set W of color j shares at least 2 vertices with U. By the axiom of choice, we select an anchor A(j) for each color j ∈ Fin q.
classical by_contra hn push_neg at hn choose A hcolor hanchor using hn
There exists a stable k-set S meeting each chosen anchor in at most one vertex.
Applying the avoidance hypothesis `havoid` to the family of chosen anchors A produces a stable k-set S such that |S ∩ A(j)| ≤ 1 for every color j.
obtain ⟨S, hS⟩ := havoid AA contradiction arises by evaluating the anchor and avoidance properties on S and its color class.
Let j = c(S) be the color of S. Since A(j) is an anchor for color j and c(S) = j, we have |A(j) ∩ S| ≥ 2. Meanwhile, the avoidance property of S gives |S ∩ A(j)| ≤ 1. Using the commutativity of intersection (`Finset.inter_comm`), the size |S ∩ A(j)| must be both at least 2 and at most 1, which is impossible by linear arithmetic (`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_stable_anchor_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 → {S : Finset (Fin m) // S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))}, ∃ S : {S : Finset (Fin m) // S.card = k ∧ (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m))}, ∀ j, (S.1 ∩ (A j).1).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 A have hlarge := hanchor (c S) S rfl have hsmall := hS (c S) rw [Finset.inter_comm] at hlarge omega