op_193_large_cycle_three_set_anchor_avoidance
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
- op_193_cubic_cycle_anchor_avoidanceOn any cycle of length at least k times ((k-1)^2+1), every family of m-2k+2 subsets of size at most k admits a stable k-set meeting each…
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.
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.
uses
le_refl,Fin.casthave 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)
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.
uses
op_193_cubic_cycle_anchor_avoidance,Fin.castobtain ⟨S, hScard, hSindep, hSinter⟩ := op_193_cubic_cycle_anchor_avoidance 3 m hk hm' (fun j => A (Fin.cast h_eq j)) hA'
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.
uses
Fin.castrefine ⟨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.
- In paper mathematics, the index sets Fin(m - 4) and Fin(m - 2 * 3 + 2) are identical because m - 2 * 3 + 2 = m - 4. In Lean, converting between these types requires an explicit cast (Fin.cast) and a simp step to show that casting back and forth is the identity.
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_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)