digraph_125_no_four_cycles_overlap_window
For a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four disjoint cycles, the common-predecessor overlap is 42 or 43 and its complement is not three-colorable, assuming the displayed induced one-, robust two-, and three-cycle criteria and the stated near-extremal coloring criterion.
Statement
theorem digraph_125_no_four_cycles_overlap_window (D : Digraph (Fin 125)) [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 → ∃ p, D.Adj p u ∧ D.Adj p v) (hin : ∀ v, ∃ C : Finset (Fin 125), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v) (hone : ∀ T : Finset (Fin 125), T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset (Fin 125), C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ T : Finset (Fin 125), T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hthree : ∀ T : Finset (Fin 125), T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hnear : ∀ (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj], G.CliqueFree 4 → 5169 ≤ G.edgeFinset.card → G.Colorable 3) (hno : ¬ ∃ c : Fin 4 → Finset (Fin 125), (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : let J := digraph_common_predecessor_graph D (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ Jᶜ.Colorable 3
- Source
- Overlap-window reduction for OP-110, using the cycle criteria in https://iti.mff.cuni.cz/series/2007/339.pdf and the coloring criterion in https://arxiv.org/abs/1409.8665, Theorem 1.1.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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_three_large_parts_no_four_cycles_cross_ge_fifty_fourIf a finite digraph of minimum outdegree seven has no four disjoint directed cycles and its vertices are partitioned into three parts each…
- graph_125_three_clique_partition_oriented_cross_boundFor a graph on 125 vertices partitioned into three cliques, with at most 2583 graph edges, each part has at least seven vertices and every…
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
- Used by 1
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
The proof, explained
The proof establishes that the common-predecessor graph J has no independent set of size 4, so its complement H = Jᶜ is K₄-free. If the common-predecessor overlap 2625 - |E(J)| were less than 125 / 3 ≈ 41.67, cycle packing would produce 4 disjoint directed cycles in D, contradicting the no-four-cycles hypothesis; this bounds |E(J)| ≤ 2583 and gives the lower bound 42 on the overlap. A hypothetical 3-coloring of H would partition J into 3 cliques, but cross-arc bounds for 3-clique partitions force at most 41 cross-arcs, contradicting the structural lower bound of 54 cross-arcs for digraphs without 4 disjoint cycles. Because H is K₄-free and not 3-colorable, the near-extremal coloring criterion bounds |E(H)| ≤ 5168, which combines with the total edge count |E(J)| + |E(H)| = 7750 to yield the upper bound 43 on the overlap.
Adjacency in the common-predecessor graph of D is decidable.
For any two vertices u and v, the condition that u ≠ v and there exists a common predecessor p with arcs p → u and p → v is decidable because the vertex set is finite and adjacency in D is decidable.
private instance in833_common_predecessor_decidable125 {α : 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_instance
The common-predecessor graph J has no independent set of size 4, so its complement H = Jᶜ contains no 4-clique (H is K₄-free).
Let J be the common-predecessor graph of D and H its complement. By digraph_common_predecessor_graph_indep_free_four, since every vertex has a directed cycle in its in-neighborhood and D has no four disjoint directed cycles, J has no independent set of size 4. Translating to the complement graph, an independent set in J is a clique in H, so H is K₄-free.
uses
digraph_common_predecessor_graph_indep_free_fourclassical let J := digraph_common_predecessor_graph D let H := Jᶜ have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 125) D hin hno have hfree : H.CliqueFree 4 := by simpa [H,J] using hindep
The sum of out-degree binomial coefficients is 2625, and every vertex has out-degree at least 5 + 2.
Since D is 7-outregular, each vertex contributes 7 choose 2 = 21 pairs of out-neighbors. Across all 125 vertices, the sum of these binomial coefficients is 125 * 21 = 2625. Furthermore, 7 ≥ 5 + 2, satisfying the degree requirement for cycle packing.
have hinc : (∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2625 := by simp [hreg] norm_num [Nat.choose] have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by intro v rw [hreg v]
The common-predecessor overlap satisfies 125 ≤ 3 * (2625 - |E(J)|), which implies |E(J)| ≤ 2583.
Suppose for contradiction that 3 * (2625 - |E(J)|) < 125. By digraph_small_overlap_cycle_packing_step with k = 3 and d = 5, the 7-regularity, looplessness, arc domination, and the 3-cycle packing condition would guarantee the existence of 3 + 1 = 4 pairwise disjoint directed cycles, contradicting the hypothesis that D has no four disjoint cycles. Thus 125 ≤ 3 * (2625 - |E(J)|), from which integer arithmetic yields |E(J)| ≤ 2583.
uses
Fintype.card_fin,digraph_small_overlap_cycle_packing_step,SimpleGraph.mem_edgeFinsethave hz : 125 ≤ 3 * (2625 - J.edgeFinset.card) := by by_contra hh have hs : 3 * ((∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - J.edgeFinset.card) < Fintype.card (Fin 125) := by rw [hinc]; simp only [Fintype.card_fin]; omega apply hno apply digraph_small_overlap_cycle_packing_step (Fin 125) D 3 5 hloop hdeg' hdom · convert hs using 4 <;> ext e <;> simp only [SimpleGraph.mem_edgeFinset] <;> rfl · exact hthree have hedges : J.edgeFinset.card ≤ 2583 := by omega
Every directed arc of D is an edge in the common-predecessor graph J.
For any arc u → v in D, the vertices u and v are distinct because D is loopless, and they share a common predecessor by the arc domination hypothesis. Therefore, u and v are adjacent in J.
have hsub : ∀ u v, D.Adj u v → J.Adj u v := by intro u v huv have hne : u ≠ v := by intro h subst v exact hloop u huv change u ≠ v ∧ ∃ p, D.Adj p u ∧ D.Adj p v exact ⟨hne, hdom u v huv⟩
The complement graph H = Jᶜ is not 3-colorable.
Suppose for contradiction that H has a proper 3-coloring. Two distinct vertices of the same color cannot be adjacent in H, so they must be adjacent in J; thus each color class induces a clique in J. By graph_125_three_clique_partition_oriented_cross_bound, because |E(J)| ≤ 2583 and D is an oriented subgraph of J, every color class must have size at least 7, and the number of cross-arcs between different color classes is at most 41. However, digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four shows that any 3-partition into parts of size at least 7 must have at least 54 cross-arcs. This contradiction (54 ≤ cross-arcs ≤ 41) proves H is not 3-colorable.
uses
SimpleGraph.compl_adj,graph_125_three_clique_partition_oriented_cross_bound,digraph_three_large_parts_no_four_cycles_cross_ge_fifty_fourhave hnotcolor : ¬ H.Colorable 3 := by intro hc obtain ⟨col⟩ := hc have hclique : ∀ u v, col u = col v → u ≠ v → J.Adj u v := by intro u v heq hne by_contra h have hadj : H.Adj u v := by simp [H, SimpleGraph.compl_adj, hne, h] exact (col.map_rel hadj) heq have hb := graph_125_three_clique_partition_oriented_cross_bound J D col hclique hsub hori hedges have hc := digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (Fin 125) D col hb.1 (by intro v; rw [hreg v]) hone htwo hthree hno omega
The total number of edges in J and H combined is 7750.
Because H is the complement of J, their edge sets are disjoint and their union is the edge set of the complete graph on 125 vertices. The number of edges in the complete graph is 125 choose 2 = 125 * 124 / 2 = 7750. Thus |E(J)| + |E(H)| = 7750.
uses
SimpleGraph.disjoint_edgeFinset,disjoint_compl_right,SimpleGraph.edgeFinset_sup,SimpleGraph.edgeFinset_inj.mpr,sup_compl_eq_top,Finset.card_union_of_disjoint,SimpleGraph.card_edgeFinset_top_eq_card_choose_two,Nat.choose_two_righthave hdis : Disjoint J.edgeFinset H.edgeFinset := by rw [SimpleGraph.disjoint_edgeFinset] change Disjoint J Jᶜ exact disjoint_compl_right have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 125)).edgeFinset := by rw [← SimpleGraph.edgeFinset_sup] change (J ⊔ Jᶜ).edgeFinset = _ exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top have htotal : J.edgeFinset.card + H.edgeFinset.card = 7750 := by rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two] rw [Nat.choose_two_right] norm_num
The complement graph H has at most 5168 edges.
If |E(H)| were at least 5169, then since H is K₄-free, the near-extremal coloring criterion would imply that H is 3-colorable. But H was already shown not to be 3-colorable, so |E(H)| ≤ 5168.
have hupper : H.edgeFinset.card ≤ 5168 := by by_contra hh exact hnotcolor (hnear H hfree (by omega))
The common-predecessor overlap 2625 - |E(J)| is 42 or 43, and H is not 3-colorable. automation
From |E(J)| ≤ 2583, the overlap satisfies 2625 - |E(J)| ≥ 2625 - 2583 = 42. From |E(J)| + |E(H)| = 7750 and |E(H)| ≤ 5168, we have |E(J)| ≥ 7750 - 5168 = 2582, so 2625 - |E(J)| ≤ 2625 - 2582 = 43. Linear arithmetic confirms 42 ≤ 2625 - |E(J)| ≤ 43, and non-3-colorability of H was established earlier.
change (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ H.Colorable 3 exact ⟨⟨by omega, by omega⟩, hnotcolor⟩
Fintype.card_fin- The cardinality of the standard finite type Fin n is n.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.choose_two_right- For any natural number n, n choose 2 equals n * (n - 1) / 2.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph if and only if they are distinct and not adjacent in the original graph.
SimpleGraph.edgeFinset_sup- The edge Finset of the supremum (join) of two graphs is the union of their edge Finsets.
SimpleGraph.edgeFinset_inj.mpr- If two simple graphs are equal, their edge Finsets are equal.
SimpleGraph.disjoint_edgeFinset- Two graphs have disjoint edge Finsets if and only if the graphs themselves are disjoint.
SimpleGraph.mem_edgeFinset- An unordered pair is in the edge Finset of a graph if and only if it belongs to its edge set.
SimpleGraph.card_edgeFinset_top_eq_card_choose_two- The number of edges in the complete graph on a vertex set V is |V| choose 2.
digraph_common_predecessor_graph_indep_free_four- If every vertex of a digraph has a directed cycle in its in-neighborhood and the digraph has no four disjoint directed cycles, then its common-predecessor graph has no independent set of size four.
digraph_small_overlap_cycle_packing_step- In a loopless digraph with dominated arcs, if the minimum out-degree is at least d + 2 and the common-predecessor overlap satisfies 3 * overlap < |V|, then any k-cycle packing property for minimum out-degree d extends to packing k + 1 pairwise disjoint cycles.
digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four- In an out-regular digraph partitioned into three parts of size at least 7 with no four disjoint cycles and satisfying the 1-, 2-, and 3-cycle packing conditions, there are at least 54 cross-arcs between different parts.
disjoint_compl_right- Any element in a Heyting or Boolean algebra is disjoint from its complement.
graph_125_three_clique_partition_oriented_cross_bound- If the common-predecessor graph on 125 vertices has at most 2583 edges and is partitioned into three cliques containing an oriented subgraph, each clique has size at least 7 and there are at most 41 cross-edges.
sup_compl_eq_top- The join of an element with its complement is the top element (the complete graph).
- Lines 3–7 define a private instance establishing decidability of adjacency in the common-predecessor graph, a formal requirement for applying the near-extremal coloring criterion.
- Linear integer arithmetic across several steps (bounding edges and establishing the overlap interval) is solved automatically by omega.
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.
set_option maxHeartbeats 5000000set_option maxRecDepth 4096private instance in833_common_predecessor_decidable125 {α : 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_125_no_four_cycles_overlap_window (D : Digraph (Fin 125)) [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 → ∃ p, D.Adj p u ∧ D.Adj p v) (hin : ∀ v, ∃ C : Finset (Fin 125), digraph_directed_cycle_on D C ∧ ∀ w ∈ C, D.Adj w v) (hone : ∀ T : Finset (Fin 125), T.Nonempty → (∀ v ∈ T, 1 ≤ (T.filter fun w => D.Adj v w).card) → ∃ C : Finset (Fin 125), C ⊆ T ∧ digraph_directed_cycle_on D C) (htwo : ∀ T : Finset (Fin 125), T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card < 3).card ≤ 2 → ∃ c : Fin 2 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hthree : ∀ T : Finset (Fin 125), T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ c : Fin 3 → Finset (Fin 125), (∀ i, c i ⊆ T ∧ digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) (hnear : ∀ (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj], G.CliqueFree 4 → 5169 ≤ G.edgeFinset.card → G.Colorable 3) (hno : ¬ ∃ c : Fin 4 → Finset (Fin 125), (∀ i, digraph_directed_cycle_on D (c i)) ∧ Pairwise (fun i j => Disjoint (c i) (c j))) : let J := digraph_common_predecessor_graph D (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ Jᶜ.Colorable 3 := by classical let J := digraph_common_predecessor_graph D let H := Jᶜ have hindep := digraph_common_predecessor_graph_indep_free_four (Fin 125) D hin hno have hfree : H.CliqueFree 4 := by simpa [H,J] using hindep have hinc : (∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) = 2625 := by simp [hreg] norm_num [Nat.choose] have hdeg' : ∀ v, 5 + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card := by intro v rw [hreg v] have hz : 125 ≤ 3 * (2625 - J.edgeFinset.card) := by by_contra hh have hs : 3 * ((∑ v : Fin 125, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - J.edgeFinset.card) < Fintype.card (Fin 125) := by rw [hinc]; simp only [Fintype.card_fin]; omega apply hno apply digraph_small_overlap_cycle_packing_step (Fin 125) D 3 5 hloop hdeg' hdom · convert hs using 4 <;> ext e <;> simp only [SimpleGraph.mem_edgeFinset] <;> rfl · exact hthree have hedges : J.edgeFinset.card ≤ 2583 := by omega have hsub : ∀ u v, D.Adj u v → J.Adj u v := by intro u v huv have hne : u ≠ v := by intro h subst v exact hloop u huv change u ≠ v ∧ ∃ p, D.Adj p u ∧ D.Adj p v exact ⟨hne, hdom u v huv⟩ have hnotcolor : ¬ H.Colorable 3 := by intro hc obtain ⟨col⟩ := hc have hclique : ∀ u v, col u = col v → u ≠ v → J.Adj u v := by intro u v heq hne by_contra h have hadj : H.Adj u v := by simp [H, SimpleGraph.compl_adj, hne, h] exact (col.map_rel hadj) heq have hb := graph_125_three_clique_partition_oriented_cross_bound J D col hclique hsub hori hedges have hc := digraph_three_large_parts_no_four_cycles_cross_ge_fifty_four (Fin 125) D col hb.1 (by intro v; rw [hreg v]) hone htwo hthree hno omega have hdis : Disjoint J.edgeFinset H.edgeFinset := by rw [SimpleGraph.disjoint_edgeFinset] change Disjoint J Jᶜ exact disjoint_compl_right have hunion : J.edgeFinset ∪ H.edgeFinset = (⊤ : SimpleGraph (Fin 125)).edgeFinset := by rw [← SimpleGraph.edgeFinset_sup] change (J ⊔ Jᶜ).edgeFinset = _ exact SimpleGraph.edgeFinset_inj.mpr sup_compl_eq_top have htotal : J.edgeFinset.card + H.edgeFinset.card = 7750 := by rw [← Finset.card_union_of_disjoint hdis, hunion, SimpleGraph.card_edgeFinset_top_eq_card_choose_two] rw [Nat.choose_two_right] norm_num have hupper : H.edgeFinset.card ≤ 5168 := by by_contra hh exact hnotcolor (hnear H hfree (by omega)) change (42 ≤ 2625 - J.edgeFinset.card ∧ 2625 - J.edgeFinset.card ≤ 43) ∧ ¬ H.Colorable 3 exact ⟨⟨by omega, by omega⟩, hnotcolor⟩