digraph_oriented_arc_map_missing_dirty_budget
For a finite loopless oriented digraph and a chosen common predecessor for each arc, the number of dirty parents plus the number of arcs missing from the associated predecessor arc-map image is at most three times the excess common-predecessor incidence count. A parent is dirty if its out-neighborhood contains a pair with a different common predecessor.
Statement
theorem digraph_oriented_arc_map_missing_dirty_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (hloop : ∀ u, ¬ D.Adj u u) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (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 dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤ 3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card)
- Source
- Sharp collision-budget bottleneck for the small-overlap structural route to OP-110; experiments 13163 and 13186.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- 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 3
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- digraph_girth_arc_map_weighted_budgetFor 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…
- digraph_oriented_small_overlap_good_centerIn an oriented arc-dominated digraph, if repeated common-predecessor pair incidences are less than one third of the order, some vertex has…
The proof, explained
The proof maps each directed arc to the arc formed by its tail and a chosen common predecessor of its endpoints. Arcs missing from the image correspond to collisions under this map, which are charged to unordered pairs of heads sharing the same common predecessor. Each such collision pair belongs to the repeated edges of the common-predecessor graph (those with at least two parents), and every dirty vertex is a parent of at least one repeated edge. The general collision budget lemma finite_parent_collision_budget_with_cover then bounds the sum of dirty vertices and missing arcs by three times the excess parent sum, which coincides with the excess common-predecessor incidence count.
Adjacency in the common-predecessor graph is decidable. automation
Given vertices u and v, we unfold the definition of adjacency in digraph_common_predecessor_graph (requiring u ≠ v and the existence of a common predecessor). Typeclass inference synthesizes decidability since equality and adjacency in D are decidable on the finite type α.
intro u v unfold digraph_common_predecessor_graph infer_instance
The predecessor arc map f has a choice section r satisfying f (r (f x)) = f x for all arcs x.
We work classically. An arc is a pair with an edge in D. The map f sends arc e to (choose(e.1, e.2), e.1). The function r picks a preimage under f using Classical.choose if one exists, and defaults to the input otherwise. Since x witnesses that f x is in the image, Classical.choose_spec guarantees 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
If f x = f y then tail x = tail y, and the map x ↦ (tail x, head x) is injective on arcs.
The head of f x is tail x, so f x = f y implies tail x = tail y by congrArg. Arcs are defined as a subtype of pairs α × α, so any arc is uniquely determined by its tail and head via 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
For any collision r (f x) ≠ x, the arcs x and r (f x) share the same tail, have distinct heads, and share the same chosen predecessor.
We define parents of pairs, repeated edges (those with at least 2 parents), dirty vertices, missing arcs, non-representative collision arcs (where r (f x) ≠ x), and the edge and charge maps. Because f (r (f x)) = f x, both arcs share the same tail and the same chosen predecessor. Since the arcs are distinct, their heads must be distinct by Subtype.ext and Prod.ext.
uses
Subtype.ext,Prod.extlet 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
Every collision arc x with r (f x) ≠ x charges an edge in repeated.
Both x and r (f x) are directed arcs emanating from tail x to head x and head (r (f x)), respectively. Since the two heads are distinct and tail x chooses the same common predecessor for both, lemma digraph_arc_choice_collision_repeated_pair shows that the unordered pair of heads forms an edge of the common-predecessor graph with at least 2 common parents, hence 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 at most the total charge across all repeated edges.
Applying finite_endomap_collision_charge_identity with the fibration data shows that the number of arcs outside the image of f exactly equals the sum of the sizes of the charge sets over repeated edges.
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 parents of repeated edges.
A vertex u is dirty if there exist distinct vertices a ≠ b and a distinct parent p ≠ u that also points to a and b. By digraph_two_common_parents_edge_multiplicity, s(a, b) is an edge with at least 2 common parents, so s(a, b) ∈ repeated, and u ∈ parent s(a, b).
uses
digraph_two_common_parents_edge_multiplicity,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_biUnion.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.
Any vertex u in charge e is the tail of some collision arc x whose head pair is e. Since tail x is adjacent to head x and tail (r (f x)) = tail x is adjacent to head (r (f x)), u is adjacent to both endpoints of e, hence u ∈ parent e.
uses
Finset.mem_image.mp,Finset.mem_filter.mp,Finset.mem_filter.mpr,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
Every repeated edge has at least two parents.
This follows immediately from the definition of repeated as the subset of edges with parent cardinality at least 2.
uses
Finset.mem_filter.mphave 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, then charge e contains at most one vertex.
Representing e as s(a, b), parent s(a, b) consists of the common parents of a and b. Any vertex in charge s(a, b) is a common parent u satisfying choose u a = choose u b. By digraph_two_parent_collision_charge_card_le_one, in a loopless oriented graph with a valid choice function, at most one of the two common parents can satisfy this equality, so |charge e| ≤ 1.
uses
Sym2.ind,Finset.mem_filter,Finset.mem_univ,true_and,Sym2.mem_mk_left,Sym2.mem_mk_right,Sym2.mem_iff.mp,digraph_two_parent_collision_charge_card_le_one,Finset.mem_image.mp,Finset.mem_filter.mp,Finset.mem_filter.mpr,Sym2.eq_iff.mp,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
Every edge in the common-predecessor graph has at least one parent.
By definition of the common-predecessor graph, an edge s(a, b) requires the existence of a common predecessor p pointing to both a and b. Thus p ∈ parent s(a, b), so |parent e| ≥ 1.
uses
Sym2.ind,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Finset.card_pos.mpr,Finset.mem_filter.mpr,Finset.mem_univ,Sym2.mem_iff.mphave 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
The sum of (|parent e| - 1) over repeated edges equals the excess predecessor incidence count.
Edges not in repeated have fewer than 2 parents, and since every edge has at least 1 parent, they have exactly 1 parent, making (|parent e| - 1) = 0. Thus the sum over repeated edges equals the sum over all edges. By digraph_common_predecessor_overlap_incidence_identity, the sum over all edges of (|parent e| - 1) equals the total sum of choose(out-degree, 2) minus the number of edges.
uses
digraph_common_predecessor_overlap_incidence_identity,Finset.sum_filter,Finset.sum_congrhave 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 number of dirty vertices plus missing arcs is at most three times the excess common-predecessor incidence count.
We apply finite_parent_collision_budget_with_cover, which takes the cover of dirty vertices, the bound on missing arcs by total charge, the minimum parent bound 2 ≤ |parent e|, the inclusion charge e ⊆ parent e, and the charge bound |charge e| ≤ 1 when |parent e| = 2, to conclude |dirty| + |missing| ≤ 3 * ∑_{e ∈ repeated} (|parent e| - 1). Rewriting this sum using the identity from the previous step completes the proof.
uses
finite_parent_collision_budget_with_coverhave hbudget := finite_parent_collision_budget_with_cover (Sym2 α) α Arc repeated parent charge dirty missing hdirty hcharge hm hsubset htwo change dirty.card + missing.card ≤ _ rw [← hsum] exact hbudget
Classical.choose_spec- For an existential statement, Classical.choose returns a witness satisfying the predicate.
congrArg- Equality of arguments implies equality of function values.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
Prod.ext- Two ordered pairs are equal if their first and second coordinates are equal.
digraph_arc_choice_collision_repeated_pair- In a loopless digraph with a valid predecessor choice function, two out-neighbors of a vertex with the same chosen predecessor form an edge of the common-predecessor graph with at least two common parents.
finite_endomap_collision_charge_identity- For a finite endomap with a choice section, the number of missing elements equals the sum over edge classes of the sizes of the sets of charged tails.
digraph_two_common_parents_edge_multiplicity- If two distinct vertices share two distinct common parents, the pair forms an edge of the common-predecessor graph with at least two parents.
digraph_two_parent_collision_charge_card_le_one- In a loopless oriented digraph, if an edge has exactly two common parents, at most one of those parents assigns both endpoints the same chosen common predecessor.
Finset.card_le_card- A subset of a finite set has cardinality at most that of the ambient set.
SimpleGraph.mem_edgeFinset- An unordered pair belongs to the edge finset of a graph if and only if it is in the edge set.
SimpleGraph.mem_edgeSet- An edge belongs to the edge set of a simple graph if and only if its endpoints are adjacent.
Finset.card_pos.mpr- A finite set has cardinality at least 1 if it contains an element.
digraph_common_predecessor_overlap_incidence_identity- The sum over all edges of the common-predecessor graph of (|parent(e)| - 1) equals the sum over vertices of choose(out-degree, 2) minus the total number of edges.
Finset.sum_filter- Summing over a filtered set equals summing over the ambient set with the summand zeroed out when the predicate fails.
Finset.sum_congr- Sums over equal finite sets of functions that agree pointwise are equal.
finite_parent_collision_budget_with_cover- A general budget lemma bounding the sum of dirty elements and missing elements by three times the sum of (|P(e)| - 1) over repeated items.
Finset.mem_filter.mp- Extracting the membership and predicate components from membership in a filtered finset.
Finset.mem_filter.mpr- Constructing membership in a filtered finset from membership in the ambient set and the predicate.
Finset.mem_biUnion.mpr- Constructing membership in a finset biUnion from an element in a component set.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.mem_image.mp- Extracting a preimage witness from membership in the image of a finset.
Sym2.mem_iff.mp- Membership in an unordered pair s(a, b) means equality with a or equality with b.
Sym2.ind- Induction on unordered pairs: it suffices to check pairs of the form s(a, b).
Sym2.eq_iff.mp- Equality of unordered pairs s(a, b) = s(c, d) holds if and only if (a = c and b = d) or (a = d and b = c).
Sym2.mem_mk_left- The first element belongs to the unordered pair s(x, y).
Sym2.mem_mk_right- The second element belongs to the unordered pair s(x, y).
Finset.mem_filter- Membership in Finset.filter p s is equivalent to membership in s and satisfying p.
true_and- True and p is equivalent to p.
- In Step 10, case analysis on the unordered pair equality is closed by `simpa` automation. In Step 12, the deduction that an edge with at least one parent and strictly fewer than two parents has exactly one parent is discharged by `omega`.
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 in504_dirty_budget_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_arc_map_missing_dirty_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (hloop : ∀ u, ¬ D.Adj u u) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (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 dirty.card + ((Finset.univ : Finset Arc) \ Finset.univ.image f).card ≤ 3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) := 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 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 hbudget := finite_parent_collision_budget_with_cover (Sym2 α) α Arc repeated parent charge dirty missing hdirty hcharge hm hsubset htwo change dirty.card + missing.card ≤ _ rw [← hsum] exact hbudget