Canonical equation sets for classes of concordant polytopes (Q811401)

Canonical maximal sets of linearly independent equations are determined that are satisfied by every point of a given finite subset X of \({\mathbb{R}}^ E\), in particular by every point of a polytope \({\mathcal P}\). The basic idea is to obtain such a set from the eigenvectors of an associated matrix B. The results apply to polytopes that are the convex hull of: spanning trees, Hamiltonian tours, perfect matchings, c-factors, balanced cuts and stars. Consideration of directed graphs leads to similar results for directed Hamiltonian tours, directed balanced cuts and tournaments. The results obtained also apply when certain subconfigurations are excluded, i.e. for the (p-cycle)-free c-factor polytope and the polytope of (directed triangle)-free tournaments. The present paper extends the author's previous work published in Math. Program., Ser. A 47, No.3, 441-459 (1990; Zbl 0713.90064) and Math. Oper. Res. 15, No.1, 139-154 (1990; Zbl 0717.52002).