Two graph isomorphism polytopes

AbstractThe 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