More facets from fences for linear ordering and acyclic subgraph polytopes
type: Item
instance of: scholarly article
title: More facets from fences for linear ordering and acyclic subgraph polytopes
zbMATH Open document ID: 0817.52017
DOI: 10.1016/0166-218X(92)00151-B
author: Jon Lee
author: Janny Leung
published in: Discrete Applied Mathematics
publication date: 1995-08-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 584664
zbMATH Keywords: facet
zbMATH Keywords: linear ordering polytope
zbMATH Keywords: acyclic subgraph
reviewed by: Frank Plastria
MaRDI profile type: Publication
cites work: Q5422499
cites work: Facet Generating Techniques
cites work: Induced binary probabilities and the linear ordering polytope: A status report
cites work: A necessary but insufficient condition for the stochastic binary choice problem
cites work: Optimal Weighted Ancestry Relationships
cites work: On the acyclic subgraph polytope
cites work: Facets of the linear ordering polytope
cites work: Q5824928
cites work: A spectral approach to polyhedral dimension
cites work: A spectral method for concordant polyhedral faces
cites work: Q4194705
cites work: Polyhedral structure and properties of a model for layout design
cites work: Finding a minimum feedback arc set in reducible flow graphs
full work available at URL: 0166-218x(92)00151-b
OpenAlex ID: W1976786056
description: scientific article; zbMATH DE number 584664