[{"oa_version":"Published Version","file":[{"file_size":927290,"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2024_LIPICs_Filakovsky.pdf","checksum":"0524d4189fd1ed08989546511343edf3","success":1,"date_updated":"2024-03-25T07:44:30Z","date_created":"2024-03-25T07:44:30Z","relation":"main_file","file_id":"15175"}],"ddc":["510"],"status":"public","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","intvolume":" 289","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"15168","abstract":[{"lang":"eng","text":"A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the \"linearly ordered chromatic number\" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023)."}],"alternative_title":["LIPIcs"],"type":"conference","date_published":"2024-03-01T00:00:00Z","publication":"41st International Symposium on Theoretical Aspects of Computer Science","citation":{"chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In 41st International Symposium on Theoretical Aspects of Computer Science, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.STACS.2024.34.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” 41st International Symposium on Theoretical Aspects of Computer Science, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.STACS.2024.34.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2024.34","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in 41st International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand, France, 2024, vol. 289.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: 41st International Symposium on Theoretical Aspects of Computer Science. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.STACS.2024.34"},"day":"01","has_accepted_license":"1","article_processing_charge":"No","scopus_import":"1","date_updated":"2024-03-25T07:45:54Z","date_created":"2024-03-24T23:00:59Z","volume":289,"author":[{"full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský"},{"full_name":"Nakajima, Tamio Vesa","first_name":"Tamio Vesa","last_name":"Nakajima"},{"full_name":"Opršal, Jakub","last_name":"Opršal","first_name":"Jakub","orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242"},{"first_name":"Gianluca","last_name":"Tasinato","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","full_name":"Tasinato, Gianluca"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","year":"2024","file_date_updated":"2024-03-25T07:44:30Z","ec_funded":1,"article_number":"34","language":[{"iso":"eng"}],"conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","location":"Clermont-Ferrand, France","start_date":"2024-03-12","end_date":"2024-03-14"},"doi":"10.4230/LIPIcs.STACS.2024.34","quality_controlled":"1","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"},{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2312.12981"]},"month":"03","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]}},{"department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"epub_ahead","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).","year":"2023","date_updated":"2023-12-13T12:03:35Z","date_created":"2023-08-06T22:01:12Z","related_material":{"record":[{"id":"6647","relation":"earlier_version","status":"public"}]},"author":[{"full_name":"Fulek, Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","first_name":"Radoslav","last_name":"Fulek"},{"first_name":"Bernd","last_name":"Gärtner","full_name":"Gärtner, Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"07","project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"isi":1,"quality_controlled":"1","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1812.04911","open_access":"1"}],"oa":1,"external_id":{"arxiv":["1812.04911"],"isi":["001038546500001"]},"language":[{"iso":"eng"}],"doi":"10.1007/s00454-023-00532-x","type":"journal_article","abstract":[{"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.","lang":"eng"}],"status":"public","title":"The crossing Tverberg theorem","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"13974","oa_version":"Preprint","scopus_import":"1","article_processing_charge":"No","day":"27","article_type":"original","citation":{"ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00532-x","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2023). The crossing Tverberg theorem. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00532-x","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” Discrete and Computational Geometry. Springer Nature, 2023.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00532-x."},"publication":"Discrete and Computational Geometry","date_published":"2023-07-27T00:00:00Z"},{"file_date_updated":"2023-10-31T11:20:31Z","author":[{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"},{"first_name":"Pascal","last_name":"Wild","id":"4C20D868-F248-11E8-B48F-1D18A9856A87","full_name":"Wild, Pascal"}],"volume":256,"date_updated":"2023-12-13T13:09:07Z","date_created":"2023-10-22T22:01:14Z","year":"2023","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published","publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"month":"09","doi":"10.1007/s11856-023-2521-9","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"isi":["001081646400010"]},"quality_controlled":"1","isi":1,"issue":"2","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"}],"type":"journal_article","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2023_IsraelJourMath_Wagner.pdf","creator":"dernst","file_size":623787,"content_type":"application/pdf","file_id":"14475","relation":"main_file","success":1,"checksum":"fbb05619fe4b650f341cc730425dd9c3","date_created":"2023-10-31T11:20:31Z","date_updated":"2023-10-31T11:20:31Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14445","intvolume":" 256","status":"public","ddc":["510"],"title":"Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","scopus_import":"1","date_published":"2023-09-01T00:00:00Z","citation":{"ama":"Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. 2023;256(2):675-717. doi:10.1007/s11856-023-2521-9","ista":"Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717.","ieee":"U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes,” Israel Journal of Mathematics, vol. 256, no. 2. Springer Nature, pp. 675–717, 2023.","apa":"Wagner, U., & Wild, P. (2023). Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-023-2521-9","mla":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:10.1007/s11856-023-2521-9.","short":"U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.","chicago":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2521-9."},"publication":"Israel Journal of Mathematics","page":"675-717","article_type":"original"},{"oa_version":"Preprint","intvolume":" 68","title":"Barycentric cuts through a convex body","status":"public","_id":"10776","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","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."}],"type":"journal_article","date_published":"2022-12-01T00:00:00Z","page":"1133-1154","article_type":"original","citation":{"ista":"Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body. Discrete and Computational Geometry. 68, 1133–1154.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 1133–1154, 2022.","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. Discrete and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-021-00364-7.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.","short":"Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68 (2022) 1133–1154."},"publication":"Discrete and Computational Geometry","article_processing_charge":"No","day":"01","scopus_import":"1","volume":68,"date_created":"2022-02-20T23:01:35Z","date_updated":"2023-08-02T14:38:58Z","author":[{"full_name":"Patakova, Zuzana","first_name":"Zuzana","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"published","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.","year":"2022","language":[{"iso":"eng"}],"doi":"10.1007/s00454-021-00364-7","quality_controlled":"1","isi":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.13536"}],"oa":1,"external_id":{"isi":["000750681500001"],"arxiv":["2003.13536"]},"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"12"},{"scopus_import":"1","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"day":"14","has_accepted_license":"1","article_processing_charge":"No","publication":"Discrete & Computational Geometry","citation":{"mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.","short":"U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” Discrete & Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00436-2.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. 68(4), 1227–1284.","apa":"Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022."},"article_type":"original","page":"1227-1284","date_published":"2022-11-14T00:00:00Z","type":"journal_article","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"}],"issue":"4","_id":"12129","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","ddc":["510"],"title":"Connectivity of triangulation flip graphs in the plane","intvolume":" 68","oa_version":"Published Version","file":[{"file_id":"12345","relation":"main_file","date_updated":"2023-01-23T11:10:03Z","date_created":"2023-01-23T11:10:03Z","success":1,"checksum":"307e879d09e52eddf5b225d0aaa9213a","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","access_level":"open_access","creator":"dernst","file_size":1747581,"content_type":"application/pdf"}],"month":"11","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"external_id":{"isi":["000883222200003"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"isi":1,"quality_controlled":"1","doi":"10.1007/s00454-022-00436-2","language":[{"iso":"eng"}],"file_date_updated":"2023-01-23T11:10:03Z","year":"2022","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","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","author":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"related_material":{"record":[{"id":"7807","status":"public","relation":"earlier_version"},{"relation":"earlier_version","status":"public","id":"7990"}]},"date_created":"2023-01-12T12:02:28Z","date_updated":"2023-08-04T08:51:08Z","volume":68},{"language":[{"iso":"eng"}],"date_published":"2022-01-01T00:00:00Z","doi":"10.24033/ast.1188","article_type":"original","quality_controlled":"1","page":"281-294","publication":"Bulletin de la Societe Mathematique de France","citation":{"ama":"Wagner U. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de la Societe Mathematique de France. 2022;438:281-294. doi:10.24033/ast.1188","apa":"Wagner, U. (2022). High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de La Societe Mathematique de France. Societe Mathematique de France. https://doi.org/10.24033/ast.1188","ieee":"U. Wagner, “High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others),” Bulletin de la Societe Mathematique de France, vol. 438. Societe Mathematique de France, pp. 281–294, 2022.","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.","mla":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” Bulletin de La Societe Mathematique de France, vol. 438, Societe Mathematique de France, 2022, pp. 281–94, doi:10.24033/ast.1188.","chicago":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” Bulletin de La Societe Mathematique de France. Societe Mathematique de France, 2022. https://doi.org/10.24033/ast.1188."},"day":"01","month":"01","article_processing_charge":"No","publication_identifier":{"issn":["0037-9484"],"eissn":["2102-622X"]},"scopus_import":"1","date_created":"2023-10-01T22:01:14Z","date_updated":"2023-10-03T08:04:03Z","volume":438,"oa_version":"None","author":[{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"publication_status":"published","title":"High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)","status":"public","intvolume":" 438","publisher":"Societe Mathematique de France","department":[{"_id":"UlWa"}],"_id":"14381","year":"2022","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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"},{"related_material":{"record":[{"id":"8183","relation":"earlier_version","status":"public"},{"id":"9308","status":"public","relation":"earlier_version"}]},"author":[{"last_name":"Avvakumov","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","full_name":"Avvakumov, Sergey"},{"full_name":"Mabillard, Isaac","last_name":"Mabillard","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Skopenkov, Arkadiy B.","last_name":"Skopenkov","first_name":"Arkadiy B."},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":245,"date_created":"2021-11-07T23:01:24Z","date_updated":"2023-08-14T11:43:55Z","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.","year":"2021","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"month":"10","doi":"10.1007/s11856-021-2216-z","language":[{"iso":"eng"}],"oa":1,"external_id":{"isi":["000712942100013"],"arxiv":["1511.03501"]},"main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"project":[{"call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"isi":1,"quality_controlled":"1","abstract":[{"lang":"eng","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."}],"type":"journal_article","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10220","intvolume":" 245","title":"Eliminating higher-multiplicity intersections. III. Codimension 2","status":"public","article_processing_charge":"No","day":"30","scopus_import":"1","date_published":"2021-10-30T00:00:00Z","citation":{"short":"S. Avvakumov, I. Mabillard, A.B. Skopenkov, U. Wagner, Israel Journal of Mathematics 245 (2021) 501–534.","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” Israel Journal of Mathematics, vol. 245, Springer Nature, 2021, pp. 501–534, doi:10.1007/s11856-021-2216-z.","chicago":"Avvakumov, Sergey, Isaac Mabillard, Arkadiy B. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” Israel Journal of Mathematics. Springer Nature, 2021. https://doi.org/10.1007/s11856-021-2216-z.","ama":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. 2021;245:501–534. doi:10.1007/s11856-021-2216-z","ieee":"S. Avvakumov, I. Mabillard, A. B. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections. III. Codimension 2,” Israel Journal of Mathematics, vol. 245. Springer Nature, pp. 501–534, 2021.","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A. B., & Wagner, U. (2021). Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-021-2216-z","ista":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. 2021. Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. 245, 501–534."},"publication":"Israel Journal of Mathematics","page":"501–534 ","article_type":"original"},{"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"}],"quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://doi.org/10.1137/1.9781611975994.47","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1137/1.9781611975994.47","conference":{"end_date":"2020-01-08","start_date":"2020-01-05","location":"Salt Lake City, UT, United States","name":"SODA: Symposium on Discrete Algorithms"},"publication_identifier":{"isbn":["9781611975994"]},"month":"01","publisher":"SIAM","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2020","volume":"2020-January","date_created":"2020-05-10T22:00:48Z","date_updated":"2021-01-12T08:15:38Z","author":[{"full_name":"Filakovský, Marek","first_name":"Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"full_name":"Zhechev, Stephan Y","last_name":"Zhechev","first_name":"Stephan Y","id":"3AA52972-F248-11E8-B48F-1D18A9856A87"}],"page":"767-785","citation":{"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.","apa":"Filakovský, M., Wagner, U., & Zhechev, S. Y. (2020). Embeddability of simplicial complexes is undecidable. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2020–January, pp. 767–785). Salt Lake City, UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.47","ieee":"M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial complexes is undecidable,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 767–785.","ama":"Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes is undecidable. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2020-January. SIAM; 2020:767-785. doi:10.1137/1.9781611975994.47","chicago":"Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of Simplicial Complexes Is Undecidable.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2020–January:767–85. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.47.","mla":"Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 767–85, doi:10.1137/1.9781611975994.47.","short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785."},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","date_published":"2020-01-01T00:00:00Z","scopus_import":1,"article_processing_charge":"No","day":"01","title":"Embeddability of simplicial complexes is undecidable","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7806","oa_version":"Published Version","type":"conference","abstract":[{"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.","lang":"eng"}]},{"file":[{"relation":"main_file","file_id":"8004","checksum":"ce1c9194139a664fb59d1efdfc88eaae","date_created":"2020-06-23T06:45:52Z","date_updated":"2020-07-14T12:48:06Z","access_level":"open_access","file_name":"2020_LIPIcsSoCG_Patakova.pdf","content_type":"application/pdf","file_size":750318,"creator":"dernst"}],"oa_version":"Published Version","_id":"7992","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 164","title":"Barycentric cuts through a convex body","ddc":["510"],"status":"public","abstract":[{"lang":"eng","text":"Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3."}],"type":"conference","alternative_title":["LIPIcs"],"date_published":"2020-06-01T00:00:00Z","citation":{"chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” 36th International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through a convex body. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.62","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ista":"Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 62:1-62:16.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62"},"publication":"36th International Symposium on Computational Geometry","article_processing_charge":"No","has_accepted_license":"1","day":"01","scopus_import":1,"author":[{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","first_name":"Zuzana"},{"full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":164,"date_created":"2020-06-22T09:14:20Z","date_updated":"2021-01-12T08:16:23Z","year":"2020","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","file_date_updated":"2020-07-14T12:48:06Z","article_number":"62:1 - 62:16","doi":"10.4230/LIPIcs.SoCG.2020.62","conference":{"end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2003.13536"]},"oa":1,"quality_controlled":"1","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"month":"06"},{"has_accepted_license":"1","article_processing_charge":"No","day":"01","scopus_import":1,"date_published":"2020-06-01T00:00:00Z","citation":{"chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.67.","short":"U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part II: Bistellar Flips).” 36th International Symposium on Computational Geometry, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.67.","apa":"Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.67","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips),” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","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.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips). In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.67"},"publication":"36th International Symposium on Computational Geometry","abstract":[{"lang":"eng","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)."}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"file_name":"2020_LIPIcsSoCG_Wagner.pdf","access_level":"open_access","creator":"dernst","file_size":793187,"content_type":"application/pdf","file_id":"8003","relation":"main_file","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:37:27Z","checksum":"3f6925be5f3dcdb3b14cab92f410edf7"}],"oa_version":"Published Version","intvolume":" 164","ddc":["510"],"title":"Connectivity of triangulation flip graphs in the plane (Part II: Bistellar flips)","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7990","publication_identifier":{"isbn":["9783959771436"],"issn":["18688969"]},"month":"06","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.67","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland"},"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["2003.13557"]},"file_date_updated":"2020-07-14T12:48:06Z","article_number":"67:1 - 67:16","volume":164,"date_created":"2020-06-22T09:14:19Z","date_updated":"2023-08-04T08:51:07Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"12129"}]},"author":[{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2020"},{"date_published":"2020-01-01T00:00:00Z","citation":{"ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2020-January. SIAM; 2020:2823-2841. doi:10.1137/1.9781611975994.172","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 2823–2841.","apa":"Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2020–January, pp. 2823–2841). Salt Lake City, UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.172","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.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:10.1137/1.9781611975994.172.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2020–January:2823–41. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.172."},"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","page":"2823-2841","article_processing_charge":"No","day":"01","scopus_import":1,"oa_version":"Submitted Version","_id":"7807","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)","status":"public","abstract":[{"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.","lang":"eng"}],"type":"conference","doi":"10.1137/1.9781611975994.172","conference":{"end_date":"2020-01-08","location":"Salt Lake City, UT, United States","start_date":"2020-01-05","name":"SODA: Symposium on Discrete Algorithms"},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.172"}],"oa":1,"external_id":{"arxiv":["2003.13557"]},"quality_controlled":"1","publication_identifier":{"isbn":["9781611975994"]},"month":"01","related_material":{"record":[{"relation":"later_version","status":"public","id":"12129"}]},"author":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"volume":"2020-January","date_created":"2020-05-10T22:00:48Z","date_updated":"2023-08-04T08:51:07Z","year":"2020","department":[{"_id":"UlWa"}],"publisher":"SIAM","publication_status":"published"},{"publication_identifier":{"issn":["0036-0279"]},"month":"12","external_id":{"isi":["000625983100001"],"arxiv":["1511.03501"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"isi":1,"quality_controlled":"1","doi":"10.1070/RM9943","language":[{"iso":"eng"}],"acknowledgement":"This research was carried out with the support of the Russian Foundation for Basic Research(grant no. 19-01-00169)","year":"2020","department":[{"_id":"UlWa"}],"publisher":"IOP Publishing","publication_status":"published","related_material":{"record":[{"id":"8183","status":"public","relation":"earlier_version"},{"status":"public","relation":"later_version","id":"10220"}]},"author":[{"full_name":"Avvakumov, Sergey","last_name":"Avvakumov","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"},{"full_name":"Mabillard, Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","first_name":"Isaac","last_name":"Mabillard"},{"full_name":"Skopenkov, A. B.","last_name":"Skopenkov","first_name":"A. B."}],"volume":75,"date_created":"2021-04-04T22:01:22Z","date_updated":"2023-08-14T11:43:54Z","scopus_import":"1","article_processing_charge":"No","day":"01","citation":{"chicago":"Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical Surveys. IOP Publishing, 2020. https://doi.org/10.1070/RM9943.","short":"S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical Surveys 75 (2020) 1156–1158.","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical Surveys, vol. 75, no. 6, IOP Publishing, 2020, pp. 1156–58, doi:10.1070/RM9943.","apa":"Avvakumov, S., Wagner, U., Mabillard, I., & Skopenkov, A. B. (2020). Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. IOP Publishing. https://doi.org/10.1070/RM9943","ieee":"S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity intersections, III. Codimension 2,” Russian Mathematical Surveys, vol. 75, no. 6. IOP Publishing, pp. 1156–1158, 2020.","ista":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.","ama":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. 2020;75(6):1156-1158. doi:10.1070/RM9943"},"publication":"Russian Mathematical Surveys","page":"1156-1158","article_type":"original","date_published":"2020-12-01T00:00:00Z","type":"journal_article","issue":"6","_id":"9308","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","intvolume":" 75","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","status":"public","oa_version":"Preprint"},{"article_number":"21","volume":66,"date_created":"2019-11-26T10:13:59Z","date_updated":"2023-09-06T11:10:58Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"184"}]},"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"first_name":"Pavel","last_name":"Patak","id":"B593B804-1035-11EA-B4F1-947645A5BB83","full_name":"Patak, Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"department":[{"_id":"UlWa"}],"publisher":"ACM","publication_status":"published","year":"2019","publication_identifier":{"issn":["0004-5411"]},"month":"06","language":[{"iso":"eng"}],"doi":"10.1145/3314024","isi":1,"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/pdf/1711.08436.pdf"}],"external_id":{"arxiv":["1711.08436"],"isi":["000495406300007"]},"oa":1,"issue":"3","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."}],"type":"journal_article","oa_version":"Preprint","intvolume":" 66","title":"Shellability is NP-complete","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"7108","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2019-06-01T00:00:00Z","article_type":"original","citation":{"short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” Journal of the ACM, vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.","chicago":"Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3314024.","ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. Journal of the ACM. 2019;66(3). doi:10.1145/3314024","apa":"Goaoc, X., Patak, P., Patakova, Z., Tancer, M., & Wagner, U. (2019). Shellability is NP-complete. Journal of the ACM. ACM. https://doi.org/10.1145/3314024","ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” Journal of the ACM, vol. 66, no. 3. ACM, 2019.","ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21."},"publication":"Journal of the ACM"},{"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"5986","intvolume":" 61","status":"public","title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","ddc":["000"],"oa_version":"Published Version","file":[{"content_type":"application/pdf","file_size":556276,"creator":"dernst","file_name":"2018_DiscreteGeometry_Lubiw.pdf","access_level":"open_access","date_updated":"2020-07-14T12:47:14Z","date_created":"2019-02-14T11:57:22Z","checksum":"e1bff88f1d77001b53b78c485ce048d7","relation":"main_file","file_id":"5988"}],"type":"journal_article","issue":"4","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."}],"citation":{"mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry. Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898. doi:10.1007/s00454-018-0035-8","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-018-0035-8","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” Discrete & Computational Geometry, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019."},"publication":"Discrete & Computational Geometry","page":"880-898","article_type":"original","date_published":"2019-06-01T00:00:00Z","scopus_import":"1","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","year":"2019","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"683"},{"relation":"dissertation_contains","status":"public","id":"7944"}]},"author":[{"full_name":"Lubiw, Anna","first_name":"Anna","last_name":"Lubiw"},{"full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","first_name":"Zuzana"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"volume":61,"date_created":"2019-02-14T11:54:08Z","date_updated":"2023-09-07T13:17:36Z","file_date_updated":"2020-07-14T12:47:14Z","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"isi":1,"quality_controlled":"1","doi":"10.1007/s00454-018-0035-8","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"06"},{"has_accepted_license":"1","article_processing_charge":"No","day":"01","page":"70–98","article_type":"original","citation":{"mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","apa":"Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. Computational Geometry Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019."},"publication":"Journal of Computational Geometry","date_published":"2019-11-01T00:00:00Z","type":"journal_article","issue":"2","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"}],"intvolume":" 10","ddc":["514"],"status":"public","title":"On the treewidth of triangulated 3-manifolds","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"7093","oa_version":"Published Version","file":[{"checksum":"c872d590d38d538404782bca20c4c3f5","date_created":"2019-11-23T12:35:16Z","date_updated":"2020-07-14T12:47:49Z","file_id":"7094","relation":"main_file","creator":"khuszar","file_size":857590,"content_type":"application/pdf","access_level":"open_access","file_name":"479-1917-1-PB.pdf"}],"publication_identifier":{"issn":["1920-180X"]},"month":"11","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["1712.00434"]},"language":[{"iso":"eng"}],"doi":"10.20382/JOGC.V10I2A5","file_date_updated":"2020-07-14T12:47:49Z","publisher":"Computational Geometry Laborartoy","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2019","volume":10,"date_updated":"2023-09-07T13:18:26Z","date_created":"2019-11-23T12:14:09Z","related_material":{"record":[{"id":"285","relation":"earlier_version","status":"public"},{"relation":"part_of_dissertation","status":"public","id":"8032"}]},"author":[{"last_name":"Huszár","first_name":"Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","full_name":"Huszár, Kristóf"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}]},{"alternative_title":["LIPIcs"],"type":"conference","abstract":[{"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.","lang":"eng"}],"ddc":["000","510"],"status":"public","title":"The crossing Tverberg theorem","intvolume":" 129","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6647","file":[{"access_level":"open_access","file_name":"2019_LIPICS_Fulek.pdf","file_size":559837,"content_type":"application/pdf","creator":"dernst","relation":"main_file","file_id":"6667","checksum":"d6d017f8b41291b94d102294fa96ae9c","date_updated":"2020-07-14T12:47:35Z","date_created":"2019-07-24T06:54:52Z"}],"oa_version":"Published Version","scopus_import":1,"day":"01","has_accepted_license":"1","page":"38:1-38:13","publication":"35th International Symposium on Computational Geometry","citation":{"ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” in 35th International Symposium on Computational Geometry, Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019). The crossing Tverberg theorem. In 35th International Symposium on Computational Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38","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.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.","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.","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38."},"date_published":"2019-06-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:35Z","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2019","date_updated":"2023-12-13T12:03:35Z","date_created":"2019-07-17T10:35:04Z","volume":129,"author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"full_name":"Gärtner, Bernd","last_name":"Gärtner","first_name":"Bernd"},{"full_name":"Kupavskii, Andrey","first_name":"Andrey","last_name":"Kupavskii"},{"full_name":"Valtr, Pavel","last_name":"Valtr","first_name":"Pavel"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"13974"}]},"month":"06","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771047"]},"quality_controlled":"1","project":[{"grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425","name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF"}],"external_id":{"arxiv":["1812.04911"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"conference":{"name":"SoCG 2019: Symposium on Computational Geometry","start_date":"2019-06-18","location":"Portland, OR, United States","end_date":"2019-06-21"},"doi":"10.4230/LIPICS.SOCG.2019.38"},{"file_date_updated":"2020-07-14T12:45:18Z","publist_id":"7736","date_updated":"2023-09-06T11:10:57Z","date_created":"2018-12-11T11:45:04Z","volume":99,"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"7108"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","year":"2018","month":"06","language":[{"iso":"eng"}],"conference":{"end_date":"2018-06-14","location":"Budapest, Hungary","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2018.41","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"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."}],"alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"type":"conference","oa_version":"Published Version","file":[{"checksum":"d12bdd60f04a57307867704b5f930afd","date_updated":"2020-07-14T12:45:18Z","date_created":"2018-12-17T16:35:02Z","file_id":"5725","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":718414,"access_level":"open_access","file_name":"2018_LIPIcs_Goaoc.pdf"}],"status":"public","ddc":["516","000"],"title":"Shellability is NP-complete","intvolume":" 99","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"184","day":"11","has_accepted_license":"1","scopus_import":1,"date_published":"2018-06-11T00:00:00Z","page":"41:1 - 41:16","citation":{"chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.41.","mla":"Goaoc, Xavier, et al. Shellability Is NP-Complete. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:10.4230/LIPIcs.SoCG.2018.41.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.","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.","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.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2018). Shellability is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.41","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:10.4230/LIPIcs.SoCG.2018.41"}},{"date_published":"2018-06-01T00:00:00Z","citation":{"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. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.","mla":"Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.","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.","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.","apa":"Huszár, K., Spreer, J., & 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. https://doi.org/10.4230/LIPIcs.SoCG.2018.46","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:10.4230/LIPIcs.SoCG.2018.46"},"day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":1,"oa_version":"Submitted Version","file":[{"creator":"dernst","file_size":642522,"content_type":"application/pdf","access_level":"open_access","file_name":"2018_LIPIcs_Huszar.pdf","checksum":"530d084116778135d5bffaa317479cac","date_updated":"2020-07-14T12:45:51Z","date_created":"2018-12-17T15:32:38Z","file_id":"5713","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"285","ddc":["516","000"],"status":"public","title":"On the treewidth of triangulated 3-manifolds","intvolume":" 99","abstract":[{"lang":"eng","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. 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))."}],"type":"conference","alternative_title":["LIPIcs"],"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2018-06-14","start_date":"2018-06-11","location":"Budapest, Hungary"},"doi":"10.4230/LIPIcs.SoCG.2018.46","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1712.00434"]},"oa":1,"quality_controlled":"1","month":"06","publication_identifier":{"issn":["18688969"]},"author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","last_name":"Huszár","first_name":"Kristóf"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"7093"}]},"date_created":"2018-12-11T11:45:37Z","date_updated":"2023-09-06T11:13:41Z","volume":99,"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).","year":"2018","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:45:51Z","publist_id":"7614","article_number":"46"},{"month":"12","publication_identifier":{"eissn":["2367-1734"],"issn":["2367-1726"]},"doi":"10.1007/s41468-018-0021-5","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","project":[{"name":"Robust invariants of Nonlinear Systems","call_identifier":"FWF","_id":"25F8B9BC-B435-11E9-9278-68D0E5697425","grant_number":"M01980"},{"_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1","name":"FWF Open Access Fund","call_identifier":"FWF"}],"file_date_updated":"2020-07-14T12:47:40Z","author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský","full_name":"Filakovský, Marek"},{"last_name":"Franek","first_name":"Peter","orcid":"0000-0001-8878-8397","id":"473294AE-F248-11E8-B48F-1D18A9856A87","full_name":"Franek, Peter"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Zhechev, Stephan Y","first_name":"Stephan Y","last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"6681"}]},"date_created":"2019-08-08T06:47:40Z","date_updated":"2023-09-07T13:10:36Z","volume":2,"year":"2018","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer","day":"01","has_accepted_license":"1","date_published":"2018-12-01T00:00:00Z","publication":"Journal of Applied and Computational Topology","citation":{"short":"M. Filakovský, P. Franek, U. Wagner, S.Y. Zhechev, Journal of Applied and Computational Topology 2 (2018) 177–231.","mla":"Filakovský, Marek, et al. “Computing Simplicial Representatives of Homotopy Group Elements.” Journal of Applied and Computational Topology, vol. 2, no. 3–4, Springer, 2018, pp. 177–231, doi:10.1007/s41468-018-0021-5.","chicago":"Filakovský, Marek, Peter Franek, Uli Wagner, and Stephan Y Zhechev. “Computing Simplicial Representatives of Homotopy Group Elements.” Journal of Applied and Computational Topology. Springer, 2018. https://doi.org/10.1007/s41468-018-0021-5.","ama":"Filakovský M, Franek P, Wagner U, Zhechev SY. Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. 2018;2(3-4):177-231. doi:10.1007/s41468-018-0021-5","apa":"Filakovský, M., Franek, P., Wagner, U., & Zhechev, S. Y. (2018). Computing simplicial representatives of homotopy group elements. Journal of Applied and Computational Topology. Springer. https://doi.org/10.1007/s41468-018-0021-5","ieee":"M. Filakovský, P. Franek, U. Wagner, and S. Y. Zhechev, “Computing simplicial representatives of homotopy group elements,” Journal of Applied and Computational Topology, vol. 2, no. 3–4. Springer, pp. 177–231, 2018.","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."},"article_type":"original","page":"177-231","abstract":[{"lang":"eng","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(𝑋) ."}],"issue":"3-4","type":"journal_article","file":[{"file_name":"2018_JourAppliedComputTopology_Filakovsky.pdf","access_level":"open_access","file_size":1056278,"content_type":"application/pdf","creator":"dernst","relation":"main_file","file_id":"6775","date_updated":"2020-07-14T12:47:40Z","date_created":"2019-08-08T06:55:21Z","checksum":"cf9e7fcd2a113dd4828774fc75cdb7e8"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"6774","status":"public","title":"Computing simplicial representatives of homotopy group elements","ddc":["514"],"intvolume":" 2"},{"month":"01","doi":"10.1145/3078632","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1402.0815","open_access":"1"}],"external_id":{"isi":["000425685900006"],"arxiv":["1402.0815"]},"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"}],"isi":1,"quality_controlled":"1","ec_funded":1,"publist_id":"7398","article_number":"5","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2157"}]},"author":[{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"last_name":"Sedgwick","first_name":"Eric","full_name":"Sedgwick, Eric"},{"last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"volume":65,"date_created":"2018-12-11T11:46:24Z","date_updated":"2023-09-11T13:38:49Z","year":"2018","department":[{"_id":"UlWa"}],"publisher":"ACM","publication_status":"published","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2018-01-01T00:00:00Z","citation":{"short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Journal of the ACM 65 (2018).","mla":"Matoušek, Jiří, et al. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM, vol. 65, no. 1, 5, ACM, 2018, doi:10.1145/3078632.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3-Sphere Is Decidable.” Journal of the ACM. ACM, 2018. https://doi.org/10.1145/3078632.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3-Sphere is decidable. Journal of the ACM. 2018;65(1). doi:10.1145/3078632","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3-Sphere is decidable,” Journal of the ACM, vol. 65, no. 1. ACM, 2018.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2018). Embeddability in the 3-Sphere is decidable. Journal of the ACM. ACM. https://doi.org/10.1145/3078632","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."},"publication":"Journal of the ACM","article_type":"original","issue":"1","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"}],"type":"journal_article","oa_version":"Preprint","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"425","intvolume":" 65","status":"public","title":"Embeddability in the 3-Sphere is decidable"},{"department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","year":"2018","volume":195,"date_created":"2018-12-11T11:48:16Z","date_updated":"2023-09-27T12:29:57Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1378"}]},"author":[{"full_name":"Dotterrer, Dominic","first_name":"Dominic","last_name":"Dotterrer"},{"full_name":"Kaufman, Tali","first_name":"Tali","last_name":"Kaufman"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"publist_id":"6925","file_date_updated":"2020-07-14T12:47:58Z","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"isi":1,"quality_controlled":"1","external_id":{"isi":["000437122700017"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/s10711-017-0291-4","month":"08","intvolume":" 195","ddc":["514","516"],"title":"On expansion and topological overlap","status":"public","_id":"742","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"file_id":"5835","relation":"main_file","date_updated":"2020-07-14T12:47:58Z","date_created":"2019-01-15T13:44:05Z","checksum":"d2f70fc132156504aa4c626aa378a7ab","file_name":"s10711-017-0291-4.pdf","access_level":"open_access","creator":"kschuh","content_type":"application/pdf","file_size":412486}],"oa_version":"Published Version","pubrep_id":"912","type":"journal_article","issue":"1","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."}],"page":"307–317","citation":{"ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. Geometriae Dedicata. 2018;195(1):307–317. doi:10.1007/s10711-017-0291-4","ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317.","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” Geometriae Dedicata, vol. 195, no. 1. Springer, pp. 307–317, 2018.","apa":"Dotterrer, D., Kaufman, T., & Wagner, U. (2018). On expansion and topological overlap. Geometriae Dedicata. Springer. https://doi.org/10.1007/s10711-017-0291-4","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” Geometriae Dedicata, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:10.1007/s10711-017-0291-4.","short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” Geometriae Dedicata. Springer, 2018. https://doi.org/10.1007/s10711-017-0291-4."},"publication":"Geometriae Dedicata","date_published":"2018-08-01T00:00:00Z","scopus_import":"1","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"01"},{"language":[{"iso":"eng"}],"doi":"10.1007/s00454-017-9900-0","quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1602.07907","open_access":"1"}],"external_id":{"arxiv":["1602.07907"]},"publication_identifier":{"issn":["01795376"]},"month":"06","volume":58,"date_updated":"2023-02-21T17:01:34Z","date_created":"2018-12-11T11:47:01Z","related_material":{"record":[{"id":"1379","status":"public","relation":"earlier_version"}]},"author":[{"last_name":"Burton","first_name":"Benjamin","full_name":"Burton, Benjamin"},{"full_name":"De Mesmay, Arnaud N","last_name":"De Mesmay","first_name":"Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","year":"2017","publist_id":"7283","date_published":"2017-06-09T00:00:00Z","page":"871 - 888","article_type":"original","citation":{"chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds.” Discrete & Computational Geometry. Springer, 2017. https://doi.org/10.1007/s00454-017-9900-0.","mla":"Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.” Discrete & Computational Geometry, vol. 58, no. 4, Springer, 2017, pp. 871–88, doi:10.1007/s00454-017-9900-0.","short":"B. Burton, A.N. de Mesmay, U. Wagner, Discrete & Computational Geometry 58 (2017) 871–888.","ista":"Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. 58(4), 871–888.","apa":"Burton, B., de Mesmay, A. N., & Wagner, U. (2017). Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-017-9900-0","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-Manifolds,” Discrete & Computational Geometry, vol. 58, no. 4. Springer, pp. 871–888, 2017.","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds. Discrete & Computational Geometry. 2017;58(4):871-888. doi:10.1007/s00454-017-9900-0"},"publication":"Discrete & Computational Geometry","article_processing_charge":"No","day":"09","scopus_import":1,"oa_version":"Preprint","intvolume":" 58","status":"public","title":"Finding non-orientable surfaces in 3-Manifolds","_id":"534","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","issue":"4","abstract":[{"lang":"eng","text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case."}],"type":"journal_article"},{"ec_funded":1,"publist_id":"7194","volume":222,"date_created":"2018-12-11T11:47:29Z","date_updated":"2023-02-23T10:02:13Z","related_material":{"record":[{"id":"1511","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","first_name":"Isaac","last_name":"Mabillard","full_name":"Mabillard, Isaac"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","first_name":"Zuzana"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin","full_name":"Tancer, Martin"},{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","year":"2017","acknowledgement":"The work by Z. P. was partially supported by the Israel Science Foundation grant ISF-768/12. The work by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of the Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research work of M.T. was conducted at IST Austria, supported by an IST Fellowship. The research of P. P. was supported by the ERC Advanced grant no. 320924. The work by I. M. and U. W. was supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). The collaboration between U. W. and X. G. was partially supported by the LabEx Bézout (ANR-10-LABX-58).","month":"10","language":[{"iso":"eng"}],"doi":"10.1007/s11856-017-1607-7","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1610.09063"}],"issue":"2","abstract":[{"text":"The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","intvolume":" 222","status":"public","title":"On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"610","day":"01","scopus_import":1,"date_published":"2017-10-01T00:00:00Z","page":"841 - 866","citation":{"mla":"Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics, vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:10.1007/s11856-017-1607-7.","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel Journal of Mathematics 222 (2017) 841–866.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics. Springer, 2017. https://doi.org/10.1007/s11856-017-1607-7.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 2017;222(2):841-866. doi:10.1007/s11856-017-1607-7","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2017. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 222(2), 841–866.","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result,” Israel Journal of Mathematics, vol. 222, no. 2. Springer, pp. 841–866, 2017.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-017-1607-7"},"publication":"Israel Journal of Mathematics"},{"oa_version":"Published Version","file":[{"file_size":710007,"content_type":"application/pdf","creator":"system","access_level":"open_access","file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","checksum":"24fdde981cc513352a78dcf9b0660ae9","date_updated":"2020-07-14T12:47:41Z","date_created":"2018-12-12T10:17:12Z","relation":"main_file","file_id":"5265"}],"pubrep_id":"896","status":"public","ddc":["514","516"],"title":"A proof of the orbit conjecture for flipping edge labelled triangulations","intvolume":" 77","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"683","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 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 O(n7) 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."}],"alternative_title":["LIPIcs"],"type":"conference","date_published":"2017-06-01T00:00:00Z","citation":{"ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge labelled triangulations,” presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia, 2017, vol. 77.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2017). A proof of the orbit conjecture for flipping edge labelled triangulations (Vol. 77). Presented at the SoCG: Symposium on Computational Geometry, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2017.49","ista":"Lubiw A, Masárová Z, Wagner U. 2017. A proof of the orbit conjecture for flipping edge labelled triangulations. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 77, 49.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge labelled triangulations. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.SoCG.2017.49","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations,” Vol. 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.SoCG.2017.49.","short":"A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Lubiw, Anna, et al. A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.SoCG.2017.49."},"day":"01","has_accepted_license":"1","scopus_import":1,"date_updated":"2023-09-05T15:01:43Z","date_created":"2018-12-11T11:47:54Z","volume":77,"author":[{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","first_name":"Zuzana","last_name":"Masárová","full_name":"Masárová, Zuzana"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"5986","relation":"later_version","status":"public"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2017","file_date_updated":"2020-07-14T12:47:41Z","publist_id":"7033","article_number":"49","language":[{"iso":"eng"}],"conference":{"end_date":"2017-07-07","location":"Brisbane, Australia","start_date":"2017-07-04","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2017.49","quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"month":"06"},{"abstract":[{"text":"We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b, d) such that the following holds. If F is a finite family of subsets of Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map C*(K)→C*(Rd).","lang":"eng"}],"type":"book_chapter","oa_version":"Published Version","title":"Bounding helly numbers via betti numbers","status":"public","_id":"424","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","day":"06","series_title":"A Journey Through Discrete Mathematics","scopus_import":1,"date_published":"2017-10-06T00:00:00Z","page":"407 - 447","citation":{"ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2017.Bounding helly numbers via betti numbers. In: A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. , 407–447.","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly numbers via betti numbers,” in A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017, pp. 407–447.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). Bounding helly numbers via betti numbers. In M. Loebl, J. Nešetřil, & R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek (pp. 407–447). Springer. https://doi.org/10.1007/978-3-319-44479-6_17","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding helly numbers via betti numbers. In: Loebl M, Nešetřil J, Thomas R, eds. A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. A Journey Through Discrete Mathematics. Springer; 2017:407-447. doi:10.1007/978-3-319-44479-6_17","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers.” In A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017. https://doi.org/10.1007/978-3-319-44479-6_17.","mla":"Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin Loebl et al., Springer, 2017, pp. 407–47, doi:10.1007/978-3-319-44479-6_17.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, M. Loebl, J. Nešetřil, R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, Springer, 2017, pp. 407–447."},"publication":"A Journey through Discrete Mathematics: A Tribute to Jiri Matousek","publist_id":"7399","date_updated":"2024-02-28T12:59:37Z","date_created":"2018-12-11T11:46:24Z","related_material":{"record":[{"id":"1512","status":"public","relation":"earlier_version"}]},"author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"publisher":"Springer","editor":[{"full_name":"Loebl, Martin","first_name":"Martin","last_name":"Loebl"},{"last_name":"Nešetřil","first_name":"Jaroslav","full_name":"Nešetřil, Jaroslav"},{"first_name":"Robin","last_name":"Thomas","full_name":"Thomas, Robin"}],"department":[{"_id":"UlWa"}],"publication_status":"published","year":"2017","publication_identifier":{"isbn":["978-331944479-6"]},"month":"10","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-44479-6_17","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1310.4613v3"}]},{"doi":"10.1007/s11856-016-1419-1","date_published":"2016-10-01T00:00:00Z","language":[{"iso":"eng"}],"citation":{"chicago":"Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” Israel Journal of Mathematics. Springer, 2016. https://doi.org/10.1007/s11856-016-1419-1.","mla":"Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” Israel Journal of Mathematics, vol. 216, no. 2, Springer, 2016, pp. 545–82, doi:10.1007/s11856-016-1419-1.","short":"A. Gundert, U. Wagner, Israel Journal of Mathematics 216 (2016) 545–582.","ista":"Gundert A, Wagner U. 2016. On eigenvalues of random complexes. Israel Journal of Mathematics. 216(2), 545–582.","ieee":"A. Gundert and U. Wagner, “On eigenvalues of random complexes,” Israel Journal of Mathematics, vol. 216, no. 2. Springer, pp. 545–582, 2016.","apa":"Gundert, A., & Wagner, U. (2016). On eigenvalues of random complexes. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-016-1419-1","ama":"Gundert A, Wagner U. On eigenvalues of random complexes. Israel Journal of Mathematics. 2016;216(2):545-582. doi:10.1007/s11856-016-1419-1"},"main_file_link":[{"url":"https://arxiv.org/abs/1411.4906","open_access":"1"}],"oa":1,"publication":"Israel Journal of Mathematics","page":"545 - 582","quality_controlled":"1","day":"01","month":"10","scopus_import":1,"author":[{"full_name":"Gundert, Anna","last_name":"Gundert","first_name":"Anna"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"volume":216,"oa_version":"Preprint","date_updated":"2021-01-12T06:49:36Z","date_created":"2018-12-11T11:51:07Z","_id":"1282","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","year":"2016","intvolume":" 216","publisher":"Springer","department":[{"_id":"UlWa"}],"status":"public","title":"On eigenvalues of random complexes","publication_status":"published","issue":"2","publist_id":"6034","abstract":[{"lang":"eng","text":"We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam model Xk(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns the Laplacian; we develop an analogous result for the adjacency matrix. The same arguments apply to other models of random complexes which allow for dependencies between the choices of k-dimensional simplices. In the second part of the paper, we apply this to the question of possible higher-dimensional analogues of the discrete Cheeger inequality, which in the classical case of graphs relates the eigenvalues of a graph and its edge expansion. It is very natural to ask whether this generalizes to higher dimensions and, in particular, whether the eigenvalues of the higher-dimensional Laplacian capture the notion of coboundary expansion—a higher-dimensional generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov; this question was raised, for instance, by Dotterrer and Kahle. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every k ≥ 2 and n ∈ N, there is a k-dimensional complex Yn k on n vertices that has strong spectral expansion properties (all nontrivial eigenvalues of the normalised k-dimensional Laplacian lie in the interval [1−O(1/√1), 1+0(1/√1]) but whose coboundary expansion is bounded from above by O(log n/n) and so tends to zero as n → ∞; moreover, Yn k can be taken to have vanishing integer homology in dimension less than k."}],"type":"journal_article"},{"day":"01","has_accepted_license":"1","scopus_import":1,"date_published":"2016-06-01T00:00:00Z","citation":{"mla":"Mabillard, Isaac, and Uli Wagner. Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12, doi:10.4230/LIPIcs.SoCG.2016.51.","short":"I. Mabillard, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12.","chicago":"Mabillard, Isaac, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range,” 51:51.1-51.12. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.51.","ama":"Mabillard I, Wagner U. Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH; 2016:51.1-51.12. doi:10.4230/LIPIcs.SoCG.2016.51","ista":"Mabillard I, Wagner U. 2016. Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 51.1-51.12.","ieee":"I. Mabillard and U. Wagner, “Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 51.1-51.12.","apa":"Mabillard, I., & Wagner, U. (2016). Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range (Vol. 51, p. 51.1-51.12). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2016.51"},"page":"51.1 - 51.12","abstract":[{"lang":"eng","text":"Motivated by Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into double-struck Rd without higher-multiplicity intersections. We focus on conditions for the existence of almost r-embeddings, i.e., maps f : K → double-struck Rd such that f(σ1) ∩ ⋯ ∩ f(σr) = ∅ whenever σ1, ..., σr are pairwise disjoint simplices of K. Generalizing the classical Haefliger-Weber embeddability criterion, we show that a well-known necessary deleted product condition for the existence of almost r-embeddings is sufficient in a suitable r-metastable range of dimensions: If rd ≥ (r + 1) dim K + 3, then there exists an almost r-embedding K → double-struck Rd if and only if there exists an equivariant map (K)Δ r → Sr Sd(r-1)-1, where (K)Δ r is the deleted r-fold product of K, the target Sd(r-1)-1 is the sphere of dimension d(r - 1) - 1, and Sr is the symmetric group. This significantly extends one of the main results of our previous paper (which treated the special case where d = rk and dim K = (r - 1)k for some k ≥ 3), and settles an open question raised there."}],"type":"conference","alternative_title":["LIPIcs"],"pubrep_id":"621","file":[{"file_name":"IST-2016-621-v1+1_LIPIcs-SoCG-2016-51.pdf","access_level":"open_access","content_type":"application/pdf","file_size":622969,"creator":"system","relation":"main_file","file_id":"4791","date_created":"2018-12-12T10:10:06Z","date_updated":"2020-07-14T12:44:47Z","checksum":"92c0c3735fe908f8ded6e484005cb3b1"}],"oa_version":"Published Version","_id":"1381","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range","status":"public","ddc":["510"],"intvolume":" 51","month":"06","conference":{"end_date":"2016-06-17","location":"Medford, MA, USA","start_date":"2016-06-14","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2016.51","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"quality_controlled":"1","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"file_date_updated":"2020-07-14T12:44:47Z","publist_id":"5830","author":[{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac","full_name":"Mabillard, Isaac"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"date_created":"2018-12-11T11:51:41Z","date_updated":"2021-01-12T06:50:17Z","volume":51,"year":"2016","publication_status":"published","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH","department":[{"_id":"UlWa"}]},{"issue":"4","abstract":[{"lang":"eng","text":"For random graphs, the containment problem considers the probability that a binomial random graph G(n, p) contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well known that the (sharp) threshold is at p = 1/n. We consider a natural analogue of this question for higher-dimensional random complexes Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k = 2. Improving previous results, we show that p = Θ(1/ √n) is the (coarse) threshold for containing a subdivision of any fixed complete 2-complex. For higher dimensions k > 2, we get that p = O(n−1/k) is an upper bound for the threshold probability of containing a subdivision of a fixed k-dimensional complex."}],"type":"journal_article","oa_version":"Preprint","_id":"1523","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","intvolume":" 144","status":"public","title":"On topological minors in random simplicial complexes","day":"01","scopus_import":1,"date_published":"2016-04-01T00:00:00Z","citation":{"apa":"Gundert, A., & Wagner, U. (2016). On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. American Mathematical Society. https://doi.org/10.1090/proc/12824","ieee":"A. Gundert and U. Wagner, “On topological minors in random simplicial complexes,” Proceedings of the American Mathematical Society, vol. 144, no. 4. American Mathematical Society, pp. 1815–1828, 2016.","ista":"Gundert A, Wagner U. 2016. On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. 144(4), 1815–1828.","ama":"Gundert A, Wagner U. On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. 2016;144(4):1815-1828. doi:10.1090/proc/12824","chicago":"Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” Proceedings of the American Mathematical Society. American Mathematical Society, 2016. https://doi.org/10.1090/proc/12824.","short":"A. Gundert, U. Wagner, Proceedings of the American Mathematical Society 144 (2016) 1815–1828.","mla":"Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” Proceedings of the American Mathematical Society, vol. 144, no. 4, American Mathematical Society, 2016, pp. 1815–28, doi:10.1090/proc/12824."},"publication":"Proceedings of the American Mathematical Society","page":"1815 - 1828","publist_id":"5650","author":[{"full_name":"Gundert, Anna","last_name":"Gundert","first_name":"Anna"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"volume":144,"date_updated":"2021-01-12T06:51:22Z","date_created":"2018-12-11T11:52:30Z","acknowledgement":"This research was supported by the Swiss National Science Foundation (SNF Projects 200021-125309 and 200020-138230","year":"2016","department":[{"_id":"UlWa"}],"publisher":"American Mathematical Society","publication_status":"published","month":"04","doi":"10.1090/proc/12824","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1404.2106"}],"oa":1,"quality_controlled":"1"},{"year":"2016","acknowledgement":"Supported by the ERC Adv anced Grant No. 267165. ","publication_status":"published","publisher":"Springer","department":[{"_id":"UlWa"}],"author":[{"first_name":"Jiří","last_name":"Matoušek","full_name":"Matoušek, Jiří"},{"full_name":"Sedgwick, Eric","last_name":"Sedgwick","first_name":"Eric"},{"full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2244"}]},"date_updated":"2023-02-23T10:34:31Z","date_created":"2018-12-11T11:51:52Z","volume":212,"publist_id":"5796","main_file_link":[{"url":"http://arxiv.org/abs/1302.6475","open_access":"1"}],"oa":1,"quality_controlled":"1","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"doi":"10.1007/s11856-016-1294-9","language":[{"iso":"eng"}],"month":"05","_id":"1411","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Untangling two systems of noncrossing curves","intvolume":" 212","oa_version":"Preprint","type":"journal_article","abstract":[{"lang":"eng","text":"We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov."}],"issue":"1","publication":"Israel Journal of Mathematics","citation":{"chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Israel Journal of Mathematics. Springer, 2016. https://doi.org/10.1007/s11856-016-1294-9.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, Israel Journal of Mathematics 212 (2016) 37–79.","mla":"Matoušek, Jiří, et al. “Untangling Two Systems of Noncrossing Curves.” Israel Journal of Mathematics, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:10.1007/s11856-016-1294-9.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2016). Untangling two systems of noncrossing curves. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-016-1294-9","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” Israel Journal of Mathematics, vol. 212, no. 1. Springer, pp. 37–79, 2016.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2016. Untangling two systems of noncrossing curves. Israel Journal of Mathematics. 212(1), 37–79.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. Israel Journal of Mathematics. 2016;212(1):37-79. doi:10.1007/s11856-016-1294-9"},"page":"37 - 79","date_published":"2016-05-01T00:00:00Z","scopus_import":1,"day":"01"},{"language":[{"iso":"eng"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2016-06-17","start_date":"2016-06-14","location":"Medford, MA, USA"},"doi":"10.4230/LIPIcs.SoCG.2016.24","quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"month":"06","date_updated":"2023-02-23T12:23:20Z","date_created":"2018-12-11T11:51:41Z","volume":51,"author":[{"full_name":"Burton, Benjamin","first_name":"Benjamin","last_name":"Burton"},{"full_name":"De Mesmay, Arnaud N","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","first_name":"Arnaud N","last_name":"De Mesmay"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"534"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","year":"2016","file_date_updated":"2020-07-14T12:44:47Z","publist_id":"5832","date_published":"2016-06-01T00:00:00Z","page":"24.1 - 24.15","citation":{"ista":"Burton B, de Mesmay AN, Wagner U. 2016. Finding non-orientable surfaces in 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 24.1-24.15.","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 24.1-24.15.","apa":"Burton, B., de Mesmay, A. N., & Wagner, U. (2016). Finding non-orientable surfaces in 3-manifolds (Vol. 51, p. 24.1-24.15). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.24","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-manifolds. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing; 2016:24.1-24.15. doi:10.4230/LIPIcs.SoCG.2016.24","chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds,” 51:24.1-24.15. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.24.","mla":"Burton, Benjamin, et al. Finding Non-Orientable Surfaces in 3-Manifolds. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15, doi:10.4230/LIPIcs.SoCG.2016.24.","short":"B. Burton, A.N. de Mesmay, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15."},"day":"01","has_accepted_license":"1","scopus_import":1,"file":[{"date_created":"2018-12-12T10:12:12Z","date_updated":"2020-07-14T12:44:47Z","checksum":"f04248a61c24297cfabd30c5f8e0deb9","relation":"main_file","file_id":"4930","file_size":574770,"content_type":"application/pdf","creator":"system","file_name":"IST-2016-622-v1+1_LIPIcs-SoCG-2016-24.pdf","access_level":"open_access"}],"oa_version":"Published Version","pubrep_id":"622","ddc":["510"],"status":"public","title":"Finding non-orientable surfaces in 3-manifolds","intvolume":" 51","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1379","abstract":[{"text":"We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.","lang":"eng"}],"alternative_title":["LIPIcs"],"type":"conference"},{"month":"06","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2016.35","conference":{"start_date":"2016-06-14","location":"Medford, MA, USA","end_date":"2016-06-17","name":"SoCG: Symposium on Computational Geometry"},"project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publist_id":"5833","file_date_updated":"2020-07-14T12:44:47Z","volume":51,"date_created":"2018-12-11T11:51:41Z","date_updated":"2023-09-27T12:29:56Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"742"}]},"author":[{"first_name":"Dominic","last_name":"Dotterrer","full_name":"Dotterrer, Dominic"},{"first_name":"Tali","last_name":"Kaufman","full_name":"Kaufman, Tali"},{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","publication_status":"published","year":"2016","has_accepted_license":"1","day":"01","scopus_import":1,"date_published":"2016-06-01T00:00:00Z","page":"35.1 - 35.10","citation":{"mla":"Dotterrer, Dominic, et al. On Expansion and Topological Overlap. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10, doi:10.4230/LIPIcs.SoCG.2016.35.","short":"D. Dotterrer, T. Kaufman, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap,” 51:35.1-35.10. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.35.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. In: Vol 51. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing; 2016:35.1-35.10. doi:10.4230/LIPIcs.SoCG.2016.35","ista":"Dotterrer D, Kaufman T, Wagner U. 2016. On expansion and topological overlap. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 51, 35.1-35.10.","apa":"Dotterrer, D., Kaufman, T., & Wagner, U. (2016). On expansion and topological overlap (Vol. 51, p. 35.1-35.10). Presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2016.35","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” presented at the SoCG: Symposium on Computational Geometry, Medford, MA, USA, 2016, vol. 51, p. 35.1-35.10."},"abstract":[{"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 X → ℝd there exists a point p ∈ ℝd whose preimage intersects a positive fraction μ > 0 of the d-cells of X. More generally, the conclusion holds if ℝd is replaced by any d-dimensional piecewise-linear (PL) manifold M, with a constant μ that depends only on d and on the expansion properties of X, but not on M.","lang":"eng"}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"date_updated":"2020-07-14T12:44:47Z","date_created":"2018-12-12T10:08:38Z","checksum":"cee65b0e722d50f9d1cc70c90ec1d59b","relation":"main_file","file_id":"4699","file_size":536923,"content_type":"application/pdf","creator":"system","file_name":"IST-2016-623-v1+1_LIPIcs-SoCG-2016-35.pdf","access_level":"open_access"}],"oa_version":"Published Version","pubrep_id":"623","intvolume":" 51","title":"On expansion and topological overlap","ddc":["510"],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1378"},{"scopus_import":1,"has_accepted_license":"1","day":"11","page":"476 - 490","citation":{"ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:476-490. doi:10.4230/LIPIcs.SOCG.2015.476","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2015). On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result (Vol. 34, pp. 476–490). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SOCG.2015.476","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 476–490.","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2015. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 476–490.","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–490.","mla":"Goaoc, Xavier, et al. On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:10.4230/LIPIcs.SOCG.2015.476.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result,” 34:476–90. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPIcs.SOCG.2015.476."},"date_published":"2015-06-11T00:00:00Z","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"lang":"eng","text":"The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition."}],"ddc":["510"],"title":"On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1511","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"IST-2016-502-v1+1_42.pdf","file_size":636735,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"4871","checksum":"0945811875351796324189312ca29e9e","date_created":"2018-12-12T10:11:18Z","date_updated":"2020-07-14T12:44:59Z"}],"pubrep_id":"502","month":"06","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SOCG.2015.476","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2015-06-25","location":"Eindhoven, Netherlands","start_date":"2015-06-22"},"publist_id":"5666","ec_funded":1,"file_date_updated":"2020-07-14T12:44:59Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2015","acknowledgement":"The work by Z. P. was partially supported by the Charles University Grant SVV-2014-260103. The\r\nwork by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of\r\nthe Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research\r\nwork of M. T. was conducted at IST Austria, supported by an IST Fellowship. The work by U.W.\r\nwas partially supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and\r\nSNSF-PP00P2-138948).","volume":"34 ","date_updated":"2023-02-23T12:38:00Z","date_created":"2018-12-11T11:52:27Z","related_material":{"record":[{"id":"610","relation":"later_version","status":"public"}]},"author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"full_name":"Mabillard, Isaac","last_name":"Mabillard","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Paták, Pavel","last_name":"Paták","first_name":"Pavel"},{"id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova","full_name":"Patakova, Zuzana"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}]},{"month":"11","day":"15","article_processing_charge":"No","publication":"arXiv","external_id":{"arxiv":["1511.03501"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"citation":{"mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, 1511.03501.","short":"S. Avvakumov, I. Mabillard, A. Skopenkov, U. Wagner, ArXiv (n.d.).","chicago":"Avvakumov, Sergey, Isaac Mabillard, A. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” ArXiv, n.d.","ama":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv.","ista":"Avvakumov S, Mabillard I, Skopenkov A, Wagner U. Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv, 1511.03501.","ieee":"S. Avvakumov, I. Mabillard, A. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections, III. Codimension 2,” arXiv. .","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A., & Wagner, U. (n.d.). Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv."},"language":[{"iso":"eng"}],"date_published":"2015-11-15T00:00:00Z","article_number":"1511.03501","type":"preprint","abstract":[{"lang":"eng","text":"We study conditions under which a finite simplicial complex $K$ can be mapped to $\\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\\to \\mathbb R^d$ such that the images of any $r$\r\npairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of\r\nthe $(d+1)(r-1)$-simplex in $\\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\\geq 3r$) based on a series of papers by M. \\\"Ozaydin, M. Gromov, P. Blagojevi\\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\\to \\mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\\to \\mathbb R^{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 cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \\sqcup S^3\\sqcup S^3\\to \\mathbb R^5$ up to ornament\r\nconcordance. It 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."}],"publication_status":"submitted","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","status":"public","department":[{"_id":"UlWa"}],"_id":"8183","acknowledgement":"We would like to thank A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful discussions.","year":"2015","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2020-07-30T10:45:19Z","date_updated":"2023-09-07T13:12:17Z","oa_version":"Preprint","author":[{"full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","first_name":"Sergey"},{"full_name":"Mabillard, Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac"},{"full_name":"Skopenkov, A.","last_name":"Skopenkov","first_name":"A."},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"9308"},{"status":"public","relation":"later_version","id":"10220"},{"status":"public","relation":"dissertation_contains","id":"8156"}]}},{"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SOCG.2015.507","conference":{"location":"Eindhoven, Netherlands","start_date":"2015-06-22","end_date":"2015-06-25","name":"SoCG: Symposium on Computational Geometry"},"quality_controlled":"1","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"month":"01","volume":34,"date_updated":"2024-02-28T12:59:37Z","date_created":"2018-12-11T11:52:27Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"424"}]},"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"full_name":"Paták, Pavel","last_name":"Paták","first_name":"Pavel"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","acknowledgement":"PP, ZP and MT were partially supported by the Charles University Grant GAUK 421511. ZP was\r\npartially supported by the Charles University Grant SVV-2014-260103. ZP and MT were partially\r\nsupported by the ERC Advanced Grant No. 267165 and by the project CE-ITI (GACR P202/12/G061)\r\nof the Czech Science Foundation. UW was partially supported by the Swiss National Science Foundation\r\n(grants SNSF-200020-138230 and SNSF-PP00P2-138948). Part of this work was done when XG was affiliated with INRIA Nancy Grand-Est and when MT was affiliated with Institutionen för matematik, Kungliga Tekniska Högskolan, then IST Austria.","year":"2015","publist_id":"5665","file_date_updated":"2020-07-14T12:45:00Z","date_published":"2015-01-01T00:00:00Z","page":"507 - 521","citation":{"ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding Helly numbers via Betti numbers. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:507-521. doi:10.4230/LIPIcs.SOCG.2015.507","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2015). Bounding Helly numbers via Betti numbers (Vol. 34, pp. 507–521). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SOCG.2015.507","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding Helly numbers via Betti numbers,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 507–521.","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2015. Bounding Helly numbers via Betti numbers. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 507–521.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–521.","mla":"Goaoc, Xavier, et al. Bounding Helly Numbers via Betti Numbers. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–21, doi:10.4230/LIPIcs.SOCG.2015.507.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers,” 34:507–21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPIcs.SOCG.2015.507."},"has_accepted_license":"1","article_processing_charge":"No","day":"01","scopus_import":"1","file":[{"file_id":"4794","relation":"main_file","checksum":"e6881df44d87fe0c2529c9f7b2724614","date_created":"2018-12-12T10:10:09Z","date_updated":"2020-07-14T12:45:00Z","access_level":"open_access","file_name":"IST-2016-501-v1+1_46.pdf","creator":"system","content_type":"application/pdf","file_size":633712}],"oa_version":"Submitted Version","pubrep_id":"501","intvolume":" 34","title":"Bounding Helly numbers via Betti numbers","status":"public","ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1512","abstract":[{"lang":"eng","text":"We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest."}],"alternative_title":["LIPIcs"],"type":"conference"},{"author":[{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"volume":52,"date_updated":"2021-01-12T06:55:38Z","date_created":"2018-12-11T11:56:01Z","acknowledgement":"Swiss National Science Foundation (SNF 200021-125309, 200020-138230, 200020-12507)","year":"2014","department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","publist_id":"4852","doi":"10.1007/s00454-014-9584-7","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1102.3515"}],"project":[{"grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"quality_controlled":"1","month":"07","oa_version":"Submitted Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"2154","intvolume":" 52","title":"On Gromov's method of selecting heavily covered points","status":"public","issue":"1","abstract":[{"text":"A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that for every d there exists cd > 0 such that for every n-point set P ⊂ ℝd, some point of ℝd is covered by at least (Formula presented.) of the d-simplices spanned by the points of P. The largest possible value of cd has been the subject of ongoing research. Recently Gromov improved the existing lower bounds considerably by introducing a new, topological proof method. We provide an exposition of the combinatorial component of Gromov's approach, in terms accessible to combinatorialists and discrete geometers, and we investigate the limits of his method. In particular, we give tighter bounds on the cofilling profiles for the (n - 1)-simplex. These bounds yield a minor improvement over Gromov's lower bounds on cd for large d, but they also show that the room for further improvement through the cofilling profiles alone is quite small. We also prove a slightly better lower bound for c3 by an approach using an additional structure besides the cofilling profiles. We formulate a combinatorial extremal problem whose solution might perhaps lead to a tight lower bound for cd.","lang":"eng"}],"type":"journal_article","date_published":"2014-07-01T00:00:00Z","citation":{"ama":"Matoušek J, Wagner U. On Gromov’s method of selecting heavily covered points. Discrete & Computational Geometry. 2014;52(1):1-33. doi:10.1007/s00454-014-9584-7","ista":"Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered points. Discrete & Computational Geometry. 52(1), 1–33.","apa":"Matoušek, J., & Wagner, U. (2014). On Gromov’s method of selecting heavily covered points. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-014-9584-7","ieee":"J. Matoušek and U. Wagner, “On Gromov’s method of selecting heavily covered points,” Discrete & Computational Geometry, vol. 52, no. 1. Springer, pp. 1–33, 2014.","mla":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” Discrete & Computational Geometry, vol. 52, no. 1, Springer, 2014, pp. 1–33, doi:10.1007/s00454-014-9584-7.","short":"J. Matoušek, U. Wagner, Discrete & Computational Geometry 52 (2014) 1–33.","chicago":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” Discrete & Computational Geometry. Springer, 2014. https://doi.org/10.1007/s00454-014-9584-7."},"publication":"Discrete & Computational Geometry","page":"1 - 33","day":"01","scopus_import":1},{"article_number":"17 ","publist_id":"4797","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publisher":"ACM","publication_status":"published","year":"2014","acknowledgement":"The research by M. K. was supported by project GAUK 49209. The research by M. K. was also supported by project 1M0545 by the Ministry of Education of the Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague (project P202/12/G061 of GACR). The research by U. W. was supported by the Swiss National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).","volume":61,"date_updated":"2021-01-12T06:55:50Z","date_created":"2018-12-11T11:56:12Z","author":[{"first_name":"Martin","last_name":"Čadek","full_name":"Čadek, Martin"},{"first_name":"Marek","last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","full_name":"Krcál, Marek"},{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"full_name":"Sergeraert, Francis","last_name":"Sergeraert","first_name":"Francis"},{"full_name":"Vokřínek, Lukáš","first_name":"Lukáš","last_name":"Vokřínek"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"month":"05","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1105.6257"}],"language":[{"iso":"eng"}],"doi":"10.1145/2597629","type":"journal_article","issue":"3","abstract":[{"text":"Given topological spaces X,Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X→ Y. We consider a computational version, where X,Y are given as finite simplicial complexes, and the goal is to compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected; in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or computing the Z2-index-everything in the stable range. Outside the stable range, the extension problem is undecidable.","lang":"eng"}],"intvolume":" 61","status":"public","title":"Computing all maps into a sphere","_id":"2184","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","scopus_import":1,"day":"01","citation":{"chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere.” Journal of the ACM. ACM, 2014. https://doi.org/10.1145/2597629.","short":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal of the ACM 61 (2014).","mla":"Čadek, Martin, et al. “Computing All Maps into a Sphere.” Journal of the ACM, vol. 61, no. 3, 17, ACM, 2014, doi:10.1145/2597629.","apa":"Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner, U. (2014). Computing all maps into a sphere. Journal of the ACM. ACM. https://doi.org/10.1145/2597629","ieee":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” Journal of the ACM, vol. 61, no. 3. ACM, 2014.","ista":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing all maps into a sphere. Journal of the ACM. 61(3), 17.","ama":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. Journal of the ACM. 2014;61(3). doi:10.1145/2597629"},"publication":"Journal of the ACM","date_published":"2014-05-01T00:00:00Z"},{"publist_id":"4847","file_date_updated":"2020-07-14T12:45:30Z","publisher":"ACM","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2014","acknowledgement":"Swiss National Science Foundation (Project SNSF-PP00P2-138948)","date_updated":"2023-09-07T11:56:27Z","date_created":"2018-12-11T11:56:03Z","related_material":{"record":[{"id":"1123","relation":"dissertation_contains","status":"public"}]},"author":[{"full_name":"Mabillard, Isaac","first_name":"Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"month":"06","quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"doi":"10.1145/2582112.2582134","conference":{"location":"Kyoto, Japan","start_date":"2014-06-08","end_date":"2014-06-11","name":"SoCG: Symposium on Computational Geometry"},"type":"conference","abstract":[{"lang":"eng","text":"Motivated by topological Tverberg-type problems, we consider multiple (double, triple, and higher multiplicity) selfintersection points of maps from finite simplicial complexes (compact polyhedra) into ℝd and study conditions under which such multiple points can be eliminated. The most classical case is that of embeddings (i.e., maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem, the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary condition for embeddability (namely, vanishing of the van Kampen ob-struction). For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes then one can successively remove these double points by local modifications of the map f. One of the main tools is the famous Whitney trick that permits eliminating pairs of double points of opposite intersection sign. We are interested in generalizing this approach to intersection points of higher multiplicity. We call a point y 2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e., does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time algorithm for deciding this (based on the vanishing of a cohomological obstruction, as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney trick: Given r pairwise disjoint simplices of K such that the intersection of their images contains two r-fold Tverberg points y+ and y- of opposite intersection sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper, we plan to develop this further and present a generalization of the classical Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability of κ-complexes into ℝd for a wider range of dimensions) to intersection points of higher multiplicity."}],"status":"public","title":"Eliminating Tverberg points, I. An analogue of the Whitney trick","ddc":["510"],"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"2159","oa_version":"Submitted Version","file":[{"checksum":"2aae223fee8ffeaf57bbabd8d92b6a2c","date_updated":"2020-07-14T12:45:30Z","date_created":"2018-12-12T10:09:12Z","file_id":"4735","relation":"main_file","creator":"system","content_type":"application/pdf","file_size":914396,"access_level":"open_access","file_name":"IST-2016-534-v1+1_Eliminating_Tverberg_points_I._An_analogue_of_the_Whitney_trick.pdf"}],"pubrep_id":"534","scopus_import":1,"has_accepted_license":"1","day":"08","page":"171 - 180","citation":{"ista":"Mabillard I, Wagner U. 2014. Eliminating Tverberg points, I. An analogue of the Whitney trick. Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, 171–180.","ieee":"I. Mabillard and U. Wagner, “Eliminating Tverberg points, I. An analogue of the Whitney trick,” in Proceedings of the Annual Symposium on Computational Geometry, Kyoto, Japan, 2014, pp. 171–180.","apa":"Mabillard, I., & Wagner, U. (2014). Eliminating Tverberg points, I. An analogue of the Whitney trick. In Proceedings of the Annual Symposium on Computational Geometry (pp. 171–180). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582134","ama":"Mabillard I, Wagner U. Eliminating Tverberg points, I. An analogue of the Whitney trick. In: Proceedings of the Annual Symposium on Computational Geometry. ACM; 2014:171-180. doi:10.1145/2582112.2582134","chicago":"Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue of the Whitney Trick.” In Proceedings of the Annual Symposium on Computational Geometry, 171–80. ACM, 2014. https://doi.org/10.1145/2582112.2582134.","mla":"Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue of the Whitney Trick.” Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 171–80, doi:10.1145/2582112.2582134.","short":"I. Mabillard, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 171–180."},"publication":"Proceedings of the Annual Symposium on Computational Geometry","date_published":"2014-06-08T00:00:00Z"},{"publisher":"ACM","department":[{"_id":"UlWa"}],"status":"public","title":"Embeddability in the 3 sphere is decidable","publication_status":"published","_id":"2157","acknowledgement":"ERC Advanced Grant No. 267165; Grant GRADR Eurogiga GIG/11/E023 (SNSF-PP00P2-138948); Swiss National Science Foundation (SNSF-200020-138230).","year":"2014","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","date_created":"2018-12-11T11:56:02Z","date_updated":"2023-09-11T13:38:49Z","related_material":{"record":[{"id":"425","relation":"later_version","status":"public"}]},"author":[{"full_name":"Matoušek, Jiří","last_name":"Matoušek","first_name":"Jiří"},{"first_name":"Eric","last_name":"Sedgwick","full_name":"Sedgwick, Eric"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","first_name":"Martin","last_name":"Tancer","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","publist_id":"4849","abstract":[{"text":"We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in ℝ3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3 nX with length bounded by a computable function of the number of tetrahedra of X.","lang":"eng"}],"page":"78 - 84","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1402.0815"}],"citation":{"ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Embeddability in the 3 sphere is decidable. In: Proceedings of the Annual Symposium on Computational Geometry. ACM; 2014:78-84. doi:10.1145/2582112.2582137","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2014. Embeddability in the 3 sphere is decidable. Proceedings of the Annual Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, 78–84.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Embeddability in the 3 sphere is decidable,” in Proceedings of the Annual Symposium on Computational Geometry, Kyoto, Japan, 2014, pp. 78–84.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2014). Embeddability in the 3 sphere is decidable. In Proceedings of the Annual Symposium on Computational Geometry (pp. 78–84). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582137","mla":"Matoušek, Jiří, et al. “Embeddability in the 3 Sphere Is Decidable.” Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84, doi:10.1145/2582112.2582137.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, in:, Proceedings of the Annual Symposium on Computational Geometry, ACM, 2014, pp. 78–84.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Embeddability in the 3 Sphere Is Decidable.” In Proceedings of the Annual Symposium on Computational Geometry, 78–84. ACM, 2014. https://doi.org/10.1145/2582112.2582137."},"publication":"Proceedings of the Annual Symposium on Computational Geometry","language":[{"iso":"eng"}],"doi":"10.1145/2582112.2582137","date_published":"2014-06-01T00:00:00Z","conference":{"location":"Kyoto, Japan","start_date":"2014-06-08","end_date":"2014-06-11","name":"SoCG: Symposium on Computational Geometry"},"scopus_import":1,"day":"01","month":"06"},{"date_published":"2013-09-01T00:00:00Z","page":"472 - 483","citation":{"short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.","mla":"Matoušek, Jiří, et al. Untangling Two Systems of Noncrossing Curves. Vol. 8242, Springer, 2013, pp. 472–83, doi:10.1007/978-3-319-03841-4_41.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-319-03841-4_41.","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. 2013;8242:472-483. doi:10.1007/978-3-319-03841-4_41","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2013). Untangling two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network Visualization, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-319-03841-4_41","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of noncrossing curves. 8242, 472–483."},"day":"01","series_title":"Lecture Notes in Computer Science","scopus_import":1,"oa_version":"Preprint","intvolume":" 8242","title":"Untangling two systems of noncrossing curves","status":"public","_id":"2244","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional surface ℳ with boundary. Each αi and each βj is either an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. "}],"alternative_title":["LNCS"],"type":"conference","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-03841-4_41","conference":{"start_date":"2013-09-23","location":"Bordeaux, France","end_date":"2013-09-25","name":"GD: Graph Drawing and Network Visualization"},"project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"quality_controlled":"1","external_id":{"arxiv":["1302.6475"]},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.6475"}],"oa":1,"month":"09","volume":8242,"date_updated":"2023-02-21T17:03:07Z","date_created":"2018-12-11T11:56:32Z","related_material":{"record":[{"id":"1411","relation":"later_version","status":"public"}]},"author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Sedgwick","first_name":"Eric","full_name":"Sedgwick, Eric"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714"},{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published","acknowledgement":"We would like to thank the authors of [GHR13] for mak- ing a draft of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence.","year":"2013","publist_id":"4707"},{"type":"conference","abstract":[{"text":"We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \\no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex. ","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2807","status":"public","ddc":["510"],"title":"Extending continuous maps: Polynomiality and undecidability","pubrep_id":"533","file":[{"file_name":"IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf","access_level":"open_access","file_size":447945,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"5081","date_created":"2018-12-12T10:14:29Z","date_updated":"2020-07-14T12:45:48Z","checksum":"06c2ce5c1135fbc1f71ca15eeb242dcf"}],"oa_version":"Submitted Version","scopus_import":1,"has_accepted_license":"1","day":"01","citation":{"chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner. “Extending Continuous Maps: Polynomiality and Undecidability.” In 45th Annual ACM Symposium on Theory of Computing, 595–604. ACM, 2013. https://doi.org/10.1145/2488608.2488683.","mla":"Čadek, Martin, et al. “Extending Continuous Maps: Polynomiality and Undecidability.” 45th Annual ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604, doi:10.1145/2488608.2488683.","short":"M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, U. Wagner, in:, 45th Annual ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604.","ista":"Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. 2013. Extending continuous maps: Polynomiality and undecidability. 45th Annual ACM Symposium on theory of computing. STOC: Symposium on the Theory of Computing, 595–604.","ieee":"M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, and U. Wagner, “Extending continuous maps: Polynomiality and undecidability,” in 45th Annual ACM Symposium on theory of computing, Palo Alto, CA, United States, 2013, pp. 595–604.","apa":"Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., & Wagner, U. (2013). Extending continuous maps: Polynomiality and undecidability. In 45th Annual ACM Symposium on theory of computing (pp. 595–604). Palo Alto, CA, United States: ACM. https://doi.org/10.1145/2488608.2488683","ama":"Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. Extending continuous maps: Polynomiality and undecidability. In: 45th Annual ACM Symposium on Theory of Computing. ACM; 2013:595-604. doi:10.1145/2488608.2488683"},"publication":"45th Annual ACM Symposium on theory of computing","page":"595 - 604","date_published":"2013-06-01T00:00:00Z","publist_id":"4078","file_date_updated":"2020-07-14T12:45:48Z","year":"2013","publisher":"ACM","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"publication_status":"published","author":[{"first_name":"Martin","last_name":"Čadek","full_name":"Čadek, Martin"},{"full_name":"Krcál, Marek","last_name":"Krcál","first_name":"Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"first_name":"Lukáš","last_name":"Vokřínek","full_name":"Vokřínek, Lukáš"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"date_updated":"2021-01-12T06:59:51Z","date_created":"2018-12-11T11:59:42Z","month":"06","oa":1,"quality_controlled":"1","doi":"10.1145/2488608.2488683","conference":{"name":"STOC: Symposium on the Theory of Computing","end_date":"2013-06-04","location":"Palo Alto, CA, United States","start_date":"2013-06-01"},"language":[{"iso":"eng"}]},{"type":"conference","publist_id":"4466","abstract":[{"lang":"eng","text":"We present an algorithm for computing [X, Y], i.e., all homotopy classes of continuous maps X → Y, where X, Y are topological spaces given as finite simplicial complexes, Y is (d - 1)-connected for some d ≥ 2 (for example, Y can be the d-dimensional sphere S d), and dim X ≤ 2d - 2. These conditions on X, Y guarantee that [X, Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (objects with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the ℤ 2-index, which is a quantity playing a prominent role in Borsuk-Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into ℝ d also amounts to a ℤ 2-index computation. This is the main motivation of our work. We believe that investigating the computational complexity of questions in homotopy theory and similar areas presents a fascinating research area, and we hope that our work may help bridge the cultural gap between algebraic topology and theoretical computer science."}],"extern":1,"year":"2012","_id":"2440","publisher":"SIAM","publication_status":"published","title":"Computing all maps into a sphere","status":"public","author":[{"full_name":"Čadek, Martin","last_name":"Čadek","first_name":"Martin"},{"full_name":"Marek Krcál","first_name":"Marek","last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jiří","last_name":"Matoušek","full_name":"Matoušek, Jiří"},{"last_name":"Sergeraert","first_name":"Francis","full_name":"Sergeraert, Francis"},{"first_name":"Lukáš","last_name":"Vokřínek","full_name":"Vokřínek, Lukáš"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}],"date_updated":"2021-01-12T06:57:30Z","date_created":"2018-12-11T11:57:40Z","day":"01","month":"01","citation":{"ama":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. In: SIAM; 2012:1-10.","ista":"Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2012. Computing all maps into a sphere. SODA: Symposium on Discrete Algorithms, 1–10.","apa":"Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner, U. (2012). Computing all maps into a sphere (pp. 1–10). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","ieee":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner, “Computing all maps into a sphere,” presented at the SODA: Symposium on Discrete Algorithms, 2012, pp. 1–10.","mla":"Čadek, Martin, et al. Computing All Maps into a Sphere. SIAM, 2012, pp. 1–10.","short":"M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, in:, SIAM, 2012, pp. 1–10.","chicago":"Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek, and Uli Wagner. “Computing All Maps into a Sphere,” 1–10. SIAM, 2012."},"main_file_link":[{"open_access":"0","url":"http://arxiv.org/abs/1105.6257"}],"page":"1 - 10","quality_controlled":0,"date_published":"2012-01-01T00:00:00Z","conference":{"name":"SODA: Symposium on Discrete Algorithms"}},{"day":"01","month":"03","doi":"10.1007/s00454-011-9368-2","date_published":"2012-03-01T00:00:00Z","quality_controlled":0,"page":"245 - 265","publication":"Discrete & Computational Geometry","citation":{"ista":"Matoušek J, Tancer M, Wagner U. 2012. A geometric proof of the colored Tverberg theorem. Discrete & Computational Geometry. 47(2), 245–265.","apa":"Matoušek, J., Tancer, M., & Wagner, U. (2012). A geometric proof of the colored Tverberg theorem. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-011-9368-2","ieee":"J. Matoušek, M. Tancer, and U. Wagner, “A geometric proof of the colored Tverberg theorem,” Discrete & Computational Geometry, vol. 47, no. 2. Springer, pp. 245–265, 2012.","ama":"Matoušek J, Tancer M, Wagner U. A geometric proof of the colored Tverberg theorem. Discrete & Computational Geometry. 2012;47(2):245-265. doi:10.1007/s00454-011-9368-2","chicago":"Matoušek, Jiří, Martin Tancer, and Uli Wagner. “A Geometric Proof of the Colored Tverberg Theorem.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-011-9368-2.","mla":"Matoušek, Jiří, et al. “A Geometric Proof of the Colored Tverberg Theorem.” Discrete & Computational Geometry, vol. 47, no. 2, Springer, 2012, pp. 245–65, doi:10.1007/s00454-011-9368-2.","short":"J. Matoušek, M. Tancer, U. Wagner, Discrete & Computational Geometry 47 (2012) 245–265."},"extern":1,"abstract":[{"text":"The colored Tverberg theorem asserts that for eve;ry d and r there exists t=t(d,r) such that for every set C ⊂ ℝ d of cardinality (d + 1)t, partitioned into t-point subsets C 1, C 2,...,C d+1 (which we think of as color classes; e. g., the points of C 1 are red, the points of C 2 blue, etc.), there exist r disjoint sets R 1, R 2,...,R r⊆C that are rainbow, meaning that {pipe}R i∩C j{pipe}≤1 for every i,j, and whose convex hulls all have a common point. All known proofs of this theorem are topological. We present a geometric version of a recent beautiful proof by Blagojević, Matschke, and Ziegler, avoiding a direct use of topological methods. The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience.","lang":"eng"}],"issue":"2","publist_id":"4468","type":"journal_article","date_updated":"2021-01-12T06:57:29Z","date_created":"2018-12-11T11:57:39Z","volume":47,"author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","first_name":"Martin","last_name":"Tancer","full_name":"Martin Tancer"},{"full_name":"Uli Wagner","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","status":"public","title":"A geometric proof of the colored Tverberg theorem","publisher":"Springer","intvolume":" 47","_id":"2438","year":"2012","acknowledgement":"We would like to thank Marek Krcál for useful discussions at initial stages of this research. We also thank Günter M. Ziegler for valuable comments, and Peter Landweber and two anonymous referees for detailed comments and corrections that greatly helped to improve the presentation. In particular, we are indebted to one of the referees for pointing out to us reference [19]. M. Tancer is supported by the grants SVV-2010-261313 (Discrete Methods and Algorithms) and GAUK 49209. U. Wagner’s research is supported by the Swiss National Science Foundation (SNF Projects 200021- 125309 and 200020-125027). "},{"day":"01","month":"07","doi":"10.1016/j.comgeo.2012.03.001","date_published":"2012-07-01T00:00:00Z","page":"566 - 573","quality_controlled":0,"citation":{"chicago":"Chen, Dan, Pat Morin, and Uli Wagner. “Absolute Approximation of Tukey Depth: Theory and Experiments.” Computational Geometry: Theory and Applications. Elsevier, 2012. https://doi.org/10.1016/j.comgeo.2012.03.001.","short":"D. Chen, P. Morin, U. Wagner, Computational Geometry: Theory and Applications 46 (2012) 566–573.","mla":"Chen, Dan, et al. “Absolute Approximation of Tukey Depth: Theory and Experiments.” Computational Geometry: Theory and Applications, vol. 46, no. 5, Elsevier, 2012, pp. 566–73, doi:10.1016/j.comgeo.2012.03.001.","apa":"Chen, D., Morin, P., & Wagner, U. (2012). Absolute approximation of Tukey depth: Theory and experiments. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2012.03.001","ieee":"D. Chen, P. Morin, and U. Wagner, “Absolute approximation of Tukey depth: Theory and experiments,” Computational Geometry: Theory and Applications, vol. 46, no. 5. Elsevier, pp. 566–573, 2012.","ista":"Chen D, Morin P, Wagner U. 2012. Absolute approximation of Tukey depth: Theory and experiments. Computational Geometry: Theory and Applications. 46(5), 566–573.","ama":"Chen D, Morin P, Wagner U. Absolute approximation of Tukey depth: Theory and experiments. Computational Geometry: Theory and Applications. 2012;46(5):566-573. doi:10.1016/j.comgeo.2012.03.001"},"publication":"Computational Geometry: Theory and Applications","extern":1,"publist_id":"4467","issue":"5","abstract":[{"text":"A Monte Carlo approximation algorithm for the Tukey depth problem in high dimensions is introduced. The algorithm is a generalization of an algorithm presented by Rousseeuw and Struyf (1998) . The performance of this algorithm is studied both analytically and experimentally.","lang":"eng"}],"type":"journal_article","volume":46,"date_updated":"2021-01-12T06:57:29Z","date_created":"2018-12-11T11:57:40Z","author":[{"last_name":"Chen","first_name":"Dan","full_name":"Chen, Dan"},{"full_name":"Morin, Pat","first_name":"Pat","last_name":"Morin"},{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Uli Wagner"}],"publisher":"Elsevier","intvolume":" 46","publication_status":"published","title":"Absolute approximation of Tukey depth: Theory and experiments","status":"public","_id":"2439","year":"2012"},{"month":"06","day":"01","conference":{"name":"SGC: Symposuim on Computational Geometry"},"date_published":"2012-06-01T00:00:00Z","doi":"10.1145/2261250.2261272","quality_controlled":0,"page":"151 - 160","citation":{"ama":"Gundert A, Wagner U. On Laplacians of random complexes. In: ACM; 2012:151-160. doi:10.1145/2261250.2261272","apa":"Gundert, A., & Wagner, U. (2012). On Laplacians of random complexes (pp. 151–160). Presented at the SGC: Symposuim on Computational Geometry, ACM. https://doi.org/10.1145/2261250.2261272","ieee":"A. Gundert and U. Wagner, “On Laplacians of random complexes,” presented at the SGC: Symposuim on Computational Geometry, 2012, pp. 151–160.","ista":"Gundert A, Wagner U. 2012. On Laplacians of random complexes. SGC: Symposuim on Computational Geometry, 151–160.","short":"A. Gundert, U. Wagner, in:, ACM, 2012, pp. 151–160.","mla":"Gundert, Anna, and Uli Wagner. On Laplacians of Random Complexes. ACM, 2012, pp. 151–60, doi:10.1145/2261250.2261272.","chicago":"Gundert, Anna, and Uli Wagner. “On Laplacians of Random Complexes,” 151–60. ACM, 2012. https://doi.org/10.1145/2261250.2261272."},"extern":1,"abstract":[{"text":"Eigenvalues associated to graphs are a well-studied subject. In particular the spectra of the adjacency matrix and of the Laplacian of random graphs G(n, p) are known quite precisely. We consider generalizations of these matrices to simplicial complexes of higher dimensions and study their eigenvalues for the Linial-Meshulam model X k(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(log n/n), the eigenvalues of both, the higher-dimensional adjacency matrix and the Laplacian, are a.a.s. sharply concentrated around two values. In a second part of the paper, we discuss a possible higherdimensional analogue of the Discrete Cheeger Inequality. This fundamental inequality expresses a close relationship between the eigenvalues of a graph and its combinatorial expansion properties; in particular, spectral expansion (a large eigenvalue gap) implies edge expansion. Recently, a higher-dimensional analogue of edge expansion for simplicial complexes was introduced by Gromov, and independently by Linial, Meshulam and Wallach and by Newman and Rabinovich. It is natural to ask whether there is a higher-dimensional version of Cheeger's inequality. We show that the most straightforward version of a higher-dimensional Cheeger inequality fails: for every k > 1, there is an infinite family of k-dimensional complexes that are spectrally expanding (there is a large eigenvalue gap for the Laplacian) but not combinatorially expanding.","lang":"eng"}],"publist_id":"4464","type":"conference","date_created":"2018-12-11T11:57:41Z","date_updated":"2021-01-12T06:57:30Z","author":[{"full_name":"Gundert, Anna","first_name":"Anna","last_name":"Gundert"},{"full_name":"Uli Wagner","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","title":"On Laplacians of random complexes","status":"public","publisher":"ACM","_id":"2441","year":"2012"},{"status":"public","publication_status":"published","title":"Hardness of embedding simplicial complexes in Rd","publisher":"European Mathematical Society","intvolume":" 13","_id":"2436","year":"2011","acknowledgement":"We would like to thank Colin Rourke for explanations concerning PL topology and for examples showing the difference between PL embeddability and topological embeddability\nmentioned in Section 2. We also thank Michael Joswig, Gil Kalai, Frank Lutz, Alexander Nabutovsky, and Robin Thomas for kindly answering our questions. The second author would also like to thank Sergio Cabello for helpful discussions regarding linear-time algorithms for EMBED2!2.\nFinally, we are grateful to two anonymous referees for careful reading and valuable suggestions.\nResearch of U.Wagner was supported by the Swiss National Science Foundation (SNF Projects\n200021-116741 and 200021-125309).","date_created":"2018-12-11T11:57:39Z","date_updated":"2021-01-12T06:57:28Z","volume":13,"author":[{"first_name":"Jiří","last_name":"Matoušek","full_name":"Matoušek, Jiří"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin","full_name":"Martin Tancer"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Uli Wagner"}],"type":"journal_article","extern":1,"abstract":[{"text":"Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into Rd? Known results easily imply the polynomiality of EMBEDk→2 (k = 1; 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDd→d and EMBED (d-1)→d are undecidable for each d ≥ 5. Our main result is the NP-hardness of EMBED2→4 and, more generally, of EMBED k→d for all k; d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3. These dimensions fall outside the metastable range of a theorem of Haefliger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spież, Freedman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range the deleted product obstruction is not sufficient to characterize embeddability. ","lang":"eng"}],"issue":"2","publist_id":"4470","quality_controlled":0,"page":"259 - 295","publication":"Journal of the European Mathematical Society","citation":{"ama":"Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in Rd. Journal of the European Mathematical Society. 2011;13(2):259-295. doi:10.4171/JEMS/252","ieee":"J. Matoušek, M. Tancer, and U. Wagner, “Hardness of embedding simplicial complexes in Rd,” Journal of the European Mathematical Society, vol. 13, no. 2. European Mathematical Society, pp. 259–295, 2011.","apa":"Matoušek, J., Tancer, M., & Wagner, U. (2011). Hardness of embedding simplicial complexes in Rd. Journal of the European Mathematical Society. European Mathematical Society. https://doi.org/10.4171/JEMS/252","ista":"Matoušek J, Tancer M, Wagner U. 2011. Hardness of embedding simplicial complexes in Rd. Journal of the European Mathematical Society. 13(2), 259–295.","short":"J. Matoušek, M. Tancer, U. Wagner, Journal of the European Mathematical Society 13 (2011) 259–295.","mla":"Matoušek, Jiří, et al. “Hardness of Embedding Simplicial Complexes in Rd.” Journal of the European Mathematical Society, vol. 13, no. 2, European Mathematical Society, 2011, pp. 259–95, doi:10.4171/JEMS/252.","chicago":"Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial Complexes in Rd.” Journal of the European Mathematical Society. European Mathematical Society, 2011. https://doi.org/10.4171/JEMS/252."},"doi":"10.4171/JEMS/252","date_published":"2011-01-01T00:00:00Z","month":"01","day":"01"},{"_id":"2437","year":"2011","publication_status":"published","status":"public","title":"Minors in random and expanding hypergraphs","publisher":"ACM","author":[{"full_name":"Uli Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"date_updated":"2021-01-12T06:57:29Z","date_created":"2018-12-11T11:57:39Z","type":"conference","abstract":[{"text":"We introduce a new notion of minors for simplicial complexes (hypergraphs), so-called homological minors. Our motivation is to propose a general approach to attack certain extremal problems for sparse simplicial complexes and the corresponding threshold problems for random complexes. In this paper, we focus on threshold problems. The basic model for random complexes is the Linial-Meshulam model Xk(n, p). By definition, such a complex has n vertices, a complete (k -1)-dimensional skeleton, and every possible k-dimensional simplex is chosen independently with probability p. We show that for every k, t≥ 1, there is a constant C = C(k, t) such that for p≥ C/n, the random complex Xk(n, p) asymptotically almost surely contains K tk (the complete k-dimensional complex on t vertices) as a homological minor. As corollary, the threshold for (topological) embeddability of Xk(n, p) into R2k is at p = θ(1/n). The method can be extended to other models of random complexes (for which the lower skeleta are not necessarily complete) and also to more general Tverberg-type problems, where instead of continuous maps without doubly covered image points (embeddings), we consider maps without qfold covered image points.","lang":"eng"}],"publist_id":"4469","extern":1,"citation":{"chicago":"Wagner, Uli. “Minors in Random and Expanding Hypergraphs,” 351–60. ACM, 2011. https://doi.org/10.1145/1998196.1998256.","mla":"Wagner, Uli. Minors in Random and Expanding Hypergraphs. ACM, 2011, pp. 351–60, doi:10.1145/1998196.1998256.","short":"U. Wagner, in:, ACM, 2011, pp. 351–360.","ista":"Wagner U. 2011. Minors in random and expanding hypergraphs. SGC: Symposuim on Computational Geometry, 351–360.","apa":"Wagner, U. (2011). Minors in random and expanding hypergraphs (pp. 351–360). Presented at the SGC: Symposuim on Computational Geometry, ACM. https://doi.org/10.1145/1998196.1998256","ieee":"U. Wagner, “Minors in random and expanding hypergraphs,” presented at the SGC: Symposuim on Computational Geometry, 2011, pp. 351–360.","ama":"Wagner U. Minors in random and expanding hypergraphs. In: ACM; 2011:351-360. doi:10.1145/1998196.1998256"},"quality_controlled":0,"page":"351 - 360","conference":{"name":"SGC: Symposuim on Computational Geometry"},"doi":"10.1145/1998196.1998256","date_published":"2011-01-01T00:00:00Z","month":"01","day":"01"},{"title":"On the embeddability of skeleta of spheres","status":"public","publication_status":"published","intvolume":" 174","publisher":"Springer","_id":"2435","year":"2010","date_updated":"2021-01-12T06:57:28Z","date_created":"2018-12-11T11:57:38Z","volume":174,"author":[{"first_name":"Eran","last_name":"Nevo","full_name":"Nevo, Eran"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Uli Wagner"}],"type":"journal_article","extern":1,"abstract":[{"text":"We consider a generalization of the van Kampen-Flores Theorem and relate it to the long-standing g-conjecture for simplicial spheres.\n","lang":"eng"}],"issue":"1","publist_id":"4472","quality_controlled":0,"page":"381 - 402","publication":"Israel Journal of Mathematics","citation":{"ama":"Nevo E, Wagner U. On the embeddability of skeleta of spheres. Israel Journal of Mathematics. 2010;174(1):381-402. doi:10.1007/s11856-009-0119-5","apa":"Nevo, E., & Wagner, U. (2010). On the embeddability of skeleta of spheres. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-009-0119-5","ieee":"E. Nevo and U. Wagner, “On the embeddability of skeleta of spheres,” Israel Journal of Mathematics, vol. 174, no. 1. Springer, pp. 381–402, 2010.","ista":"Nevo E, Wagner U. 2010. On the embeddability of skeleta of spheres. Israel Journal of Mathematics. 174(1), 381–402.","short":"E. Nevo, U. Wagner, Israel Journal of Mathematics 174 (2010) 381–402.","mla":"Nevo, Eran, and Uli Wagner. “On the Embeddability of Skeleta of Spheres.” Israel Journal of Mathematics, vol. 174, no. 1, Springer, 2010, pp. 381–402, doi:10.1007/s11856-009-0119-5.","chicago":"Nevo, Eran, and Uli Wagner. “On the Embeddability of Skeleta of Spheres.” Israel Journal of Mathematics. Springer, 2010. https://doi.org/10.1007/s11856-009-0119-5."},"doi":"10.1007/s11856-009-0119-5","date_published":"2010-11-01T00:00:00Z","day":"01","month":"11"},{"day":"01","month":"10","date_published":"2009-10-01T00:00:00Z","doi":"10.1016/j.comgeo.2008.03.005","publication":"Computational Geometry: Theory and Applications","citation":{"mla":"Buchin, Kevin, et al. “Transforming Spanning Trees: A Lower Bound.” Computational Geometry: Theory and Applications, vol. 42, no. 8, Elsevier, 2009, pp. 724–30, doi:10.1016/j.comgeo.2008.03.005.","short":"K. Buchin, A. Razen, T. Uno, U. Wagner, Computational Geometry: Theory and Applications 42 (2009) 724–730.","chicago":"Buchin, Kevin, Andreas Razen, Takeaki Uno, and Uli Wagner. “Transforming Spanning Trees: A Lower Bound.” Computational Geometry: Theory and Applications. Elsevier, 2009. https://doi.org/10.1016/j.comgeo.2008.03.005.","ama":"Buchin K, Razen A, Uno T, Wagner U. Transforming spanning trees: A lower bound. Computational Geometry: Theory and Applications. 2009;42(8):724-730. doi:10.1016/j.comgeo.2008.03.005","ista":"Buchin K, Razen A, Uno T, Wagner U. 2009. Transforming spanning trees: A lower bound. Computational Geometry: Theory and Applications. 42(8), 724–730.","apa":"Buchin, K., Razen, A., Uno, T., & Wagner, U. (2009). Transforming spanning trees: A lower bound. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2008.03.005","ieee":"K. Buchin, A. Razen, T. Uno, and U. Wagner, “Transforming spanning trees: A lower bound,” Computational Geometry: Theory and Applications, vol. 42, no. 8. Elsevier, pp. 724–730, 2009."},"quality_controlled":0,"page":"724 - 730","abstract":[{"text":"For a planar point set we consider the graph whose vertices are the crossing-free straight-line spanning trees of the point set, and two such spanning trees are adjacent if their union is crossing-free. An upper bound on the diameter of this graph implies an upper bound on the diameter of the flip graph of pseudo-triangulations of the underlying point set. We prove a lower bound of Ω(logn/loglogn) for the diameter of the transformation graph of spanning trees on a set of n points in the plane. This nearly matches the known upper bound of O(logn). If we measure the diameter in terms of the number of convex layers k of the point set, our lower bound construction is tight, i.e., the diameter is in Ω(logk) which matches the known upper bound of O(logk). So far only constant lower bounds were known.","lang":"eng"}],"publist_id":"4475","issue":"8","extern":1,"type":"journal_article","author":[{"full_name":"Buchin, Kevin","first_name":"Kevin","last_name":"Buchin"},{"first_name":"Andreas","last_name":"Razen","full_name":"Razen, Andreas"},{"first_name":"Takeaki","last_name":"Uno","full_name":"Uno, Takeaki"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}],"date_updated":"2021-01-12T06:57:28Z","date_created":"2018-12-11T11:57:38Z","volume":42,"_id":"2434","year":"2009","title":"Transforming spanning trees: A lower bound","status":"public","publication_status":"published","intvolume":" 42","publisher":"Elsevier"},{"oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/0807.0336"}],"citation":{"chicago":"Matoušek, Jiří, Martin Tancer, and Uli Wagner. “Hardness of Embedding Simplicial Complexes in ℝd,” 855–64. SIAM, 2009.","mla":"Matoušek, Jiří, et al. Hardness of Embedding Simplicial Complexes in ℝd. SIAM, 2009, pp. 855–64.","short":"J. Matoušek, M. Tancer, U. Wagner, in:, SIAM, 2009, pp. 855–864.","ista":"Matoušek J, Tancer M, Wagner U. 2009. Hardness of embedding simplicial complexes in ℝd. SODA: Symposium on Discrete Algorithms, 855–864.","apa":"Matoušek, J., Tancer, M., & Wagner, U. (2009). Hardness of embedding simplicial complexes in ℝd (pp. 855–864). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","ieee":"J. Matoušek, M. Tancer, and U. Wagner, “Hardness of embedding simplicial complexes in ℝd,” presented at the SODA: Symposium on Discrete Algorithms, 2009, pp. 855–864.","ama":"Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in ℝd. In: SIAM; 2009:855-864."},"quality_controlled":0,"page":"855 - 864","conference":{"name":"SODA: Symposium on Discrete Algorithms"},"date_published":"2009-01-01T00:00:00Z","day":"01","month":"01","year":"2009","_id":"2433","title":"Hardness of embedding simplicial complexes in ℝd","publication_status":"published","status":"public","publisher":"SIAM","author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"full_name":"Martin Tancer","first_name":"Martin","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}],"date_updated":"2021-01-12T06:57:27Z","date_created":"2018-12-11T11:57:38Z","type":"conference","abstract":[{"text":"Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into ℝd? Known results easily imply polynomiality of EMBEDk→2 (k = 1, 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3 (even if k is not considered fixed). We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBED d→d and EMBED(d-1)→d are undecidable for each d ≥ 5. Our main result is NP-hardness of EMBED2→4 and, more generally, of EMBEDk→d for all k, d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3.","lang":"eng"}],"publist_id":"4476","extern":1},{"publist_id":"4510","extern":1,"type":"book_chapter","alternative_title":["Contemporary Mathematics"],"author":[{"full_name":"Uli Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"date_updated":"2021-01-12T06:57:21Z","date_created":"2018-12-11T11:57:32Z","volume":453,"year":"2008","_id":"2415","title":"k-Sets and k-facets","publication_status":"published","status":"public","editor":[{"full_name":"Goodman, Jacob E","last_name":"Goodman","first_name":"Jacob"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"full_name":"Pollack, Richard","last_name":"Pollack","first_name":"Richard"}],"publisher":"American Mathematical Society","intvolume":" 453","day":"01","month":"01","date_published":"2008-01-01T00:00:00Z","doi":"10.1090/conm/453","publication":"Surveys on Discrete and Computational Geometry: Twenty Years Later","citation":{"mla":"Wagner, Uli. “K-Sets and k-Facets.” Surveys on Discrete and Computational Geometry: Twenty Years Later, edited by Jacob Goodman et al., vol. 453, American Mathematical Society, 2008, pp. 443–514, doi:10.1090/conm/453.","short":"U. Wagner, in:, J. Goodman, J. Pach, R. Pollack (Eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later, American Mathematical Society, 2008, pp. 443–514.","chicago":"Wagner, Uli. “K-Sets and k-Facets.” In Surveys on Discrete and Computational Geometry: Twenty Years Later, edited by Jacob Goodman, János Pach, and Richard Pollack, 453:443–514. American Mathematical Society, 2008. https://doi.org/10.1090/conm/453.","ama":"Wagner U. k-Sets and k-facets. In: Goodman J, Pach J, Pollack R, eds. Surveys on Discrete and Computational Geometry: Twenty Years Later. Vol 453. American Mathematical Society; 2008:443-514. doi:10.1090/conm/453","ista":"Wagner U. 2008.k-Sets and k-facets. In: Surveys on Discrete and Computational Geometry: Twenty Years Later. Contemporary Mathematics, vol. 453, 443–514.","ieee":"U. Wagner, “k-Sets and k-facets,” in Surveys on Discrete and Computational Geometry: Twenty Years Later, vol. 453, J. Goodman, J. Pach, and R. Pollack, Eds. American Mathematical Society, 2008, pp. 443–514.","apa":"Wagner, U. (2008). k-Sets and k-facets. In J. Goodman, J. Pach, & R. Pollack (Eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later (Vol. 453, pp. 443–514). American Mathematical Society. https://doi.org/10.1090/conm/453"},"quality_controlled":0,"page":"443 - 514"},{"publication_status":"published","status":"public","title":"On center regions and balls containing many points","intvolume":" 5092","publisher":"Springer","_id":"2432","year":"2008","date_updated":"2021-01-12T06:57:27Z","date_created":"2018-12-11T11:57:38Z","volume":5092,"author":[{"full_name":"Smorodinsky, Shakhar","last_name":"Smorodinsky","first_name":"Shakhar"},{"first_name":"Marek","last_name":"Sulovský","full_name":"Sulovský, Marek"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Uli Wagner"}],"alternative_title":["LNCS"],"type":"conference","extern":1,"abstract":[{"text":"We study the disk containment problem introduced by Neumann-Lara and Urrutia and its generalization to higher dimensions. We relate the problem to centerpoints and lower centerpoints of point sets. Moreover, we show that for any set of n points in ℝd, there is a subset A ⊆ S of size [d+3/2] such that any ball containing A contains at least roughly 4/5ed 3n points of S. This improves previous bounds for which the constant was exponentially small in d. We also consider a generalization of the planar disk containment problem to families of pseudodisks.","lang":"eng"}],"publist_id":"4482","quality_controlled":0,"page":"363 - 373","citation":{"ista":"Smorodinsky S, Sulovský M, Wagner U. 2008. On center regions and balls containing many points. COCOON: Conference on Computing and Combinatorics, LNCS, vol. 5092, 363–373.","apa":"Smorodinsky, S., Sulovský, M., & Wagner, U. (2008). On center regions and balls containing many points (Vol. 5092, pp. 363–373). Presented at the COCOON: Conference on Computing and Combinatorics, Springer. https://doi.org/10.1007/978-3-540-69733-6_36","ieee":"S. Smorodinsky, M. Sulovský, and U. Wagner, “On center regions and balls containing many points,” presented at the COCOON: Conference on Computing and Combinatorics, 2008, vol. 5092, pp. 363–373.","ama":"Smorodinsky S, Sulovský M, Wagner U. On center regions and balls containing many points. In: Vol 5092. Springer; 2008:363-373. doi:10.1007/978-3-540-69733-6_36","chicago":"Smorodinsky, Shakhar, Marek Sulovský, and Uli Wagner. “On Center Regions and Balls Containing Many Points,” 5092:363–73. Springer, 2008. https://doi.org/10.1007/978-3-540-69733-6_36.","mla":"Smorodinsky, Shakhar, et al. On Center Regions and Balls Containing Many Points. Vol. 5092, Springer, 2008, pp. 363–73, doi:10.1007/978-3-540-69733-6_36.","short":"S. Smorodinsky, M. Sulovský, U. Wagner, in:, Springer, 2008, pp. 363–373."},"conference":{"name":"COCOON: Conference on Computing and Combinatorics"},"date_published":"2008-01-01T00:00:00Z","doi":"10.1007/978-3-540-69733-6_36","day":"01","month":"01"},{"day":"01","month":"01","page":"613 - 627","quality_controlled":0,"citation":{"mla":"Bang Jensen, Jørgen, et al. “On Six Problems Posed by Jarik Nešetřil.” Topics in Discrete Mathematics, vol. 26, Springer, 2006, pp. 613–27, doi:10.1007/3-540-33700-8_30.","short":"J. Bang Jensen, B. Reed, B. Schacht, R. Šámal, B. Toft, U. Wagner, in:, Topics in Discrete Mathematics, Springer, 2006, pp. 613–627.","chicago":"Bang Jensen, Jørgen, Bruce Reed, Bruce Schacht, Robert Šámal, Bjarne Toft, and Uli Wagner. “On Six Problems Posed by Jarik Nešetřil.” In Topics in Discrete Mathematics, 26:613–27. Springer, 2006. https://doi.org/10.1007/3-540-33700-8_30.","ama":"Bang Jensen J, Reed B, Schacht B, Šámal R, Toft B, Wagner U. On six problems posed by Jarik Nešetřil. In: Topics in Discrete Mathematics. Vol 26. Springer; 2006:613-627. doi:10.1007/3-540-33700-8_30","ista":"Bang Jensen J, Reed B, Schacht B, Šámal R, Toft B, Wagner U. 2006.On six problems posed by Jarik Nešetřil. In: Topics in Discrete Mathematics. Algorithms and Combinatorics, vol. 26, 613–627.","ieee":"J. Bang Jensen, B. Reed, B. Schacht, R. Šámal, B. Toft, and U. Wagner, “On six problems posed by Jarik Nešetřil,” in Topics in Discrete Mathematics, vol. 26, Springer, 2006, pp. 613–627.","apa":"Bang Jensen, J., Reed, B., Schacht, B., Šámal, R., Toft, B., & Wagner, U. (2006). On six problems posed by Jarik Nešetřil. In Topics in Discrete Mathematics (Vol. 26, pp. 613–627). Springer. https://doi.org/10.1007/3-540-33700-8_30"},"publication":"Topics in Discrete Mathematics","doi":"10.1007/3-540-33700-8_30","date_published":"2006-01-01T00:00:00Z","alternative_title":["Algorithms and Combinatorics"],"type":"book_chapter","extern":1,"publist_id":"4509","intvolume":" 26","publisher":"Springer","status":"public","title":"On six problems posed by Jarik Nešetřil","publication_status":"published","year":"2006","_id":"2416","volume":26,"date_updated":"2021-01-12T06:57:21Z","date_created":"2018-12-11T11:57:32Z","author":[{"full_name":"Bang-Jensen, Jørgen","first_name":"Jørgen","last_name":"Bang Jensen"},{"full_name":"Reed, Bruce","last_name":"Reed","first_name":"Bruce"},{"first_name":"Bruce","last_name":"Schacht","full_name":"Schacht, Bruce"},{"first_name":"Robert","last_name":"Šámal","full_name":"Šámal, Robert"},{"first_name":"Bjarne","last_name":"Toft","full_name":"Toft, Bjarne"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}]},{"extern":1,"abstract":[{"lang":"eng","text":"We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√̃) colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses O(log 2 n) colors, and the second is randomized and uses O(log n) colors with high probability. We also show that the O(log 2 n) bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case."}],"issue":"5","publist_id":"4490","type":"journal_article","date_updated":"2021-01-12T06:57:26Z","date_created":"2018-12-11T11:57:37Z","volume":36,"author":[{"first_name":"Ke","last_name":"Chent","full_name":"Chent, Ke"},{"full_name":"Fiat, Amos","first_name":"Amos","last_name":"Fiat"},{"full_name":"Kaplan, Haim","last_name":"Kaplan","first_name":"Haim"},{"first_name":"Meital","last_name":"Levy","full_name":"Levy, Meital B"},{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Mossel","first_name":"Elchanan","full_name":"Mossel, Elchanan"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"last_name":"Smorodinsky","first_name":"Shakhar","full_name":"Smorodinsky, Shakhar"},{"full_name":"Uli Wagner","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"status":"public","title":"Online conflict-free coloring for intervals","publication_status":"published","intvolume":" 36","publisher":"SIAM","_id":"2430","year":"2006","day":"01","month":"01","date_published":"2006-01-01T00:00:00Z","doi":"10.1137/S0097539704446682","quality_controlled":0,"page":"1342 - 1359","publication":"SIAM Journal on Computing","citation":{"short":"K. Chent, A. Fiat, H. Kaplan, M. Levy, J. Matoušek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl, SIAM Journal on Computing 36 (2006) 1342–1359.","mla":"Chent, Ke, et al. “Online Conflict-Free Coloring for Intervals.” SIAM Journal on Computing, vol. 36, no. 5, SIAM, 2006, pp. 1342–59, doi:10.1137/S0097539704446682.","chicago":"Chent, Ke, Amos Fiat, Haim Kaplan, Meital Levy, Jiří Matoušek, Elchanan Mossel, János Pach, et al. “Online Conflict-Free Coloring for Intervals.” SIAM Journal on Computing. SIAM, 2006. https://doi.org/10.1137/S0097539704446682.","ama":"Chent K, Fiat A, Kaplan H, et al. Online conflict-free coloring for intervals. SIAM Journal on Computing. 2006;36(5):1342-1359. doi:10.1137/S0097539704446682","apa":"Chent, K., Fiat, A., Kaplan, H., Levy, M., Matoušek, J., Mossel, E., … Welzl, E. (2006). Online conflict-free coloring for intervals. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/S0097539704446682","ieee":"K. Chent et al., “Online conflict-free coloring for intervals,” SIAM Journal on Computing, vol. 36, no. 5. SIAM, pp. 1342–1359, 2006.","ista":"Chent K, Fiat A, Kaplan H, Levy M, Matoušek J, Mossel E, Pach J, Sharir M, Smorodinsky S, Wagner U, Welzl E. 2006. Online conflict-free coloring for intervals. SIAM Journal on Computing. 36(5), 1342–1359."}},{"date_updated":"2021-01-12T06:57:27Z","date_created":"2018-12-11T11:57:37Z","author":[{"full_name":"Uli Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"title":"On a geometric generalization of the Upper Bound Theorem","publication_status":"published","status":"public","publisher":"IEEE","_id":"2431","year":"2006","extern":1,"abstract":[{"text":"We prove an upper bound, tight up to a factor of 2, for the number of vertices of level at most t in an arrangement of n halfspaces in R , for arbitrary n and d (in particular, the dimension d is not considered constant). This partially settles a conjecture of Eckhoff, Linhart, and Welzl. Up to the factor of 2, the result generalizes McMullen's Upper Bound Theorem for convex polytopes (the case ℓ = O) and extends a theorem of Linhart for the case d ≤ 4. Moreover, the bound sharpens asymptotic estimates obtained by Clarkson and Shor. The proof is based on the h-matrix of the arrangement (a generalization, introduced by Mulmuley, of the h-vector of a convex polytope). We show that bounding appropriate sums of entries of this matrix reduces to a lemma about quadrupels of sets with certain intersection properties, and we prove this lemma, up to a factor of 2, using tools from multilinear algebra. This extends an approach of Alon and Kalai, who used linear algebra methods for an alternative proof of the classical Upper Bound Theorem. The bounds for the entries of the h-matrix also imply bounds for the number of i-dimensional faces, i > 0, at level at most ℓ. Furthermore, we discuss a connection with crossing numbers of graphs that was one of the main motivations for investigating exact bounds that are valid for arbitrary dimensions.","lang":"eng"}],"publist_id":"4489","alternative_title":["IEEE Conference Proceedings"],"type":"conference","conference":{"name":"FOCS: Foundations of Computer Science"},"date_published":"2006-06-08T00:00:00Z","doi":"10.1109/FOCS.2006.53","quality_controlled":0,"page":"635 - 645","citation":{"mla":"Wagner, Uli. On a Geometric Generalization of the Upper Bound Theorem. IEEE, 2006, pp. 635–45, doi:10.1109/FOCS.2006.53.","short":"U. Wagner, in:, IEEE, 2006, pp. 635–645.","chicago":"Wagner, Uli. “On a Geometric Generalization of the Upper Bound Theorem,” 635–45. IEEE, 2006. https://doi.org/10.1109/FOCS.2006.53.","ama":"Wagner U. On a geometric generalization of the Upper Bound Theorem. In: IEEE; 2006:635-645. doi:10.1109/FOCS.2006.53","ista":"Wagner U. 2006. On a geometric generalization of the Upper Bound Theorem. FOCS: Foundations of Computer Science, IEEE Conference Proceedings, , 635–645.","ieee":"U. Wagner, “On a geometric generalization of the Upper Bound Theorem,” presented at the FOCS: Foundations of Computer Science, 2006, pp. 635–645.","apa":"Wagner, U. (2006). On a geometric generalization of the Upper Bound Theorem (pp. 635–645). Presented at the FOCS: Foundations of Computer Science, IEEE. https://doi.org/10.1109/FOCS.2006.53"},"month":"06","day":"08"},{"year":"2006","_id":"2429","intvolume":" 35","publisher":"Springer","status":"public","title":"K-sets in four dimensions","publication_status":"published","author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"last_name":"Smorodinsky","first_name":"Shakhar","full_name":"Smorodinsky, Shakhar"},{"full_name":"Uli Wagner","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":35,"date_updated":"2021-01-12T06:57:26Z","date_created":"2018-12-11T11:57:37Z","type":"journal_article","issue":"2","publist_id":"4495","abstract":[{"lang":"eng","text":"We show, with an elementary proof, that the number of halving simplices in a set of n points in 4 in general position is O(n4-2/45). This improves the previous bound of O(n4-1/134). Our main new ingredient is a bound on the maximum number of halving simplices intersecting a fixed 2-plane. "}],"extern":1,"citation":{"short":"J. Matoušek, M. Sharir, S. Smorodinsky, U. Wagner, Discrete & Computational Geometry 35 (2006) 177–191.","mla":"Matoušek, Jiří, et al. “K-Sets in Four Dimensions.” Discrete & Computational Geometry, vol. 35, no. 2, Springer, 2006, pp. 177–91, doi:10.1007/s00454-005-1200-4.","chicago":"Matoušek, Jiří, Micha Sharir, Shakhar Smorodinsky, and Uli Wagner. “K-Sets in Four Dimensions.” Discrete & Computational Geometry. Springer, 2006. https://doi.org/10.1007/s00454-005-1200-4.","ama":"Matoušek J, Sharir M, Smorodinsky S, Wagner U. K-sets in four dimensions. Discrete & Computational Geometry. 2006;35(2):177-191. doi:10.1007/s00454-005-1200-4","apa":"Matoušek, J., Sharir, M., Smorodinsky, S., & Wagner, U. (2006). K-sets in four dimensions. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-005-1200-4","ieee":"J. Matoušek, M. Sharir, S. Smorodinsky, and U. Wagner, “K-sets in four dimensions,” Discrete & Computational Geometry, vol. 35, no. 2. Springer, pp. 177–191, 2006.","ista":"Matoušek J, Sharir M, Smorodinsky S, Wagner U. 2006. K-sets in four dimensions. Discrete & Computational Geometry. 35(2), 177–191."},"publication":"Discrete & Computational Geometry","page":"177 - 191","quality_controlled":0,"doi":"10.1007/s00454-005-1200-4","date_published":"2006-02-01T00:00:00Z","month":"02","day":"01"},{"day":"01","month":"01","doi":"10.1137/S0097539704446682","date_published":"2005-01-01T00:00:00Z","conference":{"name":"SODA: Symposium on Discrete Algorithms"},"citation":{"chicago":"Fiat, Amos, Meital Levy, Jiří Matoušek, Elchanan Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, and Emo Welzl. “Online Conflict-Free Coloring for Intervals,” 545–54. SIAM, 2005. https://doi.org/10.1137/S0097539704446682.","short":"A. Fiat, M. Levy, J. Matoušek, E. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl, in:, SIAM, 2005, pp. 545–554.","mla":"Fiat, Amos, et al. Online Conflict-Free Coloring for Intervals. SIAM, 2005, pp. 545–54, doi:10.1137/S0097539704446682.","ieee":"A. Fiat et al., “Online conflict-free coloring for intervals,” presented at the SODA: Symposium on Discrete Algorithms, 2005, pp. 545–554.","apa":"Fiat, A., Levy, M., Matoušek, J., Pach, E., Sharir, M., Smorodinsky, S., … Welzl, E. (2005). Online conflict-free coloring for intervals (pp. 545–554). Presented at the SODA: Symposium on Discrete Algorithms, SIAM. https://doi.org/10.1137/S0097539704446682","ista":"Fiat A, Levy M, Matoušek J, Pach E, Sharir M, Smorodinsky S, Wagner U, Welzl E. 2005. Online conflict-free coloring for intervals. SODA: Symposium on Discrete Algorithms, 545–554.","ama":"Fiat A, Levy M, Matoušek J, et al. Online conflict-free coloring for intervals. In: SIAM; 2005:545-554. doi:10.1137/S0097539704446682"},"page":"545 - 554","quality_controlled":0,"publist_id":"4496","abstract":[{"lang":"eng","text":"We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log 2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log 2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open."}],"extern":1,"type":"conference","author":[{"full_name":"Fiat, Amos","last_name":"Fiat","first_name":"Amos"},{"full_name":"Levy, Meital B","last_name":"Levy","first_name":"Meital"},{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"full_name":"Pach, Elchanan M","first_name":"Elchanan","last_name":"Pach"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"last_name":"Smorodinsky","first_name":"Shakhar","full_name":"Smorodinsky, Shakhar"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"date_updated":"2021-01-12T06:57:25Z","date_created":"2018-12-11T11:57:36Z","year":"2005","_id":"2428","publisher":"SIAM","title":"Online conflict-free coloring for intervals","status":"public","publication_status":"published"},{"title":"The Clique problem in intersection graphs of ellipses and triangles","status":"public","publication_status":"published","publisher":"Springer","intvolume":" 38","_id":"2427","year":"2005","date_created":"2018-12-11T11:57:36Z","date_updated":"2021-01-12T06:57:25Z","volume":38,"author":[{"last_name":"Ambühl","first_name":"Christoph","full_name":"Ambühl, Christoph"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Uli Wagner"}],"type":"journal_article","extern":1,"abstract":[{"text":"Intersection graphs of disks and of line segments, respectively, have been well studied, because of both practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses, which, in a sense, interpolate between disks and line segments, and show that the problem is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. Furthermore, the reduction immediately carries over to intersection graphs of triangles. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of convex objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.","lang":"eng"}],"issue":"3","publist_id":"4497","quality_controlled":0,"page":"279 - 292","publication":"Theory of Computing Systems","citation":{"short":"C. Ambühl, U. Wagner, Theory of Computing Systems 38 (2005) 279–292.","mla":"Ambühl, Christoph, and Uli Wagner. “The Clique Problem in Intersection Graphs of Ellipses and Triangles.” Theory of Computing Systems, vol. 38, no. 3, Springer, 2005, pp. 279–92, doi:10.1007/s00224-005-1141-6.","chicago":"Ambühl, Christoph, and Uli Wagner. “The Clique Problem in Intersection Graphs of Ellipses and Triangles.” Theory of Computing Systems. Springer, 2005. https://doi.org/10.1007/s00224-005-1141-6.","ama":"Ambühl C, Wagner U. The Clique problem in intersection graphs of ellipses and triangles. Theory of Computing Systems. 2005;38(3):279-292. doi:10.1007/s00224-005-1141-6","apa":"Ambühl, C., & Wagner, U. (2005). The Clique problem in intersection graphs of ellipses and triangles. Theory of Computing Systems. Springer. https://doi.org/10.1007/s00224-005-1141-6","ieee":"C. Ambühl and U. Wagner, “The Clique problem in intersection graphs of ellipses and triangles,” Theory of Computing Systems, vol. 38, no. 3. Springer, pp. 279–292, 2005.","ista":"Ambühl C, Wagner U. 2005. The Clique problem in intersection graphs of ellipses and triangles. Theory of Computing Systems. 38(3), 279–292."},"date_published":"2005-05-01T00:00:00Z","doi":"10.1007/s00224-005-1141-6","month":"05","day":"01"},{"author":[{"first_name":"László","last_name":"Lovász","full_name":"Lovász, László"},{"first_name":"Katalin","last_name":"Vesztergombi","full_name":"Vesztergombi, Katalin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Uli Wagner"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"date_updated":"2021-01-12T06:57:21Z","date_created":"2018-12-11T11:57:32Z","volume":342,"year":"2004","_id":"2417","publication_status":"published","title":"Convex quadrilaterals and k-sets ","status":"public","intvolume":" 342","editor":[{"full_name":"Pach, János","last_name":"Pach","first_name":"János"}],"publisher":"American Mathematical Society","publist_id":"4508","extern":1,"type":"book_chapter","alternative_title":["Contemporary Mathematics "],"doi":"10.1090/conm/342","date_published":"2004-01-01T00:00:00Z","publication":"Towards a Theory of Geometric Graphs","citation":{"ama":"Lovász L, Vesztergombi K, Wagner U, Welzl E. Convex quadrilaterals and k-sets . In: Pach J, ed. Towards a Theory of Geometric Graphs. Vol 342. American Mathematical Society; 2004:139-148. doi:10.1090/conm/342","apa":"Lovász, L., Vesztergombi, K., Wagner, U., & Welzl, E. (2004). Convex quadrilaterals and k-sets . In J. Pach (Ed.), Towards a Theory of Geometric Graphs (Vol. 342, pp. 139–148). American Mathematical Society. https://doi.org/10.1090/conm/342","ieee":"L. Lovász, K. Vesztergombi, U. Wagner, and E. Welzl, “Convex quadrilaterals and k-sets ,” in Towards a Theory of Geometric Graphs, vol. 342, J. Pach, Ed. American Mathematical Society, 2004, pp. 139–148.","ista":"Lovász L, Vesztergombi K, Wagner U, Welzl E. 2004.Convex quadrilaterals and k-sets . In: Towards a Theory of Geometric Graphs. Contemporary Mathematics , vol. 342, 139–148.","short":"L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl, in:, J. Pach (Ed.), Towards a Theory of Geometric Graphs, American Mathematical Society, 2004, pp. 139–148.","mla":"Lovász, László, et al. “Convex Quadrilaterals and K-Sets .” Towards a Theory of Geometric Graphs, edited by János Pach, vol. 342, American Mathematical Society, 2004, pp. 139–48, doi:10.1090/conm/342.","chicago":"Lovász, László, Katalin Vesztergombi, Uli Wagner, and Emo Welzl. “Convex Quadrilaterals and K-Sets .” In Towards a Theory of Geometric Graphs, edited by János Pach, 342:139–48. American Mathematical Society, 2004. https://doi.org/10.1090/conm/342."},"quality_controlled":0,"page":"139 - 148","month":"01","day":"01"},{"page":"245 - 267","quality_controlled":0,"citation":{"chicago":"Giesen, Joachim, and Uli Wagner. “Shape Dimension and Intrinsic Metric from Samples of Manifolds.” Discrete & Computational Geometry. Springer, 2004. https://doi.org/10.1007/s00454-004-1120-8.","short":"J. Giesen, U. Wagner, Discrete & Computational Geometry 32 (2004) 245–267.","mla":"Giesen, Joachim, and Uli Wagner. “Shape Dimension and Intrinsic Metric from Samples of Manifolds.” Discrete & Computational Geometry, vol. 32, no. 2, Springer, 2004, pp. 245–67, doi:10.1007/s00454-004-1120-8.","ieee":"J. Giesen and U. Wagner, “Shape dimension and intrinsic metric from samples of manifolds,” Discrete & Computational Geometry, vol. 32, no. 2. Springer, pp. 245–267, 2004.","apa":"Giesen, J., & Wagner, U. (2004). Shape dimension and intrinsic metric from samples of manifolds. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-004-1120-8","ista":"Giesen J, Wagner U. 2004. Shape dimension and intrinsic metric from samples of manifolds. Discrete & Computational Geometry. 32(2), 245–267.","ama":"Giesen J, Wagner U. Shape dimension and intrinsic metric from samples of manifolds. Discrete & Computational Geometry. 2004;32(2):245-267. doi:10.1007/s00454-004-1120-8"},"publication":"Discrete & Computational Geometry","doi":"10.1007/s00454-004-1120-8","date_published":"2004-09-01T00:00:00Z","day":"01","month":"09","publisher":"Springer","intvolume":" 32","status":"public","title":"Shape dimension and intrinsic metric from samples of manifolds","publication_status":"published","year":"2004","_id":"2426","volume":32,"date_updated":"2021-01-12T06:57:25Z","date_created":"2018-12-11T11:57:35Z","author":[{"last_name":"Giesen","first_name":"Joachim","full_name":"Giesen, Joachim"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}],"type":"journal_article","extern":1,"publist_id":"4499","issue":"2","abstract":[{"lang":"eng","text":"We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some Euclidean space ℝ d. We assume that M is known to us only through a finite sample P ⊂ M, as is often the case in applications. The adaptive neighborhood graph is a geometric graph on P. Its complexity is at most min{2O(k)n, n2}, where n = P and k = dim M, as opposed to the n[d/2] complexity of the Delaunay triangulation, which is often used to model manifolds. We prove that we can correctly infer the connected components and the dimension of M from the adaptive neighborhood graph provided a certain standard sampling condition is fulfilled. The running time of the dimension detection algorithm is d20(k7 log k) for each connected component of M. If the dimension is considered constant, this is a constant-time operation, and the adaptive neighborhood graph is of linear size. Moreover, the exponential dependence of the constants is only on the intrinsic dimension k, not on the ambient dimension d. This is of particular interest if the co-dimension is high, i.e., if k is much smaller than d, as is the case in many applications. The adaptive neighborhood graph also allows us to approximate the geodesic distances between the points in P."}]},{"type":"journal_article","abstract":[{"text":"A finite set N ⊂ Rd is a weak ε-net for an n-point set X ⊂ Rd (with respect to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set X in Rd admits a weak ε-net of cardinality O(ε-dpolylog(1/ε)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak ε-nets in time O(n ln(1/ε)).","lang":"eng"}],"publist_id":"4500","issue":"2","extern":1,"_id":"2425","year":"2004","publication_status":"published","status":"public","title":"New constructions of weak ε-nets","publisher":"Springer","intvolume":" 32","author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Uli Wagner"}],"date_created":"2018-12-11T11:57:35Z","date_updated":"2021-01-12T06:57:24Z","volume":32,"month":"07","day":"01","publication":"Discrete & Computational Geometry","citation":{"chicago":"Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry. Springer, 2004. https://doi.org/10.1007/s00454-004-1116-4.","short":"J. Matoušek, U. Wagner, Discrete & Computational Geometry 32 (2004) 195–206.","mla":"Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak ε-Nets.” Discrete & Computational Geometry, vol. 32, no. 2, Springer, 2004, pp. 195–206, doi:10.1007/s00454-004-1116-4.","ieee":"J. Matoušek and U. Wagner, “New constructions of weak ε-nets,” Discrete & Computational Geometry, vol. 32, no. 2. Springer, pp. 195–206, 2004.","apa":"Matoušek, J., & Wagner, U. (2004). New constructions of weak ε-nets. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-004-1116-4","ista":"Matoušek J, Wagner U. 2004. New constructions of weak ε-nets. Discrete & Computational Geometry. 32(2), 195–206.","ama":"Matoušek J, Wagner U. New constructions of weak ε-nets. Discrete & Computational Geometry. 2004;32(2):195-206. doi:10.1007/s00454-004-1116-4"},"quality_controlled":0,"page":"195 - 206","date_published":"2004-07-01T00:00:00Z","doi":"10.1007/s00454-004-1116-4"},{"day":"01","month":"01","citation":{"short":"U. Wagner, On K-Sets and Their Applications, ETH Zurich, 2003.","mla":"Wagner, Uli. On K-Sets and Their Applications. ETH Zurich, 2003, doi:10.3929/ethz-a-004708408.","chicago":"Wagner, Uli. “On K-Sets and Their Applications.” ETH Zurich, 2003. https://doi.org/10.3929/ethz-a-004708408.","ama":"Wagner U. On k-Sets and Their Applications. 2003. doi:10.3929/ethz-a-004708408","apa":"Wagner, U. (2003). On k-Sets and Their Applications. ETH Zurich. https://doi.org/10.3929/ethz-a-004708408","ieee":"U. Wagner, “On k-Sets and Their Applications,” ETH Zurich, 2003.","ista":"Wagner U. 2003. On k-Sets and Their Applications. ETH Zurich."},"quality_controlled":0,"doi":"10.3929/ethz-a-004708408","date_published":"2003-01-01T00:00:00Z","type":"dissertation","publist_id":"4511","extern":1,"year":"2003","_id":"2414","publisher":"ETH Zurich","status":"public","publication_status":"published","title":"On k-Sets and Their Applications","author":[{"full_name":"Uli Wagner","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2021-01-12T06:57:20Z","date_created":"2018-12-11T11:57:31Z"},{"date_created":"2018-12-11T11:57:35Z","date_updated":"2021-01-12T06:57:24Z","author":[{"full_name":"Giesen, Joachim","last_name":"Giesen","first_name":"Joachim"},{"full_name":"Uli Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"title":"Shape dimension and intrinsic metric from samples of manifolds with high co-dimension","status":"public","publication_status":"published","publisher":"ACM","year":"2003","_id":"2424","extern":1,"abstract":[{"lang":"eng","text":"We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some (potentially very high-dimensional) Euclidean space ℝd. We assume that M is known to us only through a finite sample P ⊂ M, as it is often the case in applications. The adaptive neighborhood graph is a geometric graph on P. Its complexity is at most min{2O(k)(n, n2}, where n = |P| and k = dim M, as opposed to the n⌈d/2⌉ complexity of the Delaunay triangulation, which is often used to model manifolds. We show that we can provably correctly infer the connectivity of M and the dimension of M from the adaptive neighborhood graph provided a certain standard sampling condition is fulfilled. The running time of the dimension detection algorithm is d2O(k7 log k) for each connected component of M. If the dimension is considered constant, this is a constant-time operation, and the adaptive neighborhood graph is of linear size. Moreover, the exponential dependence of the constants is only on the intrinsic dimension k, not on the ambient dimension d. This is of particular interest if the co-dimension is high, i.e., if k is much smaller than d, as is the case in many applications. The adaptive neighborhood graph also allows us to approximate the geodesic distances between the points in P."}],"publist_id":"4501","type":"conference","conference":{"name":"SoCG: Symposium on Computational Geometry"},"doi":"10.1145/777792.777841","date_published":"2003-06-01T00:00:00Z","quality_controlled":0,"page":"329 - 337","citation":{"ista":"Giesen J, Wagner U. 2003. Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. SoCG: Symposium on Computational Geometry, 329–337.","apa":"Giesen, J., & Wagner, U. (2003). Shape dimension and intrinsic metric from samples of manifolds with high co-dimension (pp. 329–337). Presented at the SoCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/777792.777841","ieee":"J. Giesen and U. Wagner, “Shape dimension and intrinsic metric from samples of manifolds with high co-dimension,” presented at the SoCG: Symposium on Computational Geometry, 2003, pp. 329–337.","ama":"Giesen J, Wagner U. Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. In: ACM; 2003:329-337. doi:10.1145/777792.777841","chicago":"Giesen, Joachim, and Uli Wagner. “Shape Dimension and Intrinsic Metric from Samples of Manifolds with High Co-Dimension,” 329–37. ACM, 2003. https://doi.org/10.1145/777792.777841.","mla":"Giesen, Joachim, and Uli Wagner. Shape Dimension and Intrinsic Metric from Samples of Manifolds with High Co-Dimension. ACM, 2003, pp. 329–37, doi:10.1145/777792.777841.","short":"J. Giesen, U. Wagner, in:, ACM, 2003, pp. 329–337."},"month":"06","day":"01"},{"type":"conference","extern":1,"abstract":[{"text":"A finite set N ⊃ Rd is a weak ε-net for an n-point set X ⊃ Rd (with respect to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al. [7], that every point set X in Rd admits a weak ε-net of cardinality O(ε-d polylog(1/ε)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak ε-nets in time O(n ln(1/ε)). We also prove, by a different method, a near-linear upper bound for points uniformly distributed on the (d - 1)-dimensional sphere.","lang":"eng"}],"publist_id":"4502","status":"public","publication_status":"published","title":"New constructions of weak epsilon-nets","publisher":"ACM","_id":"2423","year":"2003","date_created":"2018-12-11T11:57:34Z","date_updated":"2021-01-12T06:57:24Z","author":[{"last_name":"Matoušek","first_name":"Jiří","full_name":"Matoušek, Jiří"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Uli Wagner"}],"month":"06","day":"01","quality_controlled":0,"page":"129 - 135","citation":{"short":"J. Matoušek, U. Wagner, in:, ACM, 2003, pp. 129–135.","mla":"Matoušek, Jiří, and Uli Wagner. New Constructions of Weak Epsilon-Nets. ACM, 2003, pp. 129–35, doi:10.1145/777792.777813.","chicago":"Matoušek, Jiří, and Uli Wagner. “New Constructions of Weak Epsilon-Nets,” 129–35. ACM, 2003. https://doi.org/10.1145/777792.777813.","ama":"Matoušek J, Wagner U. New constructions of weak epsilon-nets. In: ACM; 2003:129-135. doi:10.1145/777792.777813","ieee":"J. Matoušek and U. Wagner, “New constructions of weak epsilon-nets,” presented at the SoCG: Symposium on Computational Geometry, 2003, pp. 129–135.","apa":"Matoušek, J., & Wagner, U. (2003). New constructions of weak epsilon-nets (pp. 129–135). Presented at the SoCG: Symposium on Computational Geometry, ACM. https://doi.org/10.1145/777792.777813","ista":"Matoušek J, Wagner U. 2003. New constructions of weak epsilon-nets. SoCG: Symposium on Computational Geometry, 129–135."},"conference":{"name":"SoCG: Symposium on Computational Geometry"},"doi":"10.1145/777792.777813","date_published":"2003-06-01T00:00:00Z"},{"abstract":[{"lang":"eng","text":"We prove a lower bound of 0.3288(4 n) for the rectilinear crossing number cr̄(Kn) of a complete graph on n vertices, or in other words, for the minimum number of convex quadrilaterals in any set of n points in general position in the Euclidean plane. As we see it, the main contribution of this paper is not so much the concrete numerical improvement over earlier bounds, as the novel method of proof, which is not based on bounding cr̄(Kn) for some small n."}],"publist_id":"4503","extern":1,"type":"conference","author":[{"full_name":"Uli Wagner","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2018-12-11T11:57:34Z","date_updated":"2021-01-12T06:57:24Z","year":"2003","_id":"2422","title":"On the rectilinear crossing number of complete graphs","status":"public","publication_status":"published","publisher":"SIAM","day":"01","month":"01","conference":{"name":"SODA: Symposium on Discrete Algorithms"},"date_published":"2003-01-01T00:00:00Z","citation":{"ama":"Wagner U. On the rectilinear crossing number of complete graphs. In: SIAM; 2003:583-588.","apa":"Wagner, U. (2003). On the rectilinear crossing number of complete graphs (pp. 583–588). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.","ieee":"U. Wagner, “On the rectilinear crossing number of complete graphs,” presented at the SODA: Symposium on Discrete Algorithms, 2003, pp. 583–588.","ista":"Wagner U. 2003. On the rectilinear crossing number of complete graphs. SODA: Symposium on Discrete Algorithms, 583–588.","short":"U. Wagner, in:, SIAM, 2003, pp. 583–588.","mla":"Wagner, Uli. On the Rectilinear Crossing Number of Complete Graphs. SIAM, 2003, pp. 583–88.","chicago":"Wagner, Uli. “On the Rectilinear Crossing Number of Complete Graphs,” 583–88. SIAM, 2003."},"main_file_link":[{"url":"http://dl.acm.org/citation.cfm?id=644206","open_access":"0"}],"quality_controlled":0,"page":"583 - 588"},{"quality_controlled":"1","language":[{"iso":"eng"}],"conference":{"location":"Vancouver, Canada","start_date":"2002-11-21","end_date":"2002-11-23","name":"ISAAC: International Symposium on Algorithms and Computation"},"doi":"10.1007/3-540-36136-7_43","month":"01","publication_identifier":{"isbn":["9783540001423"]},"publication_status":"published","publisher":"Springer","year":"2002","date_updated":"2023-07-25T11:48:36Z","date_created":"2018-12-11T11:57:34Z","volume":2518,"author":[{"last_name":"Ambühl","first_name":"Christoph","full_name":"Ambühl, Christoph"},{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"extern":"1","publist_id":"4504","page":"489 - 500","publication":"Proceedings of the 13th International Symposium on Algorithms and Computation","citation":{"ieee":"C. Ambühl and U. Wagner, “On the Clique problem in intersection graphs of ellipses,” in Proceedings of the 13th International Symposium on Algorithms and Computation, Vancouver, Canada, 2002, vol. 2518, pp. 489–500.","apa":"Ambühl, C., & Wagner, U. (2002). On the Clique problem in intersection graphs of ellipses. In Proceedings of the 13th International Symposium on Algorithms and Computation (Vol. 2518, pp. 489–500). Vancouver, Canada: Springer. https://doi.org/10.1007/3-540-36136-7_43","ista":"Ambühl C, Wagner U. 2002. On the Clique problem in intersection graphs of ellipses. Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 2518, 489–500.","ama":"Ambühl C, Wagner U. On the Clique problem in intersection graphs of ellipses. In: Proceedings of the 13th International Symposium on Algorithms and Computation. Vol 2518. Springer; 2002:489-500. doi:10.1007/3-540-36136-7_43","chicago":"Ambühl, Christoph, and Uli Wagner. “On the Clique Problem in Intersection Graphs of Ellipses.” In Proceedings of the 13th International Symposium on Algorithms and Computation, 2518:489–500. Springer, 2002. https://doi.org/10.1007/3-540-36136-7_43.","short":"C. Ambühl, U. Wagner, in:, Proceedings of the 13th International Symposium on Algorithms and Computation, Springer, 2002, pp. 489–500.","mla":"Ambühl, Christoph, and Uli Wagner. “On the Clique Problem in Intersection Graphs of Ellipses.” Proceedings of the 13th International Symposium on Algorithms and Computation, vol. 2518, Springer, 2002, pp. 489–500, doi:10.1007/3-540-36136-7_43."},"date_published":"2002-01-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No","title":"On the Clique problem in intersection graphs of ellipses","status":"public","intvolume":" 2518","_id":"2421","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","alternative_title":["LNCS"],"type":"conference","abstract":[{"lang":"eng","text":"Intersection graphs of disks and of line segments, respectively, have been well studied, because of both, practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses which in a sense, interpolate between disc and ellipses, and show that it is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded."}]},{"_id":"2420","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 29","status":"public","title":"On the number of corner cuts","oa_version":"None","type":"journal_article","issue":"2","abstract":[{"text":"A corner cut in dimension d is a finite subset of N0d that can be separated from its complement in N0d by an affine hyperplane disjoint from N0d. Corner cuts were first investigated by Onn and Sturmfels [Adv. Appl. Math. 23 (1999) 29-48], their original motivation stemmed from computational commutative algebra. Let us write (Nd0k)cut for the set of corner cuts of cardinality k; in the computational geometer's terminology, these are the k-sets of N0d. Among other things, Onn and Sturmfels give an upper bound of O(k2d(d-1)/(d+1)) for the size of (Nd0k)cut when the dimension is fixed. In two dimensions, it is known (see [Corteel et al., Adv. Appl. Math. 23 (1) (1999) 49-53]) that #(Nd0k)cut = Θ(k log k). We will see that in general, for any fixed dimension d, the order of magnitude of #(Nd0k)cut is between kd-1 log k and (k log k)d-1. (It has been communicated to me that the same bounds have been found independently by G. Rémond.) In fact, the elements of (Nd0k)cut correspond to the vertices of a certain polytope, and what our proof shows is that the above upper bound holds for the total number of flags of that polytope.","lang":"eng"}],"citation":{"ieee":"U. Wagner, “On the number of corner cuts,” Advances in Applied Mathematics, vol. 29, no. 2. ACM, pp. 152–161, 2002.","apa":"Wagner, U. (2002). On the number of corner cuts. Advances in Applied Mathematics. ACM. https://doi.org/10.1016/S0196-8858(02)00014-3","ista":"Wagner U. 2002. On the number of corner cuts. Advances in Applied Mathematics. 29(2), 152–161.","ama":"Wagner U. On the number of corner cuts. Advances in Applied Mathematics. 2002;29(2):152-161. doi:10.1016/S0196-8858(02)00014-3","chicago":"Wagner, Uli. “On the Number of Corner Cuts.” Advances in Applied Mathematics. ACM, 2002. https://doi.org/10.1016/S0196-8858(02)00014-3.","short":"U. Wagner, Advances in Applied Mathematics 29 (2002) 152–161.","mla":"Wagner, Uli. “On the Number of Corner Cuts.” Advances in Applied Mathematics, vol. 29, no. 2, ACM, 2002, pp. 152–61, doi:10.1016/S0196-8858(02)00014-3."},"publication":"Advances in Applied Mathematics","page":"152 - 161","article_type":"original","date_published":"2002-08-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01","acknowledgement":"I first learned about corner cuts in a seminar talk in which Artur Andrzejak\r\npresented the results from [6]. My work was initiated by that presentation and\r\nby the discussions that followed it. I also thank Komei Fukuda, Ingo Schurr, and\r\nEmo Welzl for helpful comments and discussions.","year":"2002","publisher":"ACM","publication_status":"published","author":[{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"volume":29,"date_created":"2018-12-11T11:57:33Z","date_updated":"2023-07-25T11:55:42Z","publist_id":"4505","extern":"1","quality_controlled":"1","doi":"10.1016/S0196-8858(02)00014-3","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0196-8858"]},"month":"08"},{"publication_identifier":{"issn":["0179-5376"]},"month":"01","language":[{"iso":"eng"}],"doi":"10.1007/s00454-001-0028-9","quality_controlled":"1","extern":"1","publist_id":"4506","volume":26,"date_updated":"2023-05-24T13:13:51Z","date_created":"2018-12-11T11:57:33Z","author":[{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"publisher":"Springer","publication_status":"published","acknowledgement":"We are indebted to Rolf Schneider for many helpful remarks and in particular for bringing reference [6] to our attention","year":"2001","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2001-01-01T00:00:00Z","page":"205 - 219","article_type":"original","citation":{"ieee":"U. Wagner and E. Welzl, “A continuous analogue of the Upper Bound Theorem,” Discrete & Computational Geometry, vol. 26, no. 2. Springer, pp. 205–219, 2001.","apa":"Wagner, U., & Welzl, E. (2001). A continuous analogue of the Upper Bound Theorem. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-001-0028-9","ista":"Wagner U, Welzl E. 2001. A continuous analogue of the Upper Bound Theorem. Discrete & Computational Geometry. 26(2), 205–219.","ama":"Wagner U, Welzl E. A continuous analogue of the Upper Bound Theorem. Discrete & Computational Geometry. 2001;26(2):205-219. doi:10.1007/s00454-001-0028-9","chicago":"Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.” Discrete & Computational Geometry. Springer, 2001. https://doi.org/10.1007/s00454-001-0028-9.","short":"U. Wagner, E. Welzl, Discrete & Computational Geometry 26 (2001) 205–219.","mla":"Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.” Discrete & Computational Geometry, vol. 26, no. 2, Springer, 2001, pp. 205–19, doi:10.1007/s00454-001-0028-9."},"publication":"Discrete & Computational Geometry","issue":"2","abstract":[{"lang":"eng","text":"For an absolutely continuous probability measure μ. on ℝd and a nonnegative integer k, let S̃k(μ, 0) denote the probability that the convex hull of k + d + 1 random points which are i.i.d. according to μ contains the origin 0. For d and k given, we determine a tight upper bound on S̃k(μ, 0), and we characterize the measures in ℝd which attain this bound. As we will see, this result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h-functions, continuous counterparts of h-vectors of simplicial convex polytopes."}],"type":"journal_article","oa_version":"None","intvolume":" 26","title":"A continuous analogue of the Upper Bound Theorem","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"2419"},{"day":"01","month":"05","article_processing_charge":"No","publication_identifier":{"isbn":["9781581132243"]},"scopus_import":"1","language":[{"iso":"eng"}],"conference":{"end_date":"2000-04-14","start_date":"2000-06-12","location":"Clear Water Bay Kowloon, Hong Kong","name":"SCG: Symposium on Computational Geometry"},"doi":"10.1145/336154.336176","date_published":"2000-05-01T00:00:00Z","quality_controlled":"1","page":"50 - 56","publication":"Proceedings of the 16th annual symposium on Computational geometry","citation":{"ista":"Wagner U, Welzl E. 2000. Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem. Proceedings of the 16th annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 50–56.","apa":"Wagner, U., & Welzl, E. (2000). Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem. In Proceedings of the 16th annual symposium on Computational geometry (pp. 50–56). Clear Water Bay Kowloon, Hong Kong: ACM. https://doi.org/10.1145/336154.336176","ieee":"U. Wagner and E. Welzl, “Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem,” in Proceedings of the 16th annual symposium on Computational geometry, Clear Water Bay Kowloon, Hong Kong, 2000, pp. 50–56.","ama":"Wagner U, Welzl E. Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem. In: Proceedings of the 16th Annual Symposium on Computational Geometry. ACM; 2000:50-56. doi:10.1145/336154.336176","chicago":"Wagner, Uli, and Emo Welzl. “Origin-Embracing Distributions or a Continuous Analogue of the Upper Bound Theorem.” In Proceedings of the 16th Annual Symposium on Computational Geometry, 50–56. ACM, 2000. https://doi.org/10.1145/336154.336176.","mla":"Wagner, Uli, and Emo Welzl. “Origin-Embracing Distributions or a Continuous Analogue of the Upper Bound Theorem.” Proceedings of the 16th Annual Symposium on Computational Geometry, ACM, 2000, pp. 50–56, doi:10.1145/336154.336176.","short":"U. Wagner, E. Welzl, in:, Proceedings of the 16th Annual Symposium on Computational Geometry, ACM, 2000, pp. 50–56."},"extern":"1","abstract":[{"lang":"eng","text":"For an absolutely continuous probability measure μ on Rd and a nonnegative integer k, let sk(μ, 0) denote the probability that the convex hull of k+d+1 random points which are i.i.d. according to μ contains the origin 0. For d and k given, we determine a tight upper bound on sk(μ, 0), and we characterize the measures in Rd which attain this bound. This result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h-functions, continuous counterparts of h-vectors for simplicial convex polytopes."}],"publist_id":"4507","type":"conference","date_updated":"2023-05-03T12:41:02Z","date_created":"2018-12-11T11:57:33Z","oa_version":"None","author":[{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"title":"Origin-embracing distributions or a continuous analogue of the Upper Bound Theorem","status":"public","publication_status":"published","publisher":"ACM","year":"2000","_id":"2418","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"}]