digraph_trianglefree_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_trianglefree_weighted_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) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → 4 ≤ C.card) (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) (hsmall : 8 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_double_edges α D < 3 * 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_double_edgesThe number of edges in the common-predecessor graph whose endpoints have exactly two common predecessors.
- digraph_trianglefree_arc_map_weighted_budgetFor a loopless oriented digraph of directed girth at least four with chosen common predecessors for its arcs, three times the number of…
- 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_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…
The proof, explained
The theorem shows that an oriented, loopless, arc-dominated digraph of girth at least 4 has a vertex with a clean out-neighborhood and common successors along each outgoing arc. Using the arc-domination hypothesis, each directed edge is mapped to a predecessor arc dominating it. A weighted counting lemma bounds three times the number of dirty vertices and missing arcs by the weighted common predecessor expression, which by assumption is strictly less than 3 * |α|, allowing a budget-transfer theorem to guarantee the existence of such a center vertex.
Adjacency in the common predecessor graph of D is decidable.
To construct the edge set of the common predecessor graph as a finite set, we establish decidability of adjacency between any vertices u and v. Unfolding the definition of digraph_common_predecessor_graph shows that adjacency is a bounded existential query over the finite type α, which Lean's typeclass resolution synthesizes automatically.
intro u v unfold digraph_common_predecessor_graph infer_instance
Every directed edge u → v has an assigned predecessor dominating the edge, satisfying choose(u, v) → u and choose(u, v) → v.
Using classical choice on the arc-domination hypothesis hdom, we define a function choose that selects for each arc u → v a vertex dominating that arc. The lemma Classical.choose_spec establishes that this choice satisfies both choose(u, v) → u and choose(u, v) → v.
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)
The arc subtype, the predecessor arc map f, the set of dirty vertices, and the set of missing arcs are defined.
We define Arc as the subtype of directed edges and f : Arc → Arc sending each edge (u, v) to (choose(u, v), u). A vertex is defined to be dirty if two of its out-neighbors share another common predecessor. The set missing consists of all arcs not belonging to 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
Three times the sum of the number of dirty vertices and missing arcs is bounded by the weighted common-predecessor expression.
The lemma digraph_trianglefree_arc_map_weighted_budget applies to loopless oriented digraphs of girth at least 4, establishing that 3 * (|dirty| + |missing|) is at most 8 * (∑_v (d⁺(v) choose 2) - |E(G_cp)|) + |E_2(G_cp)|.
uses
digraph_trianglefree_arc_map_weighted_budgethave hw := digraph_trianglefree_arc_map_weighted_budget α D choose hloop hori hgirth hchoiceThe total number of dirty vertices and missing arcs is strictly less than the total number of vertices, |dirty| + |missing| < |α|. automation
Hypothesis hsmall states that the weighted bound is strictly less than 3 * |α|. Combining this with the weighted budget inequality 3 * (|dirty| + |missing|) ≤ RHS via linear integer arithmetic (omega) derives |dirty| + |missing| < |α|.
have hb : dirty.card + missing.card < Fintype.card α := by change 3 * (dirty.card + missing.card) ≤ _ at hw omega
There exists a vertex with a clean out-neighborhood whose outgoing arcs each share a common successor.
Applying digraph_good_center_from_arc_map_budget with the verified budget |dirty| + |missing| < |α| yields a vertex v whose out-neighborhood contains no pairs with an outside common predecessor and such that every out-neighbor w shares a common successor with v.
uses
digraph_good_center_from_arc_map_budgetexact digraph_good_center_from_arc_map_budget α D choose hchoice hb
Classical.choose_spec- Given an existential proof ∃ x, p x, the witness Classical.choose satisfies p.
digraph_trianglefree_arc_map_weighted_budget- For a finite loopless oriented digraph of directed girth at least 4 with a dominating predecessor chosen for each arc, three times the number of dirty vertices plus missing arcs is at most 8 times the difference between the sum of pairs of out-neighbors and the common predecessor edges, plus the number of double edges.
digraph_good_center_from_arc_map_budget- If the sum of dirty vertices and arcs missing from the image of an arc-dominating map is strictly less than the total number of vertices, then the digraph contains a vertex with a clean out-neighborhood whose outgoing arcs each have a common successor.
- Lines 1–5 prove an auxiliary typeclass instance establishing the decidability of adjacency in the common predecessor graph, which Lean requires to express its edge set as a finite set (edgeFinset).
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_trianglefree_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_trianglefree_weighted_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) (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → 4 ≤ C.card) (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v) (hsmall : 8 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) + digraph_common_predecessor_double_edges α D < 3 * 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_trianglefree_arc_map_weighted_budget α D choose hloop hori hgirth hchoice have hb : dirty.card + missing.card < Fintype.card α := by change 3 * (dirty.card + missing.card) ≤ _ at hw omega exact digraph_good_center_from_arc_map_budget α D choose hchoice hb