Hostname: page-component-8448b6f56d-m8qmq Total loading time: 0 Render date: 2024-04-18T21:54:55.224Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing symmetry groups of polyhedra

Part of: Polytopes and polyhedra Permutation groups

Published online by Cambridge University Press:  01 October 2014

David Bremner ,
Mathieu Dutour Sikirić ,
Dmitrii V. Pasechnik ,
Thomas Rehn  and
Achill Schürmann
David Bremner
Affiliation:
Faculty of Computer Science, University of New Brunswick, Box 4400, Fredericton NB, E3B 5A3 Canada email bremner@unb.ca
Mathieu Dutour Sikirić
Affiliation:
Rudjer Bosković Institute, Bijenicka 54, 10000 Zagreb, Croatia email mdsikir@irb.hr
Dmitrii V. Pasechnik
Affiliation:
Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom email dima.pasechnik@cs.ox.ac.uk
Thomas Rehn
Affiliation:
initOS GmbH & Co. KG, Hegelstraße 28, 39104 Magdeburg, Germany email thomas.rehn@research.initos.com
Achill Schürmann
Affiliation:
Institute of Mathematics, University of Rostock, 18051 Rostock, Germany email achill.schuermann@uni-rostock.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Knowing the symmetries of a polyhedron can be very useful for the analysis of its structure as well as for practical polyhedral computations. In this note, we study symmetry groups preserving the linear, projective and combinatorial structure of a polyhedron. In each case we give algorithmic methods to compute the corresponding group and discuss some practical experiences. For practical purposes the linear symmetry group is the most important, as its computation can be directly translated into a graph automorphism problem. We indicate how to compute integral subgroups of the linear symmetry group that are used, for instance, in integer linear programming.

MSC classification

Secondary: 20B25: Finite automorphism groups of algebraic, geometric, or combinatorial structures 52B15: Symmetry properties of polytopes
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Issue 1 , 2014 , pp. 565 - 581
Copyright
© The Author(s) 2014 

References

References

Blind, R. and Mani-Levitska, P., ‘Puzzles and polytope isomorphism’, Aequationes Math. 34 (1987) 287–297.Google Scholar
Bödi, R., Herr, K. and Joswig, M., ‘Algorithms for highly symmetric linear and integer programs’, Math. Program. 137 (2013) 65–90.Google Scholar
Bokowski, J., Ewald, G. and Kleinschmidt, P., ‘On combinatorial and affine automorphisms of polytopes’, Israel J. Math. 47 (1984) no. 2–3, 123–130.Google Scholar
Bremner, D., Dutour Sikirić, M. and Schürmann, A., ‘Polyhedral representation conversion up to symmetries’, CRM Proc. Lecture Notes 48 (2009) 45–72.CrossRefGoogle Scholar
Coxeter, H. S. M., Projective geometry , 2nd edn (Springer, New York, 1987).Google Scholar
Cox, D. A., Little, J. B. and Schenck, H. K., Toric varieties (American Mathematical Society, Providence, RI, 2011).CrossRefGoogle Scholar
Deza, A. and Deza, M., ‘Skeletons of some relatives of the N-cube’, Operations Research Proceedings 1994 (Springer, 1995) 81–85.CrossRefGoogle Scholar
Deza, A., Goldengorin, B. and Pasechnik, D. V., ‘The isometries of the cut, metric and hypermetric cones’, J. Algebraic Combin. 23 (2006) no. 3, 197–203.Google Scholar
Dutour Sikirić, M., Hulek, K. and Schürmann, A., ‘Smoothness and singularities of the perfect form and the second Voronoi compactification of $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}{\mathcal{A}}_g$ ’, Preprint, 2013, arXiv:1303.5846.Google Scholar
Dutour Sikirić, M., Vallentin, F. and Schürmann, A., ‘Classification of eight-dimensional perfect forms’, Electron. Res. Announc. Amer. Math. Soc. 13 (2007) 21–32.Google Scholar
Dutour Sikirić, M., Schürmann, A. and Vallentin, F., ‘Complexity and algorithms for computing Voronoi cells of lattices’, Math. Comp. 78 (2009) 1713–1731.Google Scholar
Friedman, E., ‘Finding a simple polytope from its graph in polynomial time’, Discrete Comput. Geom. 41 (2009) 249–256.Google Scholar
Gévais, G., ‘A class of cellulated spheres with non-polytopal symmetries’, Canad. Math. Bull. 52 (2009) 366–379.Google Scholar
Golynski, A., ‘A polynomial time algorithm to find the minimum cycle basis of a regular matroid’, Master’s Thesis, University of New Brunswick, 2002.Google Scholar
Isaacs, I. M., Character theory of finite groups (Dover, New York, 1994).Google Scholar
Isaacs, I. M., Finite group theory , Graduate Studies in Mathematics 92 (American Mathematical Society, Providence, RI, 2008).Google Scholar
Kaibel, V. and Schwartz, A., ‘On the complexity of polytope isomorphism problems’ Graphs Comb. 19-2 (2003) 215–230.Google Scholar
Kalai, G., ‘A simple way to tell a simple polytope from its graph’, J. Combin. Theory Ser. A 49 (1988) 381–383.Google Scholar
Köbler, J., Schöning, U. and Torán, J., Graph isomorphism problem: the structural complexity (Birkhäuser, Basel, 1993).Google Scholar
Kreuzer, M. and Skarke, H., ‘On the classification of reflexive polyhedra’, Commun. Math. Phys. 185 (1997) 495–508.Google Scholar
Kreuzer, M. and Skarke, H., ‘Classification of reflexive polyhedra in three dimensions’, Adv. Theor. Math. Phys. 2–4 (1998) 853–871.Google Scholar
Kreuzer, M. and Skarke, H., ‘PALP: a package for analysing lattice polytopes with applications to toric geometry’, Comput. Phys. Comm. 157 (2004) 87–106.CrossRefGoogle Scholar
Leon, J. S., ‘Permutation group algorithms based on partitions. I. Theory and algorithms. Computational group theory, Part 2’, J. Symbolic Comput. 12 (1991) 533–583.Google Scholar
Leon, J. S., ‘Partitions, refinements, and permutation group computation’, Groups and computation, II (New Brunswick, NJ, 1995) , DIMACS Series in Discrete Mathematics and Theoretical Computer Science 28 (American Mathematical Society, Providence, RI, 1997) 123–158.Google Scholar
Li, C.-K. and Milligan, T., ‘Linear preservers of finite reflection groups’, Linear Multilinear Algebra 41 (2003) 49–81.Google Scholar
Liberti, L., ‘Reformulations in mathematical programming: automatic symmetry detection and exploitation’, Math. Program. 131 (2012) 273–304.Google Scholar
Margot, F., ‘Symmetry in integer linear programming’, 50 years of integer programming (Springer, Berlin, 2010) 647–686.Google Scholar
Oswald, M., ‘Weighted consecutive ones problems’, PhD Thesis, Universität Heidelberg, 2001.Google Scholar
Paffenholz, A. and Ziegler, G. M., ‘The E t -construction for lattices, spheres and polytopes’, Discrete Comput. Geom. 32 (2004) no. 4, 601–621.CrossRefGoogle Scholar
Pfetsch, M. E. and Rehn, T., ‘Symmetry handling in integer programs revisited’ (in preparation).Google Scholar
Plesken, W. and Souvignier, B., ‘Computing isometries of lattices’, J. Symbolic Comput. 24 (1997) 327–334.Google Scholar
Puget, J.-F., Automatic detection of variable and value symmetries , Lecture Notes in Computer Science 3709 (Springer, Berlin, 2005).Google Scholar
Rehn, T., ‘Exploring core points for fun and profit a study of lattice-free orbit polytopes’, PhD Thesis, University of Rostock, 2014.Google Scholar
Salvagnin, D., ‘A dominance procedure for integer programming’, Master’s Thesis, University of Padova, 2005.Google Scholar
Schrijver, A., Combinatorial optimization. Polyhedra and efficiency, vol. A, B, C (Springer, Berlin, 2003).Google Scholar
Schürmann, A., Computational geometry of positive definite quadratic forms (American Mathematical Society, Providence, RI, 2009).Google Scholar
Schürmann, A., ‘Exploiting symmetries in polyhedral computations’, Discrete Geometry and Optimization , Fields Institute Communications 69 (Springer, New York, 2013) 265–278.CrossRefGoogle Scholar
Ziegler, G., Lectures on polytopes , Graduate Texts in Mathematics vol. 152 (Springer, New York, 1995).Google Scholar

Software

CPLEX, ‘Mathematical programming technology’, http://www.ilog.com/products/cplex/.Google Scholar
Darga, P. T., Katebi, H., Liffiton, M., Markov, I. and Sakallah, K., saucy, http://vlsicad.eecs.umich.edu/BK/SAUCY/.Google Scholar
Dutour Sikirić, M., polyhedral, http://drobilica.irb.hr/∼mathieu/Polyhedral/.Google Scholar
The GAP group, ‘GAP—groups, algorithms, and permutations, version 4.4.6’, 2005, http://www.gap-system.org.Google Scholar
Gurobi, ‘High-end libraries for math programming’, http://www.gurobi.com/.Google Scholar
Junttila, T. and Kaski, P., bliss, http://www.tcs.hut.fi/Software/bliss/.Google Scholar
M. Kreuzer, H. Skarke and others, ‘PALP: a package for analysing lattice polytopes’, http://hep.itp.tuwien.ac.at/∼kreuzer/CY/CYpalp.html.Google Scholar
McKay, B. D., The nauty program, http://cs.anu.edu.au/people/bdm/nauty/.Google Scholar
Piperno, A., The trace program, http://cs.anu.edu.au/people/bdm/nauty/.Google Scholar
Rehn, T., Permlib, http://www.geometrie.uni-rostock.de/software/.Google Scholar
Rehn, T. and Schürmann, A., SymPol, http://www.geometrie.uni-rostock.de/software/.Google Scholar

Web page

Paffenholz, A., http://www.mathematik.tu-darmstadt.de/∼paffenholz/data.html.Google Scholar