The worlds of not-all-equal knots

Hypergraphs and colourings. A hypergraph has points and edges, where an edge may contain any number of points. In a 3-uniform hypergraph every edge has three points, and in a 3-regular one every point lies in three edges. A proper 2-colouring colours each point black or white so that no edge has all three points the same colour, which is the not-all-equal rule on every edge. The incidence graph has a vertex for each point and one for each edge, and joins each point to the edges that contain it. The note also signs some incidences: at a signed incidence, the edge sees the point's colour reversed. A twist, roughly, is where the signs differ from a Pfaffian signing, and the note defines when twists branch.

What the note proves. A 3-regular 3-uniform hypergraph is a network of not-all-equal knots in which every distinction sits in exactly three knots. Its proper 2-colourings are the network's worlds. Networks with no world at all are where these knots close up on themselves, and the program calls them three-fold spaces. Counting is #P-hard in general (Fan and Cai) and easy when the incidence graph is planar (Valiant). The note studies the class in between, Pfaffian incidence graphs, which contains every network with no world. Proved (note):

• remove any one knot from a connected network with no world, and the worlds of what is left can be counted in polynomial time;
• counting stays polynomial under twists that do not branch;
• counting becomes #P-hard once twists branch. It stays #P-hard without any signs, and even when the incidence graph is a Pfaffian brace.

See notes/pfaffian-hypergraph-colourings.