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