Signotopes Induce Unique Sink Orientations on Grids
This work extends combinatorial geometry results for polytopes, likely incremental for researchers in discrete mathematics and optimization.
The paper generalizes known characterizations of unique sink orientations (USOs) induced by linear functions from products of two simplices to products of r simplices, linking them to USOs on r-dimensional grids and (r+1)-signotopes.
A unique sink orientation (USO) is an orientation of the edges of a polytope in which every face contains a unique sink. For a product of simplices $Î_{m-1} \times Î_{n-1}$, Felsner, Gärtner and Tschirschnitz (2005) characterize USOs which are induced by linear functions as the USOs on a $(m \times n)$-grid that correspond to a two-colored arrangement of lines. We generalize some of their results to products $Î^1 \times\cdots\times Î^r$ of $r$ simplices, USOs on $r$-dimensional grids and $(r+1)$-signotopes.