digraph_girth_arc_map_weighted_budget
For a loopless oriented digraph of directed girth at least g, with g at least three and chosen common predecessors for its arcs, g−1 times dirty parents plus missing arc-map images is bounded by twice g times overlap plus the displayed multiplicity correction.
Statement
theorem digraph_girth_arc_map_weighted_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) : 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.val.1 e.val.2 e.property).1⟩ let dirty : Finset α := Finset.univ.filter fun u => ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b (g - 1) * (dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card) ≤ 2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_girth_correction α D g
- Source
- Girth-dependent center budget for the four-cycle campaign; experiment 13474.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 16
- 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.
- digraph_common_predecessor_girth_correctionThe sum, over common-predecessor edges of multiplicity at least two, of the positive part of g+1 minus twice the number of common…
- girth_parent_charge_weight_boundA charged subset of m parents satisfying the girth-dependent proper-subset condition has the displayed weighted parent-plus-charge bound.
- 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…
- digraph_oriented_arc_map_missing_dirty_budgetFor a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs…
- digraph_common_predecessor_overlap_incidence_identityFor a finite digraph, the total excess multiplicity of edges of its common-predecessor graph equals the sum of unordered pairs in its…
- finite_endomap_missing_image_eq_nonrepresentativesFor a finite endomap with a chosen representative from each nonempty fiber, the number of elements outside its image equals the number of…
- finite_function_collision_head_pair_injectiveGiven an injective tail-head encoding and a map whose fibers have a fixed tail, encoding each nonrepresentative by its tail and the…
- finite_endomap_collision_charge_identityFor a finite endomap whose fibers share a tail and whose elements are determined by tail and head, the number of missing image elements is…
- digraph_oriented_two_parent_collision_limitIn an oriented loopless digraph, if two vertices are dominated by both members of a displayed pair and have no common predecessor outside…
- digraph_two_common_parents_edge_multiplicityTwo distinct vertices with two distinct common predecessors form an edge in the common-predecessor graph with multiplicity at least two.
- digraph_arc_choice_collision_repeated_pairWhen two outgoing arcs of a loopless digraph receive the same chosen common predecessor, their distinct heads form an auxiliary edge with…
- digraph_two_parent_collision_charge_card_le_oneIn a loopless oriented digraph with a chosen common predecessor for every arc, if two vertices have exactly two common predecessors, at…
- finite_parent_collision_budget_with_coverUnder the same repeated-pair parent and charge assumptions, any dirty set covered by the parent sets and any missing set no larger than…
- oriented_overlap_multiplicity_budgetSummed multiplicities and charges cost at most three times overlap when multiplicity-two edges have at most one charge.
- Used by 2
- digraph_girth_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
- digraph_girth_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least g, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
The proof, explained
The theorem is proved by charging missing arcs and dirty parents to the repeated edges of the common predecessor graph. Each collision of the arc choice endomap f identifies an edge in the common predecessor graph with multiple common parents, allowing the number of missing arcs to be bounded by the total collision charge. The directed girth lower bound g ensures that edges with fewer than g parents cannot have all their parents charged, enabling an edge-by-edge weight inequality from girth_parent_charge_weight_bound. Summing this inequality over all repeated edges and expressing the parent multiplicities in terms of vertex out-degree overlap and the girth correction term yields the result.
Adjacency in the common predecessor graph is decidable. automation
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 in D. Since the digraph vertex type α is finite and adjacency in D is decidable, this existential condition is decidable by typeclass synthesis.
private instance in516_girth_weighted_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_instance
The arc endomap f and a chosen section r satisfy f(r(f(x))) = f(x) for all arcs x.
Working classically, we define the type of arcs as pairs of vertices with an adjacency witness. The map f sends each arc (u, v) to (choose(u, v), u), which is valid since choose(u, v) is a common predecessor of u and v. Using Classical.choose, r selects a preimage for every arc in the image of f and acts as the identity elsewhere, guaranteeing f(r(f(x))) = f(x).
uses
Classical.choose_specclassical 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.val.1 e.val.2 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
The arc projections satisfy htail (f x = f y → tail x = tail y) and an arc is uniquely determined by its tail and head.
The second component of f(x) is tail(x), so any collision f x = f y implies tail x = tail y by applying congrArg to the second component. Moreover, since an arc is a directed edge between its tail and head, the map x ↦ (tail x, head x) is injective by Subtype.ext.
uses
congrArg,Subtype.extlet tail : Arc → α := fun x => x.val.1 let head : Arc → α := fun x => x.val.2 have htail : ∀ x y, f x = f y → tail x = tail y := by intro x y h exact congrArg (fun z : Arc => z.val.2) h have hkey : Function.Injective (fun x => (tail x, head x)) := by intro x y h exact Subtype.ext h
We define the parent sets, the edges of the common predecessor graph, repeated edges, dirty vertices, missing arcs, non-representatives, and edge charges.
For an unordered pair e, parent(e) is the finset of common predecessors of its vertices. The edges of the common predecessor graph are pairs sharing at least one parent, and repeated is the subset of edges with at least 2 parents. Dirty vertices are those sharing two or more common out-neighbors with another vertex. Missing arcs are arcs outside the image of f. Non-representative arcs are those with r(f(x)) ≠ x; each non-representative arc x defines an unordered pair edge(x) = s(head(x), head(r(f(x)))), and charge(e) collects the tails of all non-representative arcs that map to e.
let parent : Sym2 α → Finset α := fun e => Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x let edges := (digraph_common_predecessor_graph D).edgeFinset let repeated := edges.filter fun e => 2 ≤ (parent e).card let dirty : Finset α := Finset.univ.filter fun u => ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b let missing : Finset Arc := Finset.univ \ Finset.univ.image f let nonrep : Finset Arc := Finset.univ.filter fun x => r (f x) ≠ x let edge : Arc → Sym2 α := fun x => s(head x, head (r (f x))) let charge : Sym2 α → Finset α := fun e => (nonrep.filter fun x => edge x = e).image tail
For every arc x, r(f(x)) has the same tail as x and identical predecessor choice, and if r(f(x)) ≠ x then their heads are distinct.
Projecting the equality f(r(f(x))) = f(x) onto the two components shows that tail(r(f(x))) = tail(x) and choose(tail(x), head(r(f(x)))) = choose(tail(x), head(x)). If r(f(x)) ≠ x, their heads must be distinct, because equal tails and equal heads would make the arcs identical by Subtype.ext and Prod.ext.
uses
congrArg,Subtype.ext,Prod.exthave hdata (x : Arc) : tail (r (f x)) = tail x ∧ choose (tail x) (head (r (f x))) = choose (tail x) (head x) := by have h := hr x have ht : tail (r (f x)) = tail x := htail _ _ h have hc : choose (tail (r (f x))) (head (r (f x))) = choose (tail x) (head x) := congrArg (fun z : Arc => z.val.1) h rw [ht] at hc exact ⟨ht,hc⟩ have hheads (x : Arc) (hx : r (f x) ≠ x) : head x ≠ head (r (f x)) := by intro h apply hx apply Subtype.ext exact Prod.ext (hdata x).1 h.symm
For every non-representative arc x, edge(x) belongs to repeated.
Since head(x) ≠ head(r(f(x))) and both are out-neighbors of tail(x), and choose(tail(x), head(x)) is a common predecessor of both heads distinct from tail(x) by looplessness, digraph_arc_choice_collision_repeated_pair shows that s(head(x), head(r(f(x)))) is an edge with at least 2 common parents, so it belongs to repeated.
uses
digraph_arc_choice_collision_repeated_pair,Finset.mem_filter.mprhave hcharged (x : Arc) (hx : r (f x) ≠ x) : edge x ∈ repeated := by have hd := hdata x have ha : D.Adj (tail x) (head x) := x.property have hb : D.Adj (tail x) (head (r (f x))) := by have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [hd.1] at hp exact hp have hh := digraph_arc_choice_collision_repeated_pair α D choose hloop hchoice (tail x) (head x) (head (r (f x))) (hheads x hx) ha hb hd.2.symm exact Finset.mem_filter.mpr hh
The number of missing arcs is bounded by the sum of charges over all repeated edges.
By the finite endomap collision charging identity finite_endomap_collision_charge_identity, the number of arcs outside the image of f equals the sum of the cardinalities of charge(e) over all repeated edges, which immediately implies the inequality.
uses
finite_endomap_collision_charge_identityhave hcharge : missing.card ≤ ∑ e ∈ repeated, (charge e).card := by have h := finite_endomap_collision_charge_identity Arc α α f r tail head repeated hr htail hkey hcharged change missing.card = ∑ e ∈ repeated, (charge e).card at h exact h.le
The set of dirty vertices is contained in the union of parent sets over all repeated edges.
A dirty vertex u shares two distinct out-neighbors a ≠ b with another vertex p ≠ u. By digraph_two_common_parents_edge_multiplicity, s(a, b) has at least two common parents (u and p) and thus belongs to repeated. Since u is adjacent to both a and b, u belongs to parent(s(a, b)).
uses
digraph_two_common_parents_edge_multiplicity,Finset.mem_biUnion.mpr,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univ,Sym2.mem_iff.mphave hdirty : dirty ⊆ repeated.biUnion parent := by intro u hu obtain ⟨_,a,b,p,hab,hpu,hua,hub,hpa,hpb⟩ := Finset.mem_filter.mp hu have hh := digraph_two_common_parents_edge_multiplicity α D a b u p hab hpu.symm hua hub hpa hpb apply Finset.mem_biUnion.mpr refine ⟨s(a,b), Finset.mem_filter.mpr hh, ?_⟩ apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact hua · exact hub
For every repeated edge e, charge(e) is a subset of parent(e), and parent(e) has cardinality at least 2.
Every vertex in charge(e) is the tail of some arc x whose head and counterpart head form e; since tail(x) = tail(r(f(x))) is adjacent to both heads, it is a common predecessor of e, so charge(e) ⊆ parent(e). The bound 2 ≤ |parent(e)| is immediate from the definition of repeated.
uses
Finset.mem_image.mp,Finset.mem_filter.mp,Finset.mem_univ,Sym2.mem_iff.mphave hsubset : ∀ e ∈ repeated, charge e ⊆ parent e := by intro e he u hu obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu have hxe : edge x = e := (Finset.mem_filter.mp hx).2 apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ intro z hz rw [← hxe] at hz change z ∈ s(head x, head (r (f x))) at hz rcases Sym2.mem_iff.mp hz with rfl | rfl · exact x.property · have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [(hdata x).1] at hp exact hp have hm : ∀ e ∈ repeated, 2 ≤ (parent e).card := by intro e he exact (Finset.mem_filter.mp he).2
If a repeated edge e has exactly two parents, its charge has cardinality at most 1.
Writing e as an unordered pair s(a, b), the parents are those vertices adjacent to both a and b. Any vertex in charge(s(a, b)) must satisfy choose(p, a) = choose(p, b). In an oriented loopless digraph with exactly two common parents, digraph_two_parent_collision_charge_card_le_one implies that at most one parent can satisfy this equality, so |charge(e)| ≤ 1.
uses
Sym2.ind,true_and,Sym2.mem_mk_left,Sym2.mem_mk_right,digraph_two_parent_collision_charge_card_le_one,Finset.card_le_cardhave htwo : ∀ e ∈ repeated, (parent e).card = 2 → (charge e).card ≤ 1 := by intro e he hm2 induction e using Sym2.ind with | h a b => have hparentEq : parent s(a,b) = Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by ext p simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩ · rintro ⟨ha,hb⟩ x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact ha · exact hb rw [hparentEq] at hm2 have hlim := digraph_two_parent_collision_charge_card_le_one α D choose hloop hori hchoice a b hm2 have hsub : charge s(a,b) ⊆ Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by intro u hu obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2 have hd := hdata x have ha : D.Adj (tail x) (head x) := x.property have hb : D.Adj (tail x) (head (r (f x))) := by have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [hd.1] at hp exact hp apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩ · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb, by simpa [hxa,hxb] using hd.2.symm⟩ · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha, by simpa [hxa,hxb] using hd.2⟩ have hh := Finset.card_le_card hsub exact hh.trans hlim
For any repeated edge e with strictly fewer than g parents, |charge(e)| < |parent(e)|.
Writing e = s(a, b), any charged parent satisfies choose(p, a) = choose(p, b). If all common parents satisfied this and |parent(e)| < g, tracing backward along choice arcs would form a directed cycle of length less than g, contradicting the girth hypothesis. This is established by digraph_short_parent_set_not_all_charged, which yields |charge(e)| < |parent(e)|.
uses
Sym2.ind,true_and,Sym2.mem_mk_left,Sym2.mem_mk_right,Finset.card_pos.mp,digraph_short_parent_set_not_all_charged,Finset.card_le_cardhave hshort : ∀ e ∈ repeated, (parent e).card < g → (charge e).card < (parent e).card := by intro e he hs induction e using Sym2.ind with | h a b => have hparentEq : parent s(a,b) = Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by ext p simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩ · rintro ⟨ha,hb⟩ x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact ha · exact hb have hnonempty : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).Nonempty := by apply Finset.card_pos.mp have h := hm s(a,b) he rw [hparentEq] at h omega have hlt := digraph_short_parent_set_not_all_charged α D choose g a b hloop hchoice hgirth hnonempty (by simpa [hparentEq] using hs) have hsub : charge s(a,b) ⊆ Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by intro u hu obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2 have hd := hdata x have ha : D.Adj (tail x) (head x) := x.property have hb : D.Adj (tail x) (head (r (f x))) := by have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [hd.1] at hp exact hp apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩ · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb, by simpa [hxa,hxb] using hd.2.symm⟩ · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha, by simpa [hxa,hxb] using hd.2⟩ have hsub' : charge s(a,b) ⊆ (Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b)).filter (fun p => choose p a = choose p b) := by intro p hp have hh := Finset.mem_filter.mp (hsub hp) exact Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, hh.2.1, hh.2.2.1⟩, hh.2.2.2⟩ have hc := Finset.card_le_card hsub' rw [hparentEq] omega
The sum of |parent(e)| - 1 over repeated edges equals the total out-degree pair overlap sum ∑_v choose(out_deg(v), 2) minus the number of edges.
Every edge in the common predecessor graph has at least one common parent (hparentPos). For edges with strictly fewer than 2 parents, |parent(e)| = 1, so |parent(e)| - 1 = 0; thus the sum over repeated edges equals the sum over all edges. By digraph_common_predecessor_overlap_incidence_identity, this sum equals the total vertex out-degree pair combinations minus the edge count.
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.card_pos.mpr,digraph_common_predecessor_overlap_incidence_identity,Finset.sum_filter,Finset.sum_congrhave hparentPos : ∀ e ∈ edges, 1 ≤ (parent e).card := by intro e he induction e using Sym2.ind with | h a b => rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he obtain ⟨_,p,hpa,hpb⟩ := he apply Finset.card_pos.mpr refine ⟨p, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩ intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact hpa · exact hpb have hsum : (∑ e ∈ repeated, ((parent e).card - 1)) = (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - edges.card := by have hall := digraph_common_predecessor_overlap_incidence_identity α D have hs : (∑ e ∈ repeated, ((parent e).card - 1)) = ∑ e ∈ edges, ((parent e).card - 1) := by dsimp [repeated] rw [Finset.sum_filter] apply Finset.sum_congr rfl intro e he by_cases h : 2 ≤ (parent e).card · simp [h] · have hp := hparentPos e he have hc : (parent e).card = 1 := by omega simp [h,hc] rw [hs] exact hall
The sum of parent and charge sizes satisfies (g - 1)(∑ |parent(e)| + ∑ |charge(e)|) ≤ 2g(∑ (|parent(e)| - 1)) + girth_correction, and dirty vertices are bounded by ∑ |parent(e)|.
By the union bound, |dirty| ≤ ∑ |parent(e)|. For each repeated edge e, girth_parent_charge_weight_bound applies using 2 ≤ |parent(e)|, |charge(e)| ≤ |parent(e)|, and |charge(e)| < |parent(e)| when |parent(e)| < g, giving (g - 1)(|parent(e)| + |charge(e)|) ≤ 2g(|parent(e)| - 1) + (g + 1 - 2|parent(e)|). Summing over repeated edges via Finset.sum_le_sum and distributing yields the aggregated budget inequality, where the second sum matches digraph_common_predecessor_girth_correction by definition.
uses
Finset.card_le_card,Finset.card_biUnion_le,girth_parent_charge_weight_bound,Finset.sum_le_sum,Nat.mul_add,Finset.mul_sum,Finset.sum_add_distrib,Finset.sum_filter,Finset.sum_congrhave hsum_parent : dirty.card ≤ ∑ e ∈ repeated, (parent e).card := by exact (Finset.card_le_card hdirty).trans Finset.card_biUnion_le have hedge : ∀ e ∈ repeated, (g - 1) * ((parent e).card + (charge e).card) ≤ 2 * g * ((parent e).card - 1) + (g + 1 - 2 * (parent e).card) := by intro e he exact girth_parent_charge_weight_bound g (parent e).card (charge e).card hg (hm e he) (Finset.card_le_card (hsubset e he)) (hshort e he) have hsumineq := Finset.sum_le_sum hedge have hbudget : (g - 1) * ((∑ e ∈ repeated, (parent e).card) + (∑ e ∈ repeated, (charge e).card)) ≤ 2 * g * (∑ e ∈ repeated, ((parent e).card - 1)) + (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) := by simpa only [Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib] using hsumineq have hcorrection : (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) = digraph_common_predecessor_girth_correction α D g := by simp only [digraph_common_predecessor_girth_correction, repeated, Finset.sum_filter] apply Finset.sum_congr · ext e simp [edges] · intro e he simp [parent]
(g - 1) * (|dirty| + |missing|) ≤ 2 * g * (overlap) + girth_correction.
Adding |dirty| ≤ ∑ |parent(e)| and |missing| ≤ ∑ |charge(e)| and multiplying by g - 1 via Nat.mul_le_mul_left and Nat.add_le_add bounds the left-hand side by the aggregated budget. Replacing the repeated parent sum by the out-degree overlap identity and the correction sum by its definition completes the proof by transitivity.
uses
Nat.mul_le_mul_left,Nat.add_le_addhave hscaled := Nat.mul_le_mul_left (g - 1) (Nat.add_le_add hsum_parent hcharge) change (g - 1) * (dirty.card + missing.card) ≤ _ rw [← hsum, ← hcorrection] exact hscaled.trans hbudget
Classical.choose_spec- Given an existential proof h : ∃ x, p x, Classical.choose h satisfies the predicate p.
congrArg- If x = y, then f x = f y.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
digraph_arc_choice_collision_repeated_pair- In a loopless digraph with common predecessor choice, if two distinct out-neighbors a ≠ b of u have choose u a = choose u b, then s(a, b) is an edge of the common predecessor graph with at least 2 common parents.
Finset.mem_filter.mpr- An element belongs to a filtered finset if it belongs to the base finset and satisfies the filter predicate.
Finset.mem_filter.mp- If an element belongs to a filtered finset, it belongs to the base finset and satisfies the filter predicate.
finite_endomap_collision_charge_identity- For a finite endomap with a section on its image and tail/head coordinates, the number of missing elements equals the sum of collision charges over a covering set of edges.
digraph_two_common_parents_edge_multiplicity- In a digraph, if distinct vertices a ≠ b have two distinct common parents t ≠ p, then s(a, b) is an edge of the common predecessor graph with at least 2 common parents.
Finset.mem_biUnion.mpr- If an element belongs to the finset associated to some index, it belongs to the indexed union (biUnion).
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Sym2.mem_iff.mp- An element x belongs to an unordered pair s(a, b) if and only if x = a or x = b.
Finset.mem_image.mp- If an element belongs to the image of a finset under a function, it is the image of some element in that finset.
Sym2.ind- A property holds for all unordered pairs if it holds for every pair of the form s(a, b).
true_and- The propositional identity (True ∧ p) = p.
Sym2.mem_mk_left- The left element belongs to the unordered pair: x ∈ s(x, y).
Sym2.mem_mk_right- The right element belongs to the unordered pair: y ∈ s(x, y).
digraph_two_parent_collision_charge_card_le_one- In an oriented loopless digraph, if an unordered pair has exactly 2 common parents, at most one of them can satisfy choose p a = choose p b.
Finset.card_le_card- If s ⊆ t for finsets, then |s| ≤ |t|.
Finset.card_pos.mp- If 0 < |s| for a finset, then s is nonempty.
Finset.card_pos.mpr- If a finset is nonempty, then 0 < |s|.
digraph_short_parent_set_not_all_charged- In a loopless digraph of directed girth at least g, if an edge has non-empty common parent set of size strictly less than g, not all parents can have identical predecessor choice on the endpoints.
SimpleGraph.mem_edgeFinset- An unordered pair belongs to the edge finset of a simple graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
digraph_common_predecessor_overlap_incidence_identity- The sum of |parent(e)| - 1 over all edges in the common predecessor graph equals the sum of choose(out_deg(v), 2) over all vertices minus the number of edges.
Finset.sum_filter- Rewrites a sum over a filtered finset as a sum over the whole finset with an indicator.
Finset.sum_congr- Two finset sums are equal if their index sets are equal and their summands agree on all elements.
Finset.card_biUnion_le- The cardinality of an indexed union of finsets is at most the sum of their individual cardinalities.
girth_parent_charge_weight_bound- If 3 ≤ g, 2 ≤ m, c ≤ m, and m < g → c < m, then (g - 1) * (m + c) ≤ 2 * g * (m - 1) + (g + 1 - 2 * m).
Finset.sum_le_sum- If f i ≤ g i for all elements i of a finset s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
Nat.mul_add- Multiplication distributes over addition: n * (m + k) = n * m + n * k.
Finset.mul_sum- Multiplication by a constant distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_add_distrib- The sum of a pointwise sum of functions equals the sum of their individual sums.
Nat.mul_le_mul_left- If n ≤ m, then k * n ≤ k * m for natural numbers.
Nat.add_le_add- If a ≤ b and c ≤ d, then a + c ≤ b + d for natural numbers.
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_weighted_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_girth_arc_map_weighted_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) : 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.val.1 e.val.2 e.property).1⟩ let dirty : Finset α := Finset.univ.filter fun u => ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b (g - 1) * (dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card) ≤ 2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_girth_correction α D g := by classical 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.val.1 e.val.2 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 x => x.val.1 let head : Arc → α := fun x => x.val.2 have htail : ∀ x y, f x = f y → tail x = tail y := by intro x y h exact congrArg (fun z : Arc => z.val.2) h have hkey : Function.Injective (fun x => (tail x, head x)) := by intro x y h exact Subtype.ext h let parent : Sym2 α → Finset α := fun e => Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x let edges := (digraph_common_predecessor_graph D).edgeFinset let repeated := edges.filter fun e => 2 ≤ (parent e).card let dirty : Finset α := Finset.univ.filter fun u => ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b let missing : Finset Arc := Finset.univ \ Finset.univ.image f let nonrep : Finset Arc := Finset.univ.filter fun x => r (f x) ≠ x let edge : Arc → Sym2 α := fun x => s(head x, head (r (f x))) let charge : Sym2 α → Finset α := fun e => (nonrep.filter fun x => edge x = e).image tail have hdata (x : Arc) : tail (r (f x)) = tail x ∧ choose (tail x) (head (r (f x))) = choose (tail x) (head x) := by have h := hr x have ht : tail (r (f x)) = tail x := htail _ _ h have hc : choose (tail (r (f x))) (head (r (f x))) = choose (tail x) (head x) := congrArg (fun z : Arc => z.val.1) h rw [ht] at hc exact ⟨ht,hc⟩ have hheads (x : Arc) (hx : r (f x) ≠ x) : head x ≠ head (r (f x)) := by intro h apply hx apply Subtype.ext exact Prod.ext (hdata x).1 h.symm have hcharged (x : Arc) (hx : r (f x) ≠ x) : edge x ∈ repeated := by have hd := hdata x have ha : D.Adj (tail x) (head x) := x.property have hb : D.Adj (tail x) (head (r (f x))) := by have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [hd.1] at hp exact hp have hh := digraph_arc_choice_collision_repeated_pair α D choose hloop hchoice (tail x) (head x) (head (r (f x))) (hheads x hx) ha hb hd.2.symm exact Finset.mem_filter.mpr hh have hcharge : missing.card ≤ ∑ e ∈ repeated, (charge e).card := by have h := finite_endomap_collision_charge_identity Arc α α f r tail head repeated hr htail hkey hcharged change missing.card = ∑ e ∈ repeated, (charge e).card at h exact h.le have hdirty : dirty ⊆ repeated.biUnion parent := by intro u hu obtain ⟨_,a,b,p,hab,hpu,hua,hub,hpa,hpb⟩ := Finset.mem_filter.mp hu have hh := digraph_two_common_parents_edge_multiplicity α D a b u p hab hpu.symm hua hub hpa hpb apply Finset.mem_biUnion.mpr refine ⟨s(a,b), Finset.mem_filter.mpr hh, ?_⟩ apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact hua · exact hub have hsubset : ∀ e ∈ repeated, charge e ⊆ parent e := by intro e he u hu obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu have hxe : edge x = e := (Finset.mem_filter.mp hx).2 apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ intro z hz rw [← hxe] at hz change z ∈ s(head x, head (r (f x))) at hz rcases Sym2.mem_iff.mp hz with rfl | rfl · exact x.property · have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [(hdata x).1] at hp exact hp have hm : ∀ e ∈ repeated, 2 ≤ (parent e).card := by intro e he exact (Finset.mem_filter.mp he).2 have htwo : ∀ e ∈ repeated, (parent e).card = 2 → (charge e).card ≤ 1 := by intro e he hm2 induction e using Sym2.ind with | h a b => have hparentEq : parent s(a,b) = Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by ext p simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩ · rintro ⟨ha,hb⟩ x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact ha · exact hb rw [hparentEq] at hm2 have hlim := digraph_two_parent_collision_charge_card_le_one α D choose hloop hori hchoice a b hm2 have hsub : charge s(a,b) ⊆ Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by intro u hu obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2 have hd := hdata x have ha : D.Adj (tail x) (head x) := x.property have hb : D.Adj (tail x) (head (r (f x))) := by have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [hd.1] at hp exact hp apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩ · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb, by simpa [hxa,hxb] using hd.2.symm⟩ · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha, by simpa [hxa,hxb] using hd.2⟩ have hh := Finset.card_le_card hsub exact hh.trans hlim have hshort : ∀ e ∈ repeated, (parent e).card < g → (charge e).card < (parent e).card := by intro e he hs induction e using Sym2.ind with | h a b => have hparentEq : parent s(a,b) = Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b) := by ext p simp only [parent, Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro h exact ⟨h a (Sym2.mem_mk_left _ _), h b (Sym2.mem_mk_right _ _)⟩ · rintro ⟨ha,hb⟩ x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact ha · exact hb have hnonempty : (Finset.univ.filter fun p => D.Adj p a ∧ D.Adj p b).Nonempty := by apply Finset.card_pos.mp have h := hm s(a,b) he rw [hparentEq] at h omega have hlt := digraph_short_parent_set_not_all_charged α D choose g a b hloop hchoice hgirth hnonempty (by simpa [hparentEq] using hs) have hsub : charge s(a,b) ⊆ Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b ∧ choose p a = choose p b) := by intro u hu obtain ⟨x, hx, rfl⟩ := Finset.mem_image.mp hu have heq : s(head x, head (r (f x))) = s(a,b) := (Finset.mem_filter.mp hx).2 have hd := hdata x have ha : D.Adj (tail x) (head x) := x.property have hb : D.Adj (tail x) (head (r (f x))) := by have hp : D.Adj (tail (r (f x))) (head (r (f x))) := (r (f x)).property rw [hd.1] at hp exact hp apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_⟩ rcases Sym2.eq_iff.mp heq with ⟨hxa,hxb⟩ | ⟨hxa,hxb⟩ · exact ⟨by simpa [hxa] using ha, by simpa [hxb] using hb, by simpa [hxa,hxb] using hd.2.symm⟩ · exact ⟨by simpa [hxb] using hb, by simpa [hxa] using ha, by simpa [hxa,hxb] using hd.2⟩ have hsub' : charge s(a,b) ⊆ (Finset.univ.filter (fun p => D.Adj p a ∧ D.Adj p b)).filter (fun p => choose p a = choose p b) := by intro p hp have hh := Finset.mem_filter.mp (hsub hp) exact Finset.mem_filter.mpr ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, hh.2.1, hh.2.2.1⟩, hh.2.2.2⟩ have hc := Finset.card_le_card hsub' rw [hparentEq] omega have hparentPos : ∀ e ∈ edges, 1 ≤ (parent e).card := by intro e he induction e using Sym2.ind with | h a b => rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he obtain ⟨_,p,hpa,hpb⟩ := he apply Finset.card_pos.mpr refine ⟨p, Finset.mem_filter.mpr ⟨Finset.mem_univ _, ?_⟩⟩ intro x hx rcases Sym2.mem_iff.mp hx with rfl | rfl · exact hpa · exact hpb have hsum : (∑ e ∈ repeated, ((parent e).card - 1)) = (∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - edges.card := by have hall := digraph_common_predecessor_overlap_incidence_identity α D have hs : (∑ e ∈ repeated, ((parent e).card - 1)) = ∑ e ∈ edges, ((parent e).card - 1) := by dsimp [repeated] rw [Finset.sum_filter] apply Finset.sum_congr rfl intro e he by_cases h : 2 ≤ (parent e).card · simp [h] · have hp := hparentPos e he have hc : (parent e).card = 1 := by omega simp [h,hc] rw [hs] exact hall have hsum_parent : dirty.card ≤ ∑ e ∈ repeated, (parent e).card := by exact (Finset.card_le_card hdirty).trans Finset.card_biUnion_le have hedge : ∀ e ∈ repeated, (g - 1) * ((parent e).card + (charge e).card) ≤ 2 * g * ((parent e).card - 1) + (g + 1 - 2 * (parent e).card) := by intro e he exact girth_parent_charge_weight_bound g (parent e).card (charge e).card hg (hm e he) (Finset.card_le_card (hsubset e he)) (hshort e he) have hsumineq := Finset.sum_le_sum hedge have hbudget : (g - 1) * ((∑ e ∈ repeated, (parent e).card) + (∑ e ∈ repeated, (charge e).card)) ≤ 2 * g * (∑ e ∈ repeated, ((parent e).card - 1)) + (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) := by simpa only [Nat.mul_add, Finset.mul_sum, Finset.sum_add_distrib] using hsumineq have hcorrection : (∑ e ∈ repeated, (g + 1 - 2 * (parent e).card)) = digraph_common_predecessor_girth_correction α D g := by simp only [digraph_common_predecessor_girth_correction, repeated, Finset.sum_filter] apply Finset.sum_congr · ext e simp [edges] · intro e he simp [parent] have hscaled := Nat.mul_le_mul_left (g - 1) (Nat.add_le_add hsum_parent hcharge) change (g - 1) * (dirty.card + missing.card) ≤ _ rw [← hsum, ← hcorrection] exact hscaled.trans hbudget