Earlier Version

# On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result

X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–490.

Download

IST-2016-502-v1+1_42.pdf
636.74 KB

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Goaoc, Xavier;
Mabillard, Isaac

^{IST Austria}; Paták, Pavel; Patakova, Zuzana^{IST Austria}^{}; Tancer, Martin^{IST Austria}^{}; Wagner, Uli^{IST Austria}^{}Department

Series Title

LIPIcs

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.

Publishing Year

Date Published

2015-06-11

Acknowledgement

The work by Z. P. was partially supported by the Charles University Grant SVV-2014-260103. The
work by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of
the Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research
work of M. T. was conducted at IST Austria, supported by an IST Fellowship. The work by U.W.
was partially supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and
SNSF-PP00P2-138948).

Volume

34

Page

476 - 490

Conference

SoCG: Symposium on Computational Geometry

Conference Location

Eindhoven, Netherlands

Conference Date

2015-06-22 – 2015-06-25

IST-REx-ID

### Cite this

Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:476-490. doi:10.4230/LIPIcs.SOCG.2015.476

Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2015). On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result (Vol. 34, pp. 476–490). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SOCG.2015.476

Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result,” 34:476–90. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPIcs.SOCG.2015.476.

X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 476–490.

Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2015. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 476–490.

Goaoc, Xavier, et al.

*On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result*. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:10.4230/LIPIcs.SOCG.2015.476.**All files available under the following license(s):**

**Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):**

**Main File(s)**

File Name

IST-2016-502-v1+1_42.pdf
636.74 KB

Access Level

Open Access

Date Uploaded

2018-12-12

MD5 Checksum

0945811875351796324189312ca29e9e

**Material in IST:**

**Later Version**