2022/10/15 by Lorenzo Ciardo, Ciardo, Lorenzo, Stanislav Živný +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2210.08293
openalex publication_date 2022/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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.