max3cut_v_e_rainbow
The maximum cut value of the E-gadget on the rainbow primary coloring ![0, 1, 2] is 18.
Statement
theorem max3cut_v_e_rainbow : max3cut_v_e ![0, 1, 2] = 18- Source
- arXiv:2611.01402 Lemma 3.1 -- Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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…
- Used by 1
- 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.
Read back from the Lean
The value of max3cut_v_e evaluated at the function ![0, 1, 2] : Fin 3 → ZMod 3 (which maps 0 ↦ 0, 1 ↦ 1, 2 ↦ 2) is equal to 18. That is, the supremum (maximum) over all colorings a : Fin 6 → ZMod 3 of the cut size max3cut_e_cut ![0, 1, 2] a equals 18.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem states that the maximum cut value of the E-gadget on the rainbow primary coloring (0, 1, 2) is 18. Because there are only 3⁶ = 729 possible colorings for the 6 auxiliary vertices, the maximum can be found by exhaustive finite evaluation. Lean establishes this directly by definitional reduction via reflexivity (`rfl`), with the maximum recursion depth increased to allow the computation to complete.
max3cut_v_e ![0, 1, 2] = 18
The quantity `max3cut_v_e ![0, 1, 2]` is defined as the maximum over all 3⁶ = 729 colorings of the 6 auxiliary vertices of gadget E. This is a finite, computable search. Increasing the recursion depth allows Lean's kernel to evaluate this finite supremum by definitional equality, establishing that the maximum cut value is 18 via reflexivity (`rfl`).
set_option maxRecDepth 50000 in rfl
- The proof evaluates the maximum cut by exhaustive computation across all 3⁶ = 729 colorings of the 6 auxiliary vertices. This definitional reduction is carried out by reflexivity (`rfl`), requiring the maximum recursion depth to be increased.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- V_E on the rainbow primary coloring (0,1,2) is 18. -/theorem max3cut_v_e_rainbow : max3cut_v_e ![0, 1, 2] = 18 := by set_option maxRecDepth 50000 in rfl