AFTD Auto-Formalizing Theoretical Domains

op_193_avoidance_forces_nonanchor

theoremverified

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

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.

  1. 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`).

    lines 9–12

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

    line 13

      obtain ⟨S, hS⟩ := havoid (fun j => (A j).1) (by intro j; rw [(A j).2.1])
  3. 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`.

    lines 14–17

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