Turning factor-critical graphs into faces of the linear ordering polytope.

Samuel Fiorini
University of Brusselles, Belgium


The linear ordering polytope is a convex polytope having one vertex per linear order on some finite ground set. It is also known as the binary choice polytope. The central question regarding this polytope is to determine its facets. Since the first appearance of the polytope in the 1960s, the latter question has received a lot of attention. But progress has been slow. In 1995, Koppen discovered new facets related to stability-critical graphs. In this talk we will show how to construct facets from factor-critical graphs. Most of these facets were not known before.