Knots from competing pairs

Conjunction and competition. Two-place rules can be combined in two ways. Under conjunction every rule must hold, and, as lesson 3.2 shows, pairs then never make a knot. Under competition the rules are preferences, and the allowed states are those that break the fewest. A state's energy counts the preferences it breaks, possibly with weights, so under competition the allowed states are those of least energy.

The intuition. Ask three distinctions to differ pairwise. Around the triangle the differences cannot all hold, so the preferences are frustrated. The states that break exactly one preference are the six not-all-equal states, and those form a knot. Competition can make a knot from pairs, but only this kind.

• Exactly four knots come from competing pairs on three variables. A knot on three variables is the set of least states of an energy with only one- and two-variable terms exactly when its excluded states are an opposite pair. These are the four not-all-equal relations, the frustrated triangles.
• None on four or more variables.
• With hidden variables, competing pairs make every knot. Ten 2-clauses and one hidden variable have the clause x ∨ y ∨ z as their best states. Classical: this is the gadget behind the NP-hardness of MAX-2-SAT (Garey, Johnson and Stockmeyer 1976).

Proved (Lean): CompetitionKernel.lean (three_variable_classification, no_knot_beyond_three, every_relation_by_gadgets, and 16 more). The three-variable case is an instance of a known criterion for least sets of pairwise energies (faces of the correlation polytope; Rauh, Kahle and Ay 2011). We have not found the four-variable statement in print.

MAX-2-SAT, in the third point, asks for a state that satisfies as many two-literal clauses as possible.

Why only four (proved here). Every function of Boolean variables is a unique polynomial with one coefficient per set of variables. A pairwise energy has no coefficient on three variables. On three variables that top coefficient is the energy summed over the states with an odd number of ones, minus the sum over the rest. Shift the energy so its least value is zero. Then only the excluded states count, each positively, so if they all had the same parity the top coefficient would not vanish. A knot's excluded states are never neighbours, and two of opposite parity must be opposite. So the excluded states are one opposite pair.

For two variables, for example, every function is p + q·A + r·B + s·A·B for exactly one choice of the numbers p, q, r and s, and s is its coefficient on the pair.

Reading. What a knot certifies depends on what is hidden. With every variable visible, a knot other than the frustrated triangles cannot come from pairwise terms, even competing ones. With hidden variables, a knot certifies only that the rules are not pairwise rules that must all hold.