triangle_hypergraph_obstruction11_properties
The explicit list has eleven 3-element triples, any two distinct triples meet in at most one point, and every point belongs to exactly three triples. Every selection of three triples contains an intersecting pair, while two displayed triples are disjoint; every selection of five contains a disjoint pair. Every set of at most four points misses some triple, whereas the displayed five-point set meets them all. Hence the packing number is two and the cover number is five, even though no five triples pairwise intersect.
Statement
theorem triangle_hypergraph_obstruction11_properties : triangle_hypergraph_obstruction11.length = 11 ∧ triangle_hypergraph_obstruction11.all (fun e => decide (e.card = 3)) = true ∧ triangle_hypergraph_obstruction11.all (fun e => triangle_hypergraph_obstruction11.all (fun f => decide (e = f ∨ (e ∩ f).card ≤ 1))) = true ∧ (∀ v : Fin 11, (triangle_hypergraph_obstruction11.filter fun e => v ∈ e).length = 3) ∧ ((List.sublistsLen 3 triangle_hypergraph_obstruction11).all fun P => P.any fun e => P.any fun f => decide (e ≠ f ∧ ¬ Disjoint e f)) = true ∧ ((List.sublistsLen 5 triangle_hypergraph_obstruction11).all fun P => P.any fun e => P.any fun f => decide (Disjoint e f)) = true ∧ (∀ F : Finset (Fin 11), F.card ≤ 4 → (triangle_hypergraph_obstruction11.any fun e => decide (Disjoint F e)) = true) ∧ (let F : Finset (Fin 11) := {0,1,2,3,5} F.card = 5 ∧ triangle_hypergraph_obstruction11.all (fun e => decide (¬ Disjoint F e)) = true) ∧ ({0,1,2} : Finset (Fin 11)) ∈ triangle_hypergraph_obstruction11 ∧ ({3,4,5} : Finset (Fin 11)) ∈ triangle_hypergraph_obstruction11 ∧ Disjoint ({0,1,2} : Finset (Fin 11)) {3,4,5}
- Source
- Finite obstruction to the linear degree-three hypergraph route for the triangle packing-cover problem; experiments 13111, 13112, 13120. No novelty is claimed for the isolated example.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- triangle_hypergraph_obstruction11An explicit eleven-point eleven-triple linear degree-three system arising as a counterexample to a proposed hypergraph extension of…
The proof, explained
The theorem establishes that the explicit 11-edge hypergraph on 11 vertices is 3-uniform, 3-regular, and linear, with packing number 2 and covering number 5, while having no pairwise intersecting family of size 5. Because the vertex set and the edge list are finite and small, every condition is a decidable proposition involving finite bounded searches over subsets and sublists. The proof proceeds entirely by computational evaluation via the `decide` tactic.
All ten structural, packing, and covering properties of the hypergraph hold: it is a 3-uniform, 3-regular, linear hypergraph on 11 vertices with packing number 2, covering number 5, and maximum intersecting family size at most 4. automation
All conjuncts are decidable propositions over finite sets: 1. Uniformity, linearity, and 3-regularity are verified by counting elements in each triple, in each pairwise intersection (at most 1 for distinct triples), and in the incidence list for each of the 11 vertices. 2. The packing number upper bound $\nu \le 2$ is checked by inspecting all $\binom{11}{3} = 165$ selections of three hyperedges and verifying that none are pairwise disjoint. The disjoint pair $\{0,1,2\}$ and $\{3,4,5\}$ witnesses $\nu \ge 2$, establishing $\nu = 2$. 3. The absence of an intersecting family of size 5 is checked across all $\binom{11}{5} = 462$ five-edge subfamilies, confirming that each contains at least one disjoint pair. 4. The transversal number lower bound $\tau \ge 5$ is verified by checking that each of the 562 vertex subsets of size at most 4 is disjoint from at least one hyperedge. The explicit set $\{0,1,2,3,5\}$ intersects all 11 edges, establishing $\tau = 5$. The `decide` tactic discharges the entire conjunction by exhaustive Boolean evaluation.
decide
- The proof relies entirely on Lean's kernel computation (`decide`) to exhaustively check all finite combinatorial configurations, requiring increased limits for `maxRecDepth` and `maxHeartbeats`.
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 10000set_option maxHeartbeats 4000000theorem triangle_hypergraph_obstruction11_properties : triangle_hypergraph_obstruction11.length = 11 ∧ triangle_hypergraph_obstruction11.all (fun e => decide (e.card = 3)) = true ∧ triangle_hypergraph_obstruction11.all (fun e => triangle_hypergraph_obstruction11.all (fun f => decide (e = f ∨ (e ∩ f).card ≤ 1))) = true ∧ (∀ v : Fin 11, (triangle_hypergraph_obstruction11.filter fun e => v ∈ e).length = 3) ∧ ((List.sublistsLen 3 triangle_hypergraph_obstruction11).all fun P => P.any fun e => P.any fun f => decide (e ≠ f ∧ ¬ Disjoint e f)) = true ∧ ((List.sublistsLen 5 triangle_hypergraph_obstruction11).all fun P => P.any fun e => P.any fun f => decide (Disjoint e f)) = true ∧ (∀ F : Finset (Fin 11), F.card ≤ 4 → (triangle_hypergraph_obstruction11.any fun e => decide (Disjoint F e)) = true) ∧ (let F : Finset (Fin 11) := {0,1,2,3,5} F.card = 5 ∧ triangle_hypergraph_obstruction11.all (fun e => decide (¬ Disjoint F e)) = true) ∧ ({0,1,2} : Finset (Fin 11)) ∈ triangle_hypergraph_obstruction11 ∧ ({3,4,5} : Finset (Fin 11)) ∈ triangle_hypergraph_obstruction11 ∧ Disjoint ({0,1,2} : Finset (Fin 11)) {3,4,5} := by decide