PreprintarXiv licencearXiv
Compactness Principles for CSPs and the Axiom of Chocie
Abstract
We can associate a compactness principle 𝒦𝒟 to the Constraint Satisfaction Problem (CSP) with constraint library 𝒟. These principles were studied by Katáy, Tóth, and Vidnyánszky and by Rorabaugh, Tardif, and Wehlau. We expand their work comparing the strength of K𝒟 for varying structures 𝒟. We characterize the structures whose compactness principles are provable from ZF; these turn out to be the width-1 structures. We compare some important compactness principles, namely those of 2SAT, 3LIN2, and K2, settling a question of Katáy, Tóth, and Vidnyánszky. And, we find an infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice.
Related
- Conservative CSPs in Logspace are in Symmetric Linear Datalog (under complexity theoretic assumptions)
- Discrete Temporal CSPs et al
- A Non-Dichotomy for CSPs of Stable ω-Categorical Structures
- Finite-on-Top-of-Temporal CSPs in Fixed-Point Logic
- An extension of Subcomplete Forcing Axiom which implies diamondsuit+
BibTeX
@misc{li2026compactness,
title = {{Compactness Principles for CSPs and the Axiom of Chocie}},
author = {Anthony Li and Ishin Shan and Matthew Snodgrass and Riley Thornton and Rui Zhou},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33873},
eprint = {2609.33873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33873},
}
RIS
TY - UNPB
TI - Compactness Principles for CSPs and the Axiom of Chocie
AU - Anthony Li
AU - Ishin Shan
AU - Matthew Snodgrass
AU - Riley Thornton
AU - Rui Zhou
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33873
UR - https://arxiv.org/abs/2609.33873
AB - We can associate a compactness principle 𝒦_𝒟 to the Constraint Satisfaction Problem (CSP) with constraint library 𝒟. These principles were studied by Katáy, Tóth, and Vidnyánszky and by Rorabaugh, Tardif, and Wehlau. We expand their work comparing the strength of K_𝒟 for varying structures 𝒟. We characterize the structures whose compactness principles are provable from ZF; these turn out to be the width-1 structures. We compare some important compactness principles, namely those of 2SAT, 3LIN2, and K_2, settling a question of Katáy, Tóth, and Vidnyánszky. And, we find an infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice.
ER -