A Dichotomy for Finite Abstract Simplicial Complexes
Abstrak
Given two finite abstract simplicial complexes A and B, one can define a new simplicial complex on the set of simplicial maps from A to B. After adding two technicalities, we call this complex Homsc(A, B). We prove the following dichotomy: For a fixed finite abstract simplicial complex B, either Homsc(A, B) is always a disjoint union of contractible spaces or every finite CW-complex can be obtained up to a homotopy equivalence as Homsc(A, B) by choosing A in a right way. We furthermore show that the first case is equivalent to the existence of a nontrivial social choice function and that in this case, the space itself is homotopy equivalent to a discrete set. Secondly, we give a generalization to finite relational structures and show that this dichotomy coincides with a complexity theoretic dichotomy for constraint satisfaction problems, namely in the first case, the problem is in P and in the second case NP-complete. This generalizes a result from [SW24] respectively arXiv:2307.03446 [cs.CC]
Topik & Kata Kunci
Penulis (1)
Sebastian Meyer
Akses Cepat
- Tahun Terbit
- 2024
- Bahasa
- en
- Total Sitasi
- 3×
- Sumber Database
- Semantic Scholar
- DOI
- 10.48550/arXiv.2408.08199
- Akses
- Open Access ✓