A Dichotomy for Finite Abstract Simplicial Complexes
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910566740656128 |
|---|---|
| author | Meyer, Sebastian |
| author_facet | Meyer, Sebastian |
| contents | 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] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08199 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Dichotomy for Finite Abstract Simplicial Complexes Meyer, Sebastian General Topology Computational Complexity 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] |
| title | A Dichotomy for Finite Abstract Simplicial Complexes |
| topic | General Topology Computational Complexity |
| url | https://arxiv.org/abs/2408.08199 |