digraph_oriented_girth_degree_deficit_overlap_budget
In a finite loopless oriented arc-dominated digraph whose directed cycles have at least g vertices, with g at least three, g−1 times the sum of positive outdegree-minus-indegree deficits is at most g times the repeated common-predecessor incidence count.
Statement
theorem digraph_oriented_girth_degree_deficit_overlap_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) : (g - 1) * (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card - (Finset.univ.filter fun w => D.Adj w v).card)) ≤ g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card)
- Source
- Girth-dependent collision accounting for the four-cycle campaign; experiment 13463.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- girth_charge_multiplicity_boundA charged subset of an m-element parent set obeys the girth-dependent multiplicity bound if it is proper whenever the parent set has fewer…
- digraph_short_parent_set_not_all_chargedIn a loopless digraph of directed girth at least g, a nonempty common-predecessor set with fewer than g members cannot have every parent…
- finite_endomap_local_degree_deficit_le_missing_imageFor a finite endomap whose image heads equal the original tails, the sum of positive local tail-count minus head-count deficits is at most…
- digraph_girth_arc_map_missing_budgetFor a loopless oriented digraph of directed girth at least g, g−1 times the number of missing predecessor arc-map images is at most g…
The proof, explained
By associating each directed edge to a chosen common predecessor of its endpoints, we define an endomap on the set of arcs whose local degree deficits are bounded by the size of the non-image arcs. The girth condition then bounds the non-image arcs by the repeated predecessor overlap count, completing the inequality.
Enable classical logic and set up the choice function.
We work classically and define a function selecting a common predecessor for each directed edge.
classical let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by intro u v h simpa [choose, h] using Classical.choose_spec (hdom u v h)
- Unresolved check: no step explains line(s) 3, 4, 5, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 38, 39 -- every tactic of the proof has to belong to some step
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 in516_girth_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_oriented_girth_degree_deficit_overlap_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) : (g - 1) * (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card - (Finset.univ.filter fun w => D.Adj w v).card)) ≤ g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) := by classical let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by intro u v h simpa [choose, h] using Classical.choose_spec (hdom u v h) let Arc := {e : α × α // D.Adj e.1 e.2} let f : Arc → Arc := fun e => ⟨(choose e.val.1 e.val.2,e.val.1), (hchoice _ _ e.property).1⟩ let r : Arc → Arc := fun y => if h : ∃ x, f x = y then Classical.choose h else y have hr : ∀ x, f (r (f x)) = f x := by intro x dsimp [r] split · rename_i h exact Classical.choose_spec h · rename_i h exact (h ⟨x,rfl⟩).elim let tail : Arc → α := fun e => e.val.1 let head : Arc → α := fun e => e.val.2 have hf : ∀ e, head (f e) = tail e := by intro e; rfl have hout (v : α) : (Finset.univ.filter fun e : Arc => tail e = v).card = (Finset.univ.filter fun w => D.Adj v w).card := by apply Finset.card_bij (fun e _ => e.val.2) · intro e he have ht : e.val.1 = v := (Finset.mem_filter.mp he).2 exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa [ht] using e.property⟩ · intro e he e' he' hh apply Subtype.ext apply Prod.ext · have h1 : e.val.1 = v := (Finset.mem_filter.mp he).2 have h2 : e'.val.1 = v := (Finset.mem_filter.mp he').2 exact h1.trans h2.symm · exact hh · intro w hw have ha : D.Adj v w := (Finset.mem_filter.mp hw).2 refine ⟨⟨(v,w),ha⟩, ?_, rfl⟩ simp [tail] have hin (v : α) : (Finset.univ.filter fun e : Arc => head e = v).card = (Finset.univ.filter fun w => D.Adj w v).card := by apply Finset.card_bij (fun e _ => e.val.1) · intro e he have ht : e.val.2 = v := (Finset.mem_filter.mp he).2 exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa [ht] using e.property⟩ · intro e he e' he' hh apply Subtype.ext apply Prod.ext · exact hh · have h1 : e.val.2 = v := (Finset.mem_filter.mp he).2 have h2 : e'.val.2 = v := (Finset.mem_filter.mp he').2 exact h1.trans h2.symm · intro w hw have ha : D.Adj w v := (Finset.mem_filter.mp hw).2 refine ⟨⟨(w,v),ha⟩, ?_, rfl⟩ simp [head] have hfinite := finite_endomap_local_degree_deficit_le_missing_image Arc α f r tail head hr hf have hsum : (∑ v : α, ((Finset.univ.filter fun w => D.Adj v w).card - (Finset.univ.filter fun w => D.Adj w v).card)) ≤ ((Finset.univ : Finset Arc) \ Finset.univ.image f).card := by simpa only [hout,hin] using hfinite have hbudget := digraph_girth_arc_map_missing_budget α D choose g hg hgirth hloop hori hchoice change (g - 1) * ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤ _ at hbudget exact (Nat.mul_le_mul_left (g - 1) hsum).trans hbudget