maxcut_five_cycle_repeats
Any five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence returning to its start after five steps.
Statement
theorem maxcut_five_cycle_repeats {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (colors : Fin 5 → V → Fin k) (hcycle : ∀ i : Fin 5, is_maxcut_strong_deviation G (colors i) (Finset.univ.filter fun v => colors (i + 1) v ≠ colors i v) (colors (i + 1))) : ∃ f : ℕ → V → Fin k, f 5 = f 0 ∧ ∀ n, is_maxcut_strong_deviation G (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1))
- Source
- Finite-cycle assembly for maxcut_unweighted_strong_deviation_cycle_exists.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
- Used by 1
- maxcut_unweighted_strong_deviation_cycle_existsThere is an unweighted simple graph on 46 vertices and an infinite sequence of three-color profiles that returns to its starting profile…
The proof, explained
The theorem extends a 5-step cycle of strong deviations into an infinite periodic sequence of strong deviations. The strategy is to wrap the natural number time index modulo 5, defining f(n) = colors(n % 5). Periodicity f(5) = f(0) holds definitionally, and the deviation condition at step n follows from the cycle hypothesis by showing that the index for n + 1 equals the successor of the index for n in Fin 5.
Define the candidate periodic sequence f and reduce the existential claim to periodicity and step-by-step strong deviation.
We define f(n) = colors(⟨n % 5, ...⟩), taking the time index n modulo 5 and using Nat.mod_lt to certify that n % 5 < 5. Proposing f as the existential witness splits the goal into two obligations: verifying periodicity f(5) = f(0), and showing that each step from f(n) to f(n + 1) is a strong deviation.
uses
Nat.mod_ltlet f : ℕ → V → Fin k := fun n => colors ⟨n % 5, Nat.mod_lt _ (by decide)⟩ refine ⟨f, ?_, ?_⟩
The sequence returns to its initial coloring after 5 steps: f(5) = f(0).
Since 5 % 5 = 0 = 0 % 5, both f(5) and f(0) evaluate definitionally to colors(⟨0, ...⟩), so the equality holds by reflexivity.
· rflFor any n ∈ ℕ, the index (n + 1) % 5 equals (n % 5) + 1 in Fin 5.
To connect the step from f(n) to f(n + 1) with the cycle hypothesis, we show that ⟨(n + 1) % 5, ...⟩ = ⟨n % 5, ...⟩ + 1 in Fin 5. By Fin.ext, it suffices to check this for their underlying natural numbers. The right-hand side has value ((n % 5) + 1) % 5 by Fin.val_add, which simplifies to (n + 1) % 5 by Nat.add_mod.
uses
Nat.mod_lt,Fin.ext,Fin.val_add,Nat.add_mod· intro n have hn : (⟨(n + 1) % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) = (⟨n % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) + 1 := by apply Fin.ext simp [Fin.val_add, Nat.add_mod]
For every step n, f(n + 1) is a strong deviation from f(n).
We specialize the cycle hypothesis hcycle to the index i = ⟨n % 5, ...⟩ in Fin 5. By the definition of f and the equality hn, f(n) is colors(i) and f(n + 1) is colors(i + 1). Substituting these into the specialized hypothesis matches the goal exactly, completing the proof.
uses
Nat.mod_ltsimpa [f, hn] using hcycle ⟨n % 5, Nat.mod_lt _ (by decide)⟩
Nat.mod_lt- For any natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Fin.val_add- The natural number value of the sum a + b in Fin n equals (↑a + ↑b) % n.
Nat.add_mod- For any natural numbers a, b, and n, (a + b) % n = (a % n + b % n) % n.
- In Lean, finite-type arithmetic modulo 5 involves explicit proofs that remainder values are bounded (`Nat.mod_lt` with `0 < 5` proved by `decide`) and conversions between `Fin 5` and `ℕ` via `Fin.ext`, whereas on paper the equivalence $(n + 1) \bmod 5 \equiv (n \bmod 5) + 1$ is taken as standard modular arithmetic.
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 maxcut_five_cycle_repeats {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (colors : Fin 5 → V → Fin k) (hcycle : ∀ i : Fin 5, is_maxcut_strong_deviation G (colors i) (Finset.univ.filter fun v => colors (i + 1) v ≠ colors i v) (colors (i + 1))) : ∃ f : ℕ → V → Fin k, f 5 = f 0 ∧ ∀ n, is_maxcut_strong_deviation G (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) := by let f : ℕ → V → Fin k := fun n => colors ⟨n % 5, Nat.mod_lt _ (by decide)⟩ refine ⟨f, ?_, ?_⟩ · rfl · intro n have hn : (⟨(n + 1) % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) = (⟨n % 5, Nat.mod_lt _ (by decide)⟩ : Fin 5) + 1 := by apply Fin.ext simp [Fin.val_add, Nat.add_mod] simpa [f, hn] using hcycle ⟨n % 5, Nat.mod_lt _ (by decide)⟩