[{"date_updated":"2023-08-02T06:43:27Z","citation":{"ista":"Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 42, 1317–1345.","chicago":"Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” <i>Combinatorica</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00493-021-4443-7\">https://doi.org/10.1007/s00493-021-4443-7</a>.","apa":"Kaluza, V., &#38; Tancer, M. (2022). Even maps, the Colin de Verdière number and representations of graphs. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-021-4443-7\">https://doi.org/10.1007/s00493-021-4443-7</a>","short":"V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.","ieee":"V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations of graphs,” <i>Combinatorica</i>, vol. 42. Springer Nature, pp. 1317–1345, 2022.","mla":"Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” <i>Combinatorica</i>, vol. 42, Springer Nature, 2022, pp. 1317–45, doi:<a href=\"https://doi.org/10.1007/s00493-021-4443-7\">10.1007/s00493-021-4443-7</a>.","ama":"Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations of graphs. <i>Combinatorica</i>. 2022;42:1317-1345. doi:<a href=\"https://doi.org/10.1007/s00493-021-4443-7\">10.1007/s00493-021-4443-7</a>"},"type":"journal_article","scopus_import":"1","month":"12","date_published":"2022-12-01T00:00:00Z","ddc":["514","516"],"doi":"10.1007/s00493-021-4443-7","article_type":"original","oa_version":"Preprint","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.","intvolume":"        42","title":"Even maps, the Colin de Verdière number and representations of graphs","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.1907.05055","open_access":"1"}],"article_processing_charge":"No","publication":"Combinatorica","year":"2022","language":[{"iso":"eng"}],"_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."}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","author":[{"id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","orcid":"0000-0002-2512-8698","last_name":"Kaluza","first_name":"Vojtech","full_name":"Kaluza, Vojtech"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin","full_name":"Tancer, Martin"}],"external_id":{"isi":["000798210100003"],"arxiv":["1907.05055"]},"volume":42,"publication_identifier":{"issn":["0209-9683"]},"department":[{"_id":"UlWa"}],"isi":1,"day":"01","arxiv":1,"oa":1,"quality_controlled":"1","page":"1317-1345","publisher":"Springer Nature","status":"public","date_created":"2021-11-25T13:49:16Z"},{"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"volume":164,"author":[{"full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683"},{"last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"arxiv":["2003.13536"]},"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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."}],"_id":"7992","date_created":"2020-06-22T09:14:20Z","status":"public","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"access_level":"open_access","file_name":"2020_LIPIcsSoCG_Patakova.pdf","date_created":"2020-06-23T06:45:52Z","checksum":"ce1c9194139a664fb59d1efdfc88eaae","date_updated":"2020-07-14T12:48:06Z","creator":"dernst","content_type":"application/pdf","file_size":750318,"file_id":"8004","relation":"main_file"}],"quality_controlled":"1","oa":1,"arxiv":1,"day":"01","department":[{"_id":"UlWa"}],"oa_version":"Published Version","file_date_updated":"2020-07-14T12:48:06Z","conference":{"end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry","start_date":"2020-06-22","location":"Zürich, Switzerland"},"doi":"10.4230/LIPIcs.SoCG.2020.62","alternative_title":["LIPIcs"],"ddc":["510"],"month":"06","date_published":"2020-06-01T00:00:00Z","scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"conference","citation":{"chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>.","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.","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","apa":"Patakova, Z., Tancer, M., &#38; Wagner, U. (2020). Barycentric cuts through a convex body. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">https://doi.org/10.4230/LIPIcs.SoCG.2020.62</a>","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.62\">10.4230/LIPIcs.SoCG.2020.62</a>"},"date_updated":"2021-01-12T08:16:23Z","has_accepted_license":"1","license":"https://creativecommons.org/licenses/by/4.0/","article_number":"62:1 - 62:16","language":[{"iso":"eng"}],"year":"2020","publication":"36th International Symposium on Computational Geometry","article_processing_charge":"No","title":"Barycentric cuts through a convex body","intvolume":"       164"},{"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"volume":99,"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."}],"_id":"184","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","file":[{"access_level":"open_access","file_name":"2018_LIPIcs_Goaoc.pdf","date_created":"2018-12-17T16:35:02Z","checksum":"d12bdd60f04a57307867704b5f930afd","date_updated":"2020-07-14T12:45:18Z","creator":"dernst","content_type":"application/pdf","file_size":718414,"file_id":"5725","relation":"main_file"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","page":"41:1 - 41:16","status":"public","date_created":"2018-12-11T11:45:04Z","day":"11","department":[{"_id":"UlWa"}],"quality_controlled":"1","oa":1,"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"related_material":{"record":[{"status":"public","relation":"later_version","id":"7108"}]},"publist_id":"7736","doi":"10.4230/LIPIcs.SoCG.2018.41","conference":{"end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","location":"Budapest, Hungary"},"oa_version":"Published Version","file_date_updated":"2020-07-14T12:45:18Z","citation":{"ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">10.4230/LIPIcs.SoCG.2018.41</a>","mla":"Goaoc, Xavier, et al. <i>Shellability Is NP-Complete</i>. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">10.4230/LIPIcs.SoCG.2018.41</a>.","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.","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.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2018). Shellability is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.41\">https://doi.org/10.4230/LIPIcs.SoCG.2018.41</a>.","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."},"has_accepted_license":"1","date_updated":"2023-09-06T11:10:57Z","type":"conference","month":"06","date_published":"2018-06-11T00:00:00Z","ddc":["516","000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"scopus_import":1,"language":[{"iso":"eng"}],"year":"2018","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","intvolume":"        99","title":"Shellability is NP-complete"},{"external_id":{"isi":["000425685900006"],"arxiv":["1402.0815"]},"author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"first_name":"Eric","last_name":"Sedgwick","full_name":"Sedgwick, Eric"},{"first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"}],"project":[{"call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"volume":65,"abstract":[{"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.","lang":"eng"}],"_id":"425","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","publisher":"ACM","status":"public","date_created":"2018-12-11T11:46:24Z","isi":1,"day":"01","department":[{"_id":"UlWa"}],"quality_controlled":"1","arxiv":1,"issue":"1","oa":1,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2157"}]},"doi":"10.1145/3078632","publist_id":"7398","article_type":"original","ec_funded":1,"oa_version":"Preprint","citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3078632\">https://doi.org/10.1145/3078632</a>","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (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.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” <i>Journal of the ACM</i>. ACM, 2018. <a href=\"https://doi.org/10.1145/3078632\">https://doi.org/10.1145/3078632</a>.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. <i>Journal of the ACM</i>. 2018;65(1). doi:<a href=\"https://doi.org/10.1145/3078632\">10.1145/3078632</a>","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” <i>Journal of the ACM</i>, vol. 65, no. 1. ACM, 2018.","mla":"Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” <i>Journal of the ACM</i>, vol. 65, no. 1, 5, ACM, 2018, doi:<a href=\"https://doi.org/10.1145/3078632\">10.1145/3078632</a>."},"date_updated":"2023-09-11T13:38:49Z","type":"journal_article","article_number":"5","month":"01","date_published":"2018-01-01T00:00:00Z","scopus_import":"1","publication":"Journal of the ACM","article_processing_charge":"No","year":"2018","language":[{"iso":"eng"}],"intvolume":"        65","title":"Embeddability in the 3-Sphere is decidable","main_file_link":[{"url":"https://arxiv.org/abs/1402.0815","open_access":"1"}]},{"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).","intvolume":"       222","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1610.09063"}],"title":"On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result","publication":"Israel Journal of Mathematics","language":[{"iso":"eng"}],"year":"2017","citation":{"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.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s11856-017-1607-7\">https://doi.org/10.1007/s11856-017-1607-7</a>.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-017-1607-7\">https://doi.org/10.1007/s11856-017-1607-7</a>","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel Journal of Mathematics 222 (2017) 841–866.","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result,” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2. Springer, pp. 841–866, 2017.","mla":"Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:<a href=\"https://doi.org/10.1007/s11856-017-1607-7\">10.1007/s11856-017-1607-7</a>.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. <i>Israel Journal of Mathematics</i>. 2017;222(2):841-866. doi:<a href=\"https://doi.org/10.1007/s11856-017-1607-7\">10.1007/s11856-017-1607-7</a>"},"date_updated":"2023-02-23T10:02:13Z","type":"journal_article","scopus_import":1,"date_published":"2017-10-01T00:00:00Z","month":"10","ec_funded":1,"related_material":{"record":[{"status":"public","id":"1511","relation":"earlier_version"}]},"publist_id":"7194","doi":"10.1007/s11856-017-1607-7","oa_version":"Preprint","department":[{"_id":"UlWa"}],"day":"01","oa":1,"issue":"2","quality_controlled":"1","page":"841 - 866","publisher":"Springer","status":"public","date_created":"2018-12-11T11:47:29Z","_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."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"first_name":"Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac"},{"full_name":"Paták, Pavel","last_name":"Paták","first_name":"Pavel"},{"full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"volume":222,"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734"}]},{"publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","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."}],"_id":"1411","project":[{"grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"volume":212,"author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Sedgwick","first_name":"Eric","full_name":"Sedgwick, Eric"},{"full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin"},{"first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"quality_controlled":"1","issue":"1","oa":1,"day":"01","department":[{"_id":"UlWa"}],"date_created":"2018-12-11T11:51:52Z","status":"public","publisher":"Springer","page":"37 - 79","month":"05","date_published":"2016-05-01T00:00:00Z","scopus_import":1,"type":"journal_article","date_updated":"2023-02-23T10:34:31Z","citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2016). Untangling two systems of noncrossing curves. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-016-1294-9\">https://doi.org/10.1007/s11856-016-1294-9</a>","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics 212 (2016) 37–79.","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.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” <i>Israel Journal of Mathematics</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s11856-016-1294-9\">https://doi.org/10.1007/s11856-016-1294-9</a>.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. <i>Israel Journal of Mathematics</i>. 2016;212(1):37-79. doi:<a href=\"https://doi.org/10.1007/s11856-016-1294-9\">10.1007/s11856-016-1294-9</a>","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1. Springer, pp. 37–79, 2016.","mla":"Matoušek, Jiří, et al. “Untangling Two Systems of Noncrossing Curves.” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:<a href=\"https://doi.org/10.1007/s11856-016-1294-9\">10.1007/s11856-016-1294-9</a>."},"oa_version":"Preprint","doi":"10.1007/s11856-016-1294-9","publist_id":"5796","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2244"}]},"title":"Untangling two systems of noncrossing curves","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.6475"}],"intvolume":"       212","acknowledgement":"Supported by the ERC Adv anced Grant No. 267165. ","language":[{"iso":"eng"}],"year":"2016","publication":"Israel Journal of Mathematics"},{"language":[{"iso":"eng"}],"year":"2015","title":"On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result","pubrep_id":"502","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).","oa_version":"Published Version","file_date_updated":"2020-07-14T12:44:59Z","publist_id":"5666","doi":"10.4230/LIPIcs.SOCG.2015.476","conference":{"end_date":"2015-06-25","name":"SoCG: Symposium on Computational Geometry","start_date":"2015-06-22","location":"Eindhoven, Netherlands"},"related_material":{"record":[{"status":"public","id":"610","relation":"later_version"}]},"alternative_title":["LIPIcs"],"ec_funded":1,"ddc":["510"],"month":"06","date_published":"2015-06-11T00:00:00Z","scopus_import":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"conference","citation":{"apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2015). On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result (Vol. 34, pp. 476–490). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>","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.","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.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result,” 34:476–90. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:476-490. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">10.4230/LIPIcs.SOCG.2015.476</a>","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.","mla":"Goaoc, Xavier, et al. <i>On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">10.4230/LIPIcs.SOCG.2015.476</a>."},"has_accepted_license":"1","date_updated":"2023-02-23T12:38:00Z","date_created":"2018-12-11T11:52:27Z","status":"public","file":[{"checksum":"0945811875351796324189312ca29e9e","date_created":"2018-12-12T10:11:18Z","file_name":"IST-2016-502-v1+1_42.pdf","access_level":"open_access","relation":"main_file","file_id":"4871","creator":"system","date_updated":"2020-07-14T12:44:59Z","file_size":636735,"content_type":"application/pdf"}],"page":"476 - 490","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","oa":1,"day":"11","department":[{"_id":"UlWa"}],"project":[{"call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"volume":"34 ","author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","first_name":"Isaac","last_name":"Mabillard","full_name":"Mabillard, Isaac"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"},{"first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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."}],"_id":"1511"},{"doi":"10.1007/s00454-015-9720-z","publist_id":"5457","oa_version":"Preprint","date_updated":"2021-01-12T06:52:32Z","citation":{"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 &#38; Computational Geometry. 54(3), 610–636.","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.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00454-015-9720-z\">https://doi.org/10.1007/s00454-015-9720-z</a>.","apa":"Karasev, R., Kynčl, J., Paták, P., Patakova, Z., &#38; Tancer, M. (2015). Bounds for Pach’s selection theorem and for the minimum solid angle in a simplex. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-015-9720-z\">https://doi.org/10.1007/s00454-015-9720-z</a>","short":"R. Karasev, J. Kynčl, P. Paták, Z. Patakova, M. Tancer, Discrete &#38; Computational Geometry 54 (2015) 610–636.","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,” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 3. Springer, pp. 610–636, 2015.","mla":"Karasev, Roman, et al. “Bounds for Pach’s Selection Theorem and for the Minimum Solid Angle in a Simplex.” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 3, Springer, 2015, pp. 610–36, doi:<a href=\"https://doi.org/10.1007/s00454-015-9720-z\">10.1007/s00454-015-9720-z</a>.","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. <i>Discrete &#38; Computational Geometry</i>. 2015;54(3):610-636. doi:<a href=\"https://doi.org/10.1007/s00454-015-9720-z\">10.1007/s00454-015-9720-z</a>"},"type":"journal_article","scopus_import":1,"date_published":"2015-10-01T00:00:00Z","month":"10","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"year":"2015","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.","intvolume":"        54","title":"Bounds for Pach's selection theorem and for the minimum solid angle in a simplex","main_file_link":[{"url":"http://arxiv.org/abs/1403.8147","open_access":"1"}],"author":[{"full_name":"Karasev, Roman","first_name":"Roman","last_name":"Karasev"},{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova"},{"full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"}],"volume":54,"_id":"1688","abstract":[{"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.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","page":"610 - 636","publisher":"Springer","status":"public","date_created":"2018-12-11T11:53:28Z","department":[{"_id":"UlWa"}],"day":"01","issue":"3","oa":1,"quality_controlled":"1"},{"oa_version":"Submitted Version","conference":{"location":"Kyoto, Japan","start_date":"2014-06-08","name":"SoCG: Symposium on Computational Geometry","end_date":"2014-06-11"},"publist_id":"4849","doi":"10.1145/2582112.2582137","author":[{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"full_name":"Sedgwick, Eric","first_name":"Eric","last_name":"Sedgwick"},{"full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714"},{"first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"related_material":{"record":[{"relation":"later_version","id":"425","status":"public"}]},"scopus_import":1,"publication_status":"published","date_published":"2014-06-01T00:00:00Z","month":"06","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"2157","type":"conference","date_updated":"2023-09-11T13:38:49Z","citation":{"ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere is decidable. In: <i>Proceedings of the Annual Symposium on Computational Geometry</i>. ACM; 2014:78-84. doi:<a href=\"https://doi.org/10.1145/2582112.2582137\">10.1145/2582112.2582137</a>","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3 sphere is decidable,” in <i>Proceedings of the Annual Symposium on Computational Geometry</i>, Kyoto, Japan, 2014, pp. 78–84.","mla":"Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.” <i>Proceedings of the Annual Symposium on Computational Geometry</i>, ACM, 2014, pp. 78–84, doi:<a href=\"https://doi.org/10.1145/2582112.2582137\">10.1145/2582112.2582137</a>.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2014). Embeddability in the 3 sphere is decidable. In <i>Proceedings of the Annual Symposium on Computational Geometry</i> (pp. 78–84). Kyoto, Japan: ACM. <a href=\"https://doi.org/10.1145/2582112.2582137\">https://doi.org/10.1145/2582112.2582137</a>","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 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.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3 Sphere Is Decidable.” In <i>Proceedings of the Annual Symposium on Computational Geometry</i>, 78–84. ACM, 2014. <a href=\"https://doi.org/10.1145/2582112.2582137\">https://doi.org/10.1145/2582112.2582137</a>."},"abstract":[{"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.","lang":"eng"}],"year":"2014","language":[{"iso":"eng"}],"date_created":"2018-12-11T11:56:02Z","status":"public","publication":"Proceedings of the Annual Symposium on Computational Geometry","page":"78 - 84","publisher":"ACM","oa":1,"title":"Embeddability in the 3 sphere is decidable","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1402.0815","open_access":"1"}],"department":[{"_id":"UlWa"}],"acknowledgement":"ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023  (SNSF-PP00P2-138948); Swiss National Science Foundation  (SNSF-200020-138230).","day":"01"},{"external_id":{"arxiv":["1302.6475"]},"author":[{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"first_name":"Eric","last_name":"Sedgwick","full_name":"Sedgwick, Eric"},{"full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948"}],"volume":8242,"abstract":[{"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 &quot;untangle&quot; 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 (&quot;holes&quot;), 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. ","lang":"eng"}],"_id":"2244","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"472 - 483","publisher":"Springer","date_created":"2018-12-11T11:56:32Z","status":"public","day":"01","series_title":"Lecture Notes in Computer Science","department":[{"_id":"UlWa"}],"quality_controlled":"1","oa":1,"arxiv":1,"doi":"10.1007/978-3-319-03841-4_41","conference":{"location":"Bordeaux, France","end_date":"2013-09-25","name":"GD: Graph Drawing and Network Visualization","start_date":"2013-09-23"},"publist_id":"4707","related_material":{"record":[{"status":"public","id":"1411","relation":"later_version"}]},"alternative_title":["LNCS"],"oa_version":"Preprint","type":"conference","citation":{"mla":"Matoušek, Jiří, et al. <i>Untangling Two Systems of Noncrossing Curves</i>. Vol. 8242, Springer, 2013, pp. 472–83, doi:<a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">10.1007/978-3-319-03841-4_41</a>.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. 2013;8242:472-483. doi:<a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">10.1007/978-3-319-03841-4_41</a>","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">https://doi.org/10.1007/978-3-319-03841-4_41</a>.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of noncrossing curves. 8242, 472–483.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2013). Untangling two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network Visualization, Bordeaux, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">https://doi.org/10.1007/978-3-319-03841-4_41</a>"},"date_updated":"2023-02-21T17:03:07Z","date_published":"2013-09-01T00:00:00Z","month":"09","scopus_import":1,"year":"2013","language":[{"iso":"eng"}],"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.","title":"Untangling two systems of noncrossing curves","main_file_link":[{"url":"http://arxiv.org/abs/1302.6475","open_access":"1"}],"intvolume":"      8242"},{"author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Martin Tancer"},{"full_name":"Uli Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"}],"publist_id":"4468","doi":"10.1007/s00454-011-9368-2","volume":47,"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."}],"date_updated":"2021-01-12T06:57:29Z","citation":{"mla":"Matoušek, Jiří, et al. “A Geometric Proof of the Colored Tverberg Theorem.” <i>Discrete &#38; Computational Geometry</i>, vol. 47, no. 2, Springer, 2012, pp. 245–65, doi:<a href=\"https://doi.org/10.1007/s00454-011-9368-2\">10.1007/s00454-011-9368-2</a>.","ieee":"J. Matoušek, M. Tancer, and U. Wagner, “A geometric proof of the colored Tverberg theorem,” <i>Discrete &#38; Computational Geometry</i>, vol. 47, no. 2. Springer, pp. 245–265, 2012.","ama":"Matoušek J, Tancer M, Wagner U. A geometric proof of the colored Tverberg theorem. <i>Discrete &#38; Computational Geometry</i>. 2012;47(2):245-265. doi:<a href=\"https://doi.org/10.1007/s00454-011-9368-2\">10.1007/s00454-011-9368-2</a>","chicago":"Matoušek, Jiří, Martin Tancer, and Uli Wagner. “A Geometric Proof of the Colored Tverberg Theorem.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2012. <a href=\"https://doi.org/10.1007/s00454-011-9368-2\">https://doi.org/10.1007/s00454-011-9368-2</a>.","ista":"Matoušek J, Tancer M, Wagner U. 2012. A geometric proof of the colored Tverberg theorem. Discrete &#38; Computational Geometry. 47(2), 245–265.","short":"J. Matoušek, M. Tancer, U. Wagner, Discrete &#38; Computational Geometry 47 (2012) 245–265.","apa":"Matoušek, J., Tancer, M., &#38; Wagner, U. (2012). A geometric proof of the colored Tverberg theorem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-011-9368-2\">https://doi.org/10.1007/s00454-011-9368-2</a>"},"type":"journal_article","_id":"2438","month":"03","date_published":"2012-03-01T00:00:00Z","publication_status":"published","extern":1,"publisher":"Springer","page":"245 - 265","publication":"Discrete & Computational Geometry","status":"public","date_created":"2018-12-11T11:57:39Z","year":"2012","day":"01","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). ","intvolume":"        47","title":"A geometric proof of the colored Tverberg theorem","quality_controlled":0,"issue":"2"},{"volume":13,"author":[{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Martin Tancer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}],"publist_id":"4470","doi":"10.4171/JEMS/252","date_published":"2011-01-01T00:00:00Z","month":"01","publication_status":"published","_id":"2436","date_updated":"2021-01-12T06:57:28Z","citation":{"apa":"Matoušek, J., Tancer, M., &#38; Wagner, U. (2011). Hardness of embedding simplicial complexes in Rd. <i>Journal of the European Mathematical Society</i>. European Mathematical Society. <a href=\"https://doi.org/10.4171/JEMS/252\">https://doi.org/10.4171/JEMS/252</a>","short":"J. Matoušek, M. Tancer, U. Wagner, Journal of the European Mathematical Society 13 (2011) 259–295.","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.","chicago":"Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial Complexes in Rd.” <i>Journal of the European Mathematical Society</i>. European Mathematical Society, 2011. <a href=\"https://doi.org/10.4171/JEMS/252\">https://doi.org/10.4171/JEMS/252</a>.","ama":"Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in Rd. <i>Journal of the European Mathematical Society</i>. 2011;13(2):259-295. doi:<a href=\"https://doi.org/10.4171/JEMS/252\">10.4171/JEMS/252</a>","ieee":"J. Matoušek, M. Tancer, and U. Wagner, “Hardness of embedding simplicial complexes in Rd,” <i>Journal of the European Mathematical Society</i>, vol. 13, no. 2. European Mathematical Society, pp. 259–295, 2011.","mla":"Matoušek, Jiří, et al. “Hardness of Embedding Simplicial Complexes in Rd.” <i>Journal of the European Mathematical Society</i>, vol. 13, no. 2, European Mathematical Society, 2011, pp. 259–95, doi:<a href=\"https://doi.org/10.4171/JEMS/252\">10.4171/JEMS/252</a>."},"abstract":[{"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. ","lang":"eng"}],"type":"journal_article","year":"2011","status":"public","date_created":"2018-12-11T11:57:39Z","page":"259 - 295","publisher":"European Mathematical Society","publication":"Journal of the European Mathematical Society","extern":1,"issue":"2","intvolume":"        13","quality_controlled":0,"title":"Hardness of embedding simplicial complexes in Rd","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\nmentioned 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.\nFinally, we are grateful to two anonymous referees for careful reading and valuable suggestions.\nResearch of U.Wagner was supported by the Swiss National Science Foundation (SNF Projects\n200021-116741 and 200021-125309).","day":"01"},{"citation":{"apa":"Matoušek, J., Tancer, M., &#38; Wagner, U. (2009). Hardness of embedding simplicial complexes in ℝd (pp. 855–864). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","short":"J. Matoušek, M. Tancer, U. Wagner, in:, SIAM, 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.","chicago":"Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial Complexes in ℝd,” 855–64. SIAM, 2009.","ama":"Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in ℝd. In: SIAM; 2009:855-864.","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.","mla":"Matoušek, Jiří, et al. <i>Hardness of Embedding Simplicial Complexes in ℝd</i>. SIAM, 2009, pp. 855–64."},"date_updated":"2021-01-12T06:57:27Z","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."}],"type":"conference","_id":"2433","date_published":"2009-01-01T00:00:00Z","month":"01","publication_status":"published","author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"full_name":"Martin Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Tancer","orcid":"0000-0002-1191-6714"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Uli Wagner"}],"conference":{"name":"SODA: Symposium on Discrete Algorithms"},"publist_id":"4476","day":"01","title":"Hardness of embedding simplicial complexes in ℝd","quality_controlled":0,"main_file_link":[{"url":"http://arxiv.org/abs/0807.0336","open_access":"1"}],"oa":1,"extern":1,"page":"855 - 864","publisher":"SIAM","status":"public","date_created":"2018-12-11T11:57:38Z","year":"2009"}]