AFTD Auto-Formalizing Theoretical Domains

op_193_large_cycle_three_set_anchor_avoidance

theoremverified

For every cycle of length at least 15, any m-4 sets of at most three cycle vertices are simultaneously met in at most one vertex by some stable triple.

Statement

theorem op_193_large_cycle_three_set_anchor_avoidance (m : ℕ) (hm : 15 ≤ m)
    (A : Fin (m-4) → Finset (Fin m))
    (hA : ∀ j, (A j).card ≤ 3) :
    ∃ S : Finset (Fin m), S.card = 3 ∧
      (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧
      ∀ j, (S ∩ A j).card ≤ 1
Source
Triangle-free extremal reduction for the anchored-color argument in arXiv:2610.17884 Section 3.
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem specializes the general cubic anchor-avoidance theorem op_193_cubic_cycle_anchor_avoidance to the case k = 3. Since m ≥ 15 = 3((3 - 1)² + 1) and m - 4 = m - 2(3) + 2, the hypotheses of the general theorem are met. Applying it yields an independent triple in the cycle graph meeting each of the m - 4 sets in at most one vertex, and a formal re-indexing transfers the property to the original index set.

  1. The conditions of the general cubic anchor-avoidance theorem hold for k = 3, and the family A is re-indexed accordingly.

    We check the preconditions to apply op_193_cubic_cycle_anchor_avoidance with k = 3: reflexivity (le_refl) gives 3 ≤ 3, while integer arithmetic (omega) verifies 3 * ((3 - 1)² + 1) = 15 ≤ m from 15 ≤ m, as well as m - 2 * 3 + 2 = m - 4. Using Fin.cast along this equality, the family A is re-indexed over Fin (m - 2 * 3 + 2), preserving the condition that each set has at most 3 elements.

    lines 7–10

    uses le_refl, Fin.cast

      have hk : 3 ≤ 3 := le_refl 3
      have hm' : 3 * ((3 - 1) ^ 2 + 1) ≤ m := by omega
      have h_eq : m - 2 * 3 + 2 = m - 4 := by omega
      have hA' : ∀ j : Fin (m - 2 * 3 + 2), (A (Fin.cast h_eq j)).card ≤ 3 := fun j => hA (Fin.cast h_eq j)
  2. There exists an independent set S of size 3 in the cycle graph meeting each set in the re-indexed family in at most one vertex.

    We instantiate the general anchor-avoidance theorem op_193_cubic_cycle_anchor_avoidance with k = 3 and the re-indexed family. This produces a subset S ⊆ Fin m of cardinality 3 that is an independent set in the cycle graph C_m and intersects each set in the re-indexed family in at most 1 vertex.

    lines 11–12

    uses op_193_cubic_cycle_anchor_avoidance, Fin.cast

      obtain ⟨S, hScard, hSindep, hSinter⟩ :=
        op_193_cubic_cycle_anchor_avoidance 3 m hk hm' (fun j => A (Fin.cast h_eq j)) hA'
  3. The set S satisfies the required intersection condition for every set in the original family A.

    We provide S as the desired witness. Its size is 3 and it is independent by construction. For any index j ∈ Fin (m - 4), rewriting j as the cast of its inverse cast Fin.cast h_eq.symm j aligns it with the re-indexed family, so the intersection bound |S ∩ A j| ≤ 1 follows directly from the bound obtained in the previous step.

    lines 13–17

    uses Fin.cast

      refine ⟨S, hScard, hSindep, ?_⟩
      intro j
      have hj : j = Fin.cast h_eq (Fin.cast h_eq.symm j) := by simp
      rw [hj]
      exact hSinter (Fin.cast h_eq.symm j)
le_refl
The less-than-or-equal relation is reflexive: a ≤ a for every a.
Fin.cast
Transfers an element of Fin n to Fin m given a proof of n = m, without changing the underlying natural number.
op_193_cubic_cycle_anchor_avoidance
In any cycle of length m ≥ k((k-1)² + 1) with k ≥ 3, any m - 2k + 2 subsets of at most k cycle vertices admit an independent set of size k meeting each subset in at most one vertex.

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_large_cycle_three_set_anchor_avoidance (m : ℕ) (hm : 15 ≤ m)    (A : Fin (m-4) → Finset (Fin m))    (hA : ∀ j, (A j).card ≤ 3) :    ∃ S : Finset (Fin m), S.card = 3 ∧      (SimpleGraph.cycleGraph m).IsIndepSet (↑S : Set (Fin m)) ∧      ∀ j, (S ∩ A j).card ≤ 1 := by  have hk : 3 ≤ 3 := le_refl 3  have hm' : 3 * ((3 - 1) ^ 2 + 1) ≤ m := by omega  have h_eq : m - 2 * 3 + 2 = m - 4 := by omega  have hA' : ∀ j : Fin (m - 2 * 3 + 2), (A (Fin.cast h_eq j)).card ≤ 3 := fun j => hA (Fin.cast h_eq j)  obtain ⟨S, hScard, hSindep, hSinter⟩ :=    op_193_cubic_cycle_anchor_avoidance 3 m hk hm' (fun j => A (Fin.cast h_eq j)) hA'  refine ⟨S, hScard, hSindep, ?_⟩  intro j  have hj : j = Fin.cast h_eq (Fin.cast h_eq.symm j) := by simp  rw [hj]  exact hSinter (Fin.cast h_eq.symm j)
See it in the graphDiscuss this resultChallenge it