Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra

Padberg (Padberg, M. W. 1973. On the facial structure of set packing polyhedra. Math. Programming5 199–215.) has shown that if a graph G with vertex set V constitutes a clique (odd cycle, odd anticycle), then the inequality Σ_x∈Vx_v ≤ 1 (Σ_x∈Vx_v ≤ ½(|V| − 1), Σ_x∈Vx_v ≤ 2) defines a facet of P(ℐ_ST(G)), the convex hull of the incidence vectors of stable sets in G. We generalize the concepts of cliques, odd cycles and anticycles to arbitrary independence systems (E, ℐ) and show that the corresponding inequalities define facets of P(ℐ), the convex hull of the incidence vectors of independent sets.