52B15 Symmetry properties of polytopes
Refine
Document Type
- ZIB-Report (2)
Language
- English (2)
Has Fulltext
- yes (2) (remove)
Is part of the Bibliography
- no (2)
Keywords
- Hirsch conjecture (1)
- Z-acyclic complexes (1)
- dual wedge (1)
- facet classification (1)
- non-PL spheres (1)
- polyhedral structure (1)
- shellability (1)
- suspension (1)
- symmetry (1)
- wreath product (1)
Institute
Usually complete linear descriptions of polytopes consist of
an enormous number of facet-defining inequalities already
for very small problem sizes. In this paper, we describe a method
for dividing the inequalities into equivalence classes without resorting to a normal form. Within each
class, facets are related by certain symmetries and it is sufficient
to list one representative of each class to give a complete
picture of the structural properties of a polytope. We propose an algorithm
for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.
It is known that the suspension of a simplicial complex can be realized with only one additional point. Suitable iterations of this construction generate highly symmetric simplicial complexes with a various interesting combinatorial and topological properties. In particular, infinitely many non-PL spheres as well as contactible simplicial complexes with a vertex-transitive group of automorphisms cab be contained in this way.