digraph_127_four_cycles_under_extremal_and_cycle_criteria
A 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed cycles, assuming the displayed induced one-, two- and three-cycle criteria and the near-extremal clique-free coloring criterion.
Statement
theorem digraph_127_four_cycles_under_extremal_and_cycle_criteria (D : Digraph (Fin 127)) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hin : ∀ v, ∃ C : Finset (Fin 127), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v) (hone : ∀ T : Finset (Fin 127), T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset (Fin 127), C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ T : Finset (Fin 127), T.Nonempty → (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 2 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hthree : ∀ T : Finset (Fin 127), T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hnear : ∀ (n s : ℕ), 2 ≤ s → 2 * s + 1 ≤ n → ∀ (G : SimpleGraph (Fin n)) [DecidableRel G.Adj], G.CliqueFree (s + 1) → (SimpleGraph.turanGraph n s).edgeFinset.card + 2 ≤ G.edgeFinset.card + n / s → G.Colorable s) : ∃ c : Fin 4 → Finset (Fin 127), (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))
- Source
- Proposed exceptional-vertex reduction for OP-110; experiments 12602 and 12603 check the finite arithmetic.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_graph_edge_count_leIf every vertex of a finite digraph has at most seven out-neighbors, then its common-predecessor graph has at most 21 times as many edges…
- digraph_common_predecessor_graph_indep_free_fourIf each in-neighborhood of a finite digraph contains a directed cycle and the digraph has no four disjoint directed cycles, then its…
- digraph_small_overlap_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for loopless arc-dominated digraphs of minimum outdegree at least d+2…
- digraph_127_regular_independence_small_overlapA seven-outregular digraph on 127 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
The proof, explained
The proof argues by contradiction: suppose D does not contain four pairwise disjoint directed cycles. Since every in-neighborhood contains a cycle, this implies that the common predecessor graph of D contains no independent set of size 4. For a 7-outregular digraph on 127 vertices, this independence condition forces the overlap defect to be strictly less than 127. Applying the cycle packing step with k = 3 and d = 5 lifts the 3-cycle packing hypothesis to produce four disjoint directed cycles, contradicting the assumption.
Assume for contradiction that D has no four pairwise disjoint directed cycles.
We apply classical reasoning and proceed by contradiction, introducing the hypothesis `hno` that there is no family of 4 pairwise disjoint directed cycles in D.
classical by_contra hnoThe common predecessor graph of D has no independent set of size 4.
Because every vertex has a directed cycle in its in-neighborhood (`hin`), an independent set of size 4 in the common predecessor graph would yield 4 disjoint directed cycles; hence the assumption `hno` implies the graph is 4-independent-set-free by `digraph_common_predecessor_graph_indep_free_four`.
uses
digraph_common_predecessor_graph_indep_free_fourhave hindep := digraph_common_predecessor_graph_indep_free_four (Fin 127) D hin hnoThe overlap defect of D is strictly bounded by 127: 3 * (∑ v, Nat.choose (d⁺(v)) 2 - |E(G)|) < 127.
We invoke `digraph_127_regular_independence_small_overlap`, which derives this small overlap inequality for any 7-regular digraph on 127 vertices whose common predecessor graph has independence number less than 4.
uses
digraph_127_regular_independence_small_overlaphave hsmall := digraph_127_regular_independence_small_overlap D hreg hindepEvery vertex v in D has out-degree at least 5 + 2 = 7.
For any vertex v, rewriting with the 7-outregularity hypothesis `hreg v` shows that 5 + 2 ≤ 7 = d⁺(v).
have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by intro v rw [hreg v]
D contains 4 pairwise disjoint directed cycles, contradicting hno.
We apply the cycle packing step `digraph_small_overlap_cycle_packing_step` with parameters k = 3 and d = 5, using the loopless property, out-degree bound, arc domination, the small overlap bound, and the 3-cycle packing criterion `hthree`. This produces 4 pairwise disjoint directed cycles, contradicting `hno` and concluding the proof.
uses
digraph_small_overlap_cycle_packing_step,SimpleGraph.mem_edgeFinsetexact hno (digraph_small_overlap_cycle_packing_step (Fin 127) D 3 5 hloop hdeg' hdom (by convert hsmall using 4; ext e; simp only [SimpleGraph.mem_edgeFinset]) hthree)
digraph_common_predecessor_graph_indep_free_four- If every vertex of a digraph has a directed cycle in its in-neighborhood and the digraph lacks 4 pairwise disjoint directed cycles, then its common predecessor graph has no independent set of size 4.
digraph_127_regular_independence_small_overlap- For a 7-outregular digraph on 127 vertices whose common predecessor graph has no independent set of size 4, the triple of the total overlap defect is strictly less than 127.
digraph_small_overlap_cycle_packing_step- In a loopless digraph with dominated arcs and minimum out-degree at least d + 2 satisfying the small overlap defect condition, if every induced subgraph with minimum out-degree at least d contains k disjoint directed cycles, then the digraph contains k + 1 disjoint directed cycles.
SimpleGraph.mem_edgeFinset- An edge belongs to the finite set of edges of a graph if and only if it belongs to its edge set.
- Hypotheses `hori` (orientation), `hone` (1-cycle criterion), `htwo` (2-cycle criterion), and `hnear` (near-extremal Turán coloring criterion) appear in the theorem statement as context but are not directly referenced in the proof, having already been incorporated into the helper lemma `digraph_127_regular_independence_small_overlap`.
- The subproof on line 35 (`convert hsmall using 4; ext e; simp only [SimpleGraph.mem_edgeFinset]`) is a technicality in Lean to reconcile the edge set finiteness instances between `hsmall` and the premise of `digraph_small_overlap_cycle_packing_step`.
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.
theorem digraph_127_four_cycles_under_extremal_and_cycle_criteria (D : Digraph (Fin 127)) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hin : ∀ v, ∃ C : Finset (Fin 127), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v) (hone : ∀ T : Finset (Fin 127), T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset (Fin 127), C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ T : Finset (Fin 127), T.Nonempty → (∀ v ∈ T, 3 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 2 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hthree : ∀ T : Finset (Fin 127), T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset (Fin 127), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hnear : ∀ (n s : ℕ), 2 ≤ s → 2 * s + 1 ≤ n → ∀ (G : SimpleGraph (Fin n)) [DecidableRel G.Adj], G.CliqueFree (s + 1) → (SimpleGraph.turanGraph n s).edgeFinset.card + 2 ≤ G.edgeFinset.card + n / s → G.Colorable s) : ∃ c : Fin 4 → Finset (Fin 127), (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j)) := by classical by_contra hno have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 127) D hin hno have hsmall := digraph_127_regular_independence_small_overlap D hreg hindep have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by intro v rw [hreg v] exact hno (digraph_small_overlap_cycle_packing_step (Fin 127) D 3 5 hloop hdeg' hdom (by convert hsmall using 4; ext e; simp only [SimpleGraph.mem_edgeFinset]) hthree)