论文标题
近似图形和晶体
Approximate Graph Colouring and Crystals
论文作者
论文摘要
我们表明，近似图形的着色无法通过仿射整数编程（AIP）层次结构的任何级别来解决。为了建立结果，我们将欺骗AIP层次结构的图表展示的问题转化为构建高度对称晶体张量的问题。为了证明晶体在任意维度中的存在，我们为可实现的张量系统提供了组合表征。即，可以实现为单个高维张量的投影的低维张量的集合。
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.
