The biorder polytope (Q1765958): Difference between revisions

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.