9 Search Results for "Tancer, Martin"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.1
Geometric Embeddability of Complexes Is ∃ℝ-Complete

Authors: Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We show that the decision problem of determining whether a given (abstract simplicial) k-complex has a geometric embedding in ℝ^d is complete for the Existential Theory of the Reals for all d ≥ 3 and k ∈ {d-1,d}. Consequently, the problem is polynomial time equivalent to determining whether a polynomial equation system has a real solution and other important problems from various fields related to packing, Nash equilibria, minimum convex covers, the Art Gallery Problem, continuous constraint satisfaction problems, and training neural networks. Moreover, this implies NP-hardness and constitutes the first hardness result for the algorithmic problem of geometric embedding (abstract simplicial) complexes. This complements recent breakthroughs for the computational complexity of piece-wise linear embeddability.
Cite as

Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Geometric Embeddability of Complexes Is ∃ℝ-Complete. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2023.1,
  author =	{Abrahamsen, Mikkel and Kleist, Linda and Miltzow, Tillmann},
  title =	{{Geometric Embeddability of Complexes Is \exists\mathbb{R}-Complete}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.1},
  URN =		{urn:nbn:de:0030-drops-178518},
  doi =		{10.4230/LIPIcs.SoCG.2023.1},
  annote =	{Keywords: simplicial complex, geometric embedding, linear embedding, hypergraph, recognition, existential theory of the reals}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.88
Parameterized Complexity of Untangling Knots

Authors: Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that the II^- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from Minimum axiom set.
Cite as

Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer. Parameterized Complexity of Untangling Knots. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{legrandduchesne_et_al:LIPIcs.ICALP.2022.88,
  author =	{Legrand-Duchesne, Cl\'{e}ment and Rai, Ashutosh and Tancer, Martin},
  title =	{{Parameterized Complexity of Untangling Knots}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{88:1--88:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.88},
  URN =		{urn:nbn:de:0030-drops-164296},
  doi =		{10.4230/LIPIcs.ICALP.2022.88},
  annote =	{Keywords: unknot recognition, parameterized complexity, Reidemeister moves, W\lbrackP\rbrack-complete}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.19
Optimal Bounds for the Colorful Fractional Helly Theorem

Authors: Denys Bulavka, Afshin Goodarzi, and Martin Tancer

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: for every α ∈ (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ∈ (0, 1] with the following property. Let ℱ₁, … , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n₁, … , n_{d+1}, respectively. If at least α n₁ n₂ ⋯ n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ∈ [d+1] such that ℱ_i contains a subfamily of size at least β_{col} n_i with a nonempty intersection. (A colorful (d+1)-tuple is a (d+1)-tuple (F₁, … , F_{d+1}) such that F_i belongs to ℱ_i for every i.) The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with β_{col} = α/(d+1). In 2017 Kim proved the theorem with better function β_{col}, which in particular tends to 1 when α tends to 1. Kim also conjectured what is the optimal bound for β_{col}(α, d) and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984. We verify Kim’s conjecture by extending Kalai’s approach to the colorful scenario. Moreover, we obtain optimal bounds also in a more general setting when we allow several sets of the same color.
Cite as

Denys Bulavka, Afshin Goodarzi, and Martin Tancer. Optimal Bounds for the Colorful Fractional Helly Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bulavka_et_al:LIPIcs.SoCG.2021.19,
  author =	{Bulavka, Denys and Goodarzi, Afshin and Tancer, Martin},
  title =	{{Optimal Bounds for the Colorful Fractional Helly Theorem}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.19},
  URN =		{urn:nbn:de:0030-drops-138186},
  doi =		{10.4230/LIPIcs.SoCG.2021.19},
  annote =	{Keywords: colorful fractional Helly theorem, d-collapsible, exterior algebra, d-representable}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.62
Barycentric Cuts Through a Convex Body

Authors: Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
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.
Cite as

Zuzana Patáková, Martin Tancer, and Uli Wagner. Barycentric Cuts Through a Convex Body. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{patakova_et_al:LIPIcs.SoCG.2020.62,
  author =	{Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{Barycentric Cuts Through a Convex Body}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{62:1--62:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.62},
  URN =		{urn:nbn:de:0030-drops-122201},
  doi =		{10.4230/LIPIcs.SoCG.2020.62},
  annote =	{Keywords: convex body, barycenter, Tukey depth, smooth manifold, critical points}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.49
The Unbearable Hardness of Unknotting

Authors: Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, and Martin Tancer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We prove that deciding if a diagram of the unknot can be untangled using at most k Reidemeister moves (where k is part of the input) is NP-hard. We also prove that several natural questions regarding links in the 3-sphere are NP-hard, including detecting whether a link contains a trivial sublink with n components, computing the unlinking number of a link, and computing a variety of link invariants related to four-dimensional topology (such as the 4-ball Euler characteristic, the slicing number, and the 4-dimensional clasp number).
Cite as

Arnaud de Mesmay, Yo'av Rieck, Eric Sedgwick, and Martin Tancer. The Unbearable Hardness of Unknotting. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{demesmay_et_al:LIPIcs.SoCG.2019.49,
  author =	{de Mesmay, Arnaud and Rieck, Yo'av and Sedgwick, Eric and Tancer, Martin},
  title =	{{The Unbearable Hardness of Unknotting}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.49},
  URN =		{urn:nbn:de:0030-drops-104530},
  doi =		{10.4230/LIPIcs.SoCG.2019.49},
  annote =	{Keywords: Knot, Link, NP-hard, Reidemeister move, Unknot recognition, Unlinking number, intermediate invariants}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.41
Shellability is NP-Complete

Authors: Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
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.
Cite as

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Shellability is NP-Complete. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SoCG.2018.41,
  author =	{Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{Shellability is NP-Complete}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{41:1--41:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.41},
  URN =		{urn:nbn:de:0030-drops-87542},
  doi =		{10.4230/LIPIcs.SoCG.2018.41},
  annote =	{Keywords: Shellability, simplicial complexes, NP-completeness, collapsibility}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.43
Shortest Path Embeddings of Graphs on Surfaces

Authors: Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding. The main question addressed in this paper is whether given a closed surface S, there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g, there exist graphs G embeddable into the orientable surface of genus g, such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G, where the probability measure is proportional to the Weil-Petersson volume on moduli space. Finally, we construct a hyperbolic metric on every orientable surface S of genus g, such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O(g) shortest paths.
Cite as

Alfredo Hubard, Vojtech Kaluža, Arnaud de Mesmay, and Martin Tancer. Shortest Path Embeddings of Graphs on Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hubard_et_al:LIPIcs.SoCG.2016.43,
  author =	{Hubard, Alfredo and Kalu\v{z}a, Vojtech and de Mesmay, Arnaud and Tancer, Martin},
  title =	{{Shortest Path Embeddings of Graphs on Surfaces}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.43},
  URN =		{urn:nbn:de:0030-drops-59356},
  doi =		{10.4230/LIPIcs.SoCG.2016.43},
  annote =	{Keywords: Graph embedding, surface, shortest path, crossing number, hyperbolic geometry}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.476
On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result

Authors: Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
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.
Cite as

Xavier Goaoc, Isaac Mabillard, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 476-490, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.476,
  author =	{Goaoc, Xavier and Mabillard, Isaac and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{476--490},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.476},
  URN =		{urn:nbn:de:0030-drops-51256},
  doi =		{10.4230/LIPIcs.SOCG.2015.476},
  annote =	{Keywords: Heawood Inequality, Embeddings, Van Kampen–Flores, Manifolds}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.507
Bounding Helly Numbers via Betti Numbers

Authors: Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.
Cite as

Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner. Bounding Helly Numbers via Betti Numbers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 507-521, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.507,
  author =	{Goaoc, Xavier and Pat\'{a}k, Pavel and Pat\'{a}kov\'{a}, Zuzana and Tancer, Martin and Wagner, Uli},
  title =	{{Bounding Helly Numbers via Betti Numbers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{507--521},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.507},
  URN =		{urn:nbn:de:0030-drops-51297},
  doi =		{10.4230/LIPIcs.SOCG.2015.507},
  annote =	{Keywords: Helly-type theorem, Ramsey’s theorem, Embedding of simplicial complexes, Homological almost-embedding, Betti numbers}
}
  • Refine by Author
  • 8 Tancer, Martin
  • 4 Patáková, Zuzana
  • 4 Wagner, Uli
  • 3 Goaoc, Xavier
  • 3 Paták, Pavel
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Geometric topology
  • 2 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Betti numbers
  • 1 Embedding of simplicial complexes
  • 1 Embeddings
  • 1 Graph embedding
  • 1 Heawood Inequality
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 2 2015
  • 1 2016
  • 1 2018
  • 1 2019
  • 1 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact