AFTD Auto-Formalizing Theoretical Domains

poc8_gmms_ok

def

Check for a bipartition (P, not P): 8 times the smaller part value is below 105 = 7·15, or one of the two parts is disconnected.

Statement

def poc8_gmms_ok (P : Fin 8 → Bool) : Bool
Source
step towards poc_linkedness_conjecture_counterexample (counterexample to arXiv:1908.05433, Conjecture 3.10; kernel-checked certificate)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • poc8_valThe total u-value of the vertex set selected by P, computed by a fold.
  • poc8_discbBoolean disconnectedness test: S is empty, or the BFS closure inside S of some vertex of S is a proper cut of S.
Used by 3
  • poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
  • poc8_gmms_check_allKernel check of the bipartition condition for all 256 Boolean membership vectors of the eight vertices.
  • poc8_gmms_checkEvery bipartition (P, not P) of the eight vertices passes the bipartition check.

Lean source view module on GitHub

/-- `8·min(u(P), u(¬P)) < 105`, or one side of the bipartition is disconnected. -/
def poc8_gmms_ok (P : Fin 8 → Bool) : Bool :=
  decide (8 * min (poc8_val P) (poc8_val fun v => !P v) < 105) || poc8_discb P ||
    poc8_discb fun v => !P v
See it in the graphDiscuss this resultChallenge it