digraph_128_regular_independence_small_overlap
A seven-outregular digraph on 128 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z overlap condition.
Statement
theorem digraph_128_regular_independence_small_overlap (D : Digraph (Fin 128)) [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 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 128)
- 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
To prove the strict overlap condition 3 * (∑ᵥ (|N⁺(v)| choose 2) - |E(J)|) < 128, the proof bounds the edge count of the common-predecessor graph J from below using Turán's theorem on its complement H = Jᶜ. Since J is K₄-independent, H is K₄-free, so Turán's theorem limits H to at most 5461 edges out of the total 8128 edges in K₁₂₈, forcing J to have at least 2667 edges. Summing the pairs of out-neighbors gives 128 * (7 choose 2) = 2688, leaving an excess of at most 2688 - 2667 = 21 edges, so 3 * 21 = 63 < 128.
Adjacency in the common-predecessor graph is decidable.
Unfolding the definition of the common-predecessor graph shows that two vertices u and v are adjacent if and only if u ≠ v and there exists a vertex w with directed edges to both u and v. Since the vertex set Fin 128 is finite and edge adjacency in D is decidable, typeclass inference synthesizes decidability of this bounded existential condition.
intro u v unfold digraph_common_predecessor_graph infer_instance
The complement graph H = Jᶜ contains no 4-clique.
Let J be the common-predecessor graph of D and H = Jᶜ its complement graph. By hypothesis hindep, J has no independent set of size 4. Since an independent set in J corresponds precisely to a clique in the complement H, simplifying with the definitions of J and H establishes that H is 4-clique-free.
classical let J := digraph_common_predecessor_graph D let H := Jᶜ have hfree : H.CliqueFree 4 := by simpa [H, J] using hindep
The complement graph H has at most 5461 edges.
By Turán's theorem (SimpleGraph.CliqueFree.card_edgeFinset_le with r = 3), any K₄-free graph on 128 vertices has at most (128² - (128 % 3)²) * (3 - 1) / (2 * 3) + (128 % 3).choose 2 edges. Computing this value via norm_num yields the upper bound |E(H)| ≤ 5461.
uses
SimpleGraph.CliqueFree.card_edgeFinset_lehave hupper : H.edgeFinset.card ≤ 5461 := by have h := SimpleGraph.CliqueFree.card_edgeFinset_le (G := H) (r := 3) hfree norm_num at h exact h
The edge sets of J and H are disjoint.
By SimpleGraph.disjoint_edgeFinset, edge sets are disjoint if and only if the underlying graphs are disjoint. Because H is defined as Jᶜ, this reduces to Disjoint J Jᶜ, which holds by disjoint_compl_right.
uses
SimpleGraph.disjoint_edgeFinset,disjoint_compl_righthave hdis : Disjoint J.edgeFinset H.edgeFinset := by rw [SimpleGraph.disjoint_edgeFinset] change Disjoint J Jᶜ exact disjoint_compl_right
The union of the edge sets of J and H is the edge set of the complete graph on 128 vertices.
By SimpleGraph.edgeFinset_sup, the union of the edge sets of J and H is the edge set of their join J ⊔ H. Since H = Jᶜ, their join is the complete graph ⊤ by sup_compl_eq_top, so SimpleGraph.edgeFinset_inj.mpr implies their edge sets are equal.
uses
SimpleGraph.edgeFinset_sup,SimpleGraph.edgeFinset_inj.mpr,sup_compl_eq_tophave hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 128)).edgeFinset := by rw [← SimpleGraph.edgeFinset_sup] change (J ⊔ Jᶜ).edgeFinset = _ exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top
The sum of the edge counts of J and H is 8128.
Because the edge sets of J and H are disjoint, the sum of their sizes equals the size of their union (Finset.card_union_of_disjoint), which is the edge set of the complete graph K₁₂₈ (SimpleGraph.card_edgeFinset_top_eq_card_choose_two). Rewriting the binomial coefficient via Nat.choose_two_right as 128 * 127 / 2 and evaluating it numerically gives 8128.
uses
Finset.card_union_of_disjoint,SimpleGraph.card_edgeFinset_top_eq_card_choose_two,Nat.choose_two_righthave htotal : J.edgeFinset.card + H.edgeFinset.card = 8128 := by rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two] rw [Nat.choose_two_right] norm_num
The sum of (out-degree choose 2) over all vertices equals 2688.
Since every vertex in D has out-degree 7 by hdeg, each term in the sum is 7.choose 2 = 21. Summing 21 over all 128 vertices yields 128 * 21 = 2688.
have hinc : (∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2688 := by simp [hdeg] norm_num [Nat.choose]
The strict 3z overlap inequality 3 * (2688 - |E(J)|) < 128 holds. automation
Substituting the sum of 2688 reduces the goal to 3 * (2688 - |E(J)|) < 128. Since |E(J)| + |E(H)| = 8128 and |E(H)| ≤ 5461, we have |E(J)| ≥ 8128 - 5461 = 2667, meaning 2688 - |E(J)| ≤ 21 and 3 * 21 = 63 < 128. The omega tactic concludes the proof by linear integer arithmetic.
change 3 * ((∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - J.edgeFinset.card) < 128 rw [hinc] omega
SimpleGraph.CliqueFree.card_edgeFinset_le- Turán's theorem: an (r+1)-clique-free graph on n vertices has at most (n² - (n % r)²) * (r - 1) / (2 * r) + (n % r).choose 2 edges.
SimpleGraph.disjoint_edgeFinset- The edge sets of two graphs are disjoint if and only if the graphs themselves are disjoint.
disjoint_compl_right- In any Heyting or Boolean algebra, an element is disjoint from its complement.
SimpleGraph.edgeFinset_sup- The edge set of the join (graph union) of two graphs is the union of their edge sets.
SimpleGraph.edgeFinset_inj.mpr- If two graphs are equal, their edge sets are equal.
sup_compl_eq_top- In a Boolean algebra, the join of any element with its complement is the top element.
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 has (card V).choose 2 edges.
Nat.choose_two_right- The binomial coefficient n.choose 2 equals n * (n - 1) / 2.
- Lines 1–5 establish decidability of adjacency in the common-predecessor graph as a technical typeclass requirement for edge counting and Turán's theorem.
- In the final step (line 40), the `omega` tactic automatically solves the linear integer arithmetic bounding the overlap expression.
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.
private instance in833_order128_decAdj (D : Digraph (Fin 128)) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instancetheorem digraph_128_regular_independence_small_overlap (D : Digraph (Fin 128)) [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 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card (Fin 128) := 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 ≤ 5461 := 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 128)).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 = 8128 := 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 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2688 := by simp [hdeg] norm_num [Nat.choose] change 3 * ((∑ v : Fin 128, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - J.edgeFinset.card) < 128 rw [hinc] omega