digraph_129_regular_independence_small_overlap
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.
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.
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
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).
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 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.
uses
SimpleGraph.CliqueFree.card_edgeFinset_lehave hupper : H.edgeFinset.card ≤ 5547 := 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.
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.
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 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.
uses
SimpleGraph.edgeFinset_sup,SimpleGraph.edgeFinset_inj.mpr,sup_compl_eq_tophave 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
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.
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 = 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
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.
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]
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.
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.
- The private instance in833_order129_decAdj on lines 1–5 establishes decidability of adjacency in the common-predecessor graph, which is required as a typeclass instance to apply Turán's theorem to the complement graph H.
- The subtraction in the overlap term is natural number subtraction. Because |E(J)| ≥ 2709, the difference 2709 - |E(J)| truncates to 0 in ℕ, so 3 * (2709 - |E(J)|) = 0, which is strictly less than 129.
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_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