Separating Non-redundancy and Chain Length

Abstract

For a constraint satisfaction problem defined by a relation $R$, its non-redundancy $\text{NRD}(R,n)$ is the size of largest instance (as a function of the number $n$ of variables) for which no constraint is implied by the rest. Its chain length $\text{CL}(R,n)$ is the largest such instance where the constraints can be ordered so that no constraint is implied by the preceding ones. Clearly $\text{CL}(R,n)\ge \text{NRD}(R,n)$ but so far no asymptotic separation was known between these quantities. We exhibit an explicit arity $4$ relation for which $\text{CL}(R,n)\ge \omega (\text{NRD}(R,n))$.

16 pages