---
_id: '1730'
abstract:
- lang: eng
text: How much cutting is needed to simplify the topology of a surface? We provide
bounds for several instances of this question, for the minimum length of topologically
non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial
map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).
Our work builds upon Riemannian systolic inequalities, which bound the minimum
length of non-trivial closed curves in terms of the genus and the area of the
surface. We first describe a systematic way to translate Riemannian systolic inequalities
to a discrete setting, and vice-versa. This implies a conjecture by Przytycka
and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993),
a number of new systolic inequalities in the discrete setting, and the fact that
a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s
systolic inequality for surfaces are essentially equivalent. We also discuss how
these proofs generalize to higher dimensions. Then we focus on topological decompositions
of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions
of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus
g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition.
Finally, we consider the problem of embedding a cut graph (or more generally a
cellular graph) with a given combinatorial map on a given surface. Using random
triangulations, we prove (essentially) that, for any choice of a combinatorial
map, there are some surfaces on which any cellular embedding with that combinatorial
map has length superlinear in the number of triangles of the triangulated combinatorial
surface. There is also a similar result for graphs embedded on polyhedral triangulations.
author:
- first_name: Éric
full_name: Colin De Verdière, Éric
last_name: Colin De Verdière
- first_name: Alfredo
full_name: Hubard, Alfredo
last_name: Hubard
- first_name: Arnaud N
full_name: De Mesmay, Arnaud N
id: 3DB2F25C-F248-11E8-B48F-1D18A9856A87
last_name: De Mesmay
citation:
ama: Colin De Verdière É, Hubard A, De Mesmay AN. Discrete systolic inequalities
and decompositions of triangulated surfaces. *Discrete & Computational Geometry*.
2015;53(3):587-620. doi:10.1007/s00454-015-9679-9
apa: Colin De Verdière, É., Hubard, A., & De Mesmay, A. N. (2015). Discrete
systolic inequalities and decompositions of triangulated surfaces. *Discrete
& Computational Geometry*, *53*(3), 587–620. https://doi.org/10.1007/s00454-015-9679-9
chicago: 'Colin De Verdière, Éric, Alfredo Hubard, and Arnaud N De Mesmay. “Discrete
Systolic Inequalities and Decompositions of Triangulated Surfaces.” *Discrete
& Computational Geometry* 53, no. 3 (2015): 587–620. https://doi.org/10.1007/s00454-015-9679-9.'
ieee: É. Colin De Verdière, A. Hubard, and A. N. De Mesmay, “Discrete systolic inequalities
and decompositions of triangulated surfaces,” *Discrete & Computational
Geometry*, vol. 53, no. 3, pp. 587–620, 2015.
ista: Colin De Verdière É, Hubard A, De Mesmay AN. 2015. Discrete systolic inequalities
and decompositions of triangulated surfaces. Discrete & Computational Geometry.
53(3), 587–620.
mla: Colin De Verdière, Éric, et al. “Discrete Systolic Inequalities and Decompositions
of Triangulated Surfaces.” *Discrete & Computational Geometry*, vol.
53, no. 3, Springer, 2015, pp. 587–620, doi:10.1007/s00454-015-9679-9.
short: É. Colin De Verdière, A. Hubard, A.N. De Mesmay, Discrete & Computational
Geometry 53 (2015) 587–620.
date_created: 2018-12-11T11:53:42Z
date_published: 2015-04-02T00:00:00Z
date_updated: 2019-01-24T13:04:22Z
day: '02'
department:
- _id: UlWa
doi: 10.1007/s00454-015-9679-9
intvolume: ' 53'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1408.4036
month: '04'
oa: 1
oa_version: Preprint
page: 587 - 620
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5397'
quality_controlled: '1'
status: public
title: Discrete systolic inequalities and decompositions of triangulated surfaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 53
year: '2015'
...
---
_id: '1595'
abstract:
- lang: eng
text: 'A drawing of a graph G is radial if the vertices of G are placed on concentric
circles C1, . . . , Ck with common center c, and edges are drawn radially: every
edge intersects every circle centered at c at most once. G is radial planar if
it has a radial embedding, that is, a crossing- free radial drawing. If the vertices
of G are ordered or partitioned into ordered levels (as they are for leveled graphs),
we require that the assignment of vertices to circles corresponds to the given
ordering or leveling. We show that a graph G is radial planar if G has a radial
drawing in which every two edges cross an even number of times; the radial embedding
has the same leveling as the radial drawing. In other words, we establish the
weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes
a result by Pach and Tóth.'
accept: '1'
acknowledgement: The research leading to these results has received funding from the
People Programme (Marie Curie Actions) of the European Union’s Seventh Framework
Programme (FP7/2007-2013) under REA grant agreement no [291734].
alternative_title:
- LNCS
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Michael
full_name: Pelsmajer, Michael
last_name: Pelsmajer
- first_name: Marcus
full_name: Schaefer, Marcus
last_name: Schaefer
citation:
ama: 'Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. In: Vol
9411. Springer; 2015:99-110. doi:10.1007/978-3-319-27261-0_9'
apa: 'Fulek, R., Pelsmajer, M., & Schaefer, M. (2015). Hanani-Tutte for radial
planarity (Vol. 9411, pp. 99–110). Presented at the GD: Graph Drawing and Network
Visualization, Los Angeles, CA, USA: Springer. https://doi.org/10.1007/978-3-319-27261-0_9'
chicago: Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte
for Radial Planarity,” 9411:99–110. Springer, 2015. https://doi.org/10.1007/978-3-319-27261-0_9.
ieee: 'R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,”
presented at the GD: Graph Drawing and Network Visualization, Los Angeles, CA,
USA, 2015, vol. 9411, pp. 99–110.'
ista: 'Fulek R, Pelsmajer M, Schaefer M. 2015. Hanani-Tutte for radial planarity.
GD: Graph Drawing and Network Visualization, LNCS, vol. 9411. 99–110.'
mla: Fulek, Radoslav, et al. *Hanani-Tutte for Radial Planarity*. Vol. 9411,
Springer, 2015, pp. 99–110, doi:10.1007/978-3-319-27261-0_9.
short: R. Fulek, M. Pelsmajer, M. Schaefer, in:, Springer, 2015, pp. 99–110.
conference:
end_date: 2015-09-26
location: Los Angeles, CA, USA
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2015-09-24
date_created: 2018-12-11T11:52:55Z
date_published: 2015-11-27T00:00:00Z
date_updated: 2020-02-19T10:23:46Z
day: '27'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/978-3-319-27261-0_9
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:36Z
date_updated: 2018-12-12T10:08:36Z
file_id: '4697'
file_name: IST-2016-594-v1+1_HTCylinder_GD_Revision.pdf
file_size: 330135
open_access: 1
relation: main_file
file_date_updated: 2018-12-12T10:08:36Z
intvolume: ' 9411'
language:
- iso: eng
month: '11'
oa_version: Submitted Version
page: 99 - 110
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication_status: published
publisher: Springer
publist_id: '5576'
pubrep_id: '594'
quality_controlled: '1'
related_material:
record:
- id: '1164'
relation: later_version
status: public
- id: '1113'
relation: later_version
status: public
status: public
title: Hanani-Tutte for radial planarity
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9411
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: 2020-01-21T11:55:30Z
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_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
status: public
title: Embeddability in the 3 sphere is decidable
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2184'
abstract:
- lang: eng
text: 'Given topological spaces X,Y, a fundamental problem of algebraic topology
is understanding the structure of all continuous maps X→ Y. We consider a computational
version, where X,Y are given as finite simplicial complexes, and the goal is to
compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem
in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected;
in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical
tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and
simplicial sets) with algorithmic tools from effective algebraic topology (locally
effective simplicial sets and objects with effective homology). In contrast, [X,Y]
is known to be uncomputable for general X,Y, since for X = S1 it includes a well
known undecidable problem: testing triviality of the fundamental group of Y. In
follow-up papers, the algorithm is shown to run in polynomial time for d fixed,
and extended to other problems, such as the extension problem, where we are given
a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or
computing the Z2-index-everything in the stable range. Outside the stable range,
the extension problem is undecidable.'
acknowledgement: The research by M. K. was supported by project GAUK 49209. The research
by M. K. was also supported by project 1M0545 by the Ministry of Education of the
Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague
(project P202/12/G061 of GACR). The research by U. W. was supported by the Swiss
National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).
article_number: '17 '
author:
- first_name: Martin
full_name: Čadek, Martin
last_name: Čadek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Francis
full_name: Sergeraert, Francis
last_name: Sergeraert
- first_name: Lukáš
full_name: Vokřínek, Lukáš
last_name: Vokřínek
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing
all maps into a sphere. *Journal of the ACM*. 2014;61(3). doi:10.1145/2597629
apa: Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner,
U. (2014). Computing all maps into a sphere. *Journal of the ACM*, *61*(3).
https://doi.org/10.1145/2597629
chicago: Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek,
and Uli Wagner. “Computing All Maps into a Sphere.” *Journal of the ACM*
61, no. 3 (2014). https://doi.org/10.1145/2597629.
ieee: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner,
“Computing all maps into a sphere,” *Journal of the ACM*, vol. 61, no. 3,
2014.
ista: Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing
all maps into a sphere. Journal of the ACM. 61(3), 17.
mla: Čadek, Martin, et al. “Computing All Maps into a Sphere.” *Journal of the
ACM*, vol. 61, no. 3, 17, ACM, 2014, doi:10.1145/2597629.
short: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal
of the ACM 61 (2014).
date_created: 2018-12-11T11:56:12Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2020-01-21T11:40:56Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2597629
intvolume: ' 61'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1105.6257
month: '05'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '4797'
quality_controlled: '1'
status: public
title: Computing all maps into a sphere
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2014'
...
---
_id: '7038'
accept: '1'
article_processing_charge: No
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Huszár K, Rolinek M. *Playful Math - An Introduction to Mathematical Games*.
IST Austria
apa: Huszár, K., & Rolinek, M. (n.d.). *Playful Math - An introduction to
mathematical games*. IST Austria.
chicago: Huszár, Kristóf, and Michal Rolinek. *Playful Math - An Introduction
to Mathematical Games*. IST Austria, n.d.
ieee: K. Huszár and M. Rolinek, *Playful Math - An introduction to mathematical
games*. IST Austria.
ista: Huszár K, Rolinek M. Playful Math - An introduction to mathematical games,
IST Austria, 5p.
mla: Huszár, Kristóf, and Michal Rolinek. *Playful Math - An Introduction to Mathematical
Games*. IST Austria.
short: K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games,
IST Austria, n.d.
date_created: 2019-11-18T15:57:05Z
date_published: 2014-06-30T00:00:00Z
date_updated: 2019-11-18T15:59:07Z
day: '30'
ddc:
- '510'
department:
- _id: VlKo
- _id: UlWa
file:
- access_level: open_access
content_type: application/pdf
creator: dernst
date_created: 2019-11-18T15:57:51Z
date_updated: 2019-11-18T15:57:51Z
file_id: '7039'
file_name: 2014_Playful_Math_Huszar.pdf
file_size: 511233
open_access: 1
relation: main_file
success: 1
file_date_updated: 2019-11-18T15:57:51Z
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '5'
publication_status: draft
publisher: IST Austria
status: public
title: Playful Math - An introduction to mathematical games
type: working_paper
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2154'
abstract:
- lang: eng
text: A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that
for every d there exists cd > 0 such that for every n-point set P ⊂ ℝd, some
point of ℝd is covered by at least (Formula presented.) of the d-simplices spanned
by the points of P. The largest possible value of cd has been the subject of ongoing
research. Recently Gromov improved the existing lower bounds considerably by introducing
a new, topological proof method. We provide an exposition of the combinatorial
component of Gromov's approach, in terms accessible to combinatorialists and discrete
geometers, and we investigate the limits of his method. In particular, we give
tighter bounds on the cofilling profiles for the (n - 1)-simplex. These bounds
yield a minor improvement over Gromov's lower bounds on cd for large d, but they
also show that the room for further improvement through the cofilling profiles
alone is quite small. We also prove a slightly better lower bound for c3 by an
approach using an additional structure besides the cofilling profiles. We formulate
a combinatorial extremal problem whose solution might perhaps lead to a tight
lower bound for cd.
acknowledgement: Swiss National Science Foundation (SNF 200021-125309, 200020-138230,
200020-12507)
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- 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, Wagner U. On Gromov’s method of selecting heavily covered points.
*Discrete & Computational Geometry*. 2014;52(1):1-33. doi:10.1007/s00454-014-9584-7
apa: Matoušek, J., & Wagner, U. (2014). On Gromov’s method of selecting heavily
covered points. *Discrete & Computational Geometry*, *52*(1), 1–33.
https://doi.org/10.1007/s00454-014-9584-7
chicago: 'Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily
Covered Points.” *Discrete & Computational Geometry* 52, no. 1 (2014):
1–33. https://doi.org/10.1007/s00454-014-9584-7.'
ieee: J. Matoušek and U. Wagner, “On Gromov’s method of selecting heavily covered
points,” *Discrete & Computational Geometry*, vol. 52, no. 1, pp. 1–33,
2014.
ista: Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered
points. Discrete & Computational Geometry. 52(1), 1–33.
mla: Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered
Points.” *Discrete & Computational Geometry*, vol. 52, no. 1, Springer,
2014, pp. 1–33, doi:10.1007/s00454-014-9584-7.
short: J. Matoušek, U. Wagner, Discrete & Computational Geometry 52 (2014) 1–33.
date_created: 2018-12-11T11:56:01Z
date_published: 2014-07-01T00:00:00Z
date_updated: 2019-08-02T12:37:37Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-014-9584-7
intvolume: ' 52'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1102.3515
month: '07'
oa: 1
oa_version: Submitted Version
page: 1 - 33
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '4852'
quality_controlled: '1'
status: public
title: On Gromov's method of selecting heavily covered points
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 52
year: '2014'
...
---
_id: '2159'
abstract:
- lang: eng
text: 'Motivated by topological Tverberg-type problems, we consider multiple (double,
triple, and higher multiplicity) selfintersection points of maps from finite simplicial
complexes (compact polyhedra) into ℝd and study conditions under which such multiple
points can be eliminated. The most classical case is that of embeddings (i.e.,
maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem,
the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary
condition for embeddability (namely, vanishing of the van Kampen ob-struction).
For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm
for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which
generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes
then one can successively remove these double points by local modifications of
the map f. One of the main tools is the famous Whitney trick that permits eliminating
pairs of double points of opposite intersection sign. We are interested in generalizing
this approach to intersection points of higher multiplicity. We call a point y
2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection
f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue
of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional
complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e.,
does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that
for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time
algorithm for deciding this (based on the vanishing of a cohomological obstruction,
as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney
trick: Given r pairwise disjoint simplices of K such that the intersection of
their images contains two r-fold Tverberg points y+ and y- of opposite intersection
sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper,
we plan to develop this further and present a generalization of the classical
Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability
of κ-complexes into ℝd for a wider range of dimensions) to intersection points
of higher multiplicity.'
accept: '1'
acknowledgement: Swiss National Science Foundation (Project SNSF-PP00P2-138948)
author:
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Mabillard I, Wagner U. Eliminating Tverberg points, I. An analogue of the
Whitney trick. In: *Proceedings of the Annual Symposium on Computational Geometry*.
ACM; 2014:171-180. doi:10.1145/2582112.2582134'
apa: 'Mabillard, I., & Wagner, U. (2014). Eliminating Tverberg points, I. An
analogue of the Whitney trick. In *Proceedings of the Annual Symposium on Computational
Geometry* (pp. 171–180). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582134'
chicago: Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue
of the Whitney Trick.” In *Proceedings of the Annual Symposium on Computational
Geometry*, 171–80. ACM, 2014. https://doi.org/10.1145/2582112.2582134.
ieee: I. Mabillard and U. Wagner, “Eliminating Tverberg points, I. An analogue of
the Whitney trick,” in *Proceedings of the Annual Symposium on Computational
Geometry*, Kyoto, Japan, 2014, pp. 171–180.
ista: 'Mabillard I, Wagner U. 2014. Eliminating Tverberg points, I. An analogue
of the Whitney trick. Proceedings of the Annual Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry 171–180.'
mla: Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue
of the Whitney Trick.” *Proceedings of the Annual Symposium on Computational
Geometry*, ACM, 2014, pp. 171–80, doi:10.1145/2582112.2582134.
short: I. Mabillard, U. Wagner, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 171–180.
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:03Z
date_published: 2014-06-08T00:00:00Z
date_updated: 2020-01-21T11:40:44Z
day: '08'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1145/2582112.2582134
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:12Z
date_updated: 2018-12-12T10:09:12Z
file_id: '4735'
file_name: IST-2016-534-v1+1_Eliminating_Tverberg_points_I._An_analogue_of_the_Whitney_trick.pdf
file_size: 914396
open_access: 1
relation: main_file
file_date_updated: 2018-12-12T10:09:12Z
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 171 - 180
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4847'
pubrep_id: '534'
quality_controlled: '1'
related_material:
record:
- id: '1123'
relation: dissertation_contains
status: public
status: public
title: Eliminating Tverberg points, I. An analogue of the Whitney trick
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '1842'
abstract:
- lang: eng
text: We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2
outerplanar triangulations in both convex and general cases. We also prove that
the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by
O(n3) and O(n10), in the convex and general case, respectively. We then apply
similar methods to prove an (Formula presented.) upper bound on the Ramsey number
of a path with n ordered vertices.
acknowledgement: Marek Krčál was supported by the ERC Advanced Grant No. 267165.
author:
- first_name: Josef
full_name: Cibulka, Josef
last_name: Cibulka
- first_name: Pu
full_name: Gao, Pu
last_name: Gao
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
- first_name: Tomáš
full_name: Valla, Tomáš
last_name: Valla
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
citation:
ama: Cibulka J, Gao P, Krcál M, Valla T, Valtr P. On the geometric ramsey number
of outerplanar graphs. *Discrete & Computational Geometry*. 2014;53(1):64-79.
doi:10.1007/s00454-014-9646-x
apa: Cibulka, J., Gao, P., Krcál, M., Valla, T., & Valtr, P. (2014). On the
geometric ramsey number of outerplanar graphs. *Discrete & Computational
Geometry*, *53*(1), 64–79. https://doi.org/10.1007/s00454-014-9646-x
chicago: 'Cibulka, Josef, Pu Gao, Marek Krcál, Tomáš Valla, and Pavel Valtr. “On
the Geometric Ramsey Number of Outerplanar Graphs.” *Discrete & Computational
Geometry* 53, no. 1 (2014): 64–79. https://doi.org/10.1007/s00454-014-9646-x.'
ieee: J. Cibulka, P. Gao, M. Krcál, T. Valla, and P. Valtr, “On the geometric ramsey
number of outerplanar graphs,” *Discrete & Computational Geometry*, vol.
53, no. 1, pp. 64–79, 2014.
ista: Cibulka J, Gao P, Krcál M, Valla T, Valtr P. 2014. On the geometric ramsey
number of outerplanar graphs. Discrete & Computational Geometry. 53(1), 64–79.
mla: Cibulka, Josef, et al. “On the Geometric Ramsey Number of Outerplanar Graphs.”
*Discrete & Computational Geometry*, vol. 53, no. 1, Springer, 2014,
pp. 64–79, doi:10.1007/s00454-014-9646-x.
short: J. Cibulka, P. Gao, M. Krcál, T. Valla, P. Valtr, Discrete & Computational
Geometry 53 (2014) 64–79.
date_created: 2018-12-11T11:54:18Z
date_published: 2014-11-14T00:00:00Z
date_updated: 2019-08-02T12:37:28Z
day: '14'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/s00454-014-9646-x
intvolume: ' 53'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1310.7004
month: '11'
oa: 1
oa_version: Submitted Version
page: 64 - 79
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '5260'
status: public
title: On the geometric ramsey number of outerplanar graphs
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 53
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
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: 2020-01-21T11:41:22Z
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
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: '2807'
abstract:
- lang: eng
text: 'We consider several basic problems of algebraic topology, with connections
to combinatorial and geometric questions, from the point of view of computational
complexity. The extension problem asks, given topological spaces X; Y , a subspace
A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X
→ Y . For computational purposes, we assume that X and Y are represented as finite
simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map.
In this generality the problem is undecidable, as follows from Novikov''s result
from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study
the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected;
informally, this means that Y has \no holes up to dimension k-1" (a basic
example of such a Y is the sphere Sk). We prove that, on the one hand, this problem
is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2,
we obtain an algorithm that solves the extension problem in polynomial time assuming
Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides
a classification of all extensions up to homotopy (continuous deformation). This
relies on results of our SODA 2012 paper, and the main new ingredient is a machinery
of objects with polynomial-time homology, which is a polynomial-time analog of
objects with effective homology developed earlier by Sergeraert et al. We also
consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected
Y . Their computability was established by Brown in 1957; we show that πk(Y )
can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick
proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where
Y is a cell complex with certain rather compact encoding. We strengthen his result
to #P-hardness for Y given as a simplicial complex. '
accept: '1'
author:
- first_name: Martin
full_name: Čadek, Martin
last_name: Čadek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Lukáš
full_name: Vokřínek, Lukáš
last_name: Vokřínek
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. Extending continuous maps:
Polynomiality and undecidability. In: *45th Annual ACM Symposium on Theory of
Computing*. ACM; 2013:595-604. doi:10.1145/2488608.2488683'
apa: 'Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., & Wagner, U. (2013).
Extending continuous maps: Polynomiality and undecidability. In *45th Annual
ACM Symposium on theory of computing* (pp. 595–604). Palo Alto, CA, United
States: ACM. https://doi.org/10.1145/2488608.2488683'
chicago: 'Čadek, Martin, Marek Krcál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner.
“Extending Continuous Maps: Polynomiality and Undecidability.” In *45th Annual
ACM Symposium on Theory of Computing*, 595–604. ACM, 2013. https://doi.org/10.1145/2488608.2488683.'
ieee: 'M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, and U. Wagner, “Extending continuous
maps: Polynomiality and undecidability,” in *45th Annual ACM Symposium on theory
of computing*, Palo Alto, CA, United States, 2013, pp. 595–604.'
ista: 'Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. 2013. Extending continuous
maps: Polynomiality and undecidability. 45th Annual ACM Symposium on theory of
computing. STOC: Symposium on the Theory of Computing 595–604.'
mla: 'Čadek, Martin, et al. “Extending Continuous Maps: Polynomiality and Undecidability.”
*45th Annual ACM Symposium on Theory of Computing*, ACM, 2013, pp. 595–604,
doi:10.1145/2488608.2488683.'
short: M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, U. Wagner, in:, 45th Annual
ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604.
conference:
end_date: 2013-06-04
location: Palo Alto, CA, United States
name: 'STOC: Symposium on the Theory of Computing'
start_date: 2013-06-01
date_created: 2018-12-11T11:59:42Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2019-08-02T12:37:51Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2488608.2488683
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:29Z
date_updated: 2018-12-12T10:14:29Z
file_id: '5081'
file_name: IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf
file_size: 447945
open_access: 1
relation: main_file
file_date_updated: 2018-12-12T10:14:29Z
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 595 - 604
publication: 45th Annual ACM Symposium on theory of computing
publication_status: published
publisher: ACM
publist_id: '4078'
pubrep_id: '533'
quality_controlled: '1'
status: public
title: 'Extending continuous maps: Polynomiality and undecidability'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...