graph_125_three_clique_partition_oriented_cross_bound
For a graph on 125 vertices partitioned into three cliques, with at most 2583 graph edges, each part has at least seven vertices and every oriented subdigraph has at most 41 arcs between the parts.
Statement
theorem graph_125_three_clique_partition_oriented_cross_bound (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (D : Digraph (Fin 125)) [DecidableRel D.Adj] (col : Fin 125 → Fin 3) (hclique : ∀ u v, col u = col v → u ≠ v → G.Adj u v) (hsub : ∀ u v, D.Adj u v → G.Adj u v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hedges : G.edgeFinset.card ≤ 2583) : (∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) ∧ (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 41
- Source
- Edge-counting step for the order-125 reduction for OP-110.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_clique_partition_oriented_cross_degree_boundIf the color classes of a finite graph are cliques and an oriented digraph is a spanning subgraph, then twice its number of crossing arcs…
- Used by 1
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
The proof, explained
The theorem is proved by combining a general degree-counting inequality for clique-partitioned graphs with algebraic optimization. First, the general bound `graph_clique_partition_oriented_cross_degree_bound` shows that the three clique sizes n_0, n_1, n_2 and the number of cross-arcs x satisfy ∑_{i=0}^2 n_i(n_i-1) + 2x ≤ 2|E(G)| ≤ 5166. Since the parts partition the 125 vertices, adding n_0 + n_1 + n_2 = 125 yields n_0^2 + n_1^2 + n_2^2 + 2x ≤ 5291. By the Cauchy-Schwarz inequality, 3(n_0^2 + n_1^2 + n_2^2) ≥ (n_0 + n_1 + n_2)^2 = 125^2, which forces x ≤ 41. Finally, if any part had size at most 6, the sum of the remaining two would be at least 119, forcing the sum of their squares to exceed 5291; hence each part must have at least 7 vertices.
a^2 + b^2 + c^2 + 2x ≤ 5291
For any natural number n, the identity n(n - 1) + n = n^2 holds, checked by case analysis on whether n is 0 or succ n. Adding the equation a + b + c = 125 to the hypothesis a(a - 1) + b(b - 1) + c(c - 1) + 2x ≤ 5166 transforms each n(n - 1) + n into n^2, giving a^2 + b^2 + c^2 + 2x ≤ 5166 + 125 = 5291.
have hprod (n : ℕ) : n * (n - 1) + n = n*n := by cases n with | zero => simp | succ n => simp; ring have ha := hprod a have hb := hprod b have hc := hprod c have hsum : a*a + b*b + c*c + 2*x ≤ 5291 := by nlinarith
x ≤ 41
Over the integers, the squares of differences (a - b)^2, (b - c)^2, and (a - c)^2 are non-negative. Expanding these differences gives 3(a^2 + b^2 + c^2) - (a + b + c)^2 ≥ 0, which implies 3(a^2 + b^2 + c^2) ≥ 125^2 = 15625. Multiplying a^2 + b^2 + c^2 + 2x ≤ 5291 by 3 gives 3(a^2 + b^2 + c^2) + 6x ≤ 15873, so 6x ≤ 15873 - 15625 = 248, which implies x ≤ 41.
uses
sq_nonneghave hx : x ≤ 41 := by have h1 : (0:ℤ) ≤ ((a:ℤ) - b)^2 := sq_nonneg _ have h2 : (0:ℤ) ≤ ((b:ℤ) - c)^2 := sq_nonneg _ have h3 : (0:ℤ) ≤ ((a:ℤ) - c)^2 := sq_nonneg _ have hs' : (a:ℤ) + b + c = 125 := by exact_mod_cast hs have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5291 := by exact_mod_cast hsum have out : (x:ℤ) ≤ 41 := by nlinarith exact_mod_cast out
Any non-negative integers p, q, r satisfying p + q + r = 125 and p^2 + q^2 + r^2 ≤ 5291 satisfy p ≥ 7
Suppose for contradiction that p ≤ 6. Then q + r = 125 - p ≥ 119, so (q + r - 119)(q + r + 119) ≥ 0. Together with the non-negativity of (q - r)^2, this implies 2(q^2 + r^2) ≥ (q + r)^2 ≥ 119^2 = 14161, whence q^2 + r^2 ≥ 7080.5. Since p^2 ≥ 0, this forces p^2 + q^2 + r^2 > 5291, contradicting the upper bound p^2 + q^2 + r^2 ≤ 5291.
uses
sq_nonneg,Nat.zero_le,mul_nonneghave hsize (p q r : ℕ) (hs : p+q+r=125) (hh : p*p + q*q + r*r ≤ 5291) : 7 ≤ p := by by_contra hp have hp' : p ≤ 6 := by omega have hs' : (p:ℤ) + q + r = 125 := by exact_mod_cast hs have hh' : (p:ℤ)*p + q*q + r*r ≤ 5291 := by exact_mod_cast hh have hp'' : (p:ℤ) ≤ 6 := by exact_mod_cast hp' have hn : (0:ℤ) ≤ p := by exact_mod_cast Nat.zero_le p have hq : (0:ℤ) ≤ q := by exact_mod_cast Nat.zero_le q have hr : (0:ℤ) ≤ r := by exact_mod_cast Nat.zero_le r have hdiff : (0:ℤ) ≤ ((q:ℤ)-(r:ℤ))^2 := sq_nonneg _ have hbig : (0:ℤ) ≤ ((q:ℤ)+(r:ℤ)-119) * ((q:ℤ)+(r:ℤ)+119) := mul_nonneg (by omega) (by omega) nlinarith [sq_nonneg (p:ℤ)]
7 ≤ a ∧ 7 ≤ b ∧ 7 ≤ c ∧ x ≤ 41
Since 2x ≥ 0, we have a^2 + b^2 + c^2 ≤ 5291. Applying the helper bound `hsize` to (a, b, c), (b, a, c), and (c, a, b) gives 7 ≤ a, 7 ≤ b, and 7 ≤ c respectively. Combining these three inequalities with x ≤ 41 finishes the lemma.
have hh : a*a+b*b+c*c ≤ 5291 := by omega refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩ · apply hsize b a c <;> omega · apply hsize c a b <;> omega
The sizes n_0, n_1, n_2 of the three color classes satisfy n_0 + n_1 + n_2 = 125
Let S_i = {v | col(v) = i} be the color classes, n_i = |S_i| their cardinalities, and cross the number of oriented cross-arcs. By `Finset.card_eq_sum_card_fiberwise`, the total number of vertices (125) equals the sum of the cardinalities of the fibers of col over Fin 3, which expands to n_0 + n_1 + n_2 = 125.
uses
Finset.card_eq_sum_card_fiberwise,Finset.card_univ,Fintype.card_fin,Fin.sum_univ_succ,Fin.sum_univ_zero,Nat.add_zeroclassical let S : Fin 3 → Finset (Fin 125) := fun i => Finset.univ.filter fun v => col v = i let n : Fin 3 → ℕ := fun i => (S i).card let cross : ℕ := ∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card have hsizes : n 0 + n 1 + n 2 = 125 := by have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := (Finset.univ : Finset (Fin 125))) (t := (Finset.univ : Finset (Fin 3))) (by simp) simp only [Finset.card_univ, Fintype.card_fin, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero] at h change 125 = n 0 + (n 1 + n 2) at h omega
n_0(n_0 - 1) + n_1(n_1 - 1) + n_2(n_2 - 1) + 2 · cross ≤ 5166
We apply `graph_clique_partition_oriented_cross_degree_bound`, which establishes that the sum of the clique edge terms plus 2 · cross is at most 2|E(G)|. Unfolding the sum over Fin 3 into the three explicit terms and using the graph edge bound |E(G)| ≤ 2583 yields the upper bound 2 · 2583 = 5166.
uses
graph_clique_partition_oriented_cross_degree_bound,Fin.sum_univ_succ,Fin.sum_univ_zero,Fin.succ_zero_eq_one,Fin.succ_one_eq_two,Nat.add_zerohave hbound := graph_clique_partition_oriented_cross_degree_bound (Fin 125) (Fin 3) G D col hclique hsub hori change (∑ i : Fin 3, n i * (n i - 1)) + 2 * cross ≤ 2 * G.edgeFinset.card at hbound have hre : (∑ i : Fin 3, n i * (n i - 1)) = n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) := by simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one, Fin.succ_one_eq_two, Nat.add_zero] omega rw [hre] at hbound have ht : n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) + 2*cross ≤ 5166 := by omega
The bounds 7 ≤ n_i for each i ∈ Fin 3 and cross ≤ 41 hold, completing the proof
We instantiate lemma `in833_arith125` with the part sizes n_0, n_1, n_2 and the cross-arc count cross. This supplies 7 ≤ n_0, 7 ≤ n_1, 7 ≤ n_2, and cross ≤ 41. We conclude by dispatching the universal quantifier 7 ≤ n_i via case analysis on i ∈ Fin 3 and taking the cross-arc inequality directly.
uses
in833_arith125have h := in833_arith125 (n 0) (n 1) (n 2) cross hsizes ht constructor · intro i change 7 ≤ n i fin_cases i · exact h.1 · exact h.2.1 · exact h.2.2.1 · exact h.2.2.2
sq_nonneg- The square of any element in an ordered semiring (such as the integers) is non-negative.
mul_nonneg- The product of two non-negative numbers is non-negative.
Nat.zero_le- Every natural number is greater than or equal to zero.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set is the sum of the cardinalities of its fibers under any map.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
Fin.sum_univ_succ- A sum over Fin (n + 1) splits into the term at 0 plus the sum over the remaining n elements.
Fin.sum_univ_zero- A sum over the empty type Fin 0 is 0.
Nat.add_zero- Adding zero to a natural number leaves it unchanged.
graph_clique_partition_oriented_cross_degree_bound- For a graph partitioned into cliques and any oriented subdigraph, the sum over all parts of n_i * (n_i - 1) plus twice the number of cross-arcs is at most twice the number of graph edges.
Fin.succ_zero_eq_one- The successor of 0 in Fin n is 1.
Fin.succ_one_eq_two- The successor of 1 in Fin n is 2.
in833_arith125- If natural numbers a, b, c sum to 125 and a(a-1) + b(b-1) + c(c-1) + 2x ≤ 5166, then a ≥ 7, b ≥ 7, c ≥ 7, and x ≤ 41.
- The algebraic deductions establishing the lower bounds on part sizes and the upper bound on cross-arcs rely on `nlinarith` to combine quadratic non-negativity hypotheses with linear relations.
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.
set_option maxHeartbeats 2000000set_option maxRecDepth 4096private lemma in833_arith125 (a b c x : ℕ) (hs : a + b + c = 125) (h : a * (a - 1) + b * (b - 1) + c * (c - 1) + 2*x ≤ 5166) : 7 ≤ a ∧ 7 ≤ b ∧ 7 ≤ c ∧ x ≤ 41 := by have hprod (n : ℕ) : n * (n - 1) + n = n*n := by cases n with | zero => simp | succ n => simp; ring have ha := hprod a have hb := hprod b have hc := hprod c have hsum : a*a + b*b + c*c + 2*x ≤ 5291 := by nlinarith have hx : x ≤ 41 := by have h1 : (0:ℤ) ≤ ((a:ℤ) - b)^2 := sq_nonneg _ have h2 : (0:ℤ) ≤ ((b:ℤ) - c)^2 := sq_nonneg _ have h3 : (0:ℤ) ≤ ((a:ℤ) - c)^2 := sq_nonneg _ have hs' : (a:ℤ) + b + c = 125 := by exact_mod_cast hs have hh' : (a:ℤ)*a + b*b + c*c + 2*x ≤ 5291 := by exact_mod_cast hsum have out : (x:ℤ) ≤ 41 := by nlinarith exact_mod_cast out have hsize (p q r : ℕ) (hs : p+q+r=125) (hh : p*p + q*q + r*r ≤ 5291) : 7 ≤ p := by by_contra hp have hp' : p ≤ 6 := by omega have hs' : (p:ℤ) + q + r = 125 := by exact_mod_cast hs have hh' : (p:ℤ)*p + q*q + r*r ≤ 5291 := by exact_mod_cast hh have hp'' : (p:ℤ) ≤ 6 := by exact_mod_cast hp' have hn : (0:ℤ) ≤ p := by exact_mod_cast Nat.zero_le p have hq : (0:ℤ) ≤ q := by exact_mod_cast Nat.zero_le q have hr : (0:ℤ) ≤ r := by exact_mod_cast Nat.zero_le r have hdiff : (0:ℤ) ≤ ((q:ℤ)-(r:ℤ))^2 := sq_nonneg _ have hbig : (0:ℤ) ≤ ((q:ℤ)+(r:ℤ)-119) * ((q:ℤ)+(r:ℤ)+119) := mul_nonneg (by omega) (by omega) nlinarith [sq_nonneg (p:ℤ)] have hh : a*a+b*b+c*c ≤ 5291 := by omega refine ⟨hsize a b c hs hh, ?_, ?_, hx⟩ · apply hsize b a c <;> omega · apply hsize c a b <;> omegatheorem graph_125_three_clique_partition_oriented_cross_bound (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (D : Digraph (Fin 125)) [DecidableRel D.Adj] (col : Fin 125 → Fin 3) (hclique : ∀ u v, col u = col v → u ≠ v → G.Adj u v) (hsub : ∀ u v, D.Adj u v → G.Adj u v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hedges : G.edgeFinset.card ≤ 2583) : (∀ i, 7 ≤ (Finset.univ.filter fun v => col v = i).card) ∧ (∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card) ≤ 41 := by classical let S : Fin 3 → Finset (Fin 125) := fun i => Finset.univ.filter fun v => col v = i let n : Fin 3 → ℕ := fun i => (S i).card let cross : ℕ := ∑ v : Fin 125, (Finset.univ.filter fun w => col w ≠ col v ∧ D.Adj v w).card have hsizes : n 0 + n 1 + n 2 = 125 := by have h := Finset.card_eq_sum_card_fiberwise (f := col) (s := (Finset.univ : Finset (Fin 125))) (t := (Finset.univ : Finset (Fin 3))) (by simp) simp only [Finset.card_univ, Fintype.card_fin, Fin.sum_univ_succ, Fin.sum_univ_zero, Nat.add_zero] at h change 125 = n 0 + (n 1 + n 2) at h omega have hbound := graph_clique_partition_oriented_cross_degree_bound (Fin 125) (Fin 3) G D col hclique hsub hori change (∑ i : Fin 3, n i * (n i - 1)) + 2 * cross ≤ 2 * G.edgeFinset.card at hbound have hre : (∑ i : Fin 3, n i * (n i - 1)) = n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) := by simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, Fin.succ_zero_eq_one, Fin.succ_one_eq_two, Nat.add_zero] omega rw [hre] at hbound have ht : n 0 * (n 0 - 1) + n 1 * (n 1 - 1) + n 2 * (n 2 - 1) + 2*cross ≤ 5166 := by omega have h := in833_arith125 (n 0) (n 1) (n 2) cross hsizes ht constructor · intro i change 7 ≤ n i fin_cases i · exact h.1 · exact h.2.1 · exact h.2.2.1 · exact h.2.2.2