PreprintarXiv licencearXiv
Separating Non-redundancy and Chain Length
Abstract
For a constraint satisfaction problem defined by a relation R, its non-redundancy 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 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 CL(R,n) ≥ NRD(R,n) but so far no asymptotic separation was known between these quantities. We exhibit an explicit arity $4$ relation for which CL(R,n) ≥ ω(NRD(R,n)).
Related
- Redundancy and Renewal of Servers in Opened Queuing Networks
- On the Observability and Redundancy of Intelligent Transportation Networks
- Redundancy and synergy in multivariate Gaussians via the Blackwell order
- Mesoscopic redundancy for dynamical frames generated by atomic singular model operators
- Some applications of binary numeration systems with nonzero redundancy to the theory of locally complex functions
BibTeX
@misc{brakensiek2026separating,
title = {{Separating Non-redundancy and Chain Length}},
author = {Joshua Brakensiek and Venkatesan Guruswami and Aaron Putterman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17914},
eprint = {2609.17914},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17914},
}
RIS
TY - UNPB
TI - Separating Non-redundancy and Chain Length
AU - Joshua Brakensiek
AU - Venkatesan Guruswami
AU - Aaron Putterman
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17914
UR - https://arxiv.org/abs/2609.17914
AB - For a constraint satisfaction problem defined by a relation R, its non-redundancy 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 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 CL(R,n) ≥ NRD(R,n) but so far no asymptotic separation was known between these quantities. We exhibit an explicit arity $4$ relation for which CL(R,n) ≥ ω(NRD(R,n)).
ER -