AFTD Auto-Formalizing Theoretical Domains

triangle_hypergraph_obstruction11_properties

theoremverified

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.

  1. 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.

    line 23

      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

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
See it in the graphDiscuss this resultChallenge it