AFTD Auto-Formalizing Theoretical Domains

op_193_stable_anchor_avoidance_forces_nonanchor

theoremverified

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

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.

  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.

    lines 10–13

      classical
      by_contra hn
      push_neg at hn
      choose A hcolor hanchor using hn
  2. 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.

    line 14

      obtain ⟨S, hS⟩ := havoid A
  3. A 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`).

    lines 15–18

    uses Finset.inter_comm

      have 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

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
See it in the graphDiscuss this resultChallenge it