digraph_trianglefree_weighted_overlap_cycle_packing_step
For a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle packing at outdegree d+2 whenever eight times the repeated-pair incidence count plus the number of multiplicity-two pairs is less than three times the order.
Statement
theorem digraph_trianglefree_weighted_overlap_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (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) (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).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 α) (hpack : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) : ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- Triangle-free center budget for the four-cycle campaign; experiments 13471 and 13473.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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…
- digraph_local_outneighborhood_cycleIf an out-neighborhood is nonempty and each of its vertices has an out-neighbor inside it, it contains a directed cycle.
- digraph_clean_outneighborhood_cycle_packing_stepA directed cycle inside a clean out-neighborhood can be added to any k-cycle packing theorem two outdegree units lower.
- 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_trianglefree_weighted_good_centerUnder the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean…
The proof, explained
The proof finds a good center vertex v whose out-neighborhood is clean (no two out-neighbors share another common predecessor) and self-dominating, via digraph_trianglefree_weighted_good_center. Because the minimum out-degree is at least d + 2 ≥ 2, v has an out-neighbor, which together with self-domination ensures the existence of a directed cycle C contained entirely within the out-neighborhood of v. By arc-domination, v also has an in-neighbor p. Finally, digraph_clean_outneighborhood_cycle_packing_step uses this clean cycle C and the in-neighbor p to extend a k-cycle packing on the remaining vertices into a (k+1)-cycle packing of D.
Adjacency in the common predecessor graph is decidable.
For any two vertices u and v, unfolding the definition of the common predecessor graph reduces adjacency to checking inequality and the existence of a common predecessor in the finite vertex type, which typeclass inference synthesizes as decidable.
intro u v unfold digraph_common_predecessor_graph infer_instance
There exists a vertex v with a clean out-neighborhood whose out-neighborhood is self-dominating.
By digraph_trianglefree_weighted_good_center, the structural hypotheses on D—being loopless, oriented, of directed girth at least four, arc-dominated, and satisfying the weighted overlap bound on common predecessors—guarantee a vertex v such that distinct out-neighbors of v share no common predecessor other than v itself, and every out-neighbor of v has an arc to another out-neighbor of v.
uses
digraph_trianglefree_weighted_good_centerclassical obtain ⟨v,hclean,hcodom⟩ := digraph_trianglefree_weighted_good_center α D hloop hori hgirth hdom hsmallThe center vertex v has positive out-degree, so it has at least one out-neighbor w.
The minimum degree hypothesis hdeg implies that the out-degree of v is at least d + 2 ≥ 2 > 0. Since the cardinality of its out-neighborhood is strictly positive, the set is nonempty, yielding an out-neighbor w.
uses
Finset.card_pos.mp,Finset.mem_filter.mphave hv : ∃ w, D.Adj v w := by have hp : 0 < (Finset.univ.filter fun w => D.Adj v w).card := by have := hdeg v omega obtain ⟨w,hw⟩ := Finset.card_pos.mp hp exact ⟨w,(Finset.mem_filter.mp hw).2⟩
The out-neighborhood of v contains a directed cycle C.
Applying digraph_local_outneighborhood_cycle to the vertex v, using that v has an out-neighbor and that its out-neighborhood is self-dominating, produces a directed cycle C all of whose vertices are out-neighbors of v.
uses
digraph_local_outneighborhood_cycleobtain ⟨C,hC,hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodomThe center vertex v has an in-neighbor p.
Using the out-neighbor w of v, the arc-domination hypothesis hdom on the directed edge (v, w) provides a vertex p that is a common predecessor of both v and w; in particular, p is adjacent to v.
obtain ⟨w,hw⟩ := hv obtain ⟨p,hpv,_⟩ := hdom v w hw
The digraph D contains a packing of k + 1 pairwise disjoint directed cycles.
The reduction lemma digraph_clean_outneighborhood_cycle_packing_step combines the cycle C in the clean out-neighborhood of v, the in-neighbor p of v, and the induction hypothesis hpack to produce k + 1 pairwise vertex-disjoint directed cycles in D.
uses
digraph_clean_outneighborhood_cycle_packing_stepexact digraph_clean_outneighborhood_cycle_packing_step α D k d hloop hori hdeg hpack v C hC hCout hclean p hpv
Finset.card_pos.mp- A finite set with strictly positive cardinality has at least one element.
Finset.mem_filter.mp- An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filter condition.
digraph_trianglefree_weighted_good_center- In a loopless oriented arc-dominated digraph of directed girth at least four satisfying the weighted common-predecessor overlap bound, there exists a vertex v with a clean out-neighborhood (no two distinct out-neighbors share any other common predecessor) such that every out-neighbor has an out-edge staying in N⁺(v).
digraph_local_outneighborhood_cycle- In a loopless digraph, if a vertex v has positive out-degree and every out-neighbor has an out-edge to another out-neighbor of v, then the out-neighborhood of v contains a directed cycle.
digraph_clean_outneighborhood_cycle_packing_step- In a loopless oriented digraph of minimum out-degree at least d + 2, if a vertex v has an in-neighbor, a clean out-neighborhood, and contains a directed cycle C within its out-neighborhood, then a k-cycle packing result at minimum out-degree d extends to a (k+1)-cycle packing in the whole digraph.
- The instance in516_weighted_pack_decAdj provides decidability of adjacency in the common predecessor graph, which is required for Lean to form the edge finset appearing in the condition hsmall.
- The strict positivity of the out-degree is resolved by the omega arithmetic tactic from the hypothesis d + 2 ≤ d⁺(v).
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_weighted_pack_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_overlap_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (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) (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).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 α) (hpack : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) : ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by classical obtain ⟨v,hclean,hcodom⟩ := digraph_trianglefree_weighted_good_center α D hloop hori hgirth hdom hsmall have hv : ∃ w, D.Adj v w := by have hp : 0 < (Finset.univ.filter fun w => D.Adj v w).card := by have := hdeg v omega obtain ⟨w,hw⟩ := Finset.card_pos.mp hp exact ⟨w,(Finset.mem_filter.mp hw).2⟩ obtain ⟨C,hC,hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodom obtain ⟨w,hw⟩ := hv obtain ⟨p,hpv,_⟩ := hdom v w hw exact digraph_clean_outneighborhood_cycle_packing_step α D k d hloop hori hdeg hpack v C hC hCout hclean p hpv