maxcut_unweighted_minimal_deviation_cycle_exists
On the specified unweighted 71-vertex graph there is an infinite three-color strong-deviation sequence returning after 33 steps, and every step is inclusion-minimal: no proper subcoalition of its changing players has a profitable deviation from that step’s starting profile.
Statement
theorem maxcut_unweighted_minimal_deviation_cycle_exists : ∃ (d : DecidableRel maxcut_cycle71_graph.Adj) (f : ℕ → Fin 71 → Fin 3), f 33 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) ∧ ∀ S : Finset (Fin 71), S ⊂ (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) → ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) S τ
- Related work
- The explicit 71-vertex unweighted minimal-deviation cycle for the potential-function question in arXiv:1810.09278, Section 7; experiments 12443, 12444, 12450 and 12452.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_cycle71_graphThe explicit 71-vertex finite simple graph with four core blocks of eight and three anchor blocks of thirteen, with edges determined by…
- maxcut_cycle71_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
- maxcut_cycle71_return_stagesThe 33 profiles of the displayed 71-vertex cycle: the initial profile, the joint deviation, and the partial singleton restorations.
- maxcut_cycle71_minimal_cycle_stepsEvery successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable…
- 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…
Read back from the Lean
There exist a decidability instance d for adjacency in the 71-vertex graph maxcut_cycle71_graph and a sequence of 3-colorings (assignments of vertices to {0, 1, 2}) f : ℕ → Fin 71 → Fin 3 such that:
1. f 33 = f 0 (the coloring after 33 steps equals the initial coloring f 0), and
2. For every n : ℕ:
(a) The transition from f n to f (n + 1) is a strong deviation by the set of deviating vertices $D_n = \{ v : \text{Fin } 71 \mid f (n + 1)(v) \neq f n(v) \}$. That is, $D_n$ is nonempty, f (n + 1) agrees with f n outside $D_n$, and every vertex $v \in D_n$ strictly increases its Max-Cut utility from f n to f (n + 1).
(b) The deviating coalition $D_n$ is minimal: for every strict subset $S \subsetneq D_n$, there does not exist any 3-coloring $\tau : \text{Fin } 71 \to \text{Fin } 3$ such that $(f n, S, \tau)$ is a strong deviation (meaning $S$ is nonempty, $\tau$ agrees with f n outside $S$, and every vertex in $S$ strictly increases its Max-Cut utility from f n to $\tau$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The existence of an infinite minimal-deviation cycle is proved by wrapping a pre-constructed 33-step cycle of 3-colorings (maxcut_cycle71_return_stages) into an infinite sequence f(n) indexed by n % 33. Periodicity f 33 = f 0 holds definitionally because 33 % 33 = 0 % 33. Each transition f n → f (n + 1) is shown to correspond to moving from index i = n % 33 to i + 1 in Fin 33, matching the premise of the prerequisite theorem maxcut_cycle71_minimal_cycle_steps which guarantees inclusion-minimal strong deviation at every step.
Adjacency in the 71-vertex graph is decidable.
We construct d as a decision procedure for adjacency between any two vertices u, v : Fin 71. Unfolding the definitions of maxcut_cycle71_graph, the boundary function maxcut_cycle71_field, and SimpleGraph.fromRel reveals that adjacency is expressed as a finite boolean combination of inequalities and modulo arithmetic on natural numbers, which Lean's typeclass synthesis (infer_instance) decides constructively.
let d : DecidableRel maxcut_cycle71_graph.Adj := by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance
The periodic coloring sequence is defined, reducing the existential claim to periodicity and per-step minimality.
We define f(n) by evaluating the 33 pre-constructed coloring stages maxcut_cycle71_return_stages at index n % 33, whose validity as an element of Fin 33 is certified by Nat.mod_lt using 0 < 33 (checked by decide). Supplying d and f as witnesses for the existential quantifier leaves two subgoals: proving f 33 = f 0 and showing that every step f n → f (n + 1) is an inclusion-minimal strong deviation.
uses
Nat.mod_ltlet f : ℕ → Fin 71 → Fin 3 := fun n => maxcut_cycle71_return_stages ⟨n % 33, Nat.mod_lt _ (by decide)⟩ refine ⟨d, f, ?_, ?_⟩
The sequence returns to its initial state after 33 steps: f 33 = f 0.
Since 33 % 33 = 0 and 0 % 33 = 0, both f 33 and f 0 evaluate definitionally to maxcut_cycle71_return_stages 0, so the equality holds by reflexivity (rfl).
· rflIn Fin 33, the index for step n + 1 is the successor of the index for step n: ⟨(n + 1) % 33, _⟩ = ⟨n % 33, _⟩ + 1.
Fixing n, by Fin.ext it suffices to check equality of their underlying natural numbers. By Fin.val_add, the value of ⟨n % 33, _⟩ + 1 in Fin 33 is (n % 33 + 1) % 33, which equals (n + 1) % 33 by Nat.add_mod, allowing the simplifier to close the goal.
uses
Fin.ext,Fin.val_add,Nat.add_mod,Nat.mod_lt· intro n have hn : (⟨(n + 1) % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) = (⟨n % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) + 1 := by apply Fin.ext simp [Fin.val_add, Nat.add_mod]
Every transition f n → f (n + 1) is an inclusion-minimal strong deviation.
Applying the pre-proved theorem maxcut_cycle71_minimal_cycle_steps at index i = ⟨n % 33, _⟩ establishes that transitioning from stage i to stage i + 1 is an inclusion-minimal strong deviation. Rewriting with the definition of f and the equality hn (which equates stage i + 1 with f (n + 1)) completes the proof.
uses
maxcut_cycle71_minimal_cycle_steps,Nat.mod_ltsimpa [f, hn] using maxcut_cycle71_minimal_cycle_steps ⟨n % 33, Nat.mod_lt _ (by decide)⟩
Nat.mod_lt- For 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 numbers are equal.
Fin.val_add- The natural number value of a sum a + b in Fin n equals (val a + val b) % n.
Nat.add_mod- For natural numbers a, b, and n, (a + b) % n = (a % n + b % n) % n.
maxcut_cycle71_minimal_cycle_steps- For each stage index i : Fin 33, transitioning from stage i to stage i + 1 is a strong deviation by all vertices whose colors change, and no proper subcoalition of those vertices can deviate profitably.
- The combinatorial core of the result—that each of the 33 transitions on this 71-vertex graph is an inclusion-minimal strong deviation—is established in the prerequisite theorem `maxcut_cycle71_minimal_cycle_steps`; this theorem packages that finite cycle into an infinite periodic sequence on ℕ using arithmetic modulo 33.
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 maxRecDepth 200000set_option maxHeartbeats 0set_option synthInstance.maxSize 200000theorem maxcut_unweighted_minimal_deviation_cycle_exists : ∃ (d : DecidableRel maxcut_cycle71_graph.Adj) (f : ℕ → Fin 71 → Fin 3), f 33 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) ∧ ∀ S : Finset (Fin 71), S ⊂ (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) → ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) S τ := by let d : DecidableRel maxcut_cycle71_graph.Adj := by intro u v; unfold maxcut_cycle71_graph maxcut_cycle71_field SimpleGraph.fromRel; infer_instance let f : ℕ → Fin 71 → Fin 3 := fun n => maxcut_cycle71_return_stages ⟨n % 33, Nat.mod_lt _ (by decide)⟩ refine ⟨d, f, ?_, ?_⟩ · rfl · intro n have hn : (⟨(n + 1) % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) = (⟨n % 33, Nat.mod_lt _ (by decide)⟩ : Fin 33) + 1 := by apply Fin.ext simp [Fin.val_add, Nat.add_mod] simpa [f, hn] using maxcut_cycle71_minimal_cycle_steps ⟨n % 33, Nat.mod_lt _ (by decide)⟩