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

Euler’s Theorem for Regular CW-Complexes

  • Original Paper
  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

For strongly connected, pure n-dimensional regular CW-complexes, we show that evenness (each \((n{-}1)\)-cell is contained in an even number of n-cells) is equivalent to generalizations of both cycle decomposition and traversability.

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

Data availability

None

References

  1. Altshuler, A.: Polyhedral realization in \({\mathbb{R} }^{3}\) of triangulations of the torus and \(2\)-manifolds in cyclic \(4\)-polytopes. Discr. Math 1, 211–238 (1971)

    Article  MathSciNet  Google Scholar 

  2. Altshuler, A.: Manifolds in stacked 4-polytopes. J. Combin. Theory Ser. A 10(3), 198–239 (1971)

    Article  MathSciNet  Google Scholar 

  3. Bahamian, A., Sajna, M.: Quasi-Eulerian Hypergraphs. Elect. J. Combinat. 24(3), 3.30 (2017)

  4. Basak, B., Swartz, E.: Three-dimensional normal pseudomanifolds with relatively few edges. Adv. Math. 365, 107035 (2020)

    Article  MathSciNet  Google Scholar 

  5. Bermond, J.C., Germa, A., Heydemann, M.C., Sotteau, D.: Hypergraph Hamiltoniens. Probleme Combinatoire et theorie des graphes, Orsey 260, 39–43 (1976)

    Google Scholar 

  6. Betke, U., Schulz, C., Wills, J.M.: Zur Zerlegbarkeit von Skeletten. Geometriae Dedicata 5(4), 435–451 (1976)

    Google Scholar 

  7. Biggs, N.L., Lloyd, E.K., Wilson, R.J.: Graph Theory, 1736 to 1936. Clarendon Press, Oxford (1976)

    Google Scholar 

  8. Björner, A.: Posets, regular CW-complexes and Bruhat order. Eur. J. Combin. 5, 7–16 (1984)

    Article  MathSciNet  Google Scholar 

  9. Bolker, E.D.: Simplicial geometry and transportation polytopes. Trans. Am. Math. Soc. 217, 121–142 (1976)

    MathSciNet  Google Scholar 

  10. Busaryev, O., Cabello, S., Chen, C., Dey, T. K., Wang, Y.: Annotating Simplices with a Homology Basis and Its Applications. Scandinavian Workshop Alg. Theo. 189–200 (2012)

  11. Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida, 1989), Congr. Numer 70-74, Utilitas Math (1990)

  12. Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures. Discr. Math. 110, 43–59 (1992)

    Article  MathSciNet  Google Scholar 

  13. Coxeter, H.S.M.: Regular skew polyhedra in three and four dimensions and their topological analogoues. Proc. London Math. Soc. 43(Ser. 2), 33–62 (1937)

  14. Cruickshank, J., Jackson, B., Tanigawa, S.: Global Rigidity of Triangulated Manifolds, arXiv:2204.02503v1 [math.CO] 5 Apr (22 pages) (2022)

  15. Dewdney, A.K.: Higher-dimensional tree structures. J. Combin. Theory (B) 17, 160–169 (1974)

    Article  Google Scholar 

  16. Dey, T.K., Edelsbrunner, H., Guha, S.: Computational topology, Computational topology. Contemp. Math. 223, 109–144 (1999)

    Article  MathSciNet  Google Scholar 

  17. Duval, A. M., Klivans, C. J., Martin, J. L., Beveridge A. et al.: Simplicial and cellular trees. In: Recent Trends in Combinatorics pp. 713–752

  18. Edmonds, J., Johnson, E.L.: Matching, Euler Tours, and the Chinese Postman. Math. Progr. 5, 88–124 (1973)

    Article  MathSciNet  Google Scholar 

  19. Effenberger, F., Kühnel, W.: Hamiltonian submanifolds of regular polytopes. Discrete Comput. Geom. 43, 242–262 (2010)

    Article  MathSciNet  Google Scholar 

  20. Euler, L.: Solutio problematis ad geometriam situs pertinentis. Comment. Acad. Sci. I. Petropolitanae 8, 128–140 (1736)

  21. Euler, L.: Solutio problematis ad geometriam situs pertinentis. Opera Omnia Series I-7, 1–10 (1766)

  22. Fogelsanger, A.: The generic rigidity of minimal cycles, Ph.D. Dissertation, Cornell University (1988). See http://www.armadillodanceproject.com/af/cornell/rigidity.htm

  23. Glock, S., Joos, F., Kühn, D., Osthus, D.: Euler tours in hypergraphs. Combinatorica 40, 679–690 (2020)

    Article  MathSciNet  Google Scholar 

  24. Glock, S., Kühn, D., Lo, A., Osthus, D.: The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\). Memoirs Amer. Math. Soc. 284, 131 (2023)

    Article  MathSciNet  Google Scholar 

  25. Grünbaum, B.: Graphs, complexes, and polytopes. In: Tutte, W.T. (ed.) Recent Progress in Combinatorics, pp. 85–90. Academic Press, NY (1969)

    Google Scholar 

  26. Hammack, R.H., Kainen, P.C.: Eulerian 2-complexes, Math Magazine, to appear

  27. Hammack, R. H., Kainen, P. C.: Sphere-decompositions of hypercubes. Art Discrete Appl. Math. 3(2), 2.09 (2020)

  28. Hammack, R.H., Kainen, P.C.: Graph bases and commutative diagrams. Graphs Combin. 34(4), 523–534 (2018)

    Article  MathSciNet  Google Scholar 

  29. Hammack, R.H., Kainen, P.C.: On \(2\)-skeleta of Platonic polytopes. Bull. Hell. Math. Soc. 62, 94–102 (2018)

    MathSciNet  Google Scholar 

  30. Hammack, R.H., Kainen, P.C.: Factorization of Platonic polytopes into canonical spheres. Geombinatorics XXX I(1), 5–9 (2021)

    MathSciNet  Google Scholar 

  31. Hammack, R.H., Kainen, P.C.: A new view of hypercube genus. Am. Math. Month. 128(4), 352–359 (2021)

    Article  MathSciNet  Google Scholar 

  32. Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1969)

    Book  Google Scholar 

  33. Hierholzer, C.: Über die Möglichkeit, einen linienzug ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Ann. 6, 30–32 (1873)

    Article  MathSciNet  Google Scholar 

  34. Kainen, P. C.: On \(2\)-skeleta of hypercubes. Art Discrete Appl. Math. 3(2), 2.06 (2020)

  35. Kainen, P.C.: Canonical Sphere Bases for Simplicial and Cubical Complexes. J. Knot Theory Ramif. 32(03), 2350019 (2023)

    Article  MathSciNet  Google Scholar 

  36. Kalai, G.: Polytope skeletons and paths, Chap. 19. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. CRC Press, Boca Raton, FL (2017)

    Google Scholar 

  37. Katona, G.Y., Kierstead, H.: Hamiltonian chains in hypergraphs. J. Graph Theo. 30(3), 205–212 (1999)

    Article  MathSciNet  Google Scholar 

  38. Keevash, P.: Counting designs. J. Eur. Math. Soc. 20(4), 903–927 (2018). also Existence of designs, arXiv, 2014–2019

  39. Klee, V.: A \(d\)-pseudomanifold with \(f_0\) vertices has at least \(df_0 - (d-1)(d+2) d\)-simplices. Houston J. Math 1(1), 81–86 (1975)

    MathSciNet  Google Scholar 

  40. Kühnel, W., Schulz, Ch.: Submanifolds of the cube, In: P. Gritzman, B. Sturmfels, (eds.). Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, DIMACS, Ser. in Discr. Math. and Theoretical Comp. Sci., Vol. 4, AMS/ACM, pp. 423–432 (1991)

  41. Kühnel, W.: Tight Polyhedral Submanifolds and Tight Triangulations, Lect. Notes in Math., Springer (1996)

  42. Lovász, L., Plummer, M.D.: Matching Theory. N. Holland, Amsterdam (1986)

    Google Scholar 

  43. Massey, W. S.: A Basic Course in Algebraic Topology (1991)

  44. Massey, W. S.: Homology of CW-complexes (Chap. 4), In: Singular Homology Theory, Springer, NY pp. 76–104 (1980)

  45. Mathew, R., Newman, I., Rabinovich, Y., Rajendraprasad, D.: Boundaries of hypertrees, and Hamiltonian cycles in simplicial complexes, arXiv: 1507.04471v2 (2018)

  46. Pippert, R.E., Beineke, L.W.: Characterizations of 2-dimensional trees. In: Chartrand, G., Kapoor, S.F. (eds). The Many Facets of Graph Theory. Springer, Lect. Notes in Math. 110, 263–270 (1969)

  47. Pokorny, F.T., Kragic, D.: Data-driven topological motion planning with persistent cohomology, In: Robotics: Science and Systems, Buchli J.,Hsu D.,Kavraki L.E., Eds., MIT Press. Vol. 11. http://www.roboticsproceedings.org/rss11/p49.pdf (2015)

  48. Sajna, M., Steimle, Y.: Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts. Discr. Math. 341(10), 2808–2819 (2018)

    Article  MathSciNet  Google Scholar 

  49. Schulz, Ch.: Mannigfaltigkeiten mit Zellzerlegung im Randkomplex eines konvexen Polytops verallgemeinerte Hamilton-Kreise, dissertation, Bochum (1974)

  50. Sos, V.T., Erdos, P., Brown, W.G.: On the existence of triangulated spheres in \(3\)-graphs and related problems. Per. Math. Hung. 3(3–4), 221–228 (1973)

    Article  MathSciNet  Google Scholar 

  51. Spanier, E.H.: Algebraic Topology. McGraw-Hill, New York (1966)

    Google Scholar 

  52. Spreer, J.: Partitioning the triangles of the cross polytope into surfaces. Beitr. Algebra Geom. 53, 473–486 (2012)

    Article  MathSciNet  Google Scholar 

  53. Veblen, O.: An application of modular equations in analysis situs. Ann. Math. 14(1), 86–94 (1912)

    Article  MathSciNet  Google Scholar 

  54. Wagner, A.: Eulerian Properties of Design Hypergraphs and Hypergraphs with Small Edge Cuts, Ph. D. dissertation, University of Ottawa (2019)

  55. Welsh, D. J. A.: Matroid Theory, LMS Monograph No. 8, Acad. Press, London (1976)

Download references

Acknowledgements

We appreciate the advice and criticisms supplied by our referees, who helped us to clarify definitions and proofs. We are grateful for their attentive reading of the paper and for their generosity in providing specific corrections.

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, Georgetown University, 37th and O Streets, N.W., Washington DC, 20057, USA

    Paul C. Kainen

  2. Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, P.O. Box 2014, Richmond, VA, 23284, USA

    Richard H. Hammack

Authors
  1. Richard H. Hammack
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paul C. Kainen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paul C. Kainen.

Additional information

Publisher's Note

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

Supported by Simons Collaboration Grant for Mathematicians 523748.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hammack, R.H., Kainen, P.C. Euler’s Theorem for Regular CW-Complexes. Combinatorica 44, 453–465 (2024). https://doi.org/10.1007/s00493-023-00080-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-023-00080-1

Keywords

Mathematics Subject Classification

Search

Navigation