Knots on the cube

Free pairs on the cube. The cube of lesson 1.1 turns the knot test on three variables into a picture. Mark the states a relation excludes. A pair of variables, say A and B, is constrained exactly when some combination of their values never occurs, and that happens exactly when both completions of the combination are excluded: the state with c = 0 and the state with c = 1. Those two states differ only in c, so they are neighbours. The same holds for every pair, so:

Every pair is free exactly when no two excluded states are neighbours.

Which relations are knots. On three variables, forgetting one variable leaves a pair. So a relation on three variables is a knot exactly when it excludes at least one state (K1) and no two of its excluded states are neighbours (K2).

• The atom excludes the single corner 110, so it is a knot.
• Parity A ⊕ B ⊕ c = 0 excludes the four corners with an odd number of 1s: 001, 010, 100 and 111. Changing one bit changes the number of 1s by one, so no two of these corners are neighbours, and parity is a knot. No knot on three variables excludes more corners than parity does.
• Not-all-equal excludes 000 and 111, which are opposite, so it is a knot.
• The common hub excludes 010, 100 and 110, and 110 is a neighbour of both of the others, so it is not a knot.

Independent sets. A set of corners with no two of them neighbours is called an independent set of the cube. The knots on three variables are therefore the nonempty independent sets of excluded states. Two excluded corners of a knot never differ in just one variable: they differ in two, which is called Hamming distance two (as 110 and 000 do), or they are opposite. The next lesson counts these knots: there are 34, in five shapes.