Approximate Graph Colouring and the Hollow Shadow

We show that approximate graph colouring is not solved by constantly many levels of the liftand-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest. * N = M * N = tr(M T N ) (Frobenius inner product of matrices). Let a ∈ N 0 and a ∈ N a . Given i ∈ [a], we denote by E i the i-th standard unit tensor ; i.e., the tensor in T a (Q) all of whose entries are 0, except the i-th entry that is 1. Observe that, for any T ∈ T a (Q), we may express the i-th entry of T as E i * T . We let the support of T be the set of indices of all nonzero entries of T ; i.e., the set supp(T ) = i ∈ [a] : E i * T ̸ = 0. Tensor contraction satisfies the following form of associativity. Lemma 16. Take five integers a, b, c, d, e ∈ N 0 , five tuples a ∈ N a , b ∈ N b , c ∈ N c , d ∈ N d , e ∈ N e , and three tensors T ∈ T (a,b) (Q), U ∈ T (b,c,d) (Q), V ∈ T (d,e) (Q). Then (T b * U ) d * V = T b * (U d * V ).