digraph_good_center_from_arc_map_budget
For a finite digraph with a chosen common predecessor for every arc, if the number of dirty parents plus the number of missing predecessor arc-map images is smaller than the order, there is a vertex with a clean out-neighborhood whose outgoing arcs all have a common successor.
Statement
theorem digraph_good_center_from_arc_map_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) (hbudget : 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 < Fintype.card α) : ∃ v, (∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ p, D.Adj p a → D.Adj p b → p = v) ∧ (∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x)
- Source
- Final finite pigeonhole step for the small-overlap good-center route to OP-110.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 5
- 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_trianglefree_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
- digraph_trianglefree_weighted_overlap_cycle_packing_stepFor a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle…
- 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…
- 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 uses a counting (pigeonhole) argument followed by local reconstruction. Given a choice of common predecessor for every arc, we map each arc (u, v) to (choose(u, v), u). By the budget hypothesis, the dirty vertices (those sharing two or more distinct out-neighbors with another vertex) together with the tails of arcs missing from the image of this map number strictly fewer than the total number of vertices |α|. A vertex v avoiding both sets therefore exists: its out-neighborhood is clean, and since no outgoing arc from v is missing from the image, every out-neighbor of v shares a common successor with v.
The number of tail vertices of arcs missing from the image of f is bounded by |missing|, and |dirty ∪ tails| < |α|.
We define the set of arcs of D, the predecessor arc map f(u, v) = (choose(u, v), u), the set dirty of vertices sharing two distinct out-neighbors with another vertex, the set missing of arcs not in the image of f, and the set tails of sources (first components) of missing arcs. The cardinality of tails is at most |missing| because tails is the image of missing under projection. By the union bound and the budget hypothesis, |dirty ∪ tails| ≤ |dirty| + |tails| ≤ |dirty| + |missing| < |α|.
uses
Finset.card_image_le,Finset.card_union_leclassical 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 let missing : Finset Arc := Finset.univ \ Finset.univ.image f let tails : Finset α := missing.image fun e => e.val.1 have htail : tails.card ≤ missing.card := Finset.card_image_le have hunion : (dirty ∪ tails).card ≤ dirty.card + tails.card := Finset.card_union_le _ _ have hb : dirty.card + missing.card < Fintype.card α := hbudget
There exists a vertex v that is neither dirty nor the source of a missing arc (v ∉ dirty and v ∉ tails).
Suppose for contradiction that every vertex belongs to dirty ∪ tails. Then the universal set of all vertices would be a subset of dirty ∪ tails, which would imply |α| ≤ |dirty ∪ tails|. But by the previous bounds, |dirty ∪ tails| ≤ |dirty| + |missing| < |α|, a contradiction. Therefore, a vertex v outside dirty ∪ tails must exist.
uses
Finset.mem_union_left,Finset.mem_union_right,Finset.card_le_card,Finset.card_univhave hex : ∃ v, v ∉ dirty ∧ v ∉ tails := by by_contra h have hs : (Finset.univ : Finset α) ⊆ dirty ∪ tails := by intro v _ by_contra hv apply h refine ⟨v, ?_, ?_⟩ · intro hd exact hv (Finset.mem_union_left _ hd) · intro ht exact hv (Finset.mem_union_right _ ht) have hc := Finset.card_le_card hs simp only [Finset.card_univ] at hc omega
Fixing v ∉ dirty ∪ tails, no other vertex p ≠ v shares two distinct out-neighbors with v.
We instantiate the existential witness with v. To show that v has a clean out-neighborhood, suppose for contradiction that there exist distinct out-neighbors a ≠ b of v that are also both out-neighbors of some vertex p ≠ v. Then v would satisfy the defining predicate of the dirty set, contradicting v ∉ dirty. Hence any such p must equal v.
uses
Finset.mem_filter.mpr,Finset.mem_univobtain ⟨v, hvdirty, hvtail⟩ := hex refine ⟨v, ?_, ?_⟩ · intro a b hab hva hvb p hpa hpb by_contra hp apply hvdirty exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, a, b, p, hab, hp, hva, hvb, hpa, hpb⟩
Every out-neighbor w of v shares a common successor with v in D.
For any out-neighbor w of v, consider the arc e = (v, w). Because its source is v and v ∉ tails, e cannot belong to missing. Hence e must be in the image of f, meaning e = f(e') for some arc e' = (u', x). Expanding the definition of f gives v = choose(u', x) and w = u'. By the choice hypothesis, choose(u', x) has an outgoing arc to x, so v → x. Since e' is an arc, u' → x, which means w → x. Thus x is a common successor of v and w.
uses
Finset.mem_image.mpr,Finset.mem_sdiff.mpr,Finset.mem_univ,Finset.mem_image.mp,congrArg· intro w hvw let e : Arc := ⟨(v,w), hvw⟩ have hnot : e ∉ missing := by intro hm apply hvtail exact Finset.mem_image.mpr ⟨e, hm, rfl⟩ have he : e ∈ Finset.univ.image f := by by_contra h apply hnot exact Finset.mem_sdiff.mpr ⟨Finset.mem_univ _, h⟩ obtain ⟨e', _, heq⟩ := Finset.mem_image.mp he have hp : choose e'.val.1 e'.val.2 = v := congrArg (fun z : Arc => z.val.1) heq have ht : e'.val.1 = w := congrArg (fun z : Arc => z.val.2) heq refine ⟨e'.val.2, ?_, ?_⟩ · simpa [hp] using (hchoice e'.val.1 e'.val.2 e'.property).2 · simpa [ht] using e'.property
Finset.card_image_le- The cardinality of the image of a finite set under any function is at most the cardinality of the original set.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their individual cardinalities.
Finset.mem_union_left- If an element belongs to a set s, it belongs to the union s ∪ t.
Finset.mem_union_right- If an element belongs to a set t, it belongs to the union s ∪ t.
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.card_univ- The cardinality of the universal finite set of a finite type is equal to the cardinality of the type itself.
Finset.mem_univ- Every element of a finite type belongs to its universal finite set.
Finset.mem_filter.mpr- An element belongs to the filtered subset {x ∈ s | P(x)} if it belongs to s and satisfies the predicate P.
Finset.mem_image.mpr- An element y belongs to the image f(s) if there exists some x ∈ s such that f(x) = y.
Finset.mem_image.mp- If an element y belongs to the image f(s), then there exists some x ∈ s such that f(x) = y.
Finset.mem_sdiff.mpr- An element belongs to the set difference s \ t if it belongs to s and does not belong to t.
congrArg- Applying a function to equal arguments produces equal results (a₁ = a₂ implies f(a₁) = f(a₂)).
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.
theorem digraph_good_center_from_arc_map_budget (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (choose : α → α → α) (hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v) (hbudget : 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 < Fintype.card α) : ∃ v, (∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ p, D.Adj p a → D.Adj p b → p = v) ∧ (∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x) := 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 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 tails : Finset α := missing.image fun e => e.val.1 have htail : tails.card ≤ missing.card := Finset.card_image_le have hunion : (dirty ∪ tails).card ≤ dirty.card + tails.card := Finset.card_union_le _ _ have hb : dirty.card + missing.card < Fintype.card α := hbudget have hex : ∃ v, v ∉ dirty ∧ v ∉ tails := by by_contra h have hs : (Finset.univ : Finset α) ⊆ dirty ∪ tails := by intro v _ by_contra hv apply h refine ⟨v, ?_, ?_⟩ · intro hd exact hv (Finset.mem_union_left _ hd) · intro ht exact hv (Finset.mem_union_right _ ht) have hc := Finset.card_le_card hs simp only [Finset.card_univ] at hc omega obtain ⟨v, hvdirty, hvtail⟩ := hex refine ⟨v, ?_, ?_⟩ · intro a b hab hva hvb p hpa hpb by_contra hp apply hvdirty exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, a, b, p, hab, hp, hva, hvb, hpa, hpb⟩ · intro w hvw let e : Arc := ⟨(v,w), hvw⟩ have hnot : e ∉ missing := by intro hm apply hvtail exact Finset.mem_image.mpr ⟨e, hm, rfl⟩ have he : e ∈ Finset.univ.image f := by by_contra h apply hnot exact Finset.mem_sdiff.mpr ⟨Finset.mem_univ _, h⟩ obtain ⟨e', _, heq⟩ := Finset.mem_image.mp he have hp : choose e'.val.1 e'.val.2 = v := congrArg (fun z : Arc => z.val.1) heq have ht : e'.val.1 = w := congrArg (fun z : Arc => z.val.2) heq refine ⟨e'.val.2, ?_, ?_⟩ · simpa [hp] using (hchoice e'.val.1 e'.val.2 e'.property).2 · simpa [ht] using e'.property