---
_id: '10776'
abstract:
- lang: eng
  text: 'Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior).
    Given a point p in the interior of K, a hyperplane h passing through p is called
    barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question
    whether, for every K, there exists an interior point p through which there are
    at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly
    resolved affirmatively by showing that this is the case if p=p0 is the point of
    maximal depth in K. However, while working on a related question, we noticed that
    one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample;
    this re-opens Grünbaum’s question. It follows from known results that for n≥2,
    there are always at least three distinct barycentric cuts through the point p0∈K
    of maximal depth. Using tools related to Morse theory we are able to improve this
    bound: four distinct barycentric cuts through p0 are guaranteed if n≥3.'
acknowledgement: The work by Zuzana Patáková has been partially supported by Charles
  University Research Center Program No. UNCE/SCI/022, and part of it was done during
  her research stay at IST Austria. The work by Martin Tancer is supported by the
  GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and
  UNCE/SCI/004.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- 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
  last_name: Tancer
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. <i>Discrete
    and Computational Geometry</i>. 2022;68:1133-1154. doi:<a href="https://doi.org/10.1007/s00454-021-00364-7">10.1007/s00454-021-00364-7</a>
  apa: Patakova, Z., Tancer, M., &#38; Wagner, U. (2022). Barycentric cuts through
    a convex body. <i>Discrete and Computational Geometry</i>. Springer Nature. <a
    href="https://doi.org/10.1007/s00454-021-00364-7">https://doi.org/10.1007/s00454-021-00364-7</a>
  chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
    a Convex Body.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2022.
    <a href="https://doi.org/10.1007/s00454-021-00364-7">https://doi.org/10.1007/s00454-021-00364-7</a>.
  ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
    body,” <i>Discrete and Computational Geometry</i>, vol. 68. Springer Nature, pp.
    1133–1154, 2022.
  ista: Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body.
    Discrete and Computational Geometry. 68, 1133–1154.
  mla: Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>Discrete
    and Computational Geometry</i>, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:<a
    href="https://doi.org/10.1007/s00454-021-00364-7">10.1007/s00454-021-00364-7</a>.
  short: Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68
    (2022) 1133–1154.
date_created: 2022-02-20T23:01:35Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-02T14:38:58Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-021-00364-7
external_id:
  arxiv:
  - '2003.13536'
  isi:
  - '000750681500001'
intvolume: '        68'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2003.13536
month: '12'
oa: 1
oa_version: Preprint
page: 1133-1154
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Barycentric cuts through a convex body
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '7960'
abstract:
- lang: eng
  text: Let A={A1,…,An} be a family of sets in the plane. For 0≤i<n, denote by fi
    the number of subsets σ of {1,…,n} of cardinality i+1 that satisfy ⋂i∈σAi≠∅. Let
    k≥2 be an integer. We prove that if each k-wise and (k+1)-wise intersection of
    sets from A is empty, or a single point, or both open and path-connected, then
    fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on k. Similarly,
    let b≥2, k>2b be integers. We prove that if each k-wise or (k+1)-wise intersection
    of sets from A has at most b path-connected components, which all are open, then
    fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k.
    These results also extend to two-dimensional compact surfaces.
acknowledgement: "We are very grateful to Pavel Paták for many helpful discussions
  and remarks. We also thank the referees for helpful comments, which greatly improved
  the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK
  was also partially supported by NSF grant DMS1300120. The research stay of ZP at
  IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement
  of internationalization in the field of research and development at Charles University,
  through the support of quality projects MSCA-IF."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Gil
  full_name: Kalai, Gil
  last_name: Kalai
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
citation:
  ama: Kalai G, Patakova Z. Intersection patterns of planar sets. <i>Discrete and
    Computational Geometry</i>. 2020;64:304-323. doi:<a href="https://doi.org/10.1007/s00454-020-00205-z">10.1007/s00454-020-00205-z</a>
  apa: Kalai, G., &#38; Patakova, Z. (2020). Intersection patterns of planar sets.
    <i>Discrete and Computational Geometry</i>. Springer Nature. <a href="https://doi.org/10.1007/s00454-020-00205-z">https://doi.org/10.1007/s00454-020-00205-z</a>
  chicago: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.”
    <i>Discrete and Computational Geometry</i>. Springer Nature, 2020. <a href="https://doi.org/10.1007/s00454-020-00205-z">https://doi.org/10.1007/s00454-020-00205-z</a>.
  ieee: G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” <i>Discrete
    and Computational Geometry</i>, vol. 64. Springer Nature, pp. 304–323, 2020.
  ista: Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete
    and Computational Geometry. 64, 304–323.
  mla: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” <i>Discrete
    and Computational Geometry</i>, vol. 64, Springer Nature, 2020, pp. 304–23, doi:<a
    href="https://doi.org/10.1007/s00454-020-00205-z">10.1007/s00454-020-00205-z</a>.
  short: G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.
date_created: 2020-06-14T22:00:50Z
date_published: 2020-09-01T00:00:00Z
date_updated: 2023-08-21T08:26:34Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-020-00205-z
external_id:
  arxiv:
  - '1907.00885'
  isi:
  - '000537329400001'
intvolume: '        64'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1907.00885
month: '09'
oa: 1
oa_version: Preprint
page: 304-323
publication: Discrete and Computational Geometry
publication_identifier:
  eissn:
  - '14320444'
  issn:
  - '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Intersection patterns of planar sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '7989'
abstract:
- lang: eng
  text: 'We prove general topological Radon-type theorems for sets in ℝ^d, smooth
    real manifolds or finite dimensional simplicial complexes. Combined with a recent
    result of Holmsen and Lee, it gives fractional Helly theorem, and consequently
    the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X
    be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex.
    Then if F is a finite, intersection-closed family of sets in X such that the ith
    reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every
    non-negative integer i less or equal to k, then the Radon number of F is bounded
    in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1
    if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X
    is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent
    result of the author and Kalai, we manage to prove the following optimal bound
    on fractional Helly number for families of open sets in a surface: Let F be a
    finite family of open sets in a surface S such that the intersection of any subfamily
    of F is either empty, or path-connected. Then the fractional Helly number of F
    is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about
    an existence of a (p,q)-theorem for open subsets of a surface.'
alternative_title:
- LIPIcs
article_number: 61:1-61:13
article_processing_charge: No
arxiv: 1
author:
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
citation:
  ama: 'Patakova Z. Bounding radon number via Betti numbers. In: <i>36th International
    Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">10.4230/LIPIcs.SoCG.2020.61</a>'
  apa: 'Patakova, Z. (2020). Bounding radon number via Betti numbers. In <i>36th International
    Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>'
  chicago: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In <i>36th
    International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">https://doi.org/10.4230/LIPIcs.SoCG.2020.61</a>.
  ieee: Z. Patakova, “Bounding radon number via Betti numbers,” in <i>36th International
    Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.
  ista: 'Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International
    Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
    LIPIcs, vol. 164, 61:1-61:13.'
  mla: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” <i>36th International
    Symposium on Computational Geometry</i>, vol. 164, 61:1-61:13, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.61">10.4230/LIPIcs.SoCG.2020.61</a>.
  short: Z. Patakova, in:, 36th International Symposium on Computational Geometry,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
date_created: 2020-06-22T09:14:18Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2021-01-12T08:16:22Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.61
external_id:
  arxiv:
  - '1908.01677'
file:
- access_level: open_access
  checksum: d0996ca5f6eb32ce955ce782b4f2afbe
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T06:56:23Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8005'
  file_name: 2020_LIPIcsSoCG_Patakova_61.pdf
  file_size: 645421
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bounding radon number via Betti numbers
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: 164
year: '2020'
...
---
_id: '7992'
abstract:
- lang: eng
  text: 'Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior).
    Given a point p in the interior of K, a hyperplane h passing through p is called
    barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question
    whether, for every K, there exists an interior point p through which there are
    at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly
    resolved affirmatively by showing that this is the case if p=p₀ is the point of
    maximal depth in K. However, while working on a related question, we noticed that
    one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample;
    this re-opens Grünbaum’s question. It follows from known results that for n ≥
    2, there are always at least three distinct barycentric cuts through the point
    p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve
    this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.'
alternative_title:
- LIPIcs
article_number: 62:1 - 62:16
article_processing_charge: No
arxiv: 1
author:
- 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: 'Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In:
    <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">10.4230/LIPIcs.SoCG.2020.62</a>'
  apa: 'Patakova, Z., Tancer, M., &#38; Wagner, U. (2020). Barycentric cuts through
    a convex body. In <i>36th International Symposium on Computational Geometry</i>
    (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>'
  chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
    a Convex Body.” In <i>36th International Symposium on Computational Geometry</i>,
    Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>.
  ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
    body,” in <i>36th International Symposium on Computational Geometry</i>, Zürich,
    Switzerland, 2020, vol. 164.
  ista: 'Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body.
    36th International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 164, 62:1-62:16.'
  mla: Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>36th
    International Symposium on Computational Geometry</i>, vol. 164, 62:1-62:16, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.62">10.4230/LIPIcs.SoCG.2020.62</a>.
  short: Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational
    Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-06-26
  location: Zürich, Switzerland
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2020-06-22
date_created: 2020-06-22T09:14:20Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2021-01-12T08:16:23Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.62
external_id:
  arxiv:
  - '2003.13536'
file:
- access_level: open_access
  checksum: ce1c9194139a664fb59d1efdfc88eaae
  content_type: application/pdf
  creator: dernst
  date_created: 2020-06-23T06:45:52Z
  date_updated: 2020-07-14T12:48:06Z
  file_id: '8004'
  file_name: 2020_LIPIcsSoCG_Patakova.pdf
  file_size: 750318
  relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: '       164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959771436'
  issn:
  - '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Barycentric cuts through a convex body
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: 164
year: '2020'
...
---
_id: '7108'
abstract:
- lang: eng
  text: We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial
    complex is shellable is NP-hard, hence NP-complete. This resolves a question raised,
    e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d
    ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable
    is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible
    pure d-dimensional complexes. Another simple corollary of our result is that it
    is NP-hard to decide whether a given poset is CL-shellable.
article_number: '21'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xavier
  full_name: Goaoc, Xavier
  last_name: Goaoc
- first_name: Pavel
  full_name: Patak, Pavel
  id: B593B804-1035-11EA-B4F1-947645A5BB83
  last_name: Patak
- 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
  last_name: Tancer
- 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, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete.
    <i>Journal of the ACM</i>. 2019;66(3). doi:<a href="https://doi.org/10.1145/3314024">10.1145/3314024</a>
  apa: Goaoc, X., Patak, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2019). Shellability
    is NP-complete. <i>Journal of the ACM</i>. ACM. <a href="https://doi.org/10.1145/3314024">https://doi.org/10.1145/3314024</a>
  chicago: Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner.
    “Shellability Is NP-Complete.” <i>Journal of the ACM</i>. ACM, 2019. <a href="https://doi.org/10.1145/3314024">https://doi.org/10.1145/3314024</a>.
  ieee: X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is
    NP-complete,” <i>Journal of the ACM</i>, vol. 66, no. 3. ACM, 2019.
  ista: Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete.
    Journal of the ACM. 66(3), 21.
  mla: Goaoc, Xavier, et al. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>,
    vol. 66, no. 3, 21, ACM, 2019, doi:<a href="https://doi.org/10.1145/3314024">10.1145/3314024</a>.
  short: X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM
    66 (2019).
date_created: 2019-11-26T10:13:59Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-06T11:10:58Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3314024
external_id:
  arxiv:
  - '1711.08436'
  isi:
  - '000495406300007'
intvolume: '        66'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/pdf/1711.08436.pdf
month: '06'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_identifier:
  issn:
  - 0004-5411
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
  record:
  - id: '184'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Shellability is NP-complete
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
year: '2019'
...
---
_id: '184'
abstract:
- lang: eng
  text: We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial
    complex is shellable is NP-hard, hence NP-complete. This resolves a question raised,
    e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d
    ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable
    is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible
    pure d-dimensional complexes.
acknowledgement: 'Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR:
  38087RM) of Czech-French collaboration.'
alternative_title:
- Leibniz International Proceedings in Information, LIPIcs
author:
- first_name: Xavier
  full_name: Goaoc, Xavier
  last_name: Goaoc
- 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, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete.
    In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16.
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">10.4230/LIPIcs.SoCG.2018.41</a>'
  apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2018). Shellability
    is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational
    Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>'
  chicago: Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner.
    “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2018. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>.
  ieee: 'X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability
    is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest,
    Hungary, 2018, vol. 99, p. 41:1-41:16.'
  ista: 'Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete.
    SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in
    Information, LIPIcs, vol. 99, 41:1-41:16.'
  mla: Goaoc, Xavier, et al. <i>Shellability Is NP-Complete</i>. Vol. 99, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2018.41">10.4230/LIPIcs.SoCG.2018.41</a>.
  short: X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.
conference:
  end_date: 2018-06-14
  location: Budapest, Hungary
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2018-06-11
date_created: 2018-12-11T11:45:04Z
date_published: 2018-06-11T00:00:00Z
date_updated: 2023-09-06T11:10:57Z
day: '11'
ddc:
- '516'
- '000'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2018.41
file:
- access_level: open_access
  checksum: d12bdd60f04a57307867704b5f930afd
  content_type: application/pdf
  creator: dernst
  date_created: 2018-12-17T16:35:02Z
  date_updated: 2020-07-14T12:45:18Z
  file_id: '5725'
  file_name: 2018_LIPIcs_Goaoc.pdf
  file_size: 718414
  relation: main_file
file_date_updated: 2020-07-14T12:45:18Z
has_accepted_license: '1'
intvolume: '        99'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 41:1 - 41:16
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7736'
quality_controlled: '1'
related_material:
  record:
  - id: '7108'
    relation: later_version
    status: public
scopus_import: 1
status: public
title: Shellability is NP-complete
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: 99
year: '2018'
...
---
_id: '701'
abstract:
- lang: eng
  text: A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if
    it can be tiled by k simplices with disjoint interiors that are all mutually congruent
    and similar to S. For d = 2, triangular k-reptiles exist for all k of the form
    a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris,
    and Williams. On the other hand, the only k-reptile simplices that are known for
    d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify
    the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra
    can exist only for k = m^3. We then prove a weaker analogue of this result for
    d = 4 by showing that four-dimensional k-reptile simplices can exist only for
    k = m^2.
author:
- first_name: Jan
  full_name: Kynčl, Jan
  last_name: Kynčl
- first_name: Zuzana
  full_name: Patakova, Zuzana
  id: 48B57058-F248-11E8-B48F-1D18A9856A87
  last_name: Patakova
  orcid: 0000-0002-3975-1683
citation:
  ama: Kynčl J, Patakova Z. On the nonexistence of k reptile simplices in ℝ^3 and
    ℝ^4. <i>The Electronic Journal of Combinatorics</i>. 2017;24(3):1-44.
  apa: Kynčl, J., &#38; Patakova, Z. (2017). On the nonexistence of k reptile simplices
    in ℝ^3 and ℝ^4. <i>The Electronic Journal of Combinatorics</i>. International
    Press.
  chicago: Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices
    in ℝ^3 and ℝ^4.” <i>The Electronic Journal of Combinatorics</i>. International
    Press, 2017.
  ieee: J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3
    and ℝ^4,” <i>The Electronic Journal of Combinatorics</i>, vol. 24, no. 3. International
    Press, pp. 1–44, 2017.
  ista: Kynčl J, Patakova Z. 2017. On the nonexistence of k reptile simplices in ℝ^3
    and ℝ^4. The Electronic Journal of Combinatorics. 24(3), 1–44.
  mla: Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices
    in ℝ^3 and ℝ^4.” <i>The Electronic Journal of Combinatorics</i>, vol. 24, no.
    3, International Press, 2017, pp. 1–44.
  short: J. Kynčl, Z. Patakova, The Electronic Journal of Combinatorics 24 (2017)
    1–44.
date_created: 2018-12-11T11:48:00Z
date_published: 2017-07-14T00:00:00Z
date_updated: 2021-01-12T08:11:28Z
day: '14'
ddc:
- '500'
department:
- _id: UlWa
file:
- access_level: open_access
  checksum: a431e573e31df13bc0f66de3061006ec
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:14:25Z
  date_updated: 2020-07-14T12:47:47Z
  file_id: '5077'
  file_name: IST-2018-984-v1+1_Patakova_on_the_nonexistence_of_k-reptile_simplices_in_R_3_and_R_4_2017.pdf
  file_size: 544042
  relation: main_file
file_date_updated: 2020-07-14T12:47:47Z
has_accepted_license: '1'
intvolume: '        24'
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 1-44
publication: The Electronic Journal of Combinatorics
publication_identifier:
  issn:
  - '10778926'
publication_status: published
publisher: International Press
publist_id: '6996'
pubrep_id: '984'
quality_controlled: '1'
status: public
title: On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2017'
...
---
_id: '610'
abstract:
- lang: eng
  text: 'The fact that the complete graph K5 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 Kn embeds in a closed surface M (other than the Klein bottle) if and only
    if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-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 Kn+1) embeds in R2k if and only if
    n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex
    embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk
    only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1
    2k+1)bk. This is a common generalization of the case of graphs on surfaces as
    well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we
    prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold
    with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than
    the generalized Heawood inequality, but does not require the assumption that M
    is (k−1)-connected. Our results generalize to maps without q-covered points, in
    the spirit of Tverberg’s theorem, for q a prime power. 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 Israel Science Foundation
  grant ISF-768/12. 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 research of P. P. was supported by the ERC Advanced
  grant no. 320924. The work by I. M. and U. W. was supported by the Swiss National
  Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). The collaboration
  between U. W. and X. G. was partially supported by the LabEx Bézout (ANR-10-LABX-58).
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. <i>Israel Journal of Mathematics</i>. 2017;222(2):841-866. doi:<a href="https://doi.org/10.1007/s11856-017-1607-7">10.1007/s11856-017-1607-7</a>'
  apa: 'Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner,
    U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores
    type nonembeddability result. <i>Israel Journal of Mathematics</i>. Springer.
    <a href="https://doi.org/10.1007/s11856-017-1607-7">https://doi.org/10.1007/s11856-017-1607-7</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.” <i>Israel Journal of Mathematics</i>. Springer,
    2017. <a href="https://doi.org/10.1007/s11856-017-1607-7">https://doi.org/10.1007/s11856-017-1607-7</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,” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2. Springer, pp.
    841–866, 2017.'
  ista: 'Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2017. On generalized
    Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability
    result. Israel Journal of Mathematics. 222(2), 841–866.'
  mla: 'Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds:
    A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>,
    vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:<a href="https://doi.org/10.1007/s11856-017-1607-7">10.1007/s11856-017-1607-7</a>.'
  short: X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel
    Journal of Mathematics 222 (2017) 841–866.
date_created: 2018-12-11T11:47:29Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2023-02-23T10:02:13Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s11856-017-1607-7
ec_funded: 1
intvolume: '       222'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1610.09063
month: '10'
oa: 1
oa_version: Preprint
page: 841 - 866
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '291734'
  name: International IST Postdoc Fellowship Programme
publication: Israel Journal of Mathematics
publication_status: published
publisher: Springer
publist_id: '7194'
quality_controlled: '1'
related_material:
  record:
  - id: '1511'
    relation: earlier_version
    status: public
scopus_import: 1
status: public
title: 'On generalized Heawood inequalities for manifolds: A van Kampen–Flores type
  nonembeddability result'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 222
year: '2017'
...
---
_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: 2023-02-23T12:38:00Z
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
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'
...