365体育网站

Advertisement

Springer Nature is making SARS-CoV-2 and COVID-19 research free. View research | View latest news | Sign up for updates

On Lattice-Free Orbit Polytopes

Abstract

Given a permutation group acting on coordinates of \({{\mathbb {R}}}^n\), we consider lattice-free polytopes that are the convex hull of an orbit of one integral vector. The vertices of such polytopes are called core points and they play a key role in a recent approach to exploit symmetry in integer convex optimization problems. Here, naturally the question arises, for which groups the number of core points is finite up to translations by vectors fixed by the group. In this paper we consider transitive permutation groups and prove this type of finiteness for the \(2\)-homogeneous ones. We provide tools for practical computations of core points and obtain a complete list of representatives for all \(2\)-homogeneous groups up to degree twelve. For transitive groups that are not \(2\)365体育网站-homogeneous we conjecture that there exist infinitely many core points up to translations by the all-ones-vector. We prove our conjecture for two large classes of groups: For imprimitive groups and groups that have an irrational invariant subspace.

This is a preview of subscription content, log in365体育网站 to check access.

Fig. 1
Fig. 2
Fig. 3

References

  1. 1.

    Bárány, I., Kantor, J.-M.: On the number of lattice free polytopes. Eur. J. Combin. 21365体育网站(1), 103–110 (2000)

  2. 2.

    365体育网站Barvinok, A.: A Course in Convexity. Graduate Studies in Mathematics, vol. 54. American Mathematical Society (AMS), Providence, RI (2002)

  3. 3.

    365体育网站Barvinok, A., Blekherman, G.: Convex geometry of orbits. In: Combinatorial and Computational Geometry. Mathematical Sciences Research Institute Publications, vol. 52, pp. 51–77. Cambridge University Press, Cambridge (2005)

  4. 4.

    Bödi, R., Herr, K., Joswig, M.: Algorithms for highly symmetric linear and integer programs. Math. Program. Ser. A 137, 65–90 (2013). doi:

  5. 5.

    365体育网站Bruns, W., Ichim, B., Söger, C.: Normaliz, . Accessed 1 Sept 2014

  6. 6.

    Bruns, W., Ichim, B., Söger, C.: The power of pyramid decomposition in normaliz (2012).

  7. 7.

    Cameron, P.J.: Bounding the rank of certain permutation groups. Math. Z. 124, 343–352 (1972)

  8. 8.

    Deza, M., Onn, S.: Lattice-free polytopes and their diameter. Discrete Comput. Geom. 13(1), 59–75 (1995)

  9. 9.

    Dixon, J.D.: Permutation representations and rational irreducibility. Bull. Aust. Math. Soc. 71365体育网站(3), 493–503 (2005)

  10. 10.

    GAP—Groups, Algorithms, Programming—A System for Computational Discrete Algebra.

  11. 11.

    365体育网站Gawrilow, M., Joswig, M., et al.: Polymake, . Accessed 1 Sept 2014

  12. 12.

    Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes. In: Polytopes–Combinatorics and Computation (Oberwolfach, 1997), DMV Sem, vol. 29, pp. 43–73. Birkhäuser, Basel (2000)

  13. 13.

    Haase, C., Ziegler, G.M.: On the maximal width of empty lattice simplices. Eur. J. Combin. 21365体育网站(1), 111–119 (2000)

  14. 14.

    365体育网站Herr, K.: Core Sets and Symmetric Convex Optimization. PhD thesis, TU Darmstadt (2013)

  15. 15.

    Herr, K., Rehn, T., Schürmann, A.: Exploiting symmetry in integer convex optimization using core points. Oper. Res. Lett. 41, 298–304 (2013)

  16. 16.

    Hurkens, C.A.J.: Blowing up convex sets in the plane. Linear Algebra Appl. 134, 121–128 (1990)

  17. 17.

    365体育网站John, F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pp. 187–204. Interscience, New York, NY (1948)

  18. 18.

    Kantor, W.M.: \(k\)-Homogeneous groups. Math. Z. 124365体育网站, 261–265 (1972)

  19. 19.

    365体育网站Knörr, R.: Personal communication (2011)

  20. 20.

    Komei, F.: Polyhedral computation FAQ (2004). . Accessed 1 Sept 2014

  21. 21.

    Rehn, T.: Exploring core points for fun and profit—a study of lattice-free orbit polytopes. PhD thesis, Universität Rostock (2013)

  22. 22.

    365体育网站Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken, NJ (1998)

  23. 23.

    Sebő, A.: An introduction to empty lattice simplices. In Integer Programming and Combinatorial Optimization (Graz, 1999). Lecture Notes in Computer Science, vol. 1610, pp. 400–414. Springer, Berlin (1999)

  24. 24.

    Seress, Á.: Primitive groups with no regular orbits on the set of subsets. Bull. London Math. Soc. 29(6), 697–704 (1997)

  25. 25.

    Serre, J.-P.: Linear Representations of Finite Groups. Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, vol. 42, Springer, New York (1977)

Download references

Acknowledgments

We thank Reinhard Knörr and Michael Joswig for valuable discussions and we thank Erik Friese and Frieder Ladisch for helpful comments on a previous version of the paper. We also thank the anonymous referees for their beneficial remarks. Research by the first author was partially supported by Studienstiftung des deutschen Volkes and the paper was partially completed while the third author was visiting the Institute for Mathematical Sciences, National University of Singapore, in 2013.

Author information

Correspondence to Achill Schürmann.

Rights and permissions

About this article

Cite this article

Herr, K., Rehn, T. & Schürmann, A. On Lattice-Free Orbit Polytopes. Discrete Comput Geom 53, 144–172 (2015). http://doi.org/10.1007/s00454-014-9638-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

Keywords

  • Symmetry
  • Core points
  • Orbit polytopes
  • Lattice-free

Mathematics Subject Classification

  • 52B15
  • 90C10
  • 20C99