  We explore some connections between association schemes and the analyses of
the semidefinite programming (SDP) based convex relaxations of combinatorial
optimization problems in the Lov\'{a}sz--Schrijver lift-and-project hierarchy.
Our analysis of the relaxations of the stable set polytope leads to bounds on
the clique and stability numbers of some regular graphs reminiscent of
classical bounds by Delsarte and Hoffman, as well as the notion of deeply
vertex-transitive graphs -- highly symmetric graphs that we show arise
naturally from some association schemes. We also study relaxations of the
hypergraph matching problem, and determine exactly or provide bounds on the
lift-and-project ranks of these relaxations. Our proofs for these results also
inspire the study of the general hypermatching pseudo-scheme, which is an
association scheme except it is generally non-commutative. We then illustrate
the usefulness of obtaining commutative subschemes from non-commutative
pseudo-schemes via contraction in this context.
