Approximate graph colouring and crystals

Autor:	Ciardo, L, Živný, S
Jazyk:	angličtina
Rok vydání:	2022
Předmět:	FOS: Computer and information sciences Computer Science - Computational Complexity Discrete Mathematics (cs.DM) FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) Computational Complexity (cs.CC) Computer Science - Discrete Mathematics
Zdroj:	Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Popis:	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. Comment: Full version of a SODA 2023 paper
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba78262f25e9e89898d78814d19e629b https://ora.ox.ac.uk/objects/uuid:6d265e49-86a1-4f89-ad85-3559ba1c771c Zobrazit plný text záznamu