triangle_hypergraph_obstruction_properties
The six given triples each have three points; distinct triples meet in exactly one point; no point is in more than three triples; no set of at most two points meets all triples; and a three-point cover exists. Thus the maximum packing has size one and the minimum cover size three, despite the system having fewer than seven edges.
Statement
theorem triangle_hypergraph_obstruction_properties : triangle_hypergraph_obstruction.card = 6 ∧ (∀ e ∈ triangle_hypergraph_obstruction, e.card = 3) ∧ (∀ e ∈ triangle_hypergraph_obstruction, ∀ f ∈ triangle_hypergraph_obstruction, e ≠ f → (e ∩ f).card = 1) ∧ (∀ v : Fin 7, (triangle_hypergraph_obstruction.filter fun e => v ∈ e).card ≤ 3) ∧ (∀ F : Finset (Fin 7), F.card ≤ 2 → ∃ e ∈ triangle_hypergraph_obstruction, Disjoint F e) ∧ (∃ F : Finset (Fin 7), F.card = 3 ∧ ∀ e ∈ triangle_hypergraph_obstruction, ¬ Disjoint F e)
- Source
- Finite obstruction to the linear degree-three hypergraph route for the triangle packing-cover problem; computed in experiment 13104. No novelty is claimed for this small plane-derived example.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- triangle_hypergraph_obstructionThe six-triple seven-point linear hypergraph used to show that the triangle packing-cover inequality does not extend to all linear…
- Used by 1
- triangle_hypergraph_stable_minimum_cover_incompatible_pairIn the existing six-triple linear obstruction, every point is active and can be omitted by a maximum one-triple packing; the triple…
The proof, explained
The theorem establishes six combinatorial properties of an explicit 3-uniform hypergraph on seven vertices with six edges: it has size 6, every edge has size 3, distinct edges pairwise intersect in exactly one vertex, every vertex has degree at most 3, its transversal number is strictly greater than 2, and its transversal number is at most 3 (hence exactly 3). Because the hypergraph is finite and all quantifiers range over finite sets, the entire conjunction is decidable. The proof consists of a single invocation of the `decide` tactic, which verifies all conditions by exhaustive computation.
The hypergraph consists of 6 edges of cardinality 3, every distinct pair intersects in exactly 1 point, every vertex has degree at most 3, no vertex set of size at most 2 meets every edge, and there is a vertex set of size 3 meeting every edge. automation
All six conjuncts are bounded quantifiers and decidable relations over the finite type `Fin 7` and the explicitly defined family of edges. The `decide` tactic evaluates the entire conjunction by exhaustive computation: it verifies the size of the hypergraph, the cardinality of each of the 6 edges, the 15 pairwise intersections, the degree of each of the 7 vertices, the existence of a disjoint edge for each of the 29 subsets of size at most 2, and the existence of a 3-element hitting set among the 35 subsets of size 3.
decide
- The proof is carried out entirely by Lean's computational evaluator `decide`, which verifies all six combinatorial properties by exhaustive finite search and arithmetic evaluation over the subsets of `Fin 7`.
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 2000000theorem triangle_hypergraph_obstruction_properties : triangle_hypergraph_obstruction.card = 6 ∧ (∀ e ∈ triangle_hypergraph_obstruction, e.card = 3) ∧ (∀ e ∈ triangle_hypergraph_obstruction, ∀ f ∈ triangle_hypergraph_obstruction, e ≠ f → (e ∩ f).card = 1) ∧ (∀ v : Fin 7, (triangle_hypergraph_obstruction.filter fun e => v ∈ e).card ≤ 3) ∧ (∀ F : Finset (Fin 7), F.card ≤ 2 → ∃ e ∈ triangle_hypergraph_obstruction, Disjoint F e) ∧ (∃ F : Finset (Fin 7), F.card = 3 ∧ ∀ e ∈ triangle_hypergraph_obstruction, ¬ Disjoint F e) := by decide