---
_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
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. Discrete
and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7
apa: Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through
a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7
chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022.
https://doi.org/10.1007/s00454-021-00364-7.
ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
body,” Discrete and Computational Geometry, 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.” Discrete
and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.
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: '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
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: 36th International
Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61'
apa: 'Patakova, Z. (2020). Bounding radon number via Betti numbers. In 36th International
Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61'
chicago: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In 36th
International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61.
ieee: Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International
Symposium on Computational Geometry, 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.” 36th International
Symposium on Computational Geometry, vol. 164, 61:1-61:13, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61.
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
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:
36th International Symposium on Computational Geometry. Vol 164. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62'
apa: 'Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through
a convex body. In 36th International Symposium on Computational Geometry
(Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2020.62'
chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
a Convex Body.” In 36th International Symposium on Computational Geometry,
Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.
ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
body,” in 36th International Symposium on Computational Geometry, 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.” 36th
International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.
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: '7960'
abstract:
- lang: eng
text: Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b 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
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. Discrete and
Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z
apa: Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets.
Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z
chicago: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.”
Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z.
ieee: G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete
and Computational Geometry, 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.” Discrete
and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.
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: '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
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.
Journal of the ACM. 2019;66(3). doi:10.1145/3314024
apa: Goaoc, X., Patak, P., Patakova, Z., Tancer, M., & Wagner, U. (2019). Shellability
is NP-complete. Journal of the ACM. ACM. https://doi.org/10.1145/3314024
chicago: Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner.
“Shellability Is NP-Complete.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3314024.
ieee: X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is
NP-complete,” Journal of the ACM, 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.” Journal of the ACM,
vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.
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:10.4230/LIPIcs.SoCG.2018.41'
apa: 'Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & 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.
https://doi.org/10.4230/LIPIcs.SoCG.2018.41'
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. https://doi.org/10.4230/LIPIcs.SoCG.2018.41.
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. Shellability Is NP-Complete. Vol. 99, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:10.4230/LIPIcs.SoCG.2018.41.
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: '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. Israel Journal of Mathematics. 2017;222(2):841-866. doi:10.1007/s11856-017-1607-7'
apa: '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. Springer.
https://doi.org/10.1007/s11856-017-1607-7'
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.” Israel Journal of Mathematics. Springer,
2017. https://doi.org/10.1007/s11856-017-1607-7.'
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,” Israel Journal of Mathematics, 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.” Israel Journal of Mathematics,
vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:10.1007/s11856-017-1607-7.'
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: '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. The Electronic Journal of Combinatorics. 2017;24(3):1-44.
apa: Kynčl, J., & Patakova, Z. (2017). On the nonexistence of k reptile simplices
in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. International
Press.
chicago: Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices
in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics. International
Press, 2017.
ieee: J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3
and ℝ^4,” The Electronic Journal of Combinatorics, 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.” The Electronic Journal of Combinatorics, 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: '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:10.4230/LIPIcs.SOCG.2015.476'
apa: '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'
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. https://doi.org/10.4230/LIPIcs.SOCG.2015.476.'
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. 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.'
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'
...