An (n-2)-dimensional Quadratic Surface Determining All Cliques and a Least Square Formulation for the Maximum Clique Problem

Arranging an n-vertex graph as the standard simplex in R^n, we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines … Read more