4
[2210.08293] Approximate Graph Colouring and Crystals
source link: https://arxiv.org/abs/2210.08293
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 15 Oct 2022]
Approximate Graph Colouring and Crystals
We show that approximate graph colouring is not solved by any level of the affine integer programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiting a graph fooling a level of the AIP hierarchy into the problem of constructing a highly symmetric crystal tensor. In order to prove the existence of crystals in arbitrary dimension, we provide a combinatorial characterisation for realisable systems of tensors; i.e., sets of low-dimensional tensors that can be realised as the projections of a single high-dimensional tensor.
| Comments: | Full version of a SODA 2023 paper |
| Subjects: | Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO) |
| Cite as: | arXiv:2210.08293 [cs.CC] |
| (or arXiv:2210.08293v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2210.08293 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK