  The maximum stable set problem is a well-known NP-hard problem in
combinatorial optimization, which can be formulated as the maximization of a
quadratic square-free polynomial over the (Boolean) hypercube. We investigate a
hierarchy of linear programming relaxations for this problem, based on a result
of Handelman showing that a positive polynomial over a polytope with non-empty
interior can be represented as conic combination of products of the linear
constraints defining the polytope. We relate the rank of Handelman's hierarchy
with structural properties of graphs. In particular we show a relation to
fractional clique covers which we use to upper bound the Handelman rank for
perfect graphs and determine its exact value in the vertex-transitive case.
Moreover we show two upper bounds on the Handelman rank in terms of the
(fractional) stability number of the graph and compute the Handelman rank for
several classes of graphs including odd cycles and wheels and their
complements. We also point out links to several other linear and semidefinite
programming hierarchies.
