digraph_common_predecessor_girth_correction
def
The sum, over common-predecessor edges of multiplicity at least two, of the positive part of g+1 minus twice the number of common predecessors.
Statement
noncomputable def digraph_common_predecessor_girth_correction (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g : ℕ) : ℕ
- Source
- Girth-dependent center budget for the four-cycle campaign.
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 3
- digraph_girth_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
- 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…
- 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…
Lean source view module on GitHub
noncomputable def digraph_common_predecessor_girth_correction (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g : ℕ) : ℕ := by classical exact ∑ e ∈ (digraph_common_predecessor_graph D).edgeFinset.filter (fun e => 2 ≤ (Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card), (g + 1 - 2 * (Finset.univ.filter fun p => ∀ x, x ∈ e → D.Adj p x).card)