digraph_girth_weighted_overlap_cycle_packing_step
For a loopless oriented arc-dominated digraph of directed girth at least g, the k-cycle theorem at outdegree d implies a (k+1)-cycle packing at outdegree d+2 under the displayed girth-weighted overlap bound.
Statement
theorem digraph_girth_weighted_overlap_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g k d : ℕ) (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) (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 : 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 α) (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
- Girth-dependent center budget for the four-cycle campaign; experiment 13474.
- 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_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…
- 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_girth_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 deduces the (k+1)-cycle packing from the k-cycle packing hypothesis by finding a local directed cycle inside the out-neighborhood of a carefully chosen center vertex. The girth-weighted overlap bound guarantees the existence of a good center vertex v whose out-neighborhood is clean and satisfies a codomain condition. That codomain condition provides a directed cycle C contained entirely in the out-neighborhood of v, while arc-domination provides an in-neighbor p of v. Finally, digraph_clean_outneighborhood_cycle_packing_step removes C and applies the packing hypothesis on the remaining vertices to obtain k + 1 pairwise disjoint directed cycles.
Adjacency in the common predecessor graph of D is decidable. automation
For any two vertices u and v, the definition of digraph_common_predecessor_graph is unfolded to the assertion that u ≠ v and there exists a common in-neighbor w to u and v in D. Because the vertex type α is finite and adjacency in D is decidable, typeclass synthesis (infer_instance) automatically produces the decision procedure.
intro u v unfold digraph_common_predecessor_graph infer_instance
There exists a vertex v with a clean out-neighborhood that satisfies the codomain property.
Applying digraph_girth_weighted_good_center under the hypotheses that D is loopless (hloop), oriented (hori), arc-dominated (hdom), has directed girth at least g ≥ 3 (hg, hgirth), and satisfies the girth-weighted overlap bound (hsmall), we obtain a vertex v whose out-neighborhood is clean (no two distinct out-neighbors share any predecessor other than v, hclean) and satisfies the codomain property (every out-neighbor w of v shares an out-neighbor with v, hcodom).
uses
digraph_girth_weighted_good_centerclassical obtain ⟨v, hclean, hcodom⟩ := digraph_girth_weighted_good_center α D g hg hloop hori hgirth hdom hsmallThe vertex v has at least one out-neighbor in D.
By the minimum out-degree condition hdeg, the out-neighborhood of v has cardinality at least d + 2 ≥ 2 > 0. Via Finset.card_pos.mp, this strictly positive cardinality yields a witness w in the out-neighborhood, and Finset.mem_filter.mp confirms that w is an out-neighbor of v (D.Adj v w).
uses
Finset.card_pos.mp,Finset.mem_filter.mphave hv : ∃ w, D.Adj v w := by have h := hdeg v obtain ⟨w, hw⟩ := Finset.card_pos.mp (show 0 < (Finset.univ.filter fun w => D.Adj v w).card by omega) exact ⟨w, (Finset.mem_filter.mp hw).2⟩
There exists a directed cycle C contained entirely within the out-neighborhood of v.
Because D is loopless (hloop), v has an out-neighbor (hv), and v satisfies the codomain property (hcodom), digraph_local_outneighborhood_cycle guarantees the existence of a directed cycle C such that every vertex in C is an out-neighbor of v (hCout).
uses
digraph_local_outneighborhood_cycleobtain ⟨C, hC, hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodomThe vertex v has an in-neighbor p in D.
Taking the out-neighbor w of v obtained previously, the arc-domination hypothesis hdom on the directed edge from v to w yields a common predecessor p such that D.Adj p v and D.Adj p w. In particular, p is an in-neighbor of v.
obtain ⟨w, hvw⟩ := hv obtain ⟨p, hpv, _⟩ := hdom v w hvw
There exists a packing of k + 1 pairwise disjoint directed cycles in D.
All hypotheses of digraph_clean_outneighborhood_cycle_packing_step are satisfied: D is loopless and oriented, every vertex has out-degree at least d + 2, the packing hypothesis hpack holds at out-degree d, C is a directed cycle in the out-neighborhood of v, v has a clean out-neighborhood, and p is an in-neighbor of v. Applying this lemma produces k + 1 pairwise 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
digraph_girth_weighted_good_center- In any finite loopless oriented arc-dominated digraph of directed girth at least g ≥ 3 satisfying the girth-weighted overlap bound, there exists a vertex v with a clean out-neighborhood (no two distinct out-neighbors share another common predecessor) that satisfies the codomain property (every out-neighbor shares an out-neighbor with v).
Finset.card_pos.mp- A finite set is non-empty whenever its cardinality is strictly positive.
Finset.mem_filter.mp- If an element belongs to a filtered finite set {x ∈ s | P x}, then it belongs to s and satisfies the predicate P.
digraph_local_outneighborhood_cycle- In a loopless digraph, if a vertex v has at least one out-neighbor and satisfies the codomain property that every out-neighbor shares an out-neighbor with v, then there exists a directed cycle all of whose vertices lie in the out-neighborhood of v.
digraph_clean_outneighborhood_cycle_packing_step- In a loopless oriented digraph where every vertex has out-degree at least d + 2, if every non-empty induced subgraph with minimum out-degree at least d contains k disjoint directed cycles, and there exists a vertex v with a clean out-neighborhood containing a directed cycle C and an in-neighbor p of v, then the digraph contains k + 1 pairwise disjoint directed cycles.
- The helper instance in516_girth_pack_decAdj on lines 1–5 is a technical prerequisite establishing decidability of adjacency in the common predecessor graph, needed for Lean to form the finite edge set in the girth-weighted overlap inequality hsmall.
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_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_girth_weighted_overlap_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g k d : ℕ) (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) (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 : 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 α) (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_girth_weighted_good_center α D g hg hloop hori hgirth hdom hsmall have hv : ∃ w, D.Adj v w := by have h := hdeg v obtain ⟨w, hw⟩ := Finset.card_pos.mp (show 0 < (Finset.univ.filter fun w => D.Adj v w).card by omega) exact ⟨w, (Finset.mem_filter.mp hw).2⟩ obtain ⟨C, hC, hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodom obtain ⟨w, hvw⟩ := hv obtain ⟨p, hpv, _⟩ := hdom v w hvw exact digraph_clean_outneighborhood_cycle_packing_step α D k d hloop hori hdeg hpack v C hC hCout hclean p hpv