Symmetric Operations on Domains of Size at Most 4

To convert a fractional solution to an instance of a constraint satisfaction problem into a solution, a rounding scheme is needed, which can be described by a collection of symmetric operations with one of each arity. An intriguing possibility, raised in a recent paper by Carvalho and Krokhin, would imply that any clone of operations on a set $D$ which contains symmetric operations of arities $1, 2, \ldots, \lvert D \rvert$ contains symmetric operations of all arities in the clone. If true, then it is possible to check whether any given family of constraint satisfaction problems is solved by its linear programming relaxation. We characterize all idempotent clones containing symmetric operations of arities $1, 2, \ldots, \lvert D \rvert$ for all sets $D$ with size at most four and prove that each one contains symmetric operations of every arity, proving the conjecture above for $\lvert D \rvert \leq 4$.

No reviews yet.

No comments yet.