AFTD Auto-Formalizing Theoretical Domains

maxcut_fair9_graph

def

The explicit nine-vertex simple graph used to obstruct fair Nash selection.

Statement

def maxcut_fair9_graph : SimpleGraph (Fin 9)
Source
Related work: arXiv:2610.04948, Section 4, asks whether all unweighted Max-k-Cut games have a strong equilibrium; this finite obstruction to selecting a fair Nash equilibrium was discovered in experiment 12959 and independently checked in 12961, 12964 and 12973.
Verified
02 Nov 2026
Axioms
none listed
Used by 8

Lean source view module on GitHub

def maxcut_fair9_graph : SimpleGraph (Fin 9) :=
  SimpleGraph.fromRel (fun (u v : Fin 9) => (u.val, v.val) ∈
    [(0,1),(0,2),(0,3),(0,5),(0,7),(1,3),(1,6),(1,7),(1,8),
     (2,3),(2,6),(2,7),(2,8),(3,4),(3,5),(3,6),(3,8),
     (4,5),(4,7),(4,8),(5,6),(5,7),(5,8),(6,7),(7,8)])
See it in the graphDiscuss this resultChallenge it