AFTD Auto-Formalizing Theoretical Domains

digraph_129_regular_independence_small_overlap

theoremverified

A seven-outregular digraph on 129 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z overlap condition.

Statement

theorem digraph_129_regular_independence_small_overlap
    (D : Digraph (Fin 129)) [DecidableRel D.Adj]
    (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)
    (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) :
    3 * ((∑ v : Fin 129, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 129)
Source
Extremal overlap counting for OP-110.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…

The proof, explained

Proof sketch: Let J be the common-predecessor graph of the 7-outregular digraph D on 129 vertices, and let H = Jᶜ be its complement. Since J has independence number at most 3, H is K₄-free, so Turán's theorem bounds its edge count by |E(H)| ≤ 5547. Because J and H partition the 8256 edges of the complete graph K₁₂₉, J has at least 8256 - 5547 = 2709 edges. The total number of out-neighbour pairs across all vertices is 129 * Nat.choose 7 2 = 2709, meaning the overlap 2709 - |E(J)| is at most 0, and multiplying by 3 yields at most 0 < 129.

  1. Adjacency in the common-predecessor graph of D is decidable.

    Unfolding the definition of the common-predecessor graph expresses adjacency of two vertices u and v as u ≠ v and the existence of a common in-neighbour w in D. Because the vertex set Fin 129 is finite and adjacency in D is decidable, typeclass synthesis infers that this existential condition is decidable.

    lines 1–5

    private instance in833_order129_decAdj (D : Digraph (Fin 129)) [DecidableRel D.Adj] :
        DecidableRel (digraph_common_predecessor_graph D).Adj := by
      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The complement graph H = Jᶜ contains no 4-clique.

    Let J be the common-predecessor graph of D and H be its graph complement Jᶜ. Because J has no independent set of size 4 by hypothesis (hindep), its complement H contains no clique of size 4 (H.CliqueFree 4).

    lines 13–16

      classical
      let J := digraph_common_predecessor_graph D
      let H := Jᶜ
      have hfree : H.CliqueFree 4 := by simpa [H, J] using hindep
  3. The complement graph H has at most 5547 edges.

    By Turán's theorem (SimpleGraph.CliqueFree.card_edgeFinset_le with r = 3), any K₄-free graph on n = 129 vertices has at most (129² - (129 % 3)²) * 2 / 6 + (129 % 3).choose 2 edges. Since 129 is a multiple of 3, this bound evaluates to 129² / 3 = 5547.

    lines 17–20

    uses SimpleGraph.CliqueFree.card_edgeFinset_le

      have hupper : H.edgeFinset.card ≤ 5547 := by
        have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree
        norm_num at h
        exact h
  4. The edge sets of J and H are disjoint.

    The edge sets of two simple graphs are disjoint if and only if the graphs themselves are disjoint (SimpleGraph.disjoint_edgeFinset). Since H is the complement of J, disjointness follows directly from disjoint_compl_right.

    lines 21–24

    uses SimpleGraph.disjoint_edgeFinset, disjoint_compl_right

      have hdis : Disjoint J.edgeFinset H.edgeFinset := by
        rw [SimpleGraph.disjoint_edgeFinset]
        change Disjoint J Jᶜ
        exact disjoint_compl_right
  5. The union of the edge sets of J and H is the edge set of the complete graph on 129 vertices.

    The edge set of the join of two graphs is the union of their edge sets (SimpleGraph.edgeFinset_sup). Since J ⊔ Jᶜ = ⊤ by sup_compl_eq_top, their edge union equals the edge set of the complete graph ⊤ on Fin 129.

    lines 25–28

    uses SimpleGraph.edgeFinset_sup, SimpleGraph.edgeFinset_inj.mpr, sup_compl_eq_top

      have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 129)).edgeFinset := by
        rw [← SimpleGraph.edgeFinset_sup]
        change (J ⊔ Jᶜ).edgeFinset = _
        exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top
  6. The sum of the edge counts of J and H is 8256.

    Since the edge sets of J and H are disjoint and their union is the complete graph ⊤, the sum of their cardinalities equals the number of edges in ⊤ on 129 vertices (Finset.card_union_of_disjoint and SimpleGraph.card_edgeFinset_top_eq_card_choose_two). By the formula n.choose 2 = n * (n - 1) / 2 (Nat.choose_two_right), this equals 129 * 128 / 2 = 8256.

    lines 29–33

    uses Finset.card_union_of_disjoint, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Nat.choose_two_right

      have htotal : J.edgeFinset.card + H.edgeFinset.card = 8256 := by
        rw [← Finset.card_union_of_disjoint hdis, hunion,
          SimpleGraph.card_edgeFinset_top_eq_card_choose_two]
        rw [Nat.choose_two_right]
        norm_num
  7. The sum over all vertices v of the number of pairs of out-neighbours is 2709.

    Because D is 7-outregular (hdeg), every vertex has exactly 7 out-neighbours, contributing Nat.choose 7 2 = 21 pairs. Summing this constant over all 129 vertices gives 129 * 21 = 2709.

    lines 34–36

      have hinc : (∑ v : Fin 129, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2709 := by
        simp [hdeg]
        norm_num [Nat.choose]
  8. The strict 3z overlap condition holds: 3 * (2709 - |E(J)|) < 129.

    Rewriting the pair sum as 2709 reduces the goal to 3 * (2709 - J.edgeFinset.card) < 129. Since |E(J)| + |E(H)| = 8256 and |E(H)| ≤ 5547, we have |E(J)| ≥ 8256 - 5547 = 2709. In natural number arithmetic, 2709 - |E(J)| = 0, so the product is 0, which is strictly less than 129. The omega tactic closes this linear arithmetic goal.

    lines 37–40

      change 3 * ((∑ v : Fin 129, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
        J.edgeFinset.card) < 129
      rw [hinc]
      omega
SimpleGraph.CliqueFree.card_edgeFinset_le
Turán's theorem: a graph on n vertices with no (r + 1)-clique has at most ((n^2 - (n % r)^2) * (r - 1) / (2 * r)) + (n % r).choose 2 edges.
SimpleGraph.disjoint_edgeFinset
Two simple graphs have disjoint edge sets if and only if they are disjoint as graphs.
disjoint_compl_right
An element and its complement are disjoint in any Heyting algebra (such as the lattice of simple graphs).
SimpleGraph.edgeFinset_sup
The edge set of the supremum (join) of two simple graphs is the union of their edge sets.
SimpleGraph.edgeFinset_inj.mpr
If two simple graphs are equal, their edge sets are equal.
sup_compl_eq_top
In a Boolean algebra, the join of any element and its complement is the top element (the complete graph).
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two
The complete graph on a finite vertex set V has |V|.choose 2 edges.
Nat.choose_two_right
For any natural number n, n.choose 2 = n * (n - 1) / 2.

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

private instance in833_order129_decAdj (D : Digraph (Fin 129)) [DecidableRel D.Adj] :    DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_129_regular_independence_small_overlap    (D : Digraph (Fin 129)) [DecidableRel D.Adj]    (hdeg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)    (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) :    3 * ((∑ v : Fin 129, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 129) := by  classical  let J := digraph_common_predecessor_graph D  let H := Jᶜ  have hfree : H.CliqueFree 4 := by simpa [H, J] using hindep  have hupper : H.edgeFinset.card ≤ 5547 := by    have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree    norm_num at h    exact h  have hdis : Disjoint J.edgeFinset H.edgeFinset := by    rw [SimpleGraph.disjoint_edgeFinset]    change Disjoint J Jᶜ    exact disjoint_compl_right  have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 129)).edgeFinset := by    rw [← SimpleGraph.edgeFinset_sup]    change (J ⊔ Jᶜ).edgeFinset = _    exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top  have htotal : J.edgeFinset.card + H.edgeFinset.card = 8256 := by    rw [← Finset.card_union_of_disjoint hdis, hunion,      SimpleGraph.card_edgeFinset_top_eq_card_choose_two]    rw [Nat.choose_two_right]    norm_num  have hinc : (∑ v : Fin 129, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2709 := by    simp [hdeg]    norm_num [Nat.choose]  change 3 * ((∑ v : Fin 129, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -    J.edgeFinset.card) < 129  rw [hinc]  omega
See it in the graphDiscuss this resultChallenge it