Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Polytopes Close to Being Simple

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that d-polytopes with at most \(d-2\) nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and \(d-2\), showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for d-polytopes with \(d+k\) vertices and at most \(d-k+3\) nonsimple vertices, provided \(k\geqslant 5\). For \(k\leqslant 4\), the same conclusion holds under a slightly stronger assumption. Another measure of deviation from simplicity is the excess degree of a polytope, defined as \(\xi (P):=2f_1-df_0\), where \(f_k\) denotes the number of k-dimensional faces of the polytope. Simple polytopes are those with excess zero. We prove that polytopes with excess at most \(d-1\) are reconstructible from their graphs, and this is best possible. An interesting intermediate result is that d-polytopes with less than 2d vertices, and at most \(d-1\) nonsimple vertices, are necessarily pyramids.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Balinski, M.L.: On the graph structure of convex polyhedra in \(n\)-space. Pac. J. Math. 11, 431–434 (1961)

    MathSciNet  MATH  Google Scholar 

  2. Blind, R., Mani-Levitska, P.: Puzzles and polytope isomorphisms. Aequ. Math. 34(2–3), 287–297 (1987)

    MathSciNet  MATH  Google Scholar 

  3. Britton, D., Dunitz, J.D.: A complete catalogue of polyhedra with eight or fewer vertices. Acta Crystallogr. Sect. A 29(4), 362–371 (1973)

    Google Scholar 

  4. Brøndsted, A.: An Introduction to Convex Polytopes. Graduate Texts in Mathematics, vol. 90. Springer, New York (1983)

  5. Doolittle, J., Nevo, E., Pineda-Villavicencio, G., Ugon, J., Yost, D.: On the reconstruction of polytopes. Discrete Comput. Geom. https://doi.org/10.1007/s00454-018-9997-9. arXiv: 1702.08739

  6. Fukuda, K., Miyata, H., Moriyama, S.: Classification of oriented matroids. http://www-imai.is.s.u-tokyo.ac.jp/~hmiyata/oriented_matroids/ (2013)

  7. Goodman, J.E., O’Rourke, J. (eds.): Handbook of Discrete and Computational Geometry, 2nd edn. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton (2004)

  8. Gawrilow, E., Joswig, M.: polymake: a framework for analyzing convex polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes—Combinatorics and Computation (Oberwolfach, 1997). DMV Seminar, vol. 29, pp. 43–73. Birkhäuser, Basel (2000)

  9. Grünbaum, B.: Convex Polytopes. 2nd edn. Graduate Texts in Mathematics, vol. 221. Springer, New York (2003). Prepared and with a preface by V. Kaibel, V. Klee and G.M. Ziegler

  10. Joswig, M.: Reconstructing a non-simple polytope from its graph. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation (Oberwolfach, 1997). DMV Seminar, vol. 29, pp. 167–176. Birkhäuser, Basel (2000)

  11. Kalai, G.: A simple way to tell a simple polytope from its graph. J. Comb. Theory Ser. A 49(2), 381–383 (1988)

    MathSciNet  MATH  Google Scholar 

  12. Pineda-Villavicencio, G., Ugon, J., Yost, D.: Lower bound theorems for general polytopes. Eur. J. Comb. (to appear) (arXiv: 1509.08218)

  13. Pineda-Villavicencio, G., Ugon, J., Yost, D.: The excess degree of a polytope. SIAM J. Discret. Math. 32(3), 2011–2046 (2018)

    MathSciNet  MATH  Google Scholar 

  14. Przesławski, K., Yost, D.: More indecomposable polyhedra. Extr. Math. 31(2), 169–188 (2016)

    MathSciNet  MATH  Google Scholar 

  15. Shephard, G.C.: Decomposable convex polyhedra. Mathematika 10, 89–95 (1963)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Guillermo Pineda would like to thank Michael Joswig for the hospitality at the Technical University of Berlin and for suggesting looking at the reconstruction problem for polytopes with small number of vertices.

Author information

Authors and Affiliations

  1. Centre for Informatics and Applied Optimisation, Federation University Australia, Ballarat, Australia

    Guillermo Pineda-Villavicencio & David Yost

  2. School of Information Technology, Deakin University, Burwood, Australia

    Julien Ugon

Authors
  1. Guillermo Pineda-Villavicencio
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julien Ugon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Yost
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guillermo Pineda-Villavicencio.

Additional information

Editor in charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pineda-Villavicencio, G., Ugon, J. & Yost, D. Polytopes Close to Being Simple. Discrete Comput Geom 64, 200–215 (2020). https://doi.org/10.1007/s00454-018-00053-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-018-00053-y

Keywords

Mathematics Subject Classification

Search

Navigation