maxcut_unweighted_strong_deviation_cycle_exists
There is an unweighted simple graph on 46 vertices and an infinite sequence of three-color profiles that returns to its starting profile after five steps, such that every consecutive pair is a profitable deviation by exactly the players who change colors.
Statement
theorem maxcut_unweighted_strong_deviation_cycle_exists : ∃ (G : SimpleGraph (Fin 46)) (d : DecidableRel G.Adj) (f : ℕ → Fin 46 → Fin 3), f 5 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ G d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1))
- Related work
- arXiv:1810.09278, Proposition 2 gives a cycle for a weighted game; Section 7 discusses strong potential in unweighted games. Related existence question: arXiv:2610.04948, Section 4.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- maxcut_cycle46_graphA 46-vertex finite simple unweighted graph for a five-step strong-deviation cycle: four core blocks of eight, and two fixed-color anchor…
- maxcut_cycle46_coloringThe five successive three-color profiles of the 46-vertex example, with stage addition modulo five.
- maxcut_cycle46_deviationsEach successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the…
- maxcut_five_cycle_repeatsAny five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence…
- 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 simple graph G on the vertex set Fin 46, a decidability instance d for G's adjacency relation, and a sequence of 3-colorings f : ℕ → Fin 46 → Fin 3 such that: 1. f 5 = f 0 (the coloring returns to the initial coloring at step 5), and 2. for all n : ℕ, the step from f n to f (n + 1) is a strong deviation of the set of changing vertices Sₙ = {v : Fin 46 | f (n + 1) v ≠ f n v}, meaning that: - Sₙ is non-empty (at least one vertex changes its color), - every vertex not in Sₙ keeps its color (tautological by definition of Sₙ), and - for every vertex v ∈ Sₙ, the Max-Cut utility of v strictly increases from f n to f (n + 1), where the utility of v under a coloring σ is the number of neighbors w of v such that σ w ≠ σ v.
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 theorem is proved by exhibiting an explicit 46-vertex unweighted graph and lifting a verified 5-cycle of colorings to an infinite sequence. The adjacency relation on this graph is defined by explicit arithmetic on finite coordinates, which Lean verifies is decidable. The recurrence theorem `maxcut_five_cycle_repeats` is applied to this graph, the explicit 5-stage coloring schedule `maxcut_cycle46_coloring`, and the pre-verified deviations `maxcut_cycle46_deviations` to yield an infinite 5-periodic sequence of 3-colorings where every step is a max-cut strong deviation. Exhibiting this graph, its decidability instance, and the sequence concludes the proof.
The adjacency relation of the 46-vertex graph `maxcut_cycle46_graph` is decidable. automation
For arbitrary vertices $u, v \\in \\text{Fin } 46$, we introduce them and unfold the definitions of the graph and `SimpleGraph.fromRel`. The adjacency relation is an explicit boolean combination of inequalities and modular arithmetic on finite numbers, so Lean's typeclass synthesis (`infer_instance`) automatically decides whether an edge is present.
intro u v unfold maxcut_cycle46_graph SimpleGraph.fromRel infer_instance
There exists an unweighted 46-vertex graph, a decidability instance for its adjacency, and an infinite 5-periodic sequence of 3-colorings such that every consecutive step is a max-cut strong deviation.
We apply `maxcut_five_cycle_repeats` to the concrete 46-vertex graph `maxcut_cycle46_graph`, the 5-stage coloring schedule `maxcut_cycle46_coloring`, and the pre-verified deviations `maxcut_cycle46_deviations`. This produces an infinite sequence of 3-colorings $f : \\mathbb{N} \\to \\text{Fin } 46 \\to \\text{Fin } 3$ satisfying $f(5) = f(0)$ such that each transition $f(n) \\to f(n+1)$ is a strong deviation by the deviating vertices. Providing `maxcut_cycle46_graph`, the decidability instance `cycle46_decidable`, and the sequence $f$ witnesses the existential claim.
uses
maxcut_five_cycle_repeats,maxcut_cycle46_deviationsobtain ⟨f, hperiod, hsteps⟩ := maxcut_five_cycle_repeats maxcut_cycle46_graph maxcut_cycle46_coloring maxcut_cycle46_deviations exact ⟨maxcut_cycle46_graph, cycle46_decidable, f, hperiod, hsteps⟩
maxcut_five_cycle_repeats- If a finite graph with decidable adjacency admits a 5-step cycle of colorings where each transition is a max-cut strong deviation by the moving vertices, then there exists an infinite sequence of colorings returning to its start after 5 steps ($f(5) = f(0)$) such that every consecutive transition is a strong deviation.
maxcut_cycle46_deviations- For every index $i \\in \\text{Fin } 5$, transitioning from stage $i$ to stage $i + 1$ in the 5-stage coloring schedule on the 46-vertex graph is a max-cut strong deviation by the vertices that change color.
- The instance `cycle46_decidable` is a formal constructive requirement in Lean (`DecidableRel G.Adj`) needed to compute Max-Cut utilities and filter finite sets; in conventional mathematics, adjacency on a finite graph is decidable without comment.
- The non-trivial combinatorial verification that each of the five transitions in `maxcut_cycle46_coloring` strictly increases the utility of every deviating vertex was established in the auxiliary theorem `maxcut_cycle46_deviations` and is taken as an input here.
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 cycle46_decidable : DecidableRel maxcut_cycle46_graph.Adj := by intro u v unfold maxcut_cycle46_graph SimpleGraph.fromRel infer_instancetheorem maxcut_unweighted_strong_deviation_cycle_exists : ∃ (G : SimpleGraph (Fin 46)) (d : DecidableRel G.Adj) (f : ℕ → Fin 46 → Fin 3), f 5 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ G d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) := by obtain ⟨f, hperiod, hsteps⟩ := maxcut_five_cycle_repeats maxcut_cycle46_graph maxcut_cycle46_coloring maxcut_cycle46_deviations exact ⟨maxcut_cycle46_graph, cycle46_decidable, f, hperiod, hsteps⟩