digraph_arc_domination_overlap_indegree_deficit_bound
In an oriented loopless r-outregular arc-dominated digraph, the total shortfall of indegrees below r is at most choose(z+1,2), where z is the number of repeated common-predecessor pair incidences.
Statement
theorem digraph_arc_domination_overlap_indegree_deficit_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = r) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) : (∑ v : α, (r - (Finset.univ.filter fun w => D.Adj w v).card)) ≤ Nat.choose (Fintype.card α * Nat.choose r 2 - (digraph_common_predecessor_graph D).edgeFinset.card + 1) 2
- Source
- Overlap-to-regularity reduction in the general campaign route to OP-110.
- Verified
- 03 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.
- digraph_oriented_degree_deficit_overlap_budgetIn every finite loopless oriented arc-dominated digraph, twice the sum of positive outdegree-minus-indegree deficits is at most three…
The proof, explained
The proof applies a known degree deficit overlap budget inequality for oriented arc-dominated digraphs (digraph_oriented_degree_deficit_overlap_budget), which bounds twice the total degree deficit by three times the excess common-predecessor pairs z = |α|*choose(r,2) - |E(G_cp)|. Since the digraph is r-outregular, this budget specializes to 2 * ∑ v, (r - indegree(v)) ≤ 3 * z. The bound ∑ v, (r - indegree(v)) ≤ choose(z+1, 2) is then proved by case analysis on z: when z = 0 the deficit is 0, and when z ≥ 1 the bound follows from 2 * S ≤ 3 * (z+1) via Pascal's recurrence choose(z+2, 2) = (z+1) + choose(z+1, 2) and the inequality z ≤ choose(z+1, 2).
Adjacency in the common-predecessor graph of D is decidable.
To define the edge finset of the common-predecessor graph, its adjacency relation must be decidable. Unfolding the definition of digraph_common_predecessor_graph, two vertices u and v are adjacent if and only if they are distinct and share a common predecessor in D. Since the vertex type is finite with decidable equality and D has decidable adjacency, this existential condition is decidable, and typeclass inference (infer_instance) synthesizes the instance.
intro u v unfold digraph_common_predecessor_graph infer_instance
The total indegree deficit satisfies 2 * ∑ v, (r - indegree(v)) ≤ 3 * z, where z is the number of excess common-predecessor incidences.
Assuming classical logic, we invoke digraph_oriented_degree_deficit_overlap_budget, which bounds twice the total outdegree-indegree difference by three times the difference between the sum of choose(outdegree(v), 2) and the number of edges in the common-predecessor graph. By r-outregularity (hreg), every outdegree is r. We simplify the sum of the constant choose(r, 2) over all vertices to |α| * choose(r, 2) using Finset.sum_const, Finset.card_univ, and nsmul_eq_mul. Defining z to be |α| * choose(r, 2) - |E(G_cp)|, the inequality reduces to 2 * ∑ v, (r - indegree(v)) ≤ 3 * z, and the goal becomes showing that the total indegree deficit is at most choose(z+1, 2).
uses
digraph_oriented_degree_deficit_overlap_budget,Finset.sum_const,Finset.card_univ,nsmul_eq_mulclassical have h := digraph_oriented_degree_deficit_overlap_budget α D hloop hori hdom simp only [hreg, Finset.sum_const, Finset.card_univ, nsmul_eq_mul] at h generalize hz : Fintype.card α * Nat.choose r 2 - (digraph_common_predecessor_graph D).edgeFinset.card = z at h ⊢
The bound holds in the base case z = 0. automation
We split into cases on z. When z = 0, the hypothesis gives 2 * ∑ v, (r - indegree(v)) ≤ 0. In natural numbers, this forces each deficit term r - indegree(v) to be 0, so the total deficit is 0, which is at most choose(0+1, 2) = 0. Linear integer arithmetic (omega) finishes the case.
cases z with | zero => simp at *; omega
For any natural number z, z ≤ choose(z+1, 2).
In the successor case where the excess is z + 1, we first establish that z ≤ choose(z+1, 2). Expanding choose(z+1, 2) using Pascal's identity (Nat.choose_succ_succ') gives choose(z, 1) + choose(z, 2) = z + choose(z, 2), which is at least z.
uses
Nat.choose_succ_succ'| succ z => have hz : z ≤ Nat.choose (z+1) 2 := by rw [Nat.choose_succ_succ'] simpchoose(z+2, 2) = (z+1) + choose(z+1, 2).
Applying Pascal's recurrence (Nat.choose_succ_succ') to choose((z+1)+1, 1+1) yields choose(z+1, 1) + choose(z+1, 2). Rewriting with Nat.choose_one_right simplifies choose(z+1, 1) to z+1.
uses
Nat.choose_succ_succ',Nat.choose_one_righthave hc : Nat.choose (z+1+1) 2 = (z+1) + Nat.choose (z+1) 2 := by rw [Nat.choose_succ_succ'] simp only [Nat.choose_one_right]
The indegree deficit bound holds in the successor case. automation
Rewriting the goal with the recurrence for choose(z+2, 2), the required inequality becomes ∑ v, (r - indegree(v)) ≤ (z+1) + choose(z+1, 2). Combining the hypothesis that twice the sum is at most 3*(z+1) with the lemma z ≤ choose(z+1, 2), Presburger linear arithmetic (omega) closes the goal.
rw [hc] omega
digraph_oriented_degree_deficit_overlap_budget- In an oriented, loopless, arc-dominated finite digraph, twice the total degree deficit (outdegree minus indegree) is at most three times the difference between the sum of outdegree binomial coefficients choose(outdegree, 2) and the number of edges in the common-predecessor graph.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set scalar-multiplied by that value.
Finset.card_univ- The cardinality of the universal finset of a finite type is equal to the cardinality of the type.
nsmul_eq_mul- Scalar multiplication of a semiring element by a natural number equals multiplication by the natural number coerced into the semiring.
Nat.choose_succ_succ'- Pascal's recurrence for binomial coefficients: choose(n+1, k+1) = choose(n, k) + choose(n, k+1).
Nat.choose_one_right- For any natural number n, choose(n, 1) = n.
- The common-predecessor graph requires a decidability instance for its adjacency relation so that its edge finset can be formed; this instance is established beforehand via typeclass inference.
- In the inductive step, the integer linear arithmetic deduction that $2 S \le 3(z+1)$ and $z \le \binom{z+1}{2}$ imply $S \le (z+1) + \binom{z+1}{2}$ is closed by the `omega` decision procedure.
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 in478_overlap_deficit_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instancetheorem digraph_arc_domination_overlap_indegree_deficit_bound (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (r : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = r) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) : (∑ v : α, (r - (Finset.univ.filter fun w => D.Adj w v).card)) ≤ Nat.choose (Fintype.card α * Nat.choose r 2 - (digraph_common_predecessor_graph D).edgeFinset.card + 1) 2 := by classical have h := digraph_oriented_degree_deficit_overlap_budget α D hloop hori hdom simp only [hreg, Finset.sum_const, Finset.card_univ, nsmul_eq_mul] at h generalize hz : Fintype.card α * Nat.choose r 2 - (digraph_common_predecessor_graph D).edgeFinset.card = z at h ⊢ cases z with | zero => simp at *; omega | succ z => have hz : z ≤ Nat.choose (z+1) 2 := by rw [Nat.choose_succ_succ'] simp have hc : Nat.choose (z+1+1) 2 = (z+1) + Nat.choose (z+1) 2 := by rw [Nat.choose_succ_succ'] simp only [Nat.choose_one_right] rw [hc] omega