The biorder polytope
type: Item
instance of: scholarly article
title: The biorder polytope
zbMATH Open document ID: 1072.52009
author: Julie Christophe
author: Jean-Paul Doignon
author: Samuel Fiorini
published in: Order
publication date: 2005-02-25T00:00:00Z
review text: This article considers biorders, and polytopes constructed from the class of biorders. Given two sets \(X\) and \(Y\), a biorder from \(X\) to \(Y\) is a relation \(B\) such that if \(xBy\) and \(x'By'\) then either \(xBy'\) or \(x'By\). (Note therefore that if \(X=Y\), then irreflexibility implies transitivity.) Fixing \(X\) and \(Y\), a biorder from \(X\) to \(Y\) is a subset of \(X\times Y\), and therefore can be identified with a point in \({\mathbb R}^{| X\times Y|}\). The coordinate of this point corresponding to \((x,y)\in X\times Y\) is \(1\) or \(0\) depending on whether or not \(x\) is related to \(y\) under the biorder. The convex hull of all the biorders for a given \(X\) and \(Y\) is a polytope, called the biorder polytope. The article explains that the problem of finding all facets of the biorder polytope for general \(X\) and \(Y\) is an extremely hard problem. Nonetheless, the article solves this problem for the case \(| X| \leq 2\) or \(| Y| \leq 2\), and for other cases, many (though not all) nontrivial facets are found. The article also gives the combinatorial automorphism groups of the biorder polytopes for any values of \(| X| \) and \(| Y| \), and applies the same techniques that work for the biorder polytope to obtain previously unknown facets of the linear ordering polytope.
Mathematics Subject Classification ID: 52B12
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 2138854
zbMATH Keywords: biorder
zbMATH Keywords: polytope
zbMATH Keywords: polyhedral combinatorics
zbMATH Keywords: stability-critical graph
zbMATH Keywords: Ferrer's relations
zbMATH Keywords: Guttmann scale
zbMATH Keywords: linear ordering polytope
reviewed by: Michael I. Hartley
describes a project that uses: PORTA
describes a project that uses: LOLIB
MaRDI profile type: Publication
full work available at URL: s11083-004-5129-7
OpenAlex ID: W2066333776
cites work: New Facets of the Linear Ordering Polytope
cites work: Set packing relaxations of some integer programs
cites work: Q3023981
cites work: Q4947393
cites work: On realizable biorders and the biorder dimension of a relation
cites work: An approval-voting polytope for linear orders
cites work: Determining the automorphism group of the linear ordering polytope
cites work: Induced binary probabilities and the linear ordering polytope: A status report
cites work: Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
cites work: More facets from fences for linear ordering and acyclic subgraph polytopes
cites work: Critical facets of the stable set polytope
cites work: Q3207008
cites work: Q3680289
cites work: Q5804173
cites work: Geometric and combinatorial properties of the polytope of binary choice probabilities
cites work: Q4004146
cites work: Shelling polyhedral 3-balls and 4-polytopes
DOI: 10.1007/S11083-004-5129-7
Recommended article: The bipermutahedron
Recommended article: Bipermutahedron and biassociahedron
Recommended article: Bi-cyclic 4-polytopes
Recommended article: The Brascamp–Lieb Polyhedron
Recommended article: Polytopes
Recommended article: Q4702353
Recommended article: Q4328205
Recommended article: Q3715773
Recommended article: Poisson polytopes
description: scientific article; zbMATH DE number 2138854