More facets from fences for linear ordering and acyclic subgraph polytopes
The linear ordering polytope is the convex hull of the incidence vectors of linear orders on an \(n\)-element set, as subsets of the \(n(n - 1)\)- element set of pairs. Several types of inequalities, known as (augmented) fences, were known to be facets. This paper introduces (augmented) reinforced fences and show them to be facet-generating when their fences are simple. Thereby the first examples of facets which are not rank inequalities (i.e. with coefficients 0 or 1) are obtained. The question of which diagonal inequalities are facets is completely solved. Extensions of these results are indicated for the similarly defined acyclic subgraph polytope.
scientific article; zbMATH DE number 584664
scientific article