AFTD Auto-Formalizing Theoretical Domains

maxcut_strong_deviation_cast_colors

theoremverified

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.

  1. 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.

    lines 7–12

    uses Finset.mem_filter, Finset.mem_univ, true_and, ne_eq, Fin.castLE_inj

      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]
  2. 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$.

    line 13

      rcases h with ⟨hne, h_out, h_in⟩
  3. 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.

    lines 14–16

    uses congr_arg

      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⟩
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

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⟩
See it in the graphDiscuss this resultChallenge it