AFTD Auto-Formalizing Theoretical Domains

digraph_arc_domination_overlap_indegree_deficit_bound

theoremverified

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

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).

  1. 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.

    lines 2–4

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. 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).

    lines 15–19

    uses digraph_oriented_degree_deficit_overlap_budget, Finset.sum_const, Finset.card_univ, nsmul_eq_mul

      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 ⊢
  3. 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.

    lines 20–21

      cases z with
      | zero => simp at *; omega
  4. 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.

    lines 22–25

    uses Nat.choose_succ_succ'

      | succ z =>
        have hz : z ≤ Nat.choose (z+1) 2 := by
          rw [Nat.choose_succ_succ']
          simp
  5. choose(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.

    lines 26–28

    uses Nat.choose_succ_succ', Nat.choose_one_right

        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]
  6. 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.

    lines 29–30

        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.

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

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
See it in the graphDiscuss this resultChallenge it