A combinatorial study of partial order polytopes
type: Item
instance of: scholarly article
title: A combinatorial study of partial order polytopes
zbMATH Open document ID: 1020.52010
DOI: 10.1016/S0195-6698(03)00009-X
author: Samuel Fiorini
published in: European Journal of Combinatorics
publication date: 2003-04-02T00:00:00Z
review text: The convex hull of the characteristic vectors of all partial orders on a finite set \(A\) of cardinality \(\geq 2\) is called partial order polytope of \(A\). The author studies the facial structure of partial order polytopes, and his main results are the following: Deciding whether or not two distinct vertices of a partial order polytope are non-adjacent is an NP-complete problem. And a convex polytope \(P\) is affinely equivalent to a face of some partial order polytope iff \(P\) is affinely equivalent to a face of some 3-SAT polytope.
reviewed by: Horst Martini
Mathematics Subject Classification ID: 52B55
zbMATH DE Number: 1891294
zbMATH Keywords: linear ordering polytope
zbMATH Keywords: partial order polytope
zbMATH Keywords: facial structure of partial order polytopes
zbMATH Keywords: 3-SAT polytope
MaRDI profile type: Publication
cites work: Q3859808
cites work: All 0-1 polytopes are traveling salesman polytopes
cites work: New Facets of the Linear Ordering Polytope
cites work: Set packing relaxations of some integer programs
cites work: Facets of the weak order polytope derived from the induced partition projection
cites work: Determining the automorphism group of the linear ordering polytope
cites work: Facets of linear signed order polytopes.
cites work: Induced binary probabilities and the linear ordering polytope: A status report
cites work: Q4198056
cites work: A Cutting Plane Algorithm for the Linear Ordering Problem
cites work: Facets of the linear ordering polytope
cites work: Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
cites work: Q5187226
cites work: Modular decomposition and transitive orientation
cites work: Q4859913
cites work: On the partial order polytope of a digraph
cites work: Transitive packing
cites work: Hamiltonicity and combinatorial polyhedra
cites work: A note on small linear-ordering polytopes
cites work: Q3858272
full work available at URL: s0195-6698(03)00009-x
OpenAlex ID: W2077831283
description: scientific article; zbMATH DE number 1891294