max3cut_e_cut
The 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 sum of the number of pairs (p, v) in the list [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 4), (2, 5)] with x p ≠ a v, and the number of pairs (u, v) in the list [(0, 5), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4)] with a u ≠ a v.
Statement
def max3cut_e_cut (x : Fin 3 → ZMod 3) (a : Fin 6 → 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_eThe 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…
Read back from the Lean
max3cut_e_cut is a function that takes two assignments x : Fin 3 → ZMod 3 and a : Fin 6 → ZMod 3 and returns a natural number equal to the sum of:
1. The number of pairs (p, v) in the 12-element list [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 4), (2, 5)] (of type List (Fin 3 × Fin 6)) such that x p ≠ a v.
2. The number of pairs (u, v) in the 6-element list [(0, 5), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4)] (of type List (Fin 6 × Fin 6)) such that a u ≠ a v.
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 18-edge E-gadget for colorings x and a. -/ def max3cut_e_cut (x : Fin 3 → ZMod 3) (a : Fin 6 → ZMod 3) : ℕ := (([(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 4), (2, 5)] : List (Fin 3 × Fin 6)).filter fun (p, v) => x p ≠ a v).length + (([(0, 5), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4)] : List (Fin 6 × Fin 6)).filter fun (u, v) => a u ≠ a v).length