digraph_girth_weighted_good_center
Under the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean out-neighborhood whose outgoing arcs each have a common successor.
Statement
theorem digraph_girth_weighted_good_center (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) (hsmall : 2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_girth_correction α D g < (g - 1) * 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
- Weighted center route for the four-cycle campaign; experiment 13473.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_girth_correctionThe sum, over common-predecessor edges of multiplicity at least two, of the positive part of g+1 minus twice the number of common…
- 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_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…
- Used by 1
- 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…
The proof, explained
The proof selects a common predecessor for each directed arc to define an arc transition map sending (u, v) to (choose u v, u). A known weighted budget theorem bounds (g - 1) times the sum of 'dirty' vertices and 'missing' arcs by the given overlap and girth correction quantity. Combining this with the hypothesis and dividing out (g - 1) shows that the defect count is strictly less than the total number of vertices. Finally, an existing center existence theorem deduces the desired good center from this strict budget inequality.
Adjacency in the common-predecessor graph of D is decidable. automation
By unfolding the definition of digraph_common_predecessor_graph, deciding adjacency between u and v reduces to testing u ≠ v and searching over α for a common predecessor w with D.Adj w u and D.Adj w v, which typeclass inference automatically synthesizes since α is a finite type with decidable equality and adjacency.
private instance in516_girth_center_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_instance
There is a function choose mapping each arc u → v to a common predecessor of u and v.
Using classical choice on the arc-domination hypothesis hdom, choose u v selects a vertex p such that D.Adj p u and D.Adj p v whenever D.Adj u v holds.
uses
Classical.choose_specclassical let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by intro u v h simpa [choose,h] using Classical.choose_spec (hdom u v h)
Define the arc type Arc, the arc shift map f, the set of dirty vertices, and the set of missing arcs.
Arc is the subtype of pairs forming directed edges. The map f sends an arc (u, v) to (choose u v, u). The set dirty consists of vertices sharing two distinct out-neighbors with some other vertex, and missing consists of arcs not in the image of f.
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.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
(g - 1) * (|dirty| + |missing|) is bounded by the weighted overlap sum plus the girth correction term.
Applying digraph_girth_arc_map_weighted_budget with the chosen predecessor function and graph properties yields this inequality directly.
uses
digraph_girth_arc_map_weighted_budgethave hw := digraph_girth_arc_map_weighted_budget α D choose g hg hloop hori hgirth hchoiceThe sum of dirty vertices and missing arcs is strictly less than the total number of vertices |α|.
By transitivity with the hypothesis hsmall, (g - 1) * (|dirty| + |missing|) < (g - 1) * |α|. Dividing both sides by g - 1 using Nat.lt_of_mul_lt_mul_left yields |dirty| + |missing| < |α|.
uses
lt_of_le_of_lt,Nat.lt_of_mul_lt_mul_lefthave hb : dirty.card + missing.card < Fintype.card α := by change (g - 1) * (dirty.card + missing.card) ≤ _ at hw have hlt : (g - 1) * (dirty.card + missing.card) < (g - 1) * Fintype.card α := lt_of_le_of_lt hw hsmall exact Nat.lt_of_mul_lt_mul_left hlt
There exists a vertex v with a clean out-neighborhood whose outgoing arcs each have a common successor.
Applying digraph_good_center_from_arc_map_budget using the established budget inequality |dirty| + |missing| < |α| completes the proof.
uses
digraph_good_center_from_arc_map_budgetexact digraph_good_center_from_arc_map_budget α D choose hchoice hb
Classical.choose_spec- For an existential statement h : ∃ x, p x, the witness Classical.choose h satisfies p.
digraph_girth_arc_map_weighted_budget- In an oriented loopless digraph with girth at least g and a common-predecessor choice function for every arc, (g - 1) times the sum of dirty vertices and missing arcs is bounded above by 2 * g * (∑_v binom(d⁺(v), 2) - |E|) plus the girth correction term.
lt_of_le_of_lt- If a ≤ b and b < c, then a < c.
Nat.lt_of_mul_lt_mul_left- If a * b < a * c for natural numbers, then b < c.
digraph_good_center_from_arc_map_budget- If the sum of dirty vertices and missing arcs is strictly less than the total number of vertices |V|, then there exists a clean vertex whose outgoing arcs each have a common successor.
- The auxiliary instance in516_girth_center_decAdj automatically synthesizes decidability of adjacency in the common-predecessor graph via typeclass inference.
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 in516_girth_center_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_girth_weighted_good_center (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g : ℕ) (hg : 3 ≤ g) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → g ≤ C.card) (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) (hsmall : 2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_girth_correction α D g < (g - 1) * 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 choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by intro u v h simpa [choose,h] using Classical.choose_spec (hdom u v h) 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.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 have hw := digraph_girth_arc_map_weighted_budget α D choose g hg hloop hori hgirth hchoice have hb : dirty.card + missing.card < Fintype.card α := by change (g - 1) * (dirty.card + missing.card) ≤ _ at hw have hlt : (g - 1) * (dirty.card + missing.card) < (g - 1) * Fintype.card α := lt_of_le_of_lt hw hsmall exact Nat.lt_of_mul_lt_mul_left hlt exact digraph_good_center_from_arc_map_budget α D choose hchoice hb