poc8_discb
def
Boolean disconnectedness test: S is empty, or the BFS closure inside S of some vertex of S is a proper cut of S.
Statement
def poc8_discb (S : 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_closek breadth-first-search steps inside S starting from R.
- poc8_cutbBoolean cut test: R is nonempty, R ⊆ S, S ⊄ R, and no edge leads from R to a vertex of S outside R.
- Used by 2
- poc8_gmms_okCheck 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.
- poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
Lean source view module on GitHub
/-- Boolean test: `S` is empty or the BFS closure of some vertex of `S` is a proper cut of `S`. -/ def poc8_discb (S : Fin 8 → Bool) : Bool := (List.finRange 8).all (fun v => !S v) || (List.finRange 8).any fun r => S r && poc8_cutb S (poc8_close S (fun w => w == r) 7)