More facets from fences for linear ordering and acyclic subgraph polytopes

The authors present new facets for the linear ordering polytope. These new facets generalize facets induced by subgrains called fences, introduced by Grötschel et al. and augmented fences, introduced by McLennan. One novelty of the facets introduced here is that each subgraph induces not one but a family of facets, which are not generally rank inequalities. Indeed, the authors provide the smallest known example of a facet-representing inequality for the linear ordering polytope that is not a rank inequality. Gilboa introduced the diagonal inequalities for the linear ordering polytope, and Fishburn posed the question of identifying precisely which diagonal inequalities represent facets. The authors completely resolve Fishburn’s question. Some of the present results can be transported to the acyclic subgraph polytope. These new facets for the acyclic subgraph polytope are the first ones that are not represented by rank inequalities.