AFTD Auto-Formalizing Theoretical Domains

digraph_127_regular_independence_small_overlap

theoremverified

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

Statement

theorem digraph_127_regular_independence_small_overlap
    (D : Digraph (Fin 127)) [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 127, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 127)
Source
Extremal edge counting for the small-overlap approach to OP-110.
Verified
04 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…
Used by 1

The proof, explained

To prove the strict 3z overlap condition, the argument bounds the number of edges in the common-predecessor graph J from below by analyzing its complement H = Jᶜ. Since J contains no independent set of size 4, H contains no 4-clique, so Turán's theorem bounds the edges of H by at most 5376 on 127 vertices. Because J and H partition the complete graph K₁₂₇ (which has 8001 edges), J must contain at least 8001 - 5376 = 2625 edges. Since every vertex has out-degree 7, the total number of out-neighbor pairs is 127 · (7 choose 2) = 2667, meaning the overlap 2667 - |E(J)| is at most 42, and 3 · 42 = 126 < 127.

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

    For any two vertices u and v, adjacency in the common-predecessor graph is defined by u ≠ v and the existence of a common predecessor w. Since the vertex set Fin 127 is finite and adjacency in D is decidable, typeclass inference (infer_instance) decides this bounded existential condition.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The complement graph H = Jᶜ contains no 4-clique.

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

    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 5376 edges.

    Applying Turán's theorem (SimpleGraph.CliqueFree.card_edgeFinset_le with r = 3) to the 4-clique-free graph H on 127 vertices provides the upper bound ⌊(127² - 1²) · 2 / 6⌋ + (1 choose 2) = 5376, which norm_num evaluates.

    lines 17–20

    uses SimpleGraph.CliqueFree.card_edgeFinset_le

      have hupper : H.edgeFinset.card ≤ 5376 := 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.

    Two graphs have disjoint edge sets if and only if the graphs are disjoint (SimpleGraph.disjoint_edgeFinset). A graph and its complement are always disjoint by 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 127 vertices.

    The union of the edge sets equals the edge set of the supremum J ⊔ Jᶜ by SimpleGraph.edgeFinset_sup. Since J ⊔ Jᶜ is the complete graph ⊤ by sup_compl_eq_top, their union is the complete graph's edge set.

    lines 25–28

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

      have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 127)).edgeFinset := by
        rw [← SimpleGraph.edgeFinset_sup]
        change (J ⊔ Jᶜ).edgeFinset = _
        exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top
  6. The total number of edges in J and H combined is 8001.

    Since J and H have disjoint edge sets that partition the complete graph on 127 vertices, their combined edge count is (127 choose 2) = 127 · 126 / 2 = 8001.

    lines 29–32

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

      have htotal : J.edgeFinset.card + H.edgeFinset.card = 8001 := 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 of the number of pairs of out-neighbors is 2667.

    Each vertex has out-degree 7 by hypothesis hdeg, so it contributes (7 choose 2) = 21 pairs of out-neighbors. Summing over all 127 vertices gives 127 · 21 = 2667.

    lines 33–35

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

    Rewriting with the sum of pairs 2667 leaves the linear inequality 3 * (2667 - |E(J)|) < 127. From |E(H)| ≤ 5376 and |E(J)| + |E(H)| = 8001, we have |E(J)| ≥ 2625, so the overlap 2667 - |E(J)| is at most 42. Since 3 * 42 = 126 < 127, omega completes the proof.

    lines 36–38

      change 3 * ((∑ v : Fin 127, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - J.edgeFinset.card) < 127
      rw [hinc]
      omega
Finset.card_union_of_disjoint
The size of the union of two disjoint finite sets is the sum of their sizes.
Nat.choose_two_right
For any natural number n, n choose 2 equals n * (n - 1) / 2.
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.card_edgeFinset_top_eq_card_choose_two
The complete graph on a finite vertex set V has (card V choose 2) edges.
SimpleGraph.disjoint_edgeFinset
Two simple graphs have disjoint edge sets if and only if the graphs are disjoint.
SimpleGraph.edgeFinset_inj.mpr
If two simple graphs are equal, their edge sets are equal.
SimpleGraph.edgeFinset_sup
The edge set of the union (supremum) of two simple graphs is the union of their edge sets.
disjoint_compl_right
An element and its complement are disjoint.
sup_compl_eq_top
The join of an element with its complement is the top element (the complete graph).

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 in504_order127_decAdj (D : Digraph (Fin 127)) [DecidableRel D.Adj] :    DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_127_regular_independence_small_overlap    (D : Digraph (Fin 127)) [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 127, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 127) := 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 ≤ 5376 := 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 127)).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 = 8001 := 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 127, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2667 := by    simp [hdeg]    norm_num [Nat.choose]  change 3 * ((∑ v : Fin 127, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - J.edgeFinset.card) < 127  rw [hinc]  omega
See it in the graphDiscuss this resultChallenge it