digraph_oriented_small_overlap_good_center
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
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_edge_le_sum_chooseThe common-predecessor graph has at most the sum over vertices of the number of pairs in each out-neighborhood.
- oriented_overlap_multiplicity_budgetSummed multiplicities and charges cost at most three times overlap when multiplicity-two edges have at most one charge.
- digraph_good_center_from_arc_map_budgetFor a finite digraph with a chosen common predecessor for every arc, if the number of dirty parents plus the number of missing predecessor…
- 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…
- Used by 1
- digraph_small_overlap_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for oriented arc-dominated digraphs of minimum outdegree at least d+2…
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.
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.
uses
digraph_common_predecessor_graphintro u v unfold digraph_common_predecessor_graph infer_instance
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.
uses
Fintype.card_pos_iff.mpclassical have hn : 0 < Fintype.card α := by omega letI : Nonempty α := Fintype.card_pos_iff.mp hn
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.
uses
Classical.choose,Classical.choice,Classical.choose_speclet 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)
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 |α|.
uses
digraph_oriented_arc_map_missing_dirty_budget,lt_of_le_of_lthave hbudget := digraph_oriented_arc_map_missing_dirty_budget α D choose hloop hori hc have hstrict := lt_of_le_of_lt hbudget hsmall
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.
uses
digraph_good_center_from_arc_map_budgetexact 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
- The auxiliary instance in478_decadj_digraph_oriented_small_overlap_good_center (lines 1–4) provides decidability for the adjacency relation of the common-predecessor graph; this is a formal requirement for Lean to define the edge finset and count its cardinality, with no paper counterpart.
- The Presburger arithmetic tactic omega (line 17) deduces 0 < Fintype.card α from the strict inequality hsmall by observing that the left-hand side is a natural number.
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 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