max3cut_n_cut
def
The 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 triangle on the three primaries and edges of weight 3 from q to each primary vertex.
Statement
def max3cut_n_cut (x : Fin 3 → ZMod 3) (q : 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
- Used by 1
- max3cut_v_nThe 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…
Read back from the Lean
A definition of a function max3cut_n_cut that takes an assignment x : Fin 3 → ZMod 3 and an element q : ZMod 3, and returns the natural number given by:
(1 if x 0 ≠ x 1 else 0) +
(1 if x 1 ≠ x 2 else 0) +
(1 if x 2 ≠ x 0 else 0) +
3 * (the number of p : Fin 3 such that x p ≠ 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 cut weight in the N-gadget for colorings x and q. -/ def max3cut_n_cut (x : Fin 3 → ZMod 3) (q : ZMod 3) : ℕ := (if x 0 ≠ x 1 then 1 else 0) + (if x 1 ≠ x 2 then 1 else 0) + (if x 2 ≠ x 0 then 1 else 0) + 3 * (Finset.univ.filter fun p : Fin 3 => x p ≠ q).card