Two graph isomorphism polytopes

The convex hull ψ n , n of certain ( n ! ) 2 tensors was considered recently in connection with graph isomorphism. We consider the convex hull ψ n of the n ! diagonals among these tensors. We show: 1. The polytope ψ n is a face of ψ n , n . 2. Deciding if a graph G has a subgraph isomorphic to H reduces to optimization over ψ n . 3. Optimization over ψ n reduces to optimization over ψ n , n . In particular, this implies that the subgraph isomorphism problem reduces to optimization over ψ n , n .