maxcut_strong_deviation_cast_colors
Injectively embedding the available colors into a larger color set preserves a given strong deviation and its coalition.
Statement
theorem maxcut_strong_deviation_cast_colors {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k l : ℕ} (hkl : k ≤ l) (σ τ : V → Fin k) (S : Finset V) (h : is_maxcut_strong_deviation G σ S τ) : is_maxcut_strong_deviation G (fun v => Fin.castLE hkl (σ v)) S (fun v => Fin.castLE hkl (τ v))
- Source
- Lifting the 46-vertex unweighted deviation cycle from three colors to all k ≥ 3.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- maxcut_utilityIn the unweighted Max-k-Cut game on a finite simple graph G, a coloring σ : V → [k] gives player v the utility u_v(σ) = |{w ∈ N(v) : σ(w)…
The proof, explained
We show that embedding colors into a larger palette via `Fin.castLE` preserves strong deviations. Because this embedding is injective, two vertices receive different colors under the embedded configuration if and only if they did under the original one, leaving the cut utility of every vertex completely unchanged. Consequently, the coalition $S$ remains nonempty, vertices outside $S$ maintain identical colors, and every vertex in $S$ continues to strictly improve its utility.
The maxcut utility of any vertex under a coloring is unchanged when colors are embedded into a larger set.
By definition, the utility of a vertex $v$ under a coloring $\rho$ is the number of neighbors assigned a different color than $v$. By extensionality, the set of such neighbors for the embedded coloring coincides with that for $\rho$, because the color embedding `Fin.castLE` is injective (`Fin.castLE_inj`), meaning two neighbors receive distinct colors after embedding if and only if they did before.
uses
Finset.mem_filter,Finset.mem_univ,true_and,ne_eq,Fin.castLE_injhave hu (ρ : V → Fin k) (v : V) : maxcut_utility G (fun u => Fin.castLE hkl (ρ u)) v = maxcut_utility G ρ v := by unfold maxcut_utility congr 1 ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, ne_eq, Fin.castLE_inj]
The hypothesis that $(S, \tau)$ is a strong deviation from $\sigma$ provides a nonempty coalition $S$, unchanged colors outside $S$, and strict utility improvements on $S$.
We unpack the definition of `is_maxcut_strong_deviation` for the original colorings into its three constituent parts: the coalition $S$ is nonempty, vertices outside $S$ satisfy $\tau(v) = \sigma(v)$, and every vertex in $S$ strictly increases its utility from $\sigma$ to $\tau$.
rcases h with ⟨hne, h_out, h_in⟩
The embedded colorings and the same coalition $S$ satisfy the conditions of a strong deviation.
We verify the three conditions for the cast colorings: nonemptiness of $S$ is immediate; for any vertex outside $S$, applying the embedding to both sides of $\tau(v) = \sigma(v)$ via `congr_arg` ensures the cast colors remain equal; and for vertices in $S$, rewriting the utilities of the cast colorings using the invariance property established earlier reduces the strict inequality to the original utility increase.
uses
congr_argexact ⟨hne, fun v hv => congr_arg (Fin.castLE hkl) (h_out v hv), fun v hv => by rw [hu σ v, hu τ v] exact h_in v hv⟩
congr_arg- If $a_1 = a_2$, then $f(a_1) = f(a_2)$ for any function $f$.
Fin.castLE_inj- The embedding `Fin.castLE` of a smaller finite set into a larger one is injective: $\mathrm{castLE}(a) = \mathrm{castLE}(b)$ if and only if $a = b$.
Finset.mem_filter- An element $a$ belongs to `Finset.filter p s` if and only if $a \in s$ and $p(a)$ holds.
Finset.mem_univ- Every element of a finite type belongs to its universal finset `Finset.univ`.
ne_eq- The inequality $a \neq b$ is defined as $\neg (a = b)$.
true_and- The logical conjunction $\mathrm{True} \land p$ is equal to $p$.
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_strong_deviation_cast_colors {V : Type} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] {k l : ℕ} (hkl : k ≤ l) (σ τ : V → Fin k) (S : Finset V) (h : is_maxcut_strong_deviation G σ S τ) : is_maxcut_strong_deviation G (fun v => Fin.castLE hkl (σ v)) S (fun v => Fin.castLE hkl (τ v)) := by have hu (ρ : V → Fin k) (v : V) : maxcut_utility G (fun u => Fin.castLE hkl (ρ u)) v = maxcut_utility G ρ v := by unfold maxcut_utility congr 1 ext w simp only [Finset.mem_filter, Finset.mem_univ, true_and, ne_eq, Fin.castLE_inj] rcases h with ⟨hne, h_out, h_in⟩ exact ⟨hne, fun v hv => congr_arg (Fin.castLE hkl) (h_out v hv), fun v hv => by rw [hu σ v, hu τ v] exact h_in v hv⟩