digraph_127_regular_independence_small_overlap
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
- digraph_127_four_cycles_under_extremal_and_cycle_criteriaA 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed…
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.
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.
intro u v unfold digraph_common_predecessor_graph infer_instance
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.
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 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.
uses
SimpleGraph.CliqueFree.card_edgeFinset_lehave hupper : H.edgeFinset.card ≤ 5376 := 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.
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.
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 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.
uses
SimpleGraph.edgeFinset_inj.mpr,SimpleGraph.edgeFinset_sup,sup_compl_eq_tophave 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
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.
uses
Finset.card_union_of_disjoint,Nat.choose_two_right,SimpleGraph.card_edgeFinset_top_eq_card_choose_twohave 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
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.
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]
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.
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).
- The private instance in lines 1–5 establishes decidability of adjacency in the common-predecessor graph, a formal prerequisite for Lean to construct finite edge sets and invoke Turán's theorem, but a detail taken for granted in informal mathematics.
- In the final step, natural number subtraction (which truncates at zero) and the linear inequalities are verified automatically by the omega tactic.
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 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