[{"language":[{"iso":"eng"}],"ddc":["514","516"],"doi":"10.1007/s10711-017-0291-4","related_material":{"record":[{"relation":"earlier_version","id":"1378","status":"public"}]},"project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948"}],"day":"01","type":"journal_article","author":[{"first_name":"Dominic","full_name":"Dotterrer, Dominic","last_name":"Dotterrer"},{"first_name":"Tali","full_name":"Kaufman, Tali","last_name":"Kaufman"},{"last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"citation":{"short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","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,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>."},"title":"On expansion and topological overlap","department":[{"_id":"UlWa"}],"quality_controlled":"1","publication":"Geometriae Dedicata","status":"public","intvolume":"       195","publisher":"Springer","isi":1,"month":"08","date_created":"2018-12-11T11:48:16Z","page":"307–317","date_updated":"2023-09-27T12:29:57Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000437122700017"]},"scopus_import":"1","publist_id":"6925","has_accepted_license":"1","year":"2018","oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:58Z","volume":195,"pubrep_id":"912","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"publication_status":"published","oa":1,"file":[{"date_created":"2019-01-15T13:44:05Z","relation":"main_file","file_id":"5835","content_type":"application/pdf","access_level":"open_access","date_updated":"2020-07-14T12:47:58Z","checksum":"d2f70fc132156504aa4c626aa378a7ab","file_size":412486,"creator":"kschuh","file_name":"s10711-017-0291-4.pdf"}],"_id":"742","date_published":"2018-08-01T00:00:00Z","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."}],"issue":"1","article_processing_charge":"Yes (via OA deal)"},{"page":"35.1 - 35.10","month":"06","date_created":"2018-12-11T11:51:41Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","department":[{"_id":"UlWa"}],"quality_controlled":"1","intvolume":"        51","status":"public","citation":{"short":"D. Dotterrer, T. Kaufman, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10.","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:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">10.4230/LIPIcs.SoCG.2016.35</a>","apa":"Dotterrer, D., Kaufman, T., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">https://doi.org/10.4230/LIPIcs.SoCG.2016.35</a>","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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">https://doi.org/10.4230/LIPIcs.SoCG.2016.35</a>.","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.","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.","mla":"Dotterrer, Dominic, et al. <i>On Expansion and Topological Overlap</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.35\">10.4230/LIPIcs.SoCG.2016.35</a>."},"conference":{"location":"Medford, MA, USA","name":"SoCG: Symposium on Computational Geometry","end_date":"2016-06-17","start_date":"2016-06-14"},"title":"On expansion and topological overlap","day":"01","alternative_title":["LIPIcs"],"type":"conference","author":[{"full_name":"Dotterrer, Dominic","first_name":"Dominic","last_name":"Dotterrer"},{"full_name":"Kaufman, Tali","first_name":"Tali","last_name":"Kaufman"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"742"}]},"project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948"}],"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2016.35","ddc":["510"],"file":[{"content_type":"application/pdf","file_id":"4699","relation":"main_file","date_created":"2018-12-12T10:08:38Z","file_name":"IST-2016-623-v1+1_LIPIcs-SoCG-2016-35.pdf","file_size":536923,"creator":"system","checksum":"cee65b0e722d50f9d1cc70c90ec1d59b","date_updated":"2020-07-14T12:44:47Z","access_level":"open_access"}],"_id":"1378","date_published":"2016-06-01T00:00:00Z","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 μ &gt; 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"}],"publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:44:47Z","volume":51,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"pubrep_id":"623","publist_id":"5833","year":"2016","has_accepted_license":"1","oa_version":"Published Version","date_updated":"2023-09-27T12:29:56Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1},{"citation":{"short":"I. Mabillard, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12.","apa":"Mabillard, I., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">https://doi.org/10.4230/LIPIcs.SoCG.2016.51</a>","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:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">10.4230/LIPIcs.SoCG.2016.51</a>","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.","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.","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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">https://doi.org/10.4230/LIPIcs.SoCG.2016.51</a>.","mla":"Mabillard, Isaac, and Uli Wagner. <i>Eliminating Higher-Multiplicity Intersections, II. The Deleted Product Criterion in the r-Metastable Range</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2016, p. 51.1-51.12, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.51\">10.4230/LIPIcs.SoCG.2016.51</a>."},"conference":{"location":"Medford, MA, USA","name":"SoCG: Symposium on Computational Geometry","end_date":"2016-06-17","start_date":"2016-06-14"},"title":"Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range","day":"01","alternative_title":["LIPIcs"],"author":[{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac","first_name":"Isaac","last_name":"Mabillard"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner"}],"type":"conference","project":[{"grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"language":[{"iso":"eng"}],"ddc":["510"],"doi":"10.4230/LIPIcs.SoCG.2016.51","page":"51.1 - 51.12","month":"06","date_created":"2018-12-11T11:51:41Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH","department":[{"_id":"UlWa"}],"quality_controlled":"1","status":"public","intvolume":"        51","publist_id":"5830","oa_version":"Published Version","has_accepted_license":"1","year":"2016","date_updated":"2021-01-12T06:50:17Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"file":[{"checksum":"92c0c3735fe908f8ded6e484005cb3b1","access_level":"open_access","date_updated":"2020-07-14T12:44:47Z","file_size":622969,"creator":"system","file_name":"IST-2016-621-v1+1_LIPIcs-SoCG-2016-51.pdf","date_created":"2018-12-12T10:10:06Z","file_id":"4791","relation":"main_file","content_type":"application/pdf"}],"_id":"1381","date_published":"2016-06-01T00:00:00Z","abstract":[{"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.","lang":"eng"}],"publication_status":"published","oa":1,"file_date_updated":"2020-07-14T12:44:47Z","volume":51,"pubrep_id":"621","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"}},{"acknowledgement":"Supported by the ERC Adv anced Grant No. 267165. ","related_material":{"record":[{"relation":"earlier_version","id":"2244","status":"public"}]},"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"}],"title":"Untangling two systems of noncrossing curves","citation":{"apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2016). Untangling two systems of noncrossing curves. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-016-1294-9\">https://doi.org/10.1007/s11856-016-1294-9</a>","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. <i>Israel Journal of Mathematics</i>. 2016;212(1):37-79. doi:<a href=\"https://doi.org/10.1007/s11856-016-1294-9\">10.1007/s11856-016-1294-9</a>","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.” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1, Springer, 2016, pp. 37–79, doi:<a href=\"https://doi.org/10.1007/s11856-016-1294-9\">10.1007/s11856-016-1294-9</a>.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” <i>Israel Journal of Mathematics</i>, vol. 212, no. 1. Springer, pp. 37–79, 2016.","ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2016. Untangling two systems of noncrossing curves. Israel Journal of Mathematics. 212(1), 37–79.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” <i>Israel Journal of Mathematics</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s11856-016-1294-9\">https://doi.org/10.1007/s11856-016-1294-9</a>."},"author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"first_name":"Eric","full_name":"Sedgwick, Eric","last_name":"Sedgwick"},{"orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","full_name":"Tancer, Martin","last_name":"Tancer"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"type":"journal_article","day":"01","publisher":"Springer","intvolume":"       212","status":"public","department":[{"_id":"UlWa"}],"quality_controlled":"1","publication":"Israel Journal of Mathematics","page":"37 - 79","date_created":"2018-12-11T11:51:52Z","month":"05","date_updated":"2023-02-23T10:34:31Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"oa_version":"Preprint","year":"2016","publist_id":"5796","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1302.6475"}],"publication_status":"published","volume":212,"issue":"1","abstract":[{"lang":"eng","text":"We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov."}],"_id":"1411","date_published":"2016-05-01T00:00:00Z"},{"citation":{"ieee":"J. Matoušek and U. Wagner, “On Gromov’s method of selecting heavily covered points,” <i>Discrete &#38; Computational Geometry</i>, vol. 52, no. 1. Springer, pp. 1–33, 2014.","ista":"Matoušek J, Wagner U. 2014. On Gromov’s method of selecting heavily covered points. Discrete &#38; Computational Geometry. 52(1), 1–33.","chicago":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2014. <a href=\"https://doi.org/10.1007/s00454-014-9584-7\">https://doi.org/10.1007/s00454-014-9584-7</a>.","mla":"Matoušek, Jiří, and Uli Wagner. “On Gromov’s Method of Selecting Heavily Covered Points.” <i>Discrete &#38; Computational Geometry</i>, vol. 52, no. 1, Springer, 2014, pp. 1–33, doi:<a href=\"https://doi.org/10.1007/s00454-014-9584-7\">10.1007/s00454-014-9584-7</a>.","short":"J. Matoušek, U. Wagner, Discrete &#38; Computational Geometry 52 (2014) 1–33.","apa":"Matoušek, J., &#38; Wagner, U. (2014). On Gromov’s method of selecting heavily covered points. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-014-9584-7\">https://doi.org/10.1007/s00454-014-9584-7</a>","ama":"Matoušek J, Wagner U. On Gromov’s method of selecting heavily covered points. <i>Discrete &#38; Computational Geometry</i>. 2014;52(1):1-33. doi:<a href=\"https://doi.org/10.1007/s00454-014-9584-7\">10.1007/s00454-014-9584-7</a>"},"title":"On Gromov's method of selecting heavily covered points","day":"01","author":[{"first_name":"Jiří","full_name":"Matoušek, Jiří","last_name":"Matoušek"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner"}],"type":"journal_article","acknowledgement":"Swiss National Science Foundation (SNF 200021-125309, 200020-138230, 200020-12507)","project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948"}],"language":[{"iso":"eng"}],"doi":"10.1007/s00454-014-9584-7","page":"1 - 33","month":"07","date_created":"2018-12-11T11:56:01Z","publisher":"Springer","quality_controlled":"1","department":[{"_id":"UlWa"}],"publication":"Discrete & Computational Geometry","intvolume":"        52","status":"public","publist_id":"4852","year":"2014","oa_version":"Submitted Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:55:38Z","scopus_import":1,"issue":"1","_id":"2154","abstract":[{"lang":"eng","text":"A result of Boros and Füredi (d = 2) and of Bárány (arbitrary d) asserts that for every d there exists cd &gt; 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."}],"date_published":"2014-07-01T00:00:00Z","publication_status":"published","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1102.3515"}],"volume":52},{"volume":8242,"publication_status":"published","oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1302.6475","open_access":"1"}],"_id":"2244","date_published":"2013-09-01T00:00:00Z","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 &quot;untangle&quot; the βj from the αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere with h ≥ 0 boundary components (&quot;holes&quot;), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. "}],"arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-02-21T17:03:07Z","external_id":{"arxiv":["1302.6475"]},"scopus_import":1,"publist_id":"4707","year":"2013","oa_version":"Preprint","department":[{"_id":"UlWa"}],"quality_controlled":"1","intvolume":"      8242","status":"public","publisher":"Springer","month":"09","series_title":"Lecture Notes in Computer Science","date_created":"2018-12-11T11:56:32Z","page":"472 - 483","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-03841-4_41","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.","related_material":{"record":[{"id":"1411","relation":"later_version","status":"public"}]},"project":[{"_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948"}],"day":"01","alternative_title":["LNCS"],"author":[{"full_name":"Matoušek, Jiří","first_name":"Jiří","last_name":"Matoušek"},{"last_name":"Sedgwick","full_name":"Sedgwick, Eric","first_name":"Eric"},{"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","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","citation":{"ista":"Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of noncrossing curves. 8242, 472–483.","ieee":"J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.","chicago":"Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer, 2013. <a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">https://doi.org/10.1007/978-3-319-03841-4_41</a>.","mla":"Matoušek, Jiří, et al. <i>Untangling Two Systems of Noncrossing Curves</i>. Vol. 8242, Springer, 2013, pp. 472–83, doi:<a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">10.1007/978-3-319-03841-4_41</a>.","short":"J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.","apa":"Matoušek, J., Sedgwick, E., Tancer, M., &#38; Wagner, U. (2013). Untangling two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network Visualization, Bordeaux, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">https://doi.org/10.1007/978-3-319-03841-4_41</a>","ama":"Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing curves. 2013;8242:472-483. doi:<a href=\"https://doi.org/10.1007/978-3-319-03841-4_41\">10.1007/978-3-319-03841-4_41</a>"},"conference":{"start_date":"2013-09-23","end_date":"2013-09-25","name":"GD: Graph Drawing and Network Visualization","location":"Bordeaux, France"},"title":"Untangling two systems of noncrossing curves"}]