Document Open Access Logo

On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result

Authors Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, Uli Wagner

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.476.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Xavier Goaoc
Isaac Mabillard
Pavel Paták
Zuzana Patáková
Martin Tancer
Uli Wagner

Cite As Get BibTex

Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 476-490, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.SOCG.2015.476

Abstract

The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2.

Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem.

In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.

Subject Classification

Keywords
  • Heawood Inequality
  • Embeddings
  • Van Kampen–Flores
  • Manifolds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. K. Appel and W. Haken. Every planar map is four colorable. I. Discharging. Illinois J. Math., 21(3):429-490, 1977. Google Scholar
  2. K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. II. Reducibility. Illinois J. Math., 21(3):491-567, 1977. Google Scholar
  3. U. Brehm and W. Kühnel. 15-vertex triangulations of an 8-manifold. Math. Ann., 294(1):167-193, 1992. Google Scholar
  4. T. K. Dey. On counting triangulations in d dimensions. Comput. Geom., 3(6):315-325, 1993. Google Scholar
  5. A. I. Flores. Über die Existenz n-dimensionaler Komplexe, die nicht in den ℝ^2n topologisch einbettbar sind. Ergeb. Math. Kolloqu., 5:17-24, 1933. Google Scholar
  6. X. Goaoc, P. Paták, Z. Patáková, M. Tancer, and U. Wagner. Bounding Helly numbers via Betti numbers. Preprint, arXiv:1310.4613, 2013. Google Scholar
  7. B. Grünbaum. Imbeddings of simplicial complexes. Comment. Math. Helv., 44:502-513, 1969. Google Scholar
  8. A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, UK, 2002. Google Scholar
  9. P. J. Heawood. Map-colour theorem. Quart. J., 24:332-338, 1890. Google Scholar
  10. L. Heffter. Ueber das Problem der Nachbargebiete. Math. Ann., 38:477-508, 1891. Google Scholar
  11. G. Kalai. Algebraic shifting. In Computational commutative algebra and combinatorics (Osaka, 1999), volume 33 of Adv. Stud. Pure Math., pages 121-163. Math. Soc. Japan, Tokyo, 2002. Google Scholar
  12. W. Kühnel. Manifolds in the skeletons of convex polytopes, tightness, and generalized Heawood inequalities. In Polytopes: abstract, convex and computational (Scarborough, ON, 1993), volume 440 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pages 241-247. Kluwer Acad. Publ., Dordrecht, 1994. Google Scholar
  13. W. Kühnel. Tight polyhedral submanifolds and tight triangulations, volume 1612 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1995. Google Scholar
  14. W. Kühnel and T. F. Banchoff. The 9-vertex complex projective plane. Math. Intelligencer, 5(3):11-22, 1983. Google Scholar
  15. W. Kühnel and G. Lassmann. The unique 3-neighborly 4-manifold with few vertices. J. Combin. Theory Ser. A, 35(2):173-184, 1983. Google Scholar
  16. N. Linial and R. Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475-487, 2006. Google Scholar
  17. L. Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A, 25(3):319-324, 1978. Google Scholar
  18. J. Matoušek. Using the Borsuk-Ulam Theorem. Springer-Verlag, Berlin, 2003. Google Scholar
  19. R. Meshulam and N. Wallach. Homological connectivity of random k-dimensional complexes. Random Structures Algorithms, 34(3):408-417, 2009. Google Scholar
  20. J. Milnor. On spaces having the homotopy type of a CW-complex. Trans. Amer. Math. Soc., 90:272-280, 1959. Google Scholar
  21. J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Menlo Park, CA, 1984. Google Scholar
  22. G. Ringel. Map Color Theorem. Springer-Verlag, New York-Heidelberg, 1974. Die Grundlehren der mathematischen Wissenschaften, Band 209. Google Scholar
  23. E. R. van Kampen. Komplexe in euklidischen Räumen. Abh. Math. Sem. Univ. Hamburg, 9:72-78, 1932. Google Scholar
  24. A. Yu. Volovikov. On the van Kampen-Flores theorem. Mat. Zametki, 59(5):663-670, 797, 1996. Google Scholar
  25. U. Wagner. Minors in random and expanding hypergraphs. In Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), pages 351 - 360, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact