Go backward to 18 AOF-Orientation
Go up to 3 Combinatorial Structure
|
Go backward to 18 AOF-Orientation Go up to 3 Combinatorial Structure |
XHTML 1.0 |
| Input: | The (abstract) graph GP of a simple polytope P |
|---|---|
| Output: | A US-orientation of GP |
| Status (general): | Open |
|---|---|
| Status (fixed dim.): | Open |
|
Since AOF-orientations are US-orientations, it follows from the
remarks on Problem 18 that (simple) polytopes admit
US-orientations and that the problem can be solved in polynomial
time up to dimension three. By slight adaptions of the arguments
given in [32], one can prove that a polynomial time
algorithm for this problem would yield a polynomial time algorithm
for Problem 17 as well.
In contrast to Problem 18, no good characterization of US-orientations is known. It is not hard to see that, by duality of polytopes, the problem is equivalent to the problem of finding from the upper two layers a partition of the face lattice of a simplicial polytope into intervals whose upper bounds are the facets (i.e., a partition in the sense of Stanley [60]). Similar to the situation with shelling orders, it is even unknown whether such a partition can be found in polynomial time if the polytope is specified by its entire face lattice. Again, with the entire face lattice as input it can be checked in polynomial time whether a family of subsets of the face lattice is a partition in that sense. |
| Related problems: | 17, 18, 36 |
|---|
|
|
Why are some symbols not displayed correctly? |