{"id":"arxiv/2609.17914","url":"https://arxiv.org/abs/2609.17914","tags":["cs.CC","math.CO"],"score":0,"title":"Separating Non-redundancy and Chain Length","domain":"cs.CC","source":"arxiv","authors":["Joshua Brakensiek","Venkatesan Guruswami","Aaron Putterman"],"reviews":0,"subject":"cs.CC","summary":"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 ω(\\text{NRD}(R,n))$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}