AFTD Auto-Formalizing Theoretical Domains

max3cut_v_e

def

The maximum cut value V_E(x) in the E-gadget for primary coloring x : Fin 3 → ZMod 3, defined as the supremum of max3cut_e_cut x a over all auxiliary 3-colorings a : Fin 6 → ZMod 3.

Statement

def max3cut_v_e (x : Fin 3 → ZMod 3) : ℕ
Defined in
arXiv:2611.01402 Lemma 3.1 -- Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
Verified
03 Nov 2026
Axioms
none listed
Built on 1
  • max3cut_e_cutThe cut weight in the 18-edge E-gadget for primary coloring x : Fin 3 → ZMod 3 and auxiliary coloring a : Fin 6 → ZMod 3, defined as the…
Used by 5
  • max3cut_v_e_eqFor every primary coloring x : Fin 3 → ZMod 3, the maximum cut value of the E-gadget is max3cut_v_e x = if max3cut_s x = 0 then 18 else 16.
  • max3cut_gadget_cut_valuesFor every primary coloring x : Fin 3 → ZMod 3, the maximum cut value of the E-gadget is max3cut_v_e x = if max3cut_s x = 0 then 18 else…
  • max3cut_v_e_two_equalThe maximum cut value of the E-gadget on the primary coloring ![0, 0, 1] is 16.
  • max3cut_v_e_zeroThe maximum cut value of the E-gadget on the constant zero primary coloring fun _ => 0 is 18.
  • max3cut_v_e_rainbowThe maximum cut value of the E-gadget on the rainbow primary coloring ![0, 1, 2] is 18.

Read back from the Lean

Definition of a function max3cut_v_e that takes an assignment x : Fin 3 → ZMod 3 and returns a natural number, defined as the supremum (maximum) over all functions a : Fin 6 → ZMod 3 of max3cut_e_cut x a.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The maximum cut value V_E(x) of the E-gadget. -/
def max3cut_v_e (x : Fin 3 → ZMod 3) : ℕ := Finset.univ.sup (fun a => max3cut_e_cut x a)
See it in the graphDiscuss this resultChallenge it