[{"isi":1,"day":"27","department":[{"_id":"UlWa"}],"quality_controlled":"1","arxiv":1,"oa":1,"publisher":"Springer Nature","status":"public","date_created":"2023-08-06T22:01:12Z","abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2."}],"_id":"13974","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"epub_ahead","external_id":{"isi":["001038546500001"],"arxiv":["1812.04911"]},"author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"first_name":"Bernd","last_name":"Gärtner","full_name":"Gärtner, Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"last_name":"Valtr","first_name":"Pavel","full_name":"Valtr, Pavel"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M02281"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"acknowledgement":"Part of the research leading to this paper was done during the 16th Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018. We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank Stefan Felsner and Manfred Scheucher for finding, communicating the example from Sect. 3.3, and the kind permission to include their visualization of the point set. We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund (FWF), Project  M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P. Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation (GAČR).","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1812.04911"}],"title":"The crossing Tverberg theorem","article_processing_charge":"No","publication":"Discrete and Computational Geometry","language":[{"iso":"eng"}],"year":"2023","citation":{"short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2023). The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-023-00532-x\">https://doi.org/10.1007/s00454-023-00532-x</a>.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. <i>Discrete and Computational Geometry</i>. 2023. doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>Discrete and Computational Geometry</i>, Springer Nature, 2023, doi:<a href=\"https://doi.org/10.1007/s00454-023-00532-x\">10.1007/s00454-023-00532-x</a>.","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023."},"date_updated":"2023-12-13T12:03:35Z","type":"journal_article","month":"07","date_published":"2023-07-27T00:00:00Z","scopus_import":"1","related_material":{"record":[{"id":"6647","relation":"earlier_version","status":"public"}]},"doi":"10.1007/s00454-023-00532-x","article_type":"original","oa_version":"Preprint"},{"publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"volume":256,"external_id":{"isi":["001081646400010"]},"author":[{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wild, Pascal","last_name":"Wild","first_name":"Pascal","id":"4C20D868-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We prove the following quantitative Borsuk–Ulam-type result (an equivariant analogue of Gromov’s Topological Overlap Theorem): Let X be a free ℤ/2-complex of dimension d with coboundary expansion at least ηk in dimension 0 ≤ k < d. Then for every equivariant map F: X →ℤ/2 ℝd, the fraction of d-simplices σ of X with 0 ∈ F (σ) is at least 2−d Π d−1k=0ηk.\r\n\r\nAs an application, we show that for every sufficiently thick d-dimensional spherical building Y and every map f: Y → ℝ2d, we have f(σ) ∩ f(τ) ≠ ∅ for a constant fraction μd > 0 of pairs {σ, τ} of d-simplices of Y. In particular, such complexes are non-embeddable into ℝ2d, which proves a conjecture of Tancer and Vorwerk for sufficiently thick spherical buildings.\r\n\r\nWe complement these results by upper bounds on the coboundary expansion of two families of simplicial complexes; this indicates some limitations to the bounds one can obtain by straighforward applications of the quantitative Borsuk–Ulam theorem. Specifically, we prove\r\n\r\n• an upper bound of (d + 1)/2d on the normalized (d − 1)-th coboundary expansion constant of complete (d + 1)-partite d-dimensional complexes (under a mild divisibility assumption on the sizes of the parts); and\r\n\r\n• an upper bound of (d + 1)/2d + ε on the normalized (d − 1)-th coboundary expansion of the d-dimensional spherical building associated with GLd+2(Fq) for any ε > 0 and sufficiently large q. This disproves, in a rather strong sense, a conjecture of Lubotzky, Meshulam and Mozes.","lang":"eng"}],"_id":"14445","date_created":"2023-10-22T22:01:14Z","status":"public","file":[{"file_size":623787,"content_type":"application/pdf","creator":"dernst","date_updated":"2023-10-31T11:20:31Z","relation":"main_file","file_id":"14475","file_name":"2023_IsraelJourMath_Wagner.pdf","access_level":"open_access","success":1,"checksum":"fbb05619fe4b650f341cc730425dd9c3","date_created":"2023-10-31T11:20:31Z"}],"publisher":"Springer Nature","page":"675-717","quality_controlled":"1","issue":"2","oa":1,"day":"01","isi":1,"department":[{"_id":"UlWa"}],"oa_version":"Published Version","file_date_updated":"2023-10-31T11:20:31Z","doi":"10.1007/s11856-023-2521-9","article_type":"original","ddc":["510"],"month":"09","date_published":"2023-09-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":"journal_article","date_updated":"2023-12-13T13:09:07Z","has_accepted_license":"1","citation":{"mla":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:<a href=\"https://doi.org/10.1007/s11856-023-2521-9\">10.1007/s11856-023-2521-9</a>.","ieee":"U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes,” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2. Springer Nature, pp. 675–717, 2023.","ama":"Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. <i>Israel Journal of Mathematics</i>. 2023;256(2):675-717. doi:<a href=\"https://doi.org/10.1007/s11856-023-2521-9\">10.1007/s11856-023-2521-9</a>","chicago":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s11856-023-2521-9\">https://doi.org/10.1007/s11856-023-2521-9</a>.","ista":"Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717.","short":"U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.","apa":"Wagner, U., &#38; Wild, P. (2023). Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-023-2521-9\">https://doi.org/10.1007/s11856-023-2521-9</a>"},"language":[{"iso":"eng"}],"year":"2023","publication":"Israel Journal of Mathematics","article_processing_charge":"Yes (via OA deal)","title":"Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes","intvolume":"       256"},{"publisher":"Springer Nature","page":"1133-1154","status":"public","date_created":"2022-02-20T23:01:35Z","isi":1,"day":"01","department":[{"_id":"UlWa"}],"quality_controlled":"1","arxiv":1,"oa":1,"external_id":{"arxiv":["2003.13536"],"isi":["000750681500001"]},"author":[{"full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"volume":68,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"abstract":[{"lang":"eng","text":"Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p0 is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n≥2, there are always at least three distinct barycentric cuts through the point p0∈K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p0 are guaranteed if n≥3."}],"_id":"10776","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","publication":"Discrete and Computational Geometry","article_processing_charge":"No","year":"2022","language":[{"iso":"eng"}],"acknowledgement":"The work by Zuzana Patáková has been partially supported by Charles University Research Center Program No. UNCE/SCI/022, and part of it was done during her research stay at IST Austria. The work by Martin Tancer is supported by the GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and UNCE/SCI/004.","intvolume":"        68","title":"Barycentric cuts through a convex body","main_file_link":[{"url":"https://arxiv.org/abs/2003.13536","open_access":"1"}],"article_type":"original","doi":"10.1007/s00454-021-00364-7","oa_version":"Preprint","citation":{"ista":"Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body. Discrete and Computational Geometry. 68, 1133–1154.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-021-00364-7\">https://doi.org/10.1007/s00454-021-00364-7</a>.","apa":"Patakova, Z., Tancer, M., &#38; Wagner, U. (2022). Barycentric cuts through a convex body. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-021-00364-7\">https://doi.org/10.1007/s00454-021-00364-7</a>","short":"Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68 (2022) 1133–1154.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” <i>Discrete and Computational Geometry</i>, vol. 68. Springer Nature, pp. 1133–1154, 2022.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>Discrete and Computational Geometry</i>, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:<a href=\"https://doi.org/10.1007/s00454-021-00364-7\">10.1007/s00454-021-00364-7</a>.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. <i>Discrete and Computational Geometry</i>. 2022;68:1133-1154. doi:<a href=\"https://doi.org/10.1007/s00454-021-00364-7\">10.1007/s00454-021-00364-7</a>"},"date_updated":"2023-08-02T14:38:58Z","type":"journal_article","date_published":"2022-12-01T00:00:00Z","month":"12","scopus_import":"1"},{"abstract":[{"text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.","lang":"eng"}],"_id":"12129","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","author":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"external_id":{"isi":["000883222200003"]},"volume":68,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"isi":1,"day":"14","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"department":[{"_id":"UlWa"}],"quality_controlled":"1","oa":1,"issue":"4","page":"1227-1284","file":[{"content_type":"application/pdf","file_size":1747581,"creator":"dernst","date_updated":"2023-01-23T11:10:03Z","file_id":"12345","relation":"main_file","access_level":"open_access","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","success":1,"date_created":"2023-01-23T11:10:03Z","checksum":"307e879d09e52eddf5b225d0aaa9213a"}],"publisher":"Springer Nature","status":"public","date_created":"2023-01-12T12:02:28Z","citation":{"short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 68 (2022) 1227–1284.","apa":"Wagner, U., &#38; Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>.","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete &#38; Computational Geometry. 68(4), 1227–1284.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. 2022;68(4):1227-1284. doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022."},"has_accepted_license":"1","date_updated":"2023-08-04T08:51:08Z","type":"journal_article","month":"11","date_published":"2022-11-14T00:00:00Z","ddc":["510"],"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","related_material":{"record":[{"relation":"earlier_version","id":"7807","status":"public"},{"status":"public","id":"7990","relation":"earlier_version"}]},"doi":"10.1007/s00454-022-00436-2","article_type":"original","oa_version":"Published Version","file_date_updated":"2023-01-23T11:10:03Z","acknowledgement":"This is a full and revised version of [38] (on partial triangulations) in Proceedings of the 36th Annual International Symposium on Computational Geometry (SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt, Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on full triangulations. Research was supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681, and by IST Austria and Berlin Free University during a sabbatical stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger and Valentin Stoppiello for carefully reading earlier versions and for many helpful comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology Zürich","intvolume":"        68","title":"Connectivity of triangulation flip graphs in the plane","article_processing_charge":"No","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"year":"2022"},{"volume":438,"publication_identifier":{"issn":["0037-9484"],"eissn":["2102-622X"]},"oa_version":"None","author":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli"}],"doi":"10.24033/ast.1188","article_type":"original","scopus_import":"1","date_published":"2022-01-01T00:00:00Z","month":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","_id":"14381","citation":{"chicago":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” <i>Bulletin de La Societe Mathematique de France</i>. Societe Mathematique de France, 2022. <a href=\"https://doi.org/10.24033/ast.1188\">https://doi.org/10.24033/ast.1188</a>.","ista":"Wagner U. 2022. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de la Societe Mathematique de France. 438, 281–294.","short":"U. Wagner, Bulletin de La Societe Mathematique de France 438 (2022) 281–294.","apa":"Wagner, U. (2022). High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). <i>Bulletin de La Societe Mathematique de France</i>. Societe Mathematique de France. <a href=\"https://doi.org/10.24033/ast.1188\">https://doi.org/10.24033/ast.1188</a>","mla":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” <i>Bulletin de La Societe Mathematique de France</i>, vol. 438, Societe Mathematique de France, 2022, pp. 281–94, doi:<a href=\"https://doi.org/10.24033/ast.1188\">10.24033/ast.1188</a>.","ieee":"U. Wagner, “High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others),” <i>Bulletin de la Societe Mathematique de France</i>, vol. 438. Societe Mathematique de France, pp. 281–294, 2022.","ama":"Wagner U. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). <i>Bulletin de la Societe Mathematique de France</i>. 2022;438:281-294. doi:<a href=\"https://doi.org/10.24033/ast.1188\">10.24033/ast.1188</a>"},"date_updated":"2023-10-03T08:04:03Z","abstract":[{"text":"Expander graphs (sparse but highly connected graphs) have, since their inception, been the source of deep links between Mathematics and Computer Science as well as applications to other areas. In recent years, a fascinating theory of high-dimensional expanders has begun to emerge, which is still in a formative stage but has nonetheless already lead to a number of striking results. Unlike for graphs, in higher dimensions there is a rich array of non-equivalent notions of expansion (coboundary expansion, cosystolic expansion, topological expansion, spectral expansion, etc.), with differents strengths and applications. In this talk, we will survey this landscape of high-dimensional expansion, with a focus on two main results. First, we will present Gromov’s Topological Overlap Theorem, which asserts that coboundary expansion (a quantitative version of vanishing mod 2 cohomology) implies topological expansion (roughly, the property that for every map from a simplicial complex to a manifold of the same dimension, the images of a positive fraction of the simplices have a point in common). Second, we will outline a construction of bounded degree 2-dimensional topological expanders, due to Kaufman, Kazhdan, and Lubotzky.","lang":"eng"}],"type":"journal_article","language":[{"iso":"eng"}],"year":"2022","status":"public","date_created":"2023-10-01T22:01:14Z","page":"281-294","publisher":"Societe Mathematique de France","publication":"Bulletin de la Societe Mathematique de France","article_processing_charge":"No","intvolume":"       438","title":"High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)","quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"01"},{"_id":"10220","abstract":[{"text":"We study conditions under which a finite simplicial complex K can be mapped to ℝd without higher-multiplicity intersections. An almost r-embedding is a map f: K → ℝd such that the images of any r pairwise disjoint simplices of K do not have a common point. We show that if r is not a prime power and d ≥ 2r + 1, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost r-embedding of the (d +1)(r − 1)-simplex in ℝd. This improves on previous constructions of counterexamples (for d ≥ 3r) based on a series of papers by M. Özaydin, M. Gromov, P. Blagojević, F. Frick, G. Ziegler, and the second and fourth present authors.\r\n\r\nThe counterexamples are obtained by proving the following algebraic criterion in codimension 2: If r ≥ 3 and if K is a finite 2(r − 1)-complex, then there exists an almost r-embedding K → ℝ2r if and only if there exists a general position PL map f: K → ℝ2r such that the algebraic intersection number of the f-images of any r pairwise disjoint simplices of K is zero. This result can be restated in terms of a cohomological obstruction and extends an analogous codimension 3 criterion by the second and fourth authors. As another application, we classify ornaments f: S3 ⊔ S3 ⊔ S3 → ℝ5 up to ornament concordance.\r\n\r\nIt follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for r = 2 is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample.","lang":"eng"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","author":[{"full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac","full_name":"Mabillard, Isaac"},{"first_name":"Arkadiy B.","last_name":"Skopenkov","full_name":"Skopenkov, Arkadiy B."},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"external_id":{"isi":["000712942100013"],"arxiv":["1511.03501"]},"volume":245,"publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","grant_number":"P31312"}],"department":[{"_id":"UlWa"}],"isi":1,"day":"30","arxiv":1,"oa":1,"quality_controlled":"1","page":"501–534 ","publisher":"Springer Nature","status":"public","date_created":"2021-11-07T23:01:24Z","date_updated":"2023-08-14T11:43:55Z","citation":{"short":"S. Avvakumov, I. Mabillard, A.B. Skopenkov, U. Wagner, Israel Journal of Mathematics 245 (2021) 501–534.","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A. B., &#38; Wagner, U. (2021). Eliminating higher-multiplicity intersections. III. Codimension 2. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-021-2216-z\">https://doi.org/10.1007/s11856-021-2216-z</a>","chicago":"Avvakumov, Sergey, Isaac Mabillard, Arkadiy B. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s11856-021-2216-z\">https://doi.org/10.1007/s11856-021-2216-z</a>.","ista":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. 2021. Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. 245, 501–534.","ama":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. Eliminating higher-multiplicity intersections. III. Codimension 2. <i>Israel Journal of Mathematics</i>. 2021;245:501–534. doi:<a href=\"https://doi.org/10.1007/s11856-021-2216-z\">10.1007/s11856-021-2216-z</a>","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” <i>Israel Journal of Mathematics</i>, vol. 245, Springer Nature, 2021, pp. 501–534, doi:<a href=\"https://doi.org/10.1007/s11856-021-2216-z\">10.1007/s11856-021-2216-z</a>.","ieee":"S. Avvakumov, I. Mabillard, A. B. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections. III. Codimension 2,” <i>Israel Journal of Mathematics</i>, vol. 245. Springer Nature, pp. 501–534, 2021."},"type":"journal_article","scopus_import":"1","date_published":"2021-10-30T00:00:00Z","month":"10","related_material":{"record":[{"relation":"earlier_version","id":"8183","status":"public"},{"id":"9308","relation":"earlier_version","status":"public"}]},"doi":"10.1007/s11856-021-2216-z","article_type":"original","oa_version":"Preprint","acknowledgement":"Research supported by the Swiss National Science Foundation (Project SNSF-PP00P2-138948), by the Austrian Science Fund (FWF Project P31312-N35), by the Russian Foundation for Basic Research (Grants No. 15-01-06302 and 19-01-00169), by a Simons-IUM Fellowship, and by the D. Zimin Dynasty Foundation Grant. We would like to thank E. Alkin, A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful comments and discussions.","intvolume":"       245","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"title":"Eliminating higher-multiplicity intersections. III. Codimension 2","publication":"Israel Journal of Mathematics","article_processing_charge":"No","language":[{"iso":"eng"}],"year":"2021"},{"abstract":[{"lang":"eng","text":"We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.\r\nOur result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4."}],"_id":"7806","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský","full_name":"Filakovský, Marek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"},{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","first_name":"Stephan Y","last_name":"Zhechev","full_name":"Zhechev, Stephan Y"}],"project":[{"grant_number":"P31312","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"publication_identifier":{"isbn":["9781611975994"]},"volume":"2020-January","day":"01","department":[{"_id":"UlWa"}],"quality_controlled":"1","oa":1,"page":"767-785","publisher":"SIAM","date_created":"2020-05-10T22:00:48Z","status":"public","type":"conference","citation":{"ama":"Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes is undecidable. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:767-785. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>","ieee":"M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial complexes is undecidable,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 767–785.","mla":"Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 767–85, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>.","apa":"Filakovský, M., Wagner, U., &#38; Zhechev, S. Y. (2020). Embeddability of simplicial complexes is undecidable. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 767–785). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>","short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785.","ista":"Filakovský M, Wagner U, Zhechev SY. 2020. Embeddability of simplicial complexes is undecidable. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 767–785.","chicago":"Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of Simplicial Complexes Is Undecidable.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:767–85. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>."},"date_updated":"2021-01-12T08:15:38Z","month":"01","date_published":"2020-01-01T00:00:00Z","scopus_import":1,"conference":{"location":"Salt Lake City, UT, United States","name":"SODA: Symposium on Discrete Algorithms","start_date":"2020-01-05","end_date":"2020-01-08"},"doi":"10.1137/1.9781611975994.47","oa_version":"Published Version","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.47"}],"title":"Embeddability of simplicial complexes is undecidable","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","article_processing_charge":"No","language":[{"iso":"eng"}],"year":"2020"},{"volume":"2020-January","publication_identifier":{"isbn":["9781611975994"]},"external_id":{"arxiv":["2003.13557"]},"author":[{"orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","_id":"7807","abstract":[{"lang":"eng","text":"In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part."}],"status":"public","date_created":"2020-05-10T22:00:48Z","publisher":"SIAM","page":"2823-2841","arxiv":1,"oa":1,"quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"01","oa_version":"Submitted Version","related_material":{"record":[{"relation":"later_version","id":"12129","status":"public"}]},"conference":{"location":"Salt Lake City, UT, United States","end_date":"2020-01-08","start_date":"2020-01-05","name":"SODA: Symposium on Discrete Algorithms"},"doi":"10.1137/1.9781611975994.172","scopus_import":1,"date_published":"2020-01-01T00:00:00Z","month":"01","date_updated":"2023-08-04T08:51:07Z","citation":{"chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:2823–41. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.172\">https://doi.org/10.1137/1.9781611975994.172</a>.","ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.","short":"U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2823–2841.","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 2823–2841). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.172\">https://doi.org/10.1137/1.9781611975994.172</a>","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.172\">10.1137/1.9781611975994.172</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 2823–2841.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:2823-2841. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.172\">10.1137/1.9781611975994.172</a>"},"type":"conference","year":"2020","language":[{"iso":"eng"}],"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","article_processing_charge":"No","title":"Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.172"}]},{"status":"public","date_created":"2020-06-22T09:14:19Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"relation":"main_file","file_id":"8003","file_size":793187,"content_type":"application/pdf","creator":"dernst","date_updated":"2020-07-14T12:48:06Z","checksum":"3f6925be5f3dcdb3b14cab92f410edf7","date_created":"2020-06-23T06:37:27Z","file_name":"2020_LIPIcsSoCG_Wagner.pdf","access_level":"open_access"}],"arxiv":1,"oa":1,"quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"01","volume":164,"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"external_id":{"arxiv":["2003.13557"]},"author":[{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","_id":"7990","abstract":[{"text":"Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).","lang":"eng"}],"year":"2020","language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"36th International Symposium on Computational Geometry","intvolume":"       164","title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","file_date_updated":"2020-07-14T12:48:06Z","oa_version":"Published Version","related_material":{"record":[{"relation":"later_version","id":"12129","status":"public"}]},"alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2020.67","conference":{"end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry","start_date":"2020-06-22","location":"Zürich, Switzerland"},"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,"month":"06","date_published":"2020-06-01T00:00:00Z","ddc":["510"],"article_number":"67:1 - 67:16","date_updated":"2023-08-04T08:51:07Z","citation":{"ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” 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.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>.","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 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.67\">https://doi.org/10.4230/LIPIcs.SoCG.2020.67</a>","short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.67\">10.4230/LIPIcs.SoCG.2020.67</a>.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). 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.67\">10.4230/LIPIcs.SoCG.2020.67</a>"},"has_accepted_license":"1","type":"conference"},{"article_number":"62:1 - 62:16","citation":{"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.","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>.","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>","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","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.","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>.","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>"},"has_accepted_license":"1","date_updated":"2021-01-12T08:16:23Z","type":"conference","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,"month":"06","date_published":"2020-06-01T00:00:00Z","ddc":["510"],"alternative_title":["LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2020.62","conference":{"location":"Zürich, Switzerland","end_date":"2020-06-26","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"file_date_updated":"2020-07-14T12:48:06Z","oa_version":"Published Version","intvolume":"       164","title":"Barycentric cuts through a convex body","publication":"36th International Symposium on Computational Geometry","article_processing_charge":"No","language":[{"iso":"eng"}],"year":"2020","_id":"7992","abstract":[{"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.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","external_id":{"arxiv":["2003.13536"]},"author":[{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"volume":164,"publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"department":[{"_id":"UlWa"}],"day":"01","arxiv":1,"oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"content_type":"application/pdf","file_size":750318,"date_updated":"2020-07-14T12:48:06Z","creator":"dernst","file_id":"8004","relation":"main_file","access_level":"open_access","file_name":"2020_LIPIcsSoCG_Patakova.pdf","date_created":"2020-06-23T06:45:52Z","checksum":"ce1c9194139a664fb59d1efdfc88eaae"}],"status":"public","date_created":"2020-06-22T09:14:20Z"},{"type":"journal_article","citation":{"chicago":"Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical Surveys</i>. IOP Publishing, 2020. <a href=\"https://doi.org/10.1070/RM9943\">https://doi.org/10.1070/RM9943</a>.","ista":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.","short":"S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical Surveys 75 (2020) 1156–1158.","apa":"Avvakumov, S., Wagner, U., Mabillard, I., &#38; Skopenkov, A. B. (2020). Eliminating higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. IOP Publishing. <a href=\"https://doi.org/10.1070/RM9943\">https://doi.org/10.1070/RM9943</a>","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6, IOP Publishing, 2020, pp. 1156–58, doi:<a href=\"https://doi.org/10.1070/RM9943\">10.1070/RM9943</a>.","ieee":"S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity intersections, III. Codimension 2,” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6. IOP Publishing, pp. 1156–1158, 2020.","ama":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. 2020;75(6):1156-1158. doi:<a href=\"https://doi.org/10.1070/RM9943\">10.1070/RM9943</a>"},"date_updated":"2023-08-14T11:43:54Z","date_published":"2020-12-01T00:00:00Z","month":"12","scopus_import":"1","doi":"10.1070/RM9943","article_type":"original","related_material":{"record":[{"relation":"earlier_version","id":"8183","status":"public"},{"status":"public","id":"10220","relation":"later_version"}]},"oa_version":"Preprint","acknowledgement":"This research was carried out with the support of the Russian Foundation for Basic Research(grant no. 19-01-00169)","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"intvolume":"        75","article_processing_charge":"No","publication":"Russian Mathematical Surveys","year":"2020","language":[{"iso":"eng"}],"_id":"9308","publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000625983100001"],"arxiv":["1511.03501"]},"author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac"},{"last_name":"Skopenkov","first_name":"A. B.","full_name":"Skopenkov, A. B."}],"publication_identifier":{"issn":["0036-0279"]},"volume":75,"day":"01","isi":1,"department":[{"_id":"UlWa"}],"quality_controlled":"1","issue":"6","oa":1,"arxiv":1,"page":"1156-1158","publisher":"IOP Publishing","date_created":"2021-04-04T22:01:22Z","status":"public"},{"publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5986","abstract":[{"lang":"eng","text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture."}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"volume":61,"project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"author":[{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"issue":"4","oa":1,"arxiv":1,"quality_controlled":"1","department":[{"_id":"UlWa"}],"day":"01","isi":1,"date_created":"2019-02-14T11:54:08Z","status":"public","page":"880-898","publisher":"Springer Nature","file":[{"date_updated":"2020-07-14T12:47:14Z","creator":"dernst","content_type":"application/pdf","file_size":556276,"file_id":"5988","relation":"main_file","access_level":"open_access","file_name":"2018_DiscreteGeometry_Lubiw.pdf","date_created":"2019-02-14T11:57:22Z","checksum":"e1bff88f1d77001b53b78c485ce048d7"}],"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)"},"ddc":["000"],"date_published":"2019-06-01T00:00:00Z","month":"06","type":"journal_article","date_updated":"2023-09-07T13:17:36Z","citation":{"chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>.","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete &#38; Computational Geometry. 61(4), 880–898.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete &#38; Computational Geometry 61 (2019) 880–898.","apa":"Lubiw, A., Masárová, Z., &#38; Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>.","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. 2019;61(4):880-898. doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>"},"has_accepted_license":"1","file_date_updated":"2020-07-14T12:47:14Z","oa_version":"Published Version","doi":"10.1007/s00454-018-0035-8","article_type":"original","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"683"},{"relation":"dissertation_contains","id":"7944","status":"public"}]},"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","intvolume":"        61","year":"2019","language":[{"iso":"eng"}],"article_processing_charge":"Yes (via OA deal)","publication":"Discrete & Computational Geometry"},{"project":[{"name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"M02281"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]},"volume":129,"external_id":{"arxiv":["1812.04911"]},"author":[{"first_name":"Radoslav","last_name":"Fulek","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav"},{"full_name":"Gärtner, Bernd","first_name":"Bernd","last_name":"Gärtner"},{"full_name":"Kupavskii, Andrey","first_name":"Andrey","last_name":"Kupavskii"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2."}],"_id":"6647","date_created":"2019-07-17T10:35:04Z","status":"public","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","page":"38:1-38:13","file":[{"file_id":"6667","relation":"main_file","creator":"dernst","date_updated":"2020-07-14T12:47:35Z","content_type":"application/pdf","file_size":559837,"date_created":"2019-07-24T06:54:52Z","checksum":"d6d017f8b41291b94d102294fa96ae9c","access_level":"open_access","file_name":"2019_LIPICS_Fulek.pdf"}],"quality_controlled":"1","oa":1,"arxiv":1,"day":"01","department":[{"_id":"UlWa"}],"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:35Z","conference":{"location":"Portland, OR, United States","start_date":"2019-06-18","name":"SoCG 2019: Symposium on Computational Geometry","end_date":"2019-06-21"},"doi":"10.4230/LIPICS.SOCG.2019.38","alternative_title":["LIPIcs"],"related_material":{"record":[{"status":"public","id":"13974","relation":"later_version"}]},"ddc":["000","510"],"month":"06","date_published":"2019-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","date_updated":"2023-12-13T12:03:35Z","citation":{"ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in <i>35th International Symposium on Computational Geometry</i>, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” <i>35th International Symposium on Computational Geometry</i>, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">10.4230/LIPICS.SOCG.2019.38</a>.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: <i>35th International Symposium on Computational Geometry</i>. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">10.4230/LIPICS.SOCG.2019.38</a>","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In <i>35th International Symposium on Computational Geometry</i>, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., &#38; Wagner, U. (2019). The crossing Tverberg theorem. In <i>35th International Symposium on Computational Geometry</i> (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2019.38\">https://doi.org/10.4230/LIPICS.SOCG.2019.38</a>","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13."},"has_accepted_license":"1","year":"2019","language":[{"iso":"eng"}],"publication":"35th International Symposium on Computational Geometry","title":"The crossing Tverberg theorem","intvolume":"       129"},{"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:49Z","doi":"10.20382/JOGC.V10I2A5","article_type":"original","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"285"},{"relation":"part_of_dissertation","id":"8032","status":"public"}]},"ddc":["514"],"month":"11","date_published":"2019-11-01T00:00:00Z","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":"journal_article","citation":{"short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>. Computational Geometry Laborartoy, 2019. <a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">https://doi.org/10.20382/JOGC.V10I2A5</a>.","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. <i>Journal of Computational Geometry</i>. 2019;10(2):70–98. doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” <i>Journal of Computational Geometry</i>, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:<a href=\"https://doi.org/10.20382/JOGC.V10I2A5\">10.20382/JOGC.V10I2A5</a>.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” <i>Journal of Computational Geometry</i>, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019."},"has_accepted_license":"1","date_updated":"2023-09-07T13:18:26Z","language":[{"iso":"eng"}],"year":"2019","publication":"Journal of Computational Geometry","article_processing_charge":"No","title":"On the treewidth of triangulated 3-manifolds","intvolume":"        10","publication_identifier":{"issn":["1920-180X"]},"volume":10,"external_id":{"arxiv":["1712.00434"]},"author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.\r\nIn view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).\r\nWe derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).","lang":"eng"}],"_id":"7093","date_created":"2019-11-23T12:14:09Z","status":"public","publisher":"Computational Geometry Laborartoy","page":"70–98","file":[{"relation":"main_file","file_id":"7094","file_size":857590,"content_type":"application/pdf","date_updated":"2020-07-14T12:47:49Z","creator":"khuszar","checksum":"c872d590d38d538404782bca20c4c3f5","date_created":"2019-11-23T12:35:16Z","file_name":"479-1917-1-PB.pdf","access_level":"open_access"}],"quality_controlled":"1","oa":1,"issue":"2","arxiv":1,"day":"01","department":[{"_id":"UlWa"}]},{"publication_identifier":{"issn":["0004-5411"]},"volume":66,"external_id":{"isi":["000495406300007"],"arxiv":["1711.08436"]},"author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"first_name":"Pavel","last_name":"Patak","id":"B593B804-1035-11EA-B4F1-947645A5BB83","full_name":"Patak, Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","orcid":"0000-0002-3975-1683","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"first_name":"Martin","last_name":"Tancer","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"}],"publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"lang":"eng","text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable."}],"_id":"7108","date_created":"2019-11-26T10:13:59Z","status":"public","publisher":"ACM","quality_controlled":"1","oa":1,"issue":"3","arxiv":1,"day":"01","isi":1,"department":[{"_id":"UlWa"}],"oa_version":"Preprint","doi":"10.1145/3314024","article_type":"original","related_material":{"record":[{"status":"public","id":"184","relation":"earlier_version"}]},"month":"06","date_published":"2019-06-01T00:00:00Z","scopus_import":"1","type":"journal_article","date_updated":"2023-09-06T11:10:58Z","citation":{"ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.","chicago":"Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>.","apa":"Goaoc, X., Patak, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2019). Shellability is NP-complete. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3314024\">https://doi.org/10.1145/3314024</a>","short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” <i>Journal of the ACM</i>, vol. 66, no. 3. ACM, 2019.","mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” <i>Journal of the ACM</i>, vol. 66, no. 3, 21, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>.","ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. <i>Journal of the ACM</i>. 2019;66(3). doi:<a href=\"https://doi.org/10.1145/3314024\">10.1145/3314024</a>"},"article_number":"21","year":"2019","language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"Journal of the ACM","title":"Shellability is NP-complete","main_file_link":[{"url":"https://arxiv.org/pdf/1711.08436.pdf","open_access":"1"}],"intvolume":"        66"},{"intvolume":"        99","title":"Shellability is NP-complete","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","year":"2018","language":[{"iso":"eng"}],"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,"has_accepted_license":"1","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."},"date_updated":"2023-09-06T11:10:57Z","type":"conference","oa_version":"Published Version","file_date_updated":"2020-07-14T12:45:18Z","related_material":{"record":[{"id":"7108","relation":"later_version","status":"public"}]},"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"doi":"10.4230/LIPIcs.SoCG.2018.41","publist_id":"7736","conference":{"end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2018-06-11","location":"Budapest, Hungary"},"quality_controlled":"1","oa":1,"day":"11","department":[{"_id":"UlWa"}],"status":"public","date_created":"2018-12-11T11:45:04Z","page":"41:1 - 41:16","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"file_id":"5725","relation":"main_file","content_type":"application/pdf","file_size":718414,"creator":"dernst","date_updated":"2020-07-14T12:45:18Z","date_created":"2018-12-17T16:35:02Z","checksum":"d12bdd60f04a57307867704b5f930afd","access_level":"open_access","file_name":"2018_LIPIcs_Goaoc.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","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","volume":99,"author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}]},{"abstract":[{"text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how &quot;simple&quot; or &quot;thin&quot; a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1)).","lang":"eng"}],"_id":"285","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1712.00434"]},"author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","first_name":"Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár","full_name":"Huszár, Kristóf"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"},{"full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_identifier":{"issn":["18688969"]},"volume":99,"day":"01","department":[{"_id":"UlWa"}],"quality_controlled":"1","oa":1,"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"date_updated":"2020-07-14T12:45:51Z","creator":"dernst","file_size":642522,"content_type":"application/pdf","relation":"main_file","file_id":"5713","file_name":"2018_LIPIcs_Huszar.pdf","access_level":"open_access","checksum":"530d084116778135d5bffaa317479cac","date_created":"2018-12-17T15:32:38Z"}],"date_created":"2018-12-11T11:45:37Z","status":"public","type":"conference","date_updated":"2023-09-06T11:13:41Z","has_accepted_license":"1","citation":{"ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","mla":"Huszár, Kristóf, et al. <i>On the Treewidth of Triangulated 3-Manifolds</i>. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">10.4230/LIPIcs.SoCG.2018.46</a>.","apa":"Huszár, K., Spreer, J., &#38; Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). 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.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>","short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2018.46\">https://doi.org/10.4230/LIPIcs.SoCG.2018.46</a>."},"article_number":"46","ddc":["516","000"],"month":"06","date_published":"2018-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)"},"conference":{"location":"Budapest, Hungary","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14"},"publist_id":"7614","doi":"10.4230/LIPIcs.SoCG.2018.46","related_material":{"record":[{"relation":"later_version","id":"7093","status":"public"}]},"alternative_title":["LIPIcs"],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:45:51Z","acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","title":"On the treewidth of triangulated 3-manifolds","intvolume":"        99","article_processing_charge":"No","language":[{"iso":"eng"}],"year":"2018"},{"language":[{"iso":"eng"}],"year":"2018","publication":"Journal of the ACM","article_processing_charge":"No","intvolume":"        65","title":"Embeddability in the 3-Sphere is decidable","main_file_link":[{"url":"https://arxiv.org/abs/1402.0815","open_access":"1"}],"oa_version":"Preprint","ec_funded":1,"related_material":{"record":[{"status":"public","id":"2157","relation":"earlier_version"}]},"doi":"10.1145/3078632","publist_id":"7398","article_type":"original","scopus_import":"1","date_published":"2018-01-01T00:00:00Z","month":"01","article_number":"5","citation":{"short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).","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>","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>.","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.","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>","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>.","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."},"date_updated":"2023-09-11T13:38:49Z","type":"journal_article","status":"public","date_created":"2018-12-11T11:46:24Z","publisher":"ACM","arxiv":1,"oa":1,"issue":"1","quality_controlled":"1","department":[{"_id":"UlWa"}],"isi":1,"day":"01","volume":65,"project":[{"grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"external_id":{"arxiv":["1402.0815"],"isi":["000425685900006"]},"author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"full_name":"Sedgwick, Eric","first_name":"Eric","last_name":"Sedgwick"},{"full_name":"Tancer, Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","last_name":"Tancer","first_name":"Martin"},{"first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","_id":"425","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":"6774","abstract":[{"text":"A central problem of algebraic topology is to understand the homotopy groups  𝜋𝑑(𝑋)  of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group  𝜋1(𝑋)  of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with   𝜋1(𝑋)  trivial), compute the higher homotopy group   𝜋𝑑(𝑋)  for any given   𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of   𝜋𝑑(𝑋) ,   𝑑≥2  as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of   𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere   𝑆𝑑  to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes   𝜋𝑑(𝑋)  and represents its elements as simplicial maps from a suitable triangulation of the d-sphere   𝑆𝑑  to X. For fixed d, the algorithm runs in time exponential in   size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed   𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of   𝜋𝑑(𝑋) , the size of the triangulation of   𝑆𝑑  on which the map is defined, is exponential in size(𝑋) .","lang":"eng"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský"},{"full_name":"Franek, Peter","first_name":"Peter","orcid":"0000-0001-8878-8397","last_name":"Franek","id":"473294AE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stephan Y","last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87","full_name":"Zhechev, Stephan Y"}],"publication_identifier":{"issn":["2367-1726"],"eissn":["2367-1734"]},"volume":2,"project":[{"name":"Robust invariants of Nonlinear Systems","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","grant_number":"M01980","call_identifier":"FWF"},{"call_identifier":"FWF","name":"FWF Open Access Fund","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1"}],"department":[{"_id":"UlWa"}],"day":"01","oa":1,"issue":"3-4","quality_controlled":"1","file":[{"access_level":"open_access","file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","date_created":"2019-08-08T06:55:21Z","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8","content_type":"application/pdf","file_size":1056278,"date_updated":"2020-07-14T12:47:40Z","creator":"dernst","file_id":"6775","relation":"main_file"}],"page":"177-231","publisher":"Springer","date_created":"2019-08-08T06:47:40Z","status":"public","type":"journal_article","has_accepted_license":"1","date_updated":"2023-09-07T13:10:36Z","citation":{"ieee":"M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial representatives of homotopy group elements,” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.","mla":"Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>, vol. 2, no. 3–4, Springer, 2018, pp. 177–231, doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>.","ama":"Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. 2018;2(3-4):177-231. doi:<a href=\"https://doi.org/10.1007/s41468-018-0021-5\">10.1007/s41468-018-0021-5</a>","ista":"Filakovský M, Franek P, Wagner U, Zhechev SY. 2018. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2(3–4), 177–231.","chicago":"Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing Simplicial Representatives of Homotopy Group Elements.” <i>Journal of Applied and Computational Topology</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>.","apa":"Filakovský, M., Franek, P., Wagner, U., &#38; Zhechev, S. Y. (2018). Computing simplicial representatives of homotopy group elements. <i>Journal of Applied and Computational Topology</i>. Springer. <a href=\"https://doi.org/10.1007/s41468-018-0021-5\">https://doi.org/10.1007/s41468-018-0021-5</a>","short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231."},"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)"},"ddc":["514"],"month":"12","date_published":"2018-12-01T00:00:00Z","article_type":"original","doi":"10.1007/s41468-018-0021-5","related_material":{"record":[{"id":"6681","relation":"dissertation_contains","status":"public"}]},"file_date_updated":"2020-07-14T12:47:40Z","oa_version":"Published Version","title":"Computing simplicial representatives of homotopy group elements","intvolume":"         2","publication":"Journal of Applied and Computational Topology","year":"2018","language":[{"iso":"eng"}]},{"status":"public","date_created":"2018-12-11T11:48:16Z","page":"307–317","file":[{"file_name":"s10711-017-0291-4.pdf","access_level":"open_access","checksum":"d2f70fc132156504aa4c626aa378a7ab","date_created":"2019-01-15T13:44:05Z","creator":"kschuh","date_updated":"2020-07-14T12:47:58Z","file_size":412486,"content_type":"application/pdf","relation":"main_file","file_id":"5835"}],"publisher":"Springer","quality_controlled":"1","issue":"1","oa":1,"isi":1,"day":"01","department":[{"_id":"UlWa"}],"project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948"}],"volume":195,"external_id":{"isi":["000437122700017"]},"author":[{"full_name":"Dotterrer, Dominic","first_name":"Dominic","last_name":"Dotterrer"},{"last_name":"Kaufman","first_name":"Tali","full_name":"Kaufman, Tali"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","abstract":[{"lang":"eng","text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M."}],"_id":"742","year":"2018","language":[{"iso":"eng"}],"publication":"Geometriae Dedicata","article_processing_charge":"Yes (via OA deal)","intvolume":"       195","title":"On expansion and topological overlap","pubrep_id":"912","oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:58Z","related_material":{"record":[{"id":"1378","relation":"earlier_version","status":"public"}]},"publist_id":"6925","doi":"10.1007/s10711-017-0291-4","date_published":"2018-08-01T00:00:00Z","month":"08","ddc":["514","516"],"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","has_accepted_license":"1","citation":{"apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>","short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>."},"date_updated":"2023-09-27T12:29:57Z","type":"journal_article"}]