AFTD Auto-Formalizing Theoretical Domains

digraph_oriented_small_overlap_good_center

theoremverified

In an oriented arc-dominated digraph, if repeated common-predecessor pair incidences are less than one third of the order, some vertex has a clean out-neighborhood and every outgoing arc has a common successor.

Statement

theorem digraph_oriented_small_overlap_good_center
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (hloop : ∀ v, ¬ D.Adj v v)
    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)
    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)
    (hsmall : 3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) :
    ∃ v, (∀ a b, a ≠ b → D.Adj v a → D.Adj v b →
        ∀ x, D.Adj x a → D.Adj x b → x = v) ∧
      (∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x)
Source
General small-overlap center argument for OP-110; nontrivial oriented cyclic checks in experiment 12695.
Verified
03 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The proof deduces the existence of a clean, well-connected center by combining an arc-map budget inequality with the small overlap hypothesis. Given the arc-domination property, a choice function selects a common predecessor for each directed arc to define a predecessor arc mapping. The lemma digraph_oriented_arc_map_missing_dirty_budget bounds the number of dirty vertices plus the uncovered arcs by 3 times the excess common-predecessor incidences, which the hypothesis hsmall assumes is strictly less than the total number of vertices. Finally, digraph_good_center_from_arc_map_budget uses this strict bound to conclude that a vertex with a clean out-neighborhood and common successors exists.

  1. The adjacency relation of the common-predecessor graph of D is decidable.

    We introduce two vertices u and v and unfold the definition of the common-predecessor graph, which asks whether u ≠ v and there exists a common predecessor w with directed edges to both u and v. Since equality and adjacency in D are decidable and the vertex type α is finite, Lean's type class inference synthesizes decidability for this bounded existential formula.

    lines 2–4

    uses digraph_common_predecessor_graph

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The vertex type α has strictly positive cardinality, and in particular is nonempty.

    Assuming classical logic, the hypothesis hsmall bounds 3 times the excess common-predecessor incidences strictly below the order of the digraph |α|. Because the left-hand side is a non-negative integer, Presburger arithmetic (omega) deduces 0 < |α|. The lemma Fintype.card_pos_iff.mp then establishes that α is nonempty.

    lines 16–18

    uses Fintype.card_pos_iff.mp

      classical
      have hn : 0 < Fintype.card α := by omega
      letI : Nonempty α := Fintype.card_pos_iff.mp hn
  3. There exists a choice function assigning to every directed arc (u, v) a common predecessor w pointing to both u and v.

    Using the arc-domination hypothesis hdom, we define choose u v via Classical.choose to select a common predecessor when D.Adj u v holds, falling back to Classical.choice on the nonempty type α otherwise. Applying Classical.choose_spec and simplifying with the definition of choose verifies that for any arc u → v, the vertex choose u v is indeed a predecessor of both u and v.

    lines 19–23

    uses Classical.choose, Classical.choice, Classical.choose_spec

      let choose : α → α → α := fun u v =>
        if h : D.Adj u v then Classical.choose (hdom u v h) else Classical.choice ‹Nonempty α›
      have hc : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by
        intro u v huv
        simpa [choose, huv] using Classical.choose_spec (hdom u v huv)
  4. The sum of dirty vertices and arcs missing from the predecessor map image is strictly less than the total number of vertices |α|.

    The budget theorem digraph_oriented_arc_map_missing_dirty_budget shows that for a loopless, oriented digraph with choice function choose, the count of dirty vertices (those with multiple out-neighbors that share an external common predecessor) plus the arcs not covered by the predecessor map f(u → v) = (choose u v → u) is bounded above by 3 times the excess common-predecessor pairs. Transitivity of inequalities (lt_of_le_of_lt) with the hypothesis hsmall shows that this sum is strictly less than |α|.

    lines 24–25

    uses digraph_oriented_arc_map_missing_dirty_budget, lt_of_le_of_lt

      have hbudget := digraph_oriented_arc_map_missing_dirty_budget α D choose hloop hori hc
      have hstrict := lt_of_le_of_lt hbudget hsmall
  5. There exists a vertex v with a clean out-neighborhood such that every outgoing arc from v has a common successor.

    Applying digraph_good_center_from_arc_map_budget with the strict budget bound hstrict guarantees the existence of a good center: a vertex v whose out-neighbors share no common predecessor other than v, and such that every arc leaving v can be completed to a common successor.

    line 26

    uses digraph_good_center_from_arc_map_budget

      exact digraph_good_center_from_arc_map_budget α D choose hc hstrict
digraph_common_predecessor_graph
the simple graph on the vertices of a directed graph D where two distinct vertices are adjacent if and only if they share a common predecessor in D
Fintype.card_pos_iff.mp
a finite type has strictly positive cardinality if and only if it is nonempty
Classical.choose
given a proof of an existential statement ∃ x, p x, returns a witness x satisfying p x
Classical.choice
given a proof that a type is nonempty, returns an element of that type
Classical.choose_spec
the witness produced by Classical.choose satisfies the given predicate
digraph_oriented_arc_map_missing_dirty_budget
in an oriented loopless digraph with a common-predecessor choice function, the number of dirty vertices plus the number of arcs missing from the predecessor map image is at most 3 times the excess common-predecessor pairs
lt_of_le_of_lt
if a ≤ b and b < c in a preorder, then a < c
digraph_good_center_from_arc_map_budget
if the sum of dirty vertices and missing arcs in the predecessor map image is strictly less than the vertex count, then there exists a vertex with a clean out-neighborhood whose outgoing arcs each have a common successor

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

private instance in478_decadj_digraph_oriented_small_overlap_good_center {α : 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_small_overlap_good_center    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (hloop : ∀ v, ¬ D.Adj v v)    (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u)    (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v)    (hsmall : 3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) :    ∃ v, (∀ a b, a ≠ b → D.Adj v a → D.Adj v b →        ∀ x, D.Adj x a → D.Adj x b → x = v) ∧      (∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x) := by  classical  have hn : 0 < Fintype.card α := by omega  letI : Nonempty α := Fintype.card_pos_iff.mp hn  let choose : α → α → α := fun u v =>    if h : D.Adj u v then Classical.choose (hdom u v h) else Classical.choice ‹Nonempty α›  have hc : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by    intro u v huv    simpa [choose, huv] using Classical.choose_spec (hdom u v huv)  have hbudget := digraph_oriented_arc_map_missing_dirty_budget α D choose hloop hori hc  have hstrict := lt_of_le_of_lt hbudget hsmall  exact digraph_good_center_from_arc_map_budget α D choose hc hstrict
See it in the graphDiscuss this resultChallenge it