---
_id: '10335'
abstract:
- lang: eng
text: "Van der Holst and Pendavingh introduced a graph parameter σ, which coincides
with the more famous Colin de Verdière graph parameter μ for small values. However,
the definition of a is much more geometric/topological directly reflecting embeddability
properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G)
for any graph G. We confirm this conjecture. As far as we know, this is the first
topological upper bound on σ(G) which is, in general, tight.\r\nEquality between
μ and σ does not hold in general as van der Holst and Pendavingh showed that there
is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much
smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8.
We also prove that, in general, the gap can be large: The incidence graphs Hq
of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2."
acknowledgement: 'V. K. gratefully acknowledges the support of Austrian Science Fund
(FWF): P 30902-N35. This work was done mostly while he was employed at the University
of Innsbruck. During the early stage of this research, V. K. was partially supported
by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y
of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University
project UNCE/SCI/004.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vojtech
full_name: Kaluza, Vojtech
id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
last_name: Kaluza
orcid: 0000-0002-2512-8698
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
citation:
ama: Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations
of graphs. Combinatorica. 2022;42:1317-1345. doi:10.1007/s00493-021-4443-7
apa: Kaluza, V., & Tancer, M. (2022). Even maps, the Colin de Verdière number
and representations of graphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4443-7
chicago: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
and Representations of Graphs.” Combinatorica. Springer Nature, 2022. https://doi.org/10.1007/s00493-021-4443-7.
ieee: V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations
of graphs,” Combinatorica, vol. 42. Springer Nature, pp. 1317–1345, 2022.
ista: Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations
of graphs. Combinatorica. 42, 1317–1345.
mla: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
and Representations of Graphs.” Combinatorica, vol. 42, Springer Nature,
2022, pp. 1317–45, doi:10.1007/s00493-021-4443-7.
short: V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.
date_created: 2021-11-25T13:49:16Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-02T06:43:27Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.1007/s00493-021-4443-7
external_id:
arxiv:
- '1907.05055'
isi:
- '000798210100003'
intvolume: ' 42'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1907.05055'
month: '12'
oa: 1
oa_version: Preprint
page: 1317-1345
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Even maps, the Colin de Verdière number and representations of graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
year: '2022'
...
---
_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:
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: '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: '425'
abstract:
- lang: eng
text: 'We show that the following algorithmic problem is decidable: given a 2-dimensional
simplicial complex, can it be embedded (topologically, or equivalently, piecewise
linearly) in R3? By a known reduction, it suffices to decide the embeddability
of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which
allows us to simplify X and recurse, is in proving that if X can be embedded in
S3, then there is also an embedding in which X has a short meridian, that is,
an essential curve in the boundary of X bounding a disk in S3 \ X with length
bounded by a computable function of the number of tetrahedra of X.'
article_number: '5'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- 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: Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is
decidable. Journal of the ACM. 2018;65(1). doi:10.1145/3078632
apa: Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2018). Embeddability
in the 3-Sphere is decidable. Journal of the ACM. ACM. https://doi.org/10.1145/3078632
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability
in the 3-Sphere Is Decidable.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3078632.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the
3-Sphere is decidable,” Journal of the ACM, vol. 65, no. 1. ACM, 2018.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2018. Embeddability in the 3-Sphere
is decidable. Journal of the ACM. 65(1), 5.
mla: Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” Journal
of the ACM, vol. 65, no. 1, 5, ACM, 2018, doi:10.1145/3078632.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).
date_created: 2018-12-11T11:46:24Z
date_published: 2018-01-01T00:00:00Z
date_updated: 2023-09-11T13:38:49Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3078632
ec_funded: 1
external_id:
arxiv:
- '1402.0815'
isi:
- '000425685900006'
intvolume: ' 65'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1402.0815
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '7398'
quality_controlled: '1'
related_material:
record:
- id: '2157'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Embeddability in the 3-Sphere is decidable
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 65
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: '1411'
abstract:
- lang: eng
text: We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn
on a compact two-dimensional surface M with boundary. Each αi and each βj is either
an arc meeting the boundary of M at its two endpoints, or a closed curve. The
αi are pairwise disjoint except for possibly sharing endpoints, and similarly
for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of
M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise
such that the total number of crossings of the ai with the φ(βj) is as small as
possible. This problem is motivated by an application in the algorithmic theory
of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with
h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently
of h), which is asymptotically tight, as an easy lower bound shows. In general,
for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable
or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent
of h and g. The proofs rely, among other things, on a result concerning simultaneous
planar drawings of graphs by Erten and Kobourov.
acknowledgement: 'Supported by the ERC Adv anced Grant No. 267165. '
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- 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: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing
curves. Israel Journal of Mathematics. 2016;212(1):37-79. doi:10.1007/s11856-016-1294-9
apa: Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2016). Untangling
two systems of noncrossing curves. Israel Journal of Mathematics. Springer.
https://doi.org/10.1007/s11856-016-1294-9
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling
Two Systems of Noncrossing Curves.” Israel Journal of Mathematics. Springer,
2016. https://doi.org/10.1007/s11856-016-1294-9.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems
of noncrossing curves,” Israel Journal of Mathematics, vol. 212, no. 1.
Springer, pp. 37–79, 2016.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2016. Untangling two systems of
noncrossing curves. Israel Journal of Mathematics. 212(1), 37–79.
mla: Matoušek, Jiří, et al. “Untangling Two Systems of Noncrossing Curves.” Israel
Journal of Mathematics, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:10.1007/s11856-016-1294-9.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics
212 (2016) 37–79.
date_created: 2018-12-11T11:51:52Z
date_published: 2016-05-01T00:00:00Z
date_updated: 2023-02-23T10:34:31Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s11856-016-1294-9
intvolume: ' 212'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.6475
month: '05'
oa: 1
oa_version: Preprint
page: 37 - 79
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication: Israel Journal of Mathematics
publication_status: published
publisher: Springer
publist_id: '5796'
quality_controlled: '1'
related_material:
record:
- id: '2244'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Untangling two systems of noncrossing curves
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 212
year: '2016'
...
---
_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'
...
---
_id: '1688'
abstract:
- lang: eng
text: 'We estimate the selection constant in the following geometric selection theorem
by Pach: For every positive integer d, there is a constant (Formula presented.)
such that whenever (Formula presented.) are n-element subsets of (Formula presented.),
we can find a point (Formula presented.) and subsets (Formula presented.) for
every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices
determined by (Formula presented.) simplices with one vertex in each Yi. We show
a super-exponentially decreasing upper bound (Formula presented.). The ideas used
in the proof of the upper bound also help us to prove Pach’s theorem with (Formula
presented.), which is a lower bound doubly exponentially decreasing in d (up to
some polynomial in the exponent). For comparison, Pach’s original approach yields
a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and
Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem
with (Formula presented.). In our construction for the upper bound, we use the
fact that the minimum solid angle of every d-simplex is super-exponentially small.
This fact was previously unknown and might be of independent interest. For the
lower bound, we improve the ‘separation’ part of the argument by showing that
in one of the key steps only d+1 separations are necessary, compared to 2d separations
in the original proof. We also provide a measure version of Pach’s theorem.'
acknowledgement: R. K. was supported by the Russian Foundation for Basic Research
Grant 15-31-20403 (mol_a_ved) and grant 15-01-99563. J. K., Z. P., and M. T. were
partially supported by ERC Advanced Research Grant No. 267165 (DISCONV) and by the
project CE-ITI (GAČR P202/12/G061) of the Czech Science Foundation. J. K. was also
partially supported by Swiss National Science Foundation Grants 200021-137574 and
200020-14453. P. P., Z. P., and M. T. were partially supported by the Charles University
Grant GAUK 421511. P. P. was also partially supported by the Charles University
Grant SVV-2014-260107. Z. P. was also partially supported by the Charles University
Grant SVV-2014-260103.
author:
- first_name: Roman
full_name: Karasev, Roman
last_name: Karasev
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
- first_name: Pavel
full_name: Paták, Pavel
last_name: Paták
- first_name: Zuzana
full_name: Patakova, Zuzana
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
citation:
ama: Karasev R, Kynčl J, Paták P, Patakova Z, Tancer M. Bounds for Pach’s selection
theorem and for the minimum solid angle in a simplex. Discrete & Computational
Geometry. 2015;54(3):610-636. doi:10.1007/s00454-015-9720-z
apa: Karasev, R., Kynčl, J., Paták, P., Patakova, Z., & Tancer, M. (2015). Bounds
for Pach’s selection theorem and for the minimum solid angle in a simplex. Discrete
& Computational Geometry. Springer. https://doi.org/10.1007/s00454-015-9720-z
chicago: Karasev, Roman, Jan Kynčl, Pavel Paták, Zuzana Patakova, and Martin Tancer.
“Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex.”
Discrete & Computational Geometry. Springer, 2015. https://doi.org/10.1007/s00454-015-9720-z.
ieee: R. Karasev, J. Kynčl, P. Paták, Z. Patakova, and M. Tancer, “Bounds for Pach’s
selection theorem and for the minimum solid angle in a simplex,” Discrete &
Computational Geometry, vol. 54, no. 3. Springer, pp. 610–636, 2015.
ista: Karasev R, Kynčl J, Paták P, Patakova Z, Tancer M. 2015. Bounds for Pach’s
selection theorem and for the minimum solid angle in a simplex. Discrete &
Computational Geometry. 54(3), 610–636.
mla: Karasev, Roman, et al. “Bounds for Pach’s Selection Theorem and for the Minimum
Solid Angle in a Simplex.” Discrete & Computational Geometry, vol.
54, no. 3, Springer, 2015, pp. 610–36, doi:10.1007/s00454-015-9720-z.
short: R. Karasev, J. Kynčl, P. Paták, Z. Patakova, M. Tancer, Discrete & Computational
Geometry 54 (2015) 610–636.
date_created: 2018-12-11T11:53:28Z
date_published: 2015-10-01T00:00:00Z
date_updated: 2021-01-12T06:52:32Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-015-9720-z
intvolume: ' 54'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1403.8147
month: '10'
oa: 1
oa_version: Preprint
page: 610 - 636
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5457'
quality_controlled: '1'
scopus_import: 1
status: public
title: Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 54
year: '2015'
...
---
_id: '2157'
abstract:
- lang: eng
text: 'We show that the following algorithmic problem is decidable: given a 2-dimensional
simplicial complex, can it be embedded (topologically, or equivalently, piecewise
linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability
of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which
allows us to simplify X and recurse, is in proving that if X can be embedded in
S3, then there is also an embedding in which X has a short meridian, i.e., an
essential curve in the boundary of X bounding a disk in S3 nX with length bounded
by a computable function of the number of tetrahedra of X.'
acknowledgement: ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSF-PP00P2-138948);
Swiss National Science Foundation (SNSF-200020-138230).
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- 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: 'Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere
is decidable. In: Proceedings of the Annual Symposium on Computational Geometry.
ACM; 2014:78-84. doi:10.1145/2582112.2582137'
apa: 'Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2014). Embeddability
in the 3 sphere is decidable. In Proceedings of the Annual Symposium on Computational
Geometry (pp. 78–84). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582137'
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability
in the 3 Sphere Is Decidable.” In Proceedings of the Annual Symposium on Computational
Geometry, 78–84. ACM, 2014. https://doi.org/10.1145/2582112.2582137.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the
3 sphere is decidable,” in Proceedings of the Annual Symposium on Computational
Geometry, Kyoto, Japan, 2014, pp. 78–84.
ista: 'Matoušek J, Sedgwick E, Tancer M, Wagner U. 2014. Embeddability in the 3
sphere is decidable. Proceedings of the Annual Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry, 78–84.'
mla: Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.” Proceedings
of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84, doi:10.1145/2582112.2582137.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual
Symposium on Computational Geometry, ACM, 2014, pp. 78–84.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:02Z
date_published: 2014-06-01T00:00:00Z
date_updated: 2023-09-11T13:38:49Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/2582112.2582137
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1402.0815
month: '06'
oa: 1
oa_version: Submitted Version
page: 78 - 84
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4849'
quality_controlled: '1'
related_material:
record:
- id: '425'
relation: later_version
status: public
scopus_import: 1
status: public
title: Embeddability in the 3 sphere is decidable
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2244'
abstract:
- lang: eng
text: 'We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a
compact two-dimensional surface ℳ with boundary. Each αi and each βj is either
an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The
αi are pairwise disjoint except for possibly sharing endpoints, and similarly
for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism
of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of
ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is
as small as possible. This problem is motivated by an application in the algorithmic
theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere
with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be
achieved (independently of h), which is asymptotically tight, as an easy lower
bound shows. In general, for an arbitrary (orientable or nonorientable) surface
ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an
O((m + n)4) upper bound, again independent of h and g. '
acknowledgement: We would like to thank the authors of [GHR13] for mak- ing a draft
of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- 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: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing
curves. 2013;8242:472-483. doi:10.1007/978-3-319-03841-4_41
apa: 'Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2013). Untangling
two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network
Visualization, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-319-03841-4_41'
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling
Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer,
2013. https://doi.org/10.1007/978-3-319-03841-4_41.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems
of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of
noncrossing curves. 8242, 472–483.
mla: Matoušek, Jiří, et al. Untangling Two Systems of Noncrossing Curves.
Vol. 8242, Springer, 2013, pp. 472–83, doi:10.1007/978-3-319-03841-4_41.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.
conference:
end_date: 2013-09-25
location: Bordeaux, France
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2013-09-23
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2023-02-21T17:03:07Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/978-3-319-03841-4_41
external_id:
arxiv:
- '1302.6475'
intvolume: ' 8242'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.6475
month: '09'
oa: 1
oa_version: Preprint
page: 472 - 483
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication_status: published
publisher: Springer
publist_id: '4707'
quality_controlled: '1'
related_material:
record:
- id: '1411'
relation: later_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Untangling two systems of noncrossing curves
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8242
year: '2013'
...
---
_id: '2438'
abstract:
- lang: eng
text: The colored Tverberg theorem asserts that for eve;ry d and r there exists
t=t(d,r) such that for every set C ⊂ ℝ d of cardinality (d + 1)t, partitioned
into t-point subsets C 1, C 2,...,C d+1 (which we think of as color classes; e.
g., the points of C 1 are red, the points of C 2 blue, etc.), there exist r disjoint
sets R 1, R 2,...,R r⊆C that are rainbow, meaning that {pipe}R i∩C j{pipe}≤1 for
every i,j, and whose convex hulls all have a common point. All known proofs of
this theorem are topological. We present a geometric version of a recent beautiful
proof by Blagojević, Matschke, and Ziegler, avoiding a direct use of topological
methods. The purpose of this de-topologization is to make the proof more concrete
and intuitive, and accessible to a wider audience.
acknowledgement: 'We would like to thank Marek Krcál for useful discussions at initial
stages of this research. We also thank Günter M. Ziegler for valuable comments,
and Peter Landweber and two anonymous referees for detailed comments and corrections
that greatly helped to improve the presentation. In particular, we are indebted
to one of the referees for pointing out to us reference [19]. M. Tancer is supported
by the grants SVV-2010-261313 (Discrete Methods and Algorithms) and GAUK 49209.
U. Wagner’s research is supported by the Swiss National Science Foundation (SNF
Projects 200021- 125309 and 200020-125027). '
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Martin
full_name: Martin Tancer
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Uli Wagner
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Matoušek J, Tancer M, Wagner U. A geometric proof of the colored Tverberg theorem.
Discrete & Computational Geometry. 2012;47(2):245-265. doi:10.1007/s00454-011-9368-2
apa: Matoušek, J., Tancer, M., & Wagner, U. (2012). A geometric proof of the
colored Tverberg theorem. Discrete & Computational Geometry. Springer.
https://doi.org/10.1007/s00454-011-9368-2
chicago: Matoušek, Jiří, Martin Tancer, and Uli Wagner. “A Geometric Proof of the
Colored Tverberg Theorem.” Discrete & Computational Geometry. Springer,
2012. https://doi.org/10.1007/s00454-011-9368-2.
ieee: J. Matoušek, M. Tancer, and U. Wagner, “A geometric proof of the colored Tverberg
theorem,” Discrete & Computational Geometry, vol. 47, no. 2. Springer,
pp. 245–265, 2012.
ista: Matoušek J, Tancer M, Wagner U. 2012. A geometric proof of the colored Tverberg
theorem. Discrete & Computational Geometry. 47(2), 245–265.
mla: Matoušek, Jiří, et al. “A Geometric Proof of the Colored Tverberg Theorem.”
Discrete & Computational Geometry, vol. 47, no. 2, Springer, 2012,
pp. 245–65, doi:10.1007/s00454-011-9368-2.
short: J. Matoušek, M. Tancer, U. Wagner, Discrete & Computational Geometry
47 (2012) 245–265.
date_created: 2018-12-11T11:57:39Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T06:57:29Z
day: '01'
doi: 10.1007/s00454-011-9368-2
extern: 1
intvolume: ' 47'
issue: '2'
month: '03'
page: 245 - 265
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '4468'
quality_controlled: 0
status: public
title: A geometric proof of the colored Tverberg theorem
type: journal_article
volume: 47
year: '2012'
...
---
_id: '2436'
abstract:
- lang: eng
text: 'Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial
complex K of dimension at most k, does there exist a (piecewise linear) embedding
of K into Rd? Known results easily imply the polynomiality of EMBEDk→2 (k = 1;
2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3. We
show that the celebrated result of Novikov on the algorithmic unsolvability of
recognizing the 5-sphere implies that EMBEDd→d and EMBED (d-1)→d are undecidable
for each d ≥ 5. Our main result is the NP-hardness of EMBED2→4 and, more generally,
of EMBED k→d for all k; d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3. These dimensions
fall outside the metastable range of a theorem of Haefliger and Weber, which characterizes
embeddability using the deleted product obstruction. Our reductions are based
on examples, due to Segal, Spież, Freedman, Krushkal, Teichner, and Skopenkov,
showing that outside the metastable range the deleted product obstruction is not
sufficient to characterize embeddability. '
acknowledgement: |-
We would like to thank Colin Rourke for explanations concerning PL topology and for examples showing the difference between PL embeddability and topological embeddability
mentioned in Section 2. We also thank Michael Joswig, Gil Kalai, Frank Lutz, Alexander Nabutovsky, and Robin Thomas for kindly answering our questions. The second author would also like to thank Sergio Cabello for helpful discussions regarding linear-time algorithms for EMBED2!2.
Finally, we are grateful to two anonymous referees for careful reading and valuable suggestions.
Research of U.Wagner was supported by the Swiss National Science Foundation (SNF Projects
200021-116741 and 200021-125309).
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Martin
full_name: Martin Tancer
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Uli Wagner
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes
in Rd. Journal of the European Mathematical Society. 2011;13(2):259-295.
doi:10.4171/JEMS/252
apa: Matoušek, J., Tancer, M., & Wagner, U. (2011). Hardness of embedding simplicial
complexes in Rd. Journal of the European Mathematical Society. European
Mathematical Society. https://doi.org/10.4171/JEMS/252
chicago: Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial
Complexes in Rd.” Journal of the European Mathematical Society. European
Mathematical Society, 2011. https://doi.org/10.4171/JEMS/252.
ieee: J. Matoušek, M. Tancer, and U. Wagner, “Hardness of embedding simplicial complexes
in Rd,” Journal of the European Mathematical Society, vol. 13, no. 2. European
Mathematical Society, pp. 259–295, 2011.
ista: Matoušek J, Tancer M, Wagner U. 2011. Hardness of embedding simplicial complexes
in Rd. Journal of the European Mathematical Society. 13(2), 259–295.
mla: Matoušek, Jiří, et al. “Hardness of Embedding Simplicial Complexes in Rd.”
Journal of the European Mathematical Society, vol. 13, no. 2, European
Mathematical Society, 2011, pp. 259–95, doi:10.4171/JEMS/252.
short: J. Matoušek, M. Tancer, U. Wagner, Journal of the European Mathematical Society
13 (2011) 259–295.
date_created: 2018-12-11T11:57:39Z
date_published: 2011-01-01T00:00:00Z
date_updated: 2021-01-12T06:57:28Z
day: '01'
doi: 10.4171/JEMS/252
extern: 1
intvolume: ' 13'
issue: '2'
month: '01'
page: 259 - 295
publication: Journal of the European Mathematical Society
publication_status: published
publisher: European Mathematical Society
publist_id: '4470'
quality_controlled: 0
status: public
title: Hardness of embedding simplicial complexes in Rd
type: journal_article
volume: 13
year: '2011'
...
---
_id: '2433'
abstract:
- lang: eng
text: 'Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial
complex K of dimension at most k, does there exist a (piecewise linear) embedding
of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1, 2;
the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3 (even
if k is not considered fixed). We show that the celebrated result of Novikov on
the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED d→d
and EMBED(d-1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness
of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k
≥ (2d - 2)/3.'
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Martin
full_name: Martin Tancer
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Uli Wagner
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes
in ℝd. In: SIAM; 2009:855-864.'
apa: 'Matoušek, J., Tancer, M., & Wagner, U. (2009). Hardness of embedding simplicial
complexes in ℝd (pp. 855–864). Presented at the SODA: Symposium on Discrete Algorithms,
SIAM.'
chicago: Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial
Complexes in ℝd,” 855–64. SIAM, 2009.
ieee: 'J. Matoušek, M. Tancer, and U. Wagner, “Hardness of embedding simplicial
complexes in ℝd,” presented at the SODA: Symposium on Discrete Algorithms, 2009,
pp. 855–864.'
ista: 'Matoušek J, Tancer M, Wagner U. 2009. Hardness of embedding simplicial complexes
in ℝd. SODA: Symposium on Discrete Algorithms, 855–864.'
mla: Matoušek, Jiří, et al. Hardness of Embedding Simplicial Complexes in ℝd.
SIAM, 2009, pp. 855–64.
short: J. Matoušek, M. Tancer, U. Wagner, in:, SIAM, 2009, pp. 855–864.
conference:
name: 'SODA: Symposium on Discrete Algorithms'
date_created: 2018-12-11T11:57:38Z
date_published: 2009-01-01T00:00:00Z
date_updated: 2021-01-12T06:57:27Z
day: '01'
extern: 1
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/0807.0336
month: '01'
oa: 1
page: 855 - 864
publication_status: published
publisher: SIAM
publist_id: '4476'
quality_controlled: 0
status: public
title: Hardness of embedding simplicial complexes in ℝd
type: conference
year: '2009'
...