max3cut_v_n
def
The maximum cut weight V_N(x) in the N-gadget for primary coloring x : Fin 3 → ZMod 3, maximized over all 3 colorings q : ZMod 3 of the auxiliary vertex.
Statement
def max3cut_v_n (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_n_cutThe cut weight in the N-gadget with primary coloring x : Fin 3 → ZMod 3 and auxiliary coloring q : ZMod 3, consisting of a unit-weight…
- Used by 4
- max3cut_v_n_eqFor every primary coloring x : Fin 3 → ZMod 3, the maximum cut weight of the N-gadget is V_N(x) = 11 if s(x) ≠ 0 and 9 otherwise.
- 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.
Read back from the Lean
A definition of a function max3cut_v_n that takes x : Fin 3 → ZMod 3 and returns the supremum (maximum in ℕ) over all q : ZMod 3 of max3cut_n_cut x q.
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 weight V_N(x) of the N-gadget. -/ def max3cut_v_n (x : Fin 3 → ZMod 3) : ℕ := Finset.univ.sup (fun q => max3cut_n_cut x q)