maxcut_pinned_twins_graph
def
A candidate counterexample graph on 182 vertices. Replace each vertex of the paper graph G_3 by two independent twins, replace each old edge by a complete bipartite graph, and join each core twin to the selected padding anchor (j,24,0) for each j different from that core vertex’s initial color.
Statement
def maxcut_pinned_twins_graph : SimpleGraph ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2)- Source
- New construction investigated for OP-89, arXiv:2610.04948 Sec. 4 Question 2. Pin anchors are the zeroth twins of the last anchor vertices. Those core-anchor pairs were nonedges in G_3. Sanity check maxcut_pinned_twins_displayed_deviation proves the concrete profitable deviation and initial welfare. All-optimum rigidity is a separate unproved obligation.
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 2
- maxcut_anchor_three_graphThe 91-vertex graph G_3 of arXiv:2610.04948: a 16-vertex core A,B,C,D and three anchor classes of 25 vertices. Indices and colors are…
- maxcut_anchor_three_initial_coloringThe initial coloring sigma of the paper graph G_3: A and D have color 0, B color 1, C color 2, and anchor class j has color j.
- Used by 6
- maxcut_pinned_twins_refutes_of_rigidityIf every optimum of the explicit pinned-twin graph is its displayed initial coloring up to a global color permutation, then this graph has…
- maxcut_op89_optimal_strong_equilibrium_negationIt is not true that for every finite type V, simple graph G on V with decidable adjacency, and k ≥ 3, the unweighted Max-k-Cut game on G…
- maxcut_pinned_twins_displayed_deviationThe pinned-twin graph has an initial coloring of welfare 16376 and a strong deviation consisting of all 32 core twins to the doubled…
- maxcut_op89_residual_exists_negationThe residual case maxcut_op89_residual_exists of OP-89 is false: it is not true that every finite simple graph G with k ≥ 3, at least 2k+2…
- maxcut_pinned_twins_not_colorable_threeThe 182-vertex pinned twins graph maxcut_pinned_twins_graph is not 3-colorable.
- maxcut_pinned_twins_optimum_rigidityEvery welfare-maximizing 3-coloring ρ of the 182-vertex pinned twins graph maxcut_pinned_twins_graph is, up to one global permutation p of…
Lean source view module on GitHub
private instance base_graph_decidable : DecidableRel maxcut_anchor_three_graph.Adj := by unfold maxcut_anchor_three_graph infer_instance namespace MaxcutPinnedTwins private def pin_rel (u v : (Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) : Prop := match u.1, v.1 with | .inl i, .inr (j, a) => a.val = 24 ∧ v.2.val = 0 ∧ j ≠ maxcut_anchor_three_initial_coloring (.inl i) | _, _ => False private def rel (u v : (Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) : Prop := maxcut_anchor_three_graph.Adj u.1 v.1 ∨ pin_rel u v private instance rel_decidable : DecidableRel rel := by intro u v unfold rel haveI : Decidable (pin_rel u v) := by rcases u with ⟨u, a⟩ rcases v with ⟨v, b⟩ cases u <;> cases v <;> dsimp [pin_rel] <;> infer_instance infer_instance end MaxcutPinnedTwins def maxcut_pinned_twins_graph : SimpleGraph ((Fin 16 ⊕ (Fin 3 × Fin 25)) × Fin 2) :=SimpleGraph.fromRel MaxcutPinnedTwins.rel