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 o...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2023
|
| _version_ | 1826310909119692800 |
|---|---|
| author | Ciardo, L Živný, S |
| author_facet | Ciardo, L Živný, S |
| author_sort | Ciardo, L |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T08:00:28Z |
| format | Conference item |
| id | oxford-uuid:6d265e49-86a1-4f89-ad85-3559ba1c771c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:00:28Z |
| publishDate | 2023 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:6d265e49-86a1-4f89-ad85-3559ba1c771c2023-09-26T11:56:20ZApproximate graph colouring and crystalsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:6d265e49-86a1-4f89-ad85-3559ba1c771cEnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2023Ciardo, LŽivný, SWe 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. |
| spellingShingle | Ciardo, L Živný, S Approximate graph colouring and crystals |
| title | Approximate graph colouring and crystals |
| title_full | Approximate graph colouring and crystals |
| title_fullStr | Approximate graph colouring and crystals |
| title_full_unstemmed | Approximate graph colouring and crystals |
| title_short | Approximate graph colouring and crystals |
| title_sort | approximate graph colouring and crystals |
| work_keys_str_mv | AT ciardol approximategraphcolouringandcrystals AT zivnys approximategraphcolouringandcrystals |