op_193_disjoint_anchor_packings
The thirteen-cycle has nine stable triples and the fourteen-cycle has ten stable triples, respectively, with any two triples sharing at most one vertex.
Statement
theorem op_193_disjoint_anchor_packings :
(∃ A : Fin 9 → Finset (Fin 13),
(∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 13).IsIndepSet (↑(A j) : Set (Fin 13))) ∧
∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1) ∧
(∃ A : Fin 10 → Finset (Fin 14),
(∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 14).IsIndepSet (↑(A j) : Set (Fin 14))) ∧
∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1)- Source
- Finite obstructions to overlap-only improvements of the anchor edge count; experiment 23383.
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by exhibiting explicit witness families of triples for both cycle graphs. For the 13-cycle, an explicit collection of 9 triples (`in777_pack13`) is provided, and for the 14-cycle, an explicit collection of 10 triples (`in777_pack14`) is provided. In both cases, the three conditions—each triple has size three, each triple is an independent set in the cycle, and any two triples intersect in at most one vertex—are verified by finite exhaustive computation using `decide`.
Both the 13-cycle and the 14-cycle admit the required collections of independent triples with pairwise intersection of size at most 1. automation
The proof provides explicit witness families: `in777_pack13` (9 triples in the 13-cycle) and `in777_pack14` (10 triples in the 14-cycle). Because all the sets are finite and the cycle graphs are finite, verifying that each triple has size 3, forms an independent set (contains no two vertices adjacent in the cycle), and shares at most one vertex with any distinct triple is a finite boolean decision problem closed by exhaustive computation (`decide`).
exact ⟨⟨in777_pack13, by decide⟩, ⟨in777_pack14, by decide⟩⟩
- The properties of the candidate families—cardinality 3, independence in the cycle graph, and pairwise intersection size at most 1—are verified entirely by finite exhaustive computation via `decide`.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 2000000private def in777_pack13 : Fin 9 → Finset (Fin 13) := ![{0,3,6}, {0,8,10}, {0,9,11}, {1,6,9}, {1,7,11}, {2,4,8}, {2,6,12}, {2,7,10}, {5,9,12}]private def in777_pack14 : Fin 10 → Finset (Fin 14) := ![{0,3,7}, {0,8,10}, {1,3,5}, {1,10,13}, {2,4,12}, {2,5,8}, {2,6,11}, {2,9,13}, {3,6,10}, {6,8,13}]theorem op_193_disjoint_anchor_packings : (∃ A : Fin 9 → Finset (Fin 13), (∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 13).IsIndepSet (↑(A j) : Set (Fin 13))) ∧ ∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1) ∧ (∃ A : Fin 10 → Finset (Fin 14), (∀ j, (A j).card = 3 ∧ (SimpleGraph.cycleGraph 14).IsIndepSet (↑(A j) : Set (Fin 14))) ∧ ∀ i j, i ≠ j → ((A i) ∩ (A j)).card ≤ 1) := by exact ⟨⟨in777_pack13, by decide⟩, ⟨in777_pack14, by decide⟩⟩