---
_id: '1511'
abstract:
- lang: eng
  text: '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.'
acknowledgement: "The work by Z. P. was partially supported by the Charles University
  Grant SVV-2014-260103. The\r\nwork by Z. P. and M. T. was partially supported by
  the project CE-ITI (GACR P202/12/G061) of\r\nthe Czech Science Foundation and by
  the ERC Advanced Grant No. 267165. Part of the research\r\nwork of M. T. was conducted
  at IST Austria, supported by an IST Fellowship. The work by U.W.\r\nwas partially
  supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and\r\nSNSF-PP00P2-138948)."
alternative_title:
- LIPIcs
author:
- first_name: Xavier
  full_name: Goaoc, Xavier
  last_name: Goaoc
- first_name: Isaac
  full_name: Mabillard, Isaac
  id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
  last_name: Mabillard
- first_name: Pavel
  full_name: Paták, Pavel
  last_name: Paták
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
- first_name: Martin
  full_name: Tancer, Martin
  id: 38AC689C-F248-11E8-B48F-1D18A9856A87
  last_name: Tancer
  orcid: 0000-0002-1191-6714
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: '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:<a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.476">10.4230/LIPIcs.SOCG.2015.476</a>'
  apa: 'Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; 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. <a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.476">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>'
  chicago: '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. <a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.476">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>.'
  ieee: '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.'
  ista: '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.'
  mla: 'Goaoc, Xavier, et al. <i>On Generalized Heawood Inequalities for Manifolds:
    A Van Kampen–Flores-Type Nonembeddability Result</i>. Vol. 34, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:<a href="https://doi.org/10.4230/LIPIcs.SOCG.2015.476">10.4230/LIPIcs.SOCG.2015.476</a>.'
  short: 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.
conference:
  end_date: 2015-06-25
  location: Eindhoven, Netherlands
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2015-06-22
date_created: 2018-12-11T11:52:27Z
date_published: 2015-06-11T00:00:00Z
date_updated: 2025-09-11T07:35:35Z
day: '11'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SOCG.2015.476
ec_funded: 1
file:
- access_level: open_access
  checksum: 0945811875351796324189312ca29e9e
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:11:18Z
  date_updated: 2020-07-14T12:44:59Z
  file_id: '4871'
  file_name: IST-2016-502-v1+1_42.pdf
  file_size: 636735
  relation: main_file
file_date_updated: 2020-07-14T12:44:59Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 476 - 490
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5666'
pubrep_id: '502'
quality_controlled: '1'
related_material:
  record:
  - id: '610'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: 'On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type
  nonembeddability result'
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '34 '
year: '2015'
...