AFTD Auto-Formalizing Theoretical Domains

digraph_good_center_from_arc_map_budget

theoremverified

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

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.

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

    lines 15–25

    uses Finset.card_image_le, Finset.card_union_le

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

    lines 26–39

    uses Finset.mem_union_left, Finset.mem_union_right, Finset.card_le_card, Finset.card_univ

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

    lines 40–45

    uses Finset.mem_filter.mpr, Finset.mem_univ

      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⟩
  4. 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.

    lines 46–61

    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

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