[{"_id":"793","doi":"10.1016/j.comgeo.2017.07.002","year":"2017","publist_id":"6861","citation":{"ista":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. 2017. On the existence of ordinary triangles. Computational Geometry: Theory and Applications. 66, 28–31.","chicago":"Fulek, Radoslav, Hossein Mojarrad, Márton Naszódi, József Solymosi, Sebastian Stich, and May Szedlák. “On the Existence of Ordinary Triangles.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">https://doi.org/10.1016/j.comgeo.2017.07.002</a>.","mla":"Fulek, Radoslav, et al. “On the Existence of Ordinary Triangles.” <i>Computational Geometry: Theory and Applications</i>, vol. 66, Elsevier, 2017, pp. 28–31, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">10.1016/j.comgeo.2017.07.002</a>.","ama":"Fulek R, Mojarrad H, Naszódi M, Solymosi J, Stich S, Szedlák M. On the existence of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>. 2017;66:28-31. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">10.1016/j.comgeo.2017.07.002</a>","ieee":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, and M. Szedlák, “On the existence of ordinary triangles,” <i>Computational Geometry: Theory and Applications</i>, vol. 66. Elsevier, pp. 28–31, 2017.","short":"R. Fulek, H. Mojarrad, M. Naszódi, J. Solymosi, S. Stich, M. Szedlák, Computational Geometry: Theory and Applications 66 (2017) 28–31.","apa":"Fulek, R., Mojarrad, H., Naszódi, M., Solymosi, J., Stich, S., &#38; Szedlák, M. (2017). On the existence of ordinary triangles. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2017.07.002\">https://doi.org/10.1016/j.comgeo.2017.07.002</a>"},"date_created":"2018-12-11T11:48:32Z","ec_funded":1,"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"publisher":"Elsevier","date_published":"2017-01-01T00:00:00Z","page":"28 - 31","department":[{"_id":"UlWa"}],"volume":66,"quality_controlled":"1","publication_status":"published","external_id":{"isi":["000412039700003"]},"abstract":[{"text":"Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c &gt; 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). ","lang":"eng"}],"language":[{"iso":"eng"}],"publication":"Computational Geometry: Theory and Applications","oa":1,"date_updated":"2023-09-27T12:15:16Z","article_processing_charge":"No","title":"On the existence of ordinary triangles","isi":1,"intvolume":"        66","type":"journal_article","status":"public","author":[{"full_name":"Fulek, Radoslav","first_name":"Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek"},{"last_name":"Mojarrad","full_name":"Mojarrad, Hossein","first_name":"Hossein"},{"last_name":"Naszódi","full_name":"Naszódi, Márton","first_name":"Márton"},{"last_name":"Solymosi","first_name":"József","full_name":"Solymosi, József"},{"first_name":"Sebastian","full_name":"Stich, Sebastian","last_name":"Stich"},{"last_name":"Szedlák","first_name":"May","full_name":"Szedlák, May"}],"publication_identifier":{"issn":["09257721"]},"month":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1701.08183"}],"oa_version":"Submitted Version","day":"01","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"publication":"Computational Geometry: Theory and Applications","language":[{"iso":"eng"}],"scopus_import":"1","intvolume":"        66","isi":1,"title":"C-planarity of embedded cyclic c-graphs","article_processing_charge":"No","oa":1,"date_updated":"2023-09-27T12:14:49Z","type":"journal_article","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.01346"}],"day":"01","oa_version":"Preprint","month":"12","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","first_name":"Radoslav","full_name":"Fulek, Radoslav"}],"doi":"10.1016/j.comgeo.2017.06.016","_id":"794","related_material":{"record":[{"id":"1165","relation":"earlier_version","status":"public"}]},"date_created":"2018-12-11T11:48:32Z","publist_id":"6860","citation":{"mla":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” <i>Computational Geometry: Theory and Applications</i>, vol. 66, Elsevier, 2017, pp. 1–13, doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">10.1016/j.comgeo.2017.06.016</a>.","ista":"Fulek R. 2017. C-planarity of embedded cyclic c-graphs. Computational Geometry: Theory and Applications. 66, 1–13.","chicago":"Fulek, Radoslav. “C-Planarity of Embedded Cyclic c-Graphs.” <i>Computational Geometry: Theory and Applications</i>. Elsevier, 2017. <a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">https://doi.org/10.1016/j.comgeo.2017.06.016</a>.","ieee":"R. Fulek, “C-planarity of embedded cyclic c-graphs,” <i>Computational Geometry: Theory and Applications</i>, vol. 66. Elsevier, pp. 1–13, 2017.","ama":"Fulek R. C-planarity of embedded cyclic c-graphs. <i>Computational Geometry: Theory and Applications</i>. 2017;66:1-13. doi:<a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">10.1016/j.comgeo.2017.06.016</a>","short":"R. Fulek, Computational Geometry: Theory and Applications 66 (2017) 1–13.","apa":"Fulek, R. (2017). C-planarity of embedded cyclic c-graphs. <i>Computational Geometry: Theory and Applications</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.comgeo.2017.06.016\">https://doi.org/10.1016/j.comgeo.2017.06.016</a>"},"year":"2017","acknowledgement":"I would like to thank Jan Kynčl, Dömötör Pálvölgyi and anonymous referees for many comments and suggestions that helped to improve the presentation of the result.","quality_controlled":"1","volume":66,"department":[{"_id":"UlWa"}],"page":"1 - 13","date_published":"2017-12-01T00:00:00Z","publisher":"Elsevier","abstract":[{"text":"We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.","lang":"eng"}],"external_id":{"isi":["000412039700001"]},"publication_status":"published"},{"volume":24,"quality_controlled":"1","department":[{"_id":"UlWa"}],"date_published":"2017-07-28T00:00:00Z","publisher":"International Press","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"abstract":[{"lang":"eng","text":"We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof."}],"ddc":["000"],"publication_status":"published","doi":"10.37236/6663","article_type":"original","_id":"795","file_date_updated":"2020-07-14T12:48:06Z","article_number":"P3.18","ec_funded":1,"date_created":"2018-12-11T11:48:32Z","citation":{"short":"R. Fulek, J. Kynčl, D. Pálvölgyi, Electronic Journal of Combinatorics 24 (2017).","ieee":"R. Fulek, J. Kynčl, and D. Pálvölgyi, “Unified Hanani Tutte theorem,” <i>Electronic Journal of Combinatorics</i>, vol. 24, no. 3. International Press, 2017.","ama":"Fulek R, Kynčl J, Pálvölgyi D. Unified Hanani Tutte theorem. <i>Electronic Journal of Combinatorics</i>. 2017;24(3). doi:<a href=\"https://doi.org/10.37236/6663\">10.37236/6663</a>","chicago":"Fulek, Radoslav, Jan Kynčl, and Dömötör Pálvölgyi. “Unified Hanani Tutte Theorem.” <i>Electronic Journal of Combinatorics</i>. International Press, 2017. <a href=\"https://doi.org/10.37236/6663\">https://doi.org/10.37236/6663</a>.","ista":"Fulek R, Kynčl J, Pálvölgyi D. 2017. Unified Hanani Tutte theorem. Electronic Journal of Combinatorics. 24(3), P3.18.","mla":"Fulek, Radoslav, et al. “Unified Hanani Tutte Theorem.” <i>Electronic Journal of Combinatorics</i>, vol. 24, no. 3, P3.18, International Press, 2017, doi:<a href=\"https://doi.org/10.37236/6663\">10.37236/6663</a>.","apa":"Fulek, R., Kynčl, J., &#38; Pálvölgyi, D. (2017). Unified Hanani Tutte theorem. <i>Electronic Journal of Combinatorics</i>. International Press. <a href=\"https://doi.org/10.37236/6663\">https://doi.org/10.37236/6663</a>"},"publist_id":"6859","year":"2017","status":"public","type":"journal_article","file":[{"creator":"dernst","access_level":"open_access","file_size":236944,"relation":"main_file","content_type":"application/pdf","file_name":"2017_ElectrCombi_Fulek.pdf","file_id":"5853","checksum":"ef320cff0f062051e858f929be6a3581","date_updated":"2020-07-14T12:48:06Z","date_created":"2019-01-18T14:04:08Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"28","month":"07","publication_identifier":{"issn":["10778926"]},"author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"last_name":"Kynčl","first_name":"Jan","full_name":"Kynčl, Jan"},{"full_name":"Pálvölgyi, Dömötör","first_name":"Dömötör","last_name":"Pálvölgyi"}],"publication":"Electronic Journal of Combinatorics","language":[{"iso":"eng"}],"has_accepted_license":"1","intvolume":"        24","scopus_import":"1","title":"Unified Hanani Tutte theorem","issue":"3","article_processing_charge":"No","date_updated":"2022-03-18T12:58:53Z","oa":1},{"year":"2017","citation":{"short":"P. Franek, M. Krcál, Homology, Homotopy and Applications 19 (2017) 313–342.","ieee":"P. Franek and M. Krcál, “Persistence of zero sets,” <i>Homology, Homotopy and Applications</i>, vol. 19, no. 2. International Press, pp. 313–342, 2017.","ama":"Franek P, Krcál M. Persistence of zero sets. <i>Homology, Homotopy and Applications</i>. 2017;19(2):313-342. doi:<a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">10.4310/HHA.2017.v19.n2.a16</a>","mla":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” <i>Homology, Homotopy and Applications</i>, vol. 19, no. 2, International Press, 2017, pp. 313–42, doi:<a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">10.4310/HHA.2017.v19.n2.a16</a>.","chicago":"Franek, Peter, and Marek Krcál. “Persistence of Zero Sets.” <i>Homology, Homotopy and Applications</i>. International Press, 2017. <a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">https://doi.org/10.4310/HHA.2017.v19.n2.a16</a>.","ista":"Franek P, Krcál M. 2017. Persistence of zero sets. Homology, Homotopy and Applications. 19(2), 313–342.","apa":"Franek, P., &#38; Krcál, M. (2017). Persistence of zero sets. <i>Homology, Homotopy and Applications</i>. International Press. <a href=\"https://doi.org/10.4310/HHA.2017.v19.n2.a16\">https://doi.org/10.4310/HHA.2017.v19.n2.a16</a>"},"publist_id":"7246","date_created":"2018-12-11T11:47:14Z","ec_funded":1,"_id":"568","doi":"10.4310/HHA.2017.v19.n2.a16","publication_status":"published","abstract":[{"lang":"eng","text":"We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z&lt; r(f) := (g-1(0): ||g - f|| &lt; r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z&lt; r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r &gt; 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C)."}],"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","name":"Atomic-Resolution Structures of Mitochondrial Respiratory Chain Supercomplexes (H2020)","grant_number":"701309","_id":"2590DB08-B435-11E9-9278-68D0E5697425"}],"date_published":"2017-01-01T00:00:00Z","publisher":"International Press","volume":19,"quality_controlled":"1","page":"313 - 342","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"issue":"2","oa":1,"date_updated":"2021-01-12T08:03:12Z","title":"Persistence of zero sets","intvolume":"        19","scopus_import":1,"language":[{"iso":"eng"}],"publication":"Homology, Homotopy and Applications","author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","last_name":"Franek","first_name":"Peter","full_name":"Franek, Peter"},{"last_name":"Krcál","id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Krcál, Marek"}],"month":"01","publication_identifier":{"issn":["15320073"]},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"Submitted Version","main_file_link":[{"url":"https://arxiv.org/abs/1507.04310","open_access":"1"}],"status":"public","type":"journal_article"},{"status":"public","type":"journal_article","month":"10","oa_version":"Preprint","day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1610.09063"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"first_name":"Isaac","full_name":"Mabillard, Isaac","last_name":"Mabillard","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"orcid":"0000-0002-3975-1683","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"publication":"Israel Journal of Mathematics","language":[{"iso":"eng"}],"scopus_import":1,"intvolume":"       222","date_updated":"2023-02-23T10:02:13Z","oa":1,"issue":"2","title":"On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result","publisher":"Springer","date_published":"2017-10-01T00:00:00Z","department":[{"_id":"UlWa"}],"page":"841 - 866","quality_controlled":"1","volume":222,"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"abstract":[{"lang":"eng","text":"The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition."}],"publication_status":"published","doi":"10.1007/s11856-017-1607-7","_id":"610","ec_funded":1,"related_material":{"record":[{"id":"1511","relation":"earlier_version","status":"public"}]},"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).","year":"2017","date_created":"2018-12-11T11:47:29Z","publist_id":"7194","citation":{"short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel Journal of Mathematics 222 (2017) 841–866.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. <i>Israel Journal of Mathematics</i>. 2017;222(2):841-866. doi:<a href=\"https://doi.org/10.1007/s11856-017-1607-7\">10.1007/s11856-017-1607-7</a>","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result,” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2. Springer, pp. 841–866, 2017.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s11856-017-1607-7\">https://doi.org/10.1007/s11856-017-1607-7</a>.","mla":"Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” <i>Israel Journal of Mathematics</i>, vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:<a href=\"https://doi.org/10.1007/s11856-017-1607-7\">10.1007/s11856-017-1607-7</a>.","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.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-017-1607-7\">https://doi.org/10.1007/s11856-017-1607-7</a>"}},{"publication_status":"published","abstract":[{"text":"A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle.","lang":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"project":[{"name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734"},{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","volume":92,"department":[{"_id":"UlWa"}],"date_published":"2017-12-01T00:00:00Z","license":"https://creativecommons.org/licenses/by/4.0/","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2019-06-04T12:11:52Z","citation":{"apa":"Fulek, R. (2017). Embedding graphs into embedded graphs (Vol. 92). Presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">https://doi.org/10.4230/LIPICS.ISAAC.2017.34</a>","mla":"Fulek, Radoslav. <i>Embedding Graphs into Embedded Graphs</i>. Vol. 92, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">10.4230/LIPICS.ISAAC.2017.34</a>.","chicago":"Fulek, Radoslav. “Embedding Graphs into Embedded Graphs,” Vol. 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">https://doi.org/10.4230/LIPICS.ISAAC.2017.34</a>.","ista":"Fulek R. 2017. Embedding graphs into embedded graphs. ISAAC: International Symposium on Algorithms and Computation vol. 92, 34.","ama":"Fulek R. Embedding graphs into embedded graphs. In: Vol 92. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:<a href=\"https://doi.org/10.4230/LIPICS.ISAAC.2017.34\">10.4230/LIPICS.ISAAC.2017.34</a>","ieee":"R. Fulek, “Embedding graphs into embedded graphs,” presented at the ISAAC: International Symposium on Algorithms and Computation, Phuket, Thailand, 2017, vol. 92.","short":"R. Fulek, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017."},"year":"2017","article_number":"34","ec_funded":1,"_id":"6517","file_date_updated":"2020-07-14T12:47:33Z","doi":"10.4230/LIPICS.ISAAC.2017.34","author":[{"id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","first_name":"Radoslav"}],"file":[{"date_updated":"2020-07-14T12:47:33Z","date_created":"2019-06-04T12:20:35Z","file_id":"6518","checksum":"fc7a643e29621c8bbe49d36b39081f31","file_name":"2017_LIPIcs-Fulek.pdf","file_size":588982,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"kschuh"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"Published Version","month":"12","conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","start_date":"2017-12-09","location":"Phuket, Thailand","end_date":"2017-12-22"},"type":"conference","status":"public","title":"Embedding graphs into embedded graphs","oa":1,"date_updated":"2021-01-12T08:07:51Z","has_accepted_license":"1","scopus_import":1,"intvolume":"        92","language":[{"iso":"eng"}]},{"title":"A proof of the orbit conjecture for flipping edge labelled triangulations","date_updated":"2023-09-05T15:01:43Z","oa":1,"pubrep_id":"896","has_accepted_license":"1","intvolume":"        77","scopus_import":1,"language":[{"iso":"eng"}],"author":[{"last_name":"Lubiw","full_name":"Lubiw, Anna","first_name":"Anna"},{"full_name":"Masárová, Zuzana","first_name":"Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli"}],"day":"01","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_size":710007,"creator":"system","date_created":"2018-12-12T10:17:12Z","date_updated":"2020-07-14T12:47:41Z","file_name":"IST-2017-896-v1+1_LIPIcs-SoCG-2017-49.pdf","checksum":"24fdde981cc513352a78dcf9b0660ae9","file_id":"5265"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2017-07-04","location":"Brisbane, Australia","end_date":"2017-07-07"},"month":"06","alternative_title":["LIPIcs"],"status":"public","type":"conference","date_created":"2018-12-11T11:47:54Z","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.","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:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">10.4230/LIPIcs.SoCG.2017.49</a>","short":"A. Lubiw, Z. Masárová, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.","mla":"Lubiw, Anna, et al. <i>A Proof of the Orbit Conjecture for Flipping Edge Labelled Triangulations</i>. Vol. 77, 49, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">10.4230/LIPIcs.SoCG.2017.49</a>.","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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">https://doi.org/10.4230/LIPIcs.SoCG.2017.49</a>.","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.","apa":"Lubiw, A., Masárová, Z., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.49\">https://doi.org/10.4230/LIPIcs.SoCG.2017.49</a>"},"publist_id":"7033","year":"2017","article_number":"49","related_material":{"record":[{"status":"public","relation":"later_version","id":"5986"}]},"file_date_updated":"2020-07-14T12:47:41Z","_id":"683","doi":"10.4230/LIPIcs.SoCG.2017.49","publication_status":"published","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."}],"ddc":["514","516"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":77,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2017-06-01T00:00:00Z"},{"month":"06","publication_identifier":{"issn":["18688969"]},"conference":{"start_date":"2017-07-04","name":"Symposium on Computational Geometry, SoCG","end_date":"2017-07-07","location":"Brisbane, Australia"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"file_size":990546,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"system","date_updated":"2020-07-14T12:47:42Z","date_created":"2018-12-12T10:11:03Z","checksum":"067ab0cb3f962bae6c3af6bf0094e0f3","file_id":"4856","file_name":"IST-2017-895-v1+1_LIPIcs-SoCG-2017-39.pdf"}],"oa_version":"Published Version","day":"01","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"first_name":"Hubert","full_name":"Wagner, Hubert","last_name":"Wagner","id":"379CA8B8-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","status":"public","alternative_title":["LIPIcs"],"scopus_import":1,"has_accepted_license":"1","intvolume":"        77","oa":1,"date_updated":"2021-01-12T08:09:26Z","pubrep_id":"895","title":"Topological data analysis with Bregman divergences","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["514","516"],"abstract":[{"text":"We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory. ","lang":"eng"}],"publication_status":"published","date_published":"2017-06-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":77,"quality_controlled":"1","page":"391-3916","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"year":"2017","publist_id":"7021","date_created":"2018-12-11T11:47:56Z","citation":{"apa":"Edelsbrunner, H., &#38; Wagner, H. (2017). Topological data analysis with Bregman divergences (Vol. 77, pp. 391–3916). Presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">https://doi.org/10.4230/LIPIcs.SoCG.2017.39</a>","ieee":"H. Edelsbrunner and H. Wagner, “Topological data analysis with Bregman divergences,” presented at the Symposium on Computational Geometry, SoCG, Brisbane, Australia, 2017, vol. 77, pp. 391–3916.","ama":"Edelsbrunner H, Wagner H. Topological data analysis with Bregman divergences. In: Vol 77. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017:391-3916. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">10.4230/LIPIcs.SoCG.2017.39</a>","short":"H. Edelsbrunner, H. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916.","ista":"Edelsbrunner H, Wagner H. 2017. Topological data analysis with Bregman divergences. Symposium on Computational Geometry, SoCG, LIPIcs, vol. 77, 391–3916.","mla":"Edelsbrunner, Herbert, and Hubert Wagner. <i>Topological Data Analysis with Bregman Divergences</i>. Vol. 77, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 391–3916, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">10.4230/LIPIcs.SoCG.2017.39</a>.","chicago":"Edelsbrunner, Herbert, and Hubert Wagner. “Topological Data Analysis with Bregman Divergences,” 77:391–3916. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2017.39\">https://doi.org/10.4230/LIPIcs.SoCG.2017.39</a>."},"doi":"10.4230/LIPIcs.SoCG.2017.39","_id":"688","file_date_updated":"2020-07-14T12:47:42Z"},{"author":[{"first_name":"Martin","full_name":"Čadek, Martin","last_name":"Čadek"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál","full_name":"Krcál, Marek","first_name":"Marek"},{"last_name":"Vokřínek","first_name":"Lukáš","full_name":"Vokřínek, Lukáš"}],"month":"06","publication_identifier":{"issn":["01795376"]},"oa_version":"Submitted Version","day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1307.6444"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","type":"journal_article","oa":1,"date_updated":"2023-09-20T12:01:28Z","issue":"4","article_processing_charge":"No","title":"Algorithmic solvability of the lifting extension problem","isi":1,"scopus_import":"1","intvolume":"        54","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","publication_status":"published","external_id":{"isi":["000400072700008"]},"abstract":[{"lang":"eng","text":"Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation."}],"publisher":"Springer","date_published":"2017-06-01T00:00:00Z","page":"915 - 965","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":54,"year":"2017","citation":{"ista":"Čadek M, Krcál M, Vokřínek L. 2017. Algorithmic solvability of the lifting extension problem. Discrete &#38; Computational Geometry. 54(4), 915–965.","mla":"Čadek, Martin, et al. “Algorithmic Solvability of the Lifting Extension Problem.” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 4, Springer, 2017, pp. 915–65, doi:<a href=\"https://doi.org/10.1007/s00454-016-9855-6\">10.1007/s00454-016-9855-6</a>.","chicago":"Čadek, Martin, Marek Krcál, and Lukáš Vokřínek. “Algorithmic Solvability of the Lifting Extension Problem.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00454-016-9855-6\">https://doi.org/10.1007/s00454-016-9855-6</a>.","short":"M. Čadek, M. Krcál, L. Vokřínek, Discrete &#38; Computational Geometry 54 (2017) 915–965.","ieee":"M. Čadek, M. Krcál, and L. Vokřínek, “Algorithmic solvability of the lifting extension problem,” <i>Discrete &#38; Computational Geometry</i>, vol. 54, no. 4. Springer, pp. 915–965, 2017.","ama":"Čadek M, Krcál M, Vokřínek L. Algorithmic solvability of the lifting extension problem. <i>Discrete &#38; Computational Geometry</i>. 2017;54(4):915-965. doi:<a href=\"https://doi.org/10.1007/s00454-016-9855-6\">10.1007/s00454-016-9855-6</a>","apa":"Čadek, M., Krcál, M., &#38; Vokřínek, L. (2017). Algorithmic solvability of the lifting extension problem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-016-9855-6\">https://doi.org/10.1007/s00454-016-9855-6</a>"},"publist_id":"6309","date_created":"2018-12-11T11:50:00Z","_id":"1073","doi":"10.1007/s00454-016-9855-6"},{"publist_id":"6254","citation":{"apa":"Fulek, R., Pelsmajer, M., &#38; Schaefer, M. (2017). Hanani-Tutte for radial planarity. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00408\">https://doi.org/10.7155/jgaa.00408</a>","ieee":"R. Fulek, M. Pelsmajer, and M. Schaefer, “Hanani-Tutte for radial planarity,” <i>Journal of Graph Algorithms and Applications</i>, vol. 21, no. 1. Brown University, pp. 135–154, 2017.","ama":"Fulek R, Pelsmajer M, Schaefer M. Hanani-Tutte for radial planarity. <i>Journal of Graph Algorithms and Applications</i>. 2017;21(1):135-154. doi:<a href=\"https://doi.org/10.7155/jgaa.00408\">10.7155/jgaa.00408</a>","short":"R. Fulek, M. Pelsmajer, M. Schaefer, Journal of Graph Algorithms and Applications 21 (2017) 135–154.","chicago":"Fulek, Radoslav, Michael Pelsmajer, and Marcus Schaefer. “Hanani-Tutte for Radial Planarity.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2017. <a href=\"https://doi.org/10.7155/jgaa.00408\">https://doi.org/10.7155/jgaa.00408</a>.","mla":"Fulek, Radoslav, et al. “Hanani-Tutte for Radial Planarity.” <i>Journal of Graph Algorithms and Applications</i>, vol. 21, no. 1, Brown University, 2017, pp. 135–54, doi:<a href=\"https://doi.org/10.7155/jgaa.00408\">10.7155/jgaa.00408</a>.","ista":"Fulek R, Pelsmajer M, Schaefer M. 2017. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications. 21(1), 135–154."},"date_created":"2018-12-11T11:50:13Z","year":"2017","related_material":{"record":[{"status":"public","id":"1164","relation":"earlier_version"},{"status":"public","id":"1595","relation":"earlier_version"}]},"ec_funded":1,"article_type":"original","_id":"1113","file_date_updated":"2019-10-24T10:54:37Z","doi":"10.7155/jgaa.00408","publication_status":"published","abstract":[{"text":"A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth.","lang":"eng"}],"external_id":{"arxiv":["1608.08662"]},"ddc":["510"],"project":[{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"volume":21,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"135 - 154","date_published":"2017-01-01T00:00:00Z","publisher":"Brown University","title":"Hanani-Tutte for radial planarity","issue":"1","article_processing_charge":"No","date_updated":"2023-02-23T10:05:57Z","oa":1,"intvolume":"        21","scopus_import":1,"has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"Journal of Graph Algorithms and Applications","arxiv":1,"author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","full_name":"Fulek, Radoslav","first_name":"Radoslav"},{"last_name":"Pelsmajer","full_name":"Pelsmajer, Michael","first_name":"Michael"},{"last_name":"Schaefer","first_name":"Marcus","full_name":"Schaefer, Marcus"}],"file":[{"file_size":573623,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","creator":"dernst","date_created":"2019-10-24T10:54:37Z","date_updated":"2019-10-24T10:54:37Z","success":1,"file_id":"6967","file_name":"2017_JournalGraphAlgorithms_Fulek.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa_version":"Published Version","month":"01","status":"public","type":"journal_article"},{"status":"public","type":"book_chapter","author":[{"last_name":"Goaoc","first_name":"Xavier","full_name":"Goaoc, Xavier"},{"first_name":"Pavel","full_name":"Paták, Pavel","last_name":"Paták"},{"first_name":"Zuzana","full_name":"Patakova, Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683"},{"last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","first_name":"Martin"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli"}],"publication_identifier":{"isbn":["978-331944479-6"]},"month":"10","day":"06","main_file_link":[{"url":"https://arxiv.org/abs/1310.4613v3","open_access":"1"}],"oa_version":"Published Version","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"publication":"A Journey through Discrete Mathematics: A Tribute to Jiri Matousek","oa":1,"date_updated":"2024-02-28T12:59:37Z","title":"Bounding helly numbers via betti numbers","editor":[{"last_name":"Loebl","first_name":"Martin","full_name":"Loebl, Martin"},{"full_name":"Nešetřil, Jaroslav","first_name":"Jaroslav","last_name":"Nešetřil"},{"first_name":"Robin","full_name":"Thomas, Robin","last_name":"Thomas"}],"scopus_import":1,"publisher":"Springer","date_published":"2017-10-06T00:00:00Z","department":[{"_id":"UlWa"}],"page":"407 - 447","quality_controlled":"1","publication_status":"published","series_title":"A Journey Through Discrete Mathematics","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 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)."}],"_id":"424","doi":"10.1007/978-3-319-44479-6_17","year":"2017","date_created":"2018-12-11T11:46:24Z","publist_id":"7399","citation":{"apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2017). Bounding helly numbers via betti numbers. In M. Loebl, J. Nešetřil, &#38; R. Thomas (Eds.), <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i> (pp. 407–447). Springer. <a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">https://doi.org/10.1007/978-3-319-44479-6_17</a>","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. <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>. A Journey Through Discrete Mathematics. Springer; 2017:407-447. doi:<a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">10.1007/978-3-319-44479-6_17</a>","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly numbers via betti numbers,” in <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017, pp. 407–447.","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.","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.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers.” In <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, edited by Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">https://doi.org/10.1007/978-3-319-44479-6_17</a>.","mla":"Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, edited by Martin Loebl et al., Springer, 2017, pp. 407–47, doi:<a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">10.1007/978-3-319-44479-6_17</a>."},"related_material":{"record":[{"status":"public","id":"1512","relation":"earlier_version"}]}},{"citation":{"short":"B. Burton, A.N. de Mesmay, U. Wagner, Discrete &#38; Computational Geometry 58 (2017) 871–888.","ama":"Burton B, de Mesmay AN, Wagner U. Finding non-orientable surfaces in 3-Manifolds. <i>Discrete &#38; Computational Geometry</i>. 2017;58(4):871-888. doi:<a href=\"https://doi.org/10.1007/s00454-017-9900-0\">10.1007/s00454-017-9900-0</a>","ieee":"B. Burton, A. N. de Mesmay, and U. Wagner, “Finding non-orientable surfaces in 3-Manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 4. Springer, pp. 871–888, 2017.","mla":"Burton, Benjamin, et al. “Finding Non-Orientable Surfaces in 3-Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 4, Springer, 2017, pp. 871–88, doi:<a href=\"https://doi.org/10.1007/s00454-017-9900-0\">10.1007/s00454-017-9900-0</a>.","chicago":"Burton, Benjamin, Arnaud N de Mesmay, and Uli Wagner. “Finding Non-Orientable Surfaces in 3-Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2017. <a href=\"https://doi.org/10.1007/s00454-017-9900-0\">https://doi.org/10.1007/s00454-017-9900-0</a>.","ista":"Burton B, de Mesmay AN, Wagner U. 2017. Finding non-orientable surfaces in 3-Manifolds. Discrete &#38; Computational Geometry. 58(4), 871–888.","apa":"Burton, B., de Mesmay, A. N., &#38; Wagner, U. (2017). Finding non-orientable surfaces in 3-Manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-017-9900-0\">https://doi.org/10.1007/s00454-017-9900-0</a>"},"publist_id":"7283","date_created":"2018-12-11T11:47:01Z","year":"2017","related_material":{"record":[{"relation":"earlier_version","id":"1379","status":"public"}]},"article_type":"original","_id":"534","doi":"10.1007/s00454-017-9900-0","publication_status":"published","external_id":{"arxiv":["1602.07907"]},"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"}],"department":[{"_id":"UlWa"}],"page":"871 - 888","quality_controlled":"1","volume":58,"publisher":"Springer","date_published":"2017-06-09T00:00:00Z","title":"Finding non-orientable surfaces in 3-Manifolds","oa":1,"date_updated":"2023-02-21T17:01:34Z","issue":"4","article_processing_charge":"No","intvolume":"        58","scopus_import":1,"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","author":[{"last_name":"Burton","full_name":"Burton, Benjamin","first_name":"Benjamin"},{"id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","last_name":"De Mesmay","first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"arxiv":1,"oa_version":"Preprint","day":"09","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.07907"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"06","publication_identifier":{"issn":["01795376"]},"type":"journal_article","status":"public"},{"scopus_import":1,"intvolume":"      9667","title":"Computation of cubical Steenrod squares","date_updated":"2021-01-12T06:49:18Z","language":[{"iso":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"02","oa_version":"None","month":"06","conference":{"name":"CTIC: Computational Topology in Image Context","start_date":"2016-06-15","location":"Marseille, France","end_date":"2016-06-17"},"author":[{"first_name":"Marek","full_name":"Krcál, Marek","id":"33E21118-F248-11E8-B48F-1D18A9856A87","last_name":"Krcál"},{"full_name":"Pilarczyk, Pawel","first_name":"Pawel","last_name":"Pilarczyk","id":"3768D56A-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","status":"public","alternative_title":["LNCS"],"ec_funded":1,"date_created":"2018-12-11T11:50:52Z","citation":{"ieee":"M. Krcál and P. Pilarczyk, “Computation of cubical Steenrod squares,” presented at the CTIC: Computational Topology in Image Context, Marseille, France, 2016, vol. 9667, pp. 140–151.","ama":"Krcál M, Pilarczyk P. Computation of cubical Steenrod squares. In: Vol 9667. Springer; 2016:140-151. doi:<a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">10.1007/978-3-319-39441-1_13</a>","short":"M. Krcál, P. Pilarczyk, in:, Springer, 2016, pp. 140–151.","mla":"Krcál, Marek, and Pawel Pilarczyk. <i>Computation of Cubical Steenrod Squares</i>. Vol. 9667, Springer, 2016, pp. 140–51, doi:<a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">10.1007/978-3-319-39441-1_13</a>.","chicago":"Krcál, Marek, and Pawel Pilarczyk. “Computation of Cubical Steenrod Squares,” 9667:140–51. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">https://doi.org/10.1007/978-3-319-39441-1_13</a>.","ista":"Krcál M, Pilarczyk P. 2016. Computation of cubical Steenrod squares. CTIC: Computational Topology in Image Context, LNCS, vol. 9667, 140–151.","apa":"Krcál, M., &#38; Pilarczyk, P. (2016). Computation of cubical Steenrod squares (Vol. 9667, pp. 140–151). Presented at the CTIC: Computational Topology in Image Context, Marseille, France: Springer. <a href=\"https://doi.org/10.1007/978-3-319-39441-1_13\">https://doi.org/10.1007/978-3-319-39441-1_13</a>"},"publist_id":"6096","year":"2016","acknowledgement":"The research conducted by both authors has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreements no. 291734 (for M. K.) and no. 622033 (for P. P.).","doi":"10.1007/978-3-319-39441-1_13","_id":"1237","abstract":[{"text":"Bitmap images of arbitrary dimension may be formally perceived as unions of m-dimensional boxes aligned with respect to a rectangular grid in ℝm. Cohomology and homology groups are well known topological invariants of such sets. Cohomological operations, such as the cup product, provide higher-order algebraic topological invariants, especially important for digital images of dimension higher than 3. If such an operation is determined at the level of simplicial chains [see e.g. González-Díaz, Real, Homology, Homotopy Appl, 2003, 83-93], then it is effectively computable. However, decomposing a cubical complex into a simplicial one deleteriously affects the efficiency of such an approach. In order to avoid this overhead, a direct cubical approach was applied in [Pilarczyk, Real, Adv. Comput. Math., 2015, 253-275] for the cup product in cohomology, and implemented in the ChainCon software package [http://www.pawelpilarczyk.com/chaincon/]. We establish a formula for the Steenrod square operations [see Steenrod, Annals of Mathematics. Second Series, 1947, 290-320] directly at the level of cubical chains, and we prove the correctness of this formula. An implementation of this formula is programmed in C++ within the ChainCon software framework. We provide a few examples and discuss the effectiveness of this approach. One specific application follows from the fact that Steenrod squares yield tests for the topological extension problem: Can a given map A → Sd to a sphere Sd be extended to a given super-complex X of A? In particular, the ROB-SAT problem, which is to decide for a given function f: X → ℝm and a value r &gt; 0 whether every g: X → ℝm with ∥g - f ∥∞ ≤ r has a root, reduces to the extension problem.","lang":"eng"}],"publication_status":"published","volume":9667,"quality_controlled":"1","page":"140 - 151","department":[{"_id":"UlWa"},{"_id":"HeEd"}],"date_published":"2016-06-02T00:00:00Z","publisher":"Springer","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"},{"grant_number":"622033","_id":"255F06BE-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Persistent Homology - Images, Data and Maps"}]},{"publisher":"Springer","date_published":"2016-10-01T00:00:00Z","status":"public","type":"journal_article","page":"545 - 582","department":[{"_id":"UlWa"}],"volume":216,"quality_controlled":"1","author":[{"full_name":"Gundert, Anna","first_name":"Anna","last_name":"Gundert"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","full_name":"Wagner, Uli","first_name":"Uli"}],"publication_status":"published","month":"10","oa_version":"Preprint","day":"01","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1411.4906"}],"abstract":[{"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.","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1282","language":[{"iso":"eng"}],"publication":"Israel Journal of Mathematics","doi":"10.1007/s11856-016-1419-1","oa":1,"date_updated":"2021-01-12T06:49:36Z","issue":"2","year":"2016","date_created":"2018-12-11T11:51:07Z","citation":{"apa":"Gundert, A., &#38; Wagner, U. (2016). On eigenvalues of random complexes. <i>Israel Journal of Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s11856-016-1419-1\">https://doi.org/10.1007/s11856-016-1419-1</a>","short":"A. Gundert, U. Wagner, Israel Journal of Mathematics 216 (2016) 545–582.","ama":"Gundert A, Wagner U. On eigenvalues of random complexes. <i>Israel Journal of Mathematics</i>. 2016;216(2):545-582. doi:<a href=\"https://doi.org/10.1007/s11856-016-1419-1\">10.1007/s11856-016-1419-1</a>","ieee":"A. Gundert and U. Wagner, “On eigenvalues of random complexes,” <i>Israel Journal of Mathematics</i>, vol. 216, no. 2. Springer, pp. 545–582, 2016.","chicago":"Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” <i>Israel Journal of Mathematics</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s11856-016-1419-1\">https://doi.org/10.1007/s11856-016-1419-1</a>.","ista":"Gundert A, Wagner U. 2016. On eigenvalues of random complexes. Israel Journal of Mathematics. 216(2), 545–582.","mla":"Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” <i>Israel Journal of Mathematics</i>, vol. 216, no. 2, Springer, 2016, pp. 545–82, doi:<a href=\"https://doi.org/10.1007/s11856-016-1419-1\">10.1007/s11856-016-1419-1</a>."},"title":"On eigenvalues of random complexes","publist_id":"6034","intvolume":"       216","scopus_import":1},{"month":"01","publication_identifier":{"eissn":["1609-4514"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.3918"}],"day":"01","oa_version":"Preprint","arxiv":1,"author":[{"first_name":"Serhii","full_name":"Avvakumov, Serhii","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov"}],"status":"public","type":"journal_article","scopus_import":"1","intvolume":"        16","article_processing_charge":"No","issue":"1","oa":1,"date_updated":"2022-02-25T10:15:57Z","title":"The classification of certain linked 3-manifolds in 6-space","publication":"Moscow Mathematical Journal","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"We classify smooth Brunnian (i.e., unknotted on both components) embeddings (S2 × S1) ⊔ S3 → ℝ6. Any Brunnian embedding (S2 × S1) ⊔ S3 → ℝ6 is isotopic to an explicitly constructed embedding fk,m,n for some integers k, m, n such that m ≡ n (mod 2). Two embeddings fk,m,n and fk′ ,m′,n′ are isotopic if and only if k = k′, m ≡ m′ (mod 2k) and n ≡ n′ (mod 2k). We use Haefliger’s classification of embeddings S3 ⊔ S3 → ℝ6 in our proof. The relation between the embeddings (S2 × S1) ⊔ S3 → ℝ6 and S3 ⊔ S3 → ℝ6 is not trivial, however. For example, we show that there exist embeddings f: (S2 ×S1) ⊔ S3 → ℝ6 and g, g′ : S3 ⊔ S3 → ℝ6 such that the componentwise embedded connected sum f # g is isotopic to f # g′ but g is not isotopic to g′."}],"external_id":{"arxiv":["1408.3918"]},"publication_status":"published","date_published":"2016-01-01T00:00:00Z","publisher":"Independent University of Moscow","quality_controlled":"1","volume":16,"department":[{"_id":"UlWa"}],"page":"1 - 25","year":"2016","acknowledgement":"I thank A. Skopenkov for telling me about the problem and for his useful remarks.  I also thank A. Sossinsky,\r\nA. Zhubr, M. Skopenkov, P. Akhmetiev, and an anonymous referee for their feedback.  Author was partially\r\nsupported by Dobrushin fellowship, 2013, and by RFBR grant 15-01-06302.","publist_id":"5652","citation":{"short":"S. Avvakumov, Moscow Mathematical Journal 16 (2016) 1–25.","ama":"Avvakumov S. The classification of certain linked 3-manifolds in 6-space. <i>Moscow Mathematical Journal</i>. 2016;16(1):1-25. doi:<a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">10.17323/1609-4514-2016-16-1-1-25</a>","ieee":"S. Avvakumov, “The classification of certain linked 3-manifolds in 6-space,” <i>Moscow Mathematical Journal</i>, vol. 16, no. 1. Independent University of Moscow, pp. 1–25, 2016.","mla":"Avvakumov, Sergey. “The Classification of Certain Linked 3-Manifolds in 6-Space.” <i>Moscow Mathematical Journal</i>, vol. 16, no. 1, Independent University of Moscow, 2016, pp. 1–25, doi:<a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">10.17323/1609-4514-2016-16-1-1-25</a>.","chicago":"Avvakumov, Sergey. “The Classification of Certain Linked 3-Manifolds in 6-Space.” <i>Moscow Mathematical Journal</i>. Independent University of Moscow, 2016. <a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">https://doi.org/10.17323/1609-4514-2016-16-1-1-25</a>.","ista":"Avvakumov S. 2016. The classification of certain linked 3-manifolds in 6-space. Moscow Mathematical Journal. 16(1), 1–25.","apa":"Avvakumov, S. (2016). The classification of certain linked 3-manifolds in 6-space. <i>Moscow Mathematical Journal</i>. Independent University of Moscow. <a href=\"https://doi.org/10.17323/1609-4514-2016-16-1-1-25\">https://doi.org/10.17323/1609-4514-2016-16-1-1-25</a>"},"date_created":"2018-12-11T11:52:30Z","doi":"10.17323/1609-4514-2016-16-1-1-25","_id":"1522","article_type":"original"},{"year":"2016","acknowledgement":"This research was supported by the Swiss National Science Foundation (SNF Projects 200021-125309 and 200020-138230","publist_id":"5650","citation":{"chicago":"Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” <i>Proceedings of the American Mathematical Society</i>. American Mathematical Society, 2016. <a href=\"https://doi.org/10.1090/proc/12824\">https://doi.org/10.1090/proc/12824</a>.","mla":"Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” <i>Proceedings of the American Mathematical Society</i>, vol. 144, no. 4, American Mathematical Society, 2016, pp. 1815–28, doi:<a href=\"https://doi.org/10.1090/proc/12824\">10.1090/proc/12824</a>.","ista":"Gundert A, Wagner U. 2016. On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. 144(4), 1815–1828.","short":"A. Gundert, U. Wagner, Proceedings of the American Mathematical Society 144 (2016) 1815–1828.","ieee":"A. Gundert and U. Wagner, “On topological minors in random simplicial complexes,” <i>Proceedings of the American Mathematical Society</i>, vol. 144, no. 4. American Mathematical Society, pp. 1815–1828, 2016.","ama":"Gundert A, Wagner U. On topological minors in random simplicial complexes. <i>Proceedings of the American Mathematical Society</i>. 2016;144(4):1815-1828. doi:<a href=\"https://doi.org/10.1090/proc/12824\">10.1090/proc/12824</a>","apa":"Gundert, A., &#38; Wagner, U. (2016). On topological minors in random simplicial complexes. <i>Proceedings of the American Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/proc/12824\">https://doi.org/10.1090/proc/12824</a>"},"date_created":"2018-12-11T11:52:30Z","_id":"1523","doi":"10.1090/proc/12824","publication_status":"published","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 &gt; 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."}],"date_published":"2016-04-01T00:00:00Z","publisher":"American Mathematical Society","quality_controlled":"1","volume":144,"page":"1815 - 1828","department":[{"_id":"UlWa"}],"issue":"4","date_updated":"2021-01-12T06:51:22Z","oa":1,"title":"On topological minors in random simplicial complexes","scopus_import":1,"intvolume":"       144","language":[{"iso":"eng"}],"publication":"Proceedings of the American Mathematical Society","author":[{"first_name":"Anna","full_name":"Gundert, Anna","last_name":"Gundert"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"month":"04","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1404.2106"}],"day":"01","status":"public","type":"journal_article"},{"author":[{"orcid":"0000-0001-8485-1774","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","full_name":"Fulek, Radoslav","first_name":"Radoslav"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","day":"09","main_file_link":[{"url":"https://arxiv.org/abs/1610.07144","open_access":"1"}],"oa_version":"Preprint","month":"08","conference":{"location":"Helsinki, Finland","end_date":"2018-08-19","name":"IWOCA: International Workshop on Combinatorial Algorithms","start_date":"2016-08-17"},"type":"conference","status":"public","alternative_title":["LNCS"],"title":"Bounded embeddings of graphs in the plane","date_updated":"2021-01-12T06:50:03Z","oa":1,"intvolume":"      9843","scopus_import":1,"language":[{"iso":"eng"}],"publication_status":"published","abstract":[{"text":"A drawing in the plane (ℝ2) of a graph G = (V,E) equipped with a function γ : V → ℕ is x-bounded if (i) x(u) &lt; x(v) whenever γ(u) &lt; γ(v) and (ii) γ(u) ≤ γ(w) ≤ γ(v), where uv ∈ E and γ(u) ≤ γ(v), whenever x(w) ∈ x(uv), where x(.) denotes the projection to the xaxis.We prove a characterization of isotopy classes of embeddings of connected graphs equipped with γ in the plane containing an x-bounded embedding.Then we present an efficient algorithm, which relies on our result, for testing the existence of an x-bounded embedding if the given graph is a forest.This partially answers a question raised recently by Angelini et al.and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable when the underlying abstract graph is a forest.","lang":"eng"}],"project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme"}],"volume":9843,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"31 - 42","date_published":"2016-08-09T00:00:00Z","publisher":"Springer","publist_id":"5901","citation":{"apa":"Fulek, R. (2016). Bounded embeddings of graphs in the plane (Vol. 9843, pp. 31–42). Presented at the IWOCA: International Workshop on Combinatorial Algorithms, Helsinki, Finland: Springer. <a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">https://doi.org/10.1007/978-3-319-44543-4_3</a>","ista":"Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 31–42.","chicago":"Fulek, Radoslav. “Bounded Embeddings of Graphs in the Plane,” 9843:31–42. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">https://doi.org/10.1007/978-3-319-44543-4_3</a>.","mla":"Fulek, Radoslav. <i>Bounded Embeddings of Graphs in the Plane</i>. Vol. 9843, Springer, 2016, pp. 31–42, doi:<a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">10.1007/978-3-319-44543-4_3</a>.","ieee":"R. Fulek, “Bounded embeddings of graphs in the plane,” presented at the IWOCA: International Workshop on Combinatorial Algorithms, Helsinki, Finland, 2016, vol. 9843, pp. 31–42.","ama":"Fulek R. Bounded embeddings of graphs in the plane. In: Vol 9843. Springer; 2016:31-42. doi:<a href=\"https://doi.org/10.1007/978-3-319-44543-4_3\">10.1007/978-3-319-44543-4_3</a>","short":"R. Fulek, in:, Springer, 2016, pp. 31–42."},"date_created":"2018-12-11T11:51:31Z","year":"2016","ec_funded":1,"_id":"1348","doi":"10.1007/978-3-319-44543-4_3"},{"publication_status":"published","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"}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"page":"35.1 - 35.10","department":[{"_id":"UlWa"}],"quality_controlled":"1","volume":51,"publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","date_published":"2016-06-01T00:00:00Z","publist_id":"5833","citation":{"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>","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>.","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.","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.","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>","short":"D. Dotterrer, T. Kaufman, U. Wagner, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 35.1-35.10."},"date_created":"2018-12-11T11:51:41Z","year":"2016","related_material":{"record":[{"status":"public","id":"742","relation":"later_version"}]},"file_date_updated":"2020-07-14T12:44:47Z","_id":"1378","doi":"10.4230/LIPIcs.SoCG.2016.35","author":[{"first_name":"Dominic","full_name":"Dotterrer, Dominic","last_name":"Dotterrer"},{"last_name":"Kaufman","first_name":"Tali","full_name":"Kaufman, Tali"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli"}],"day":"01","oa_version":"Published Version","file":[{"creator":"system","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":536923,"file_id":"4699","file_name":"IST-2016-623-v1+1_LIPIcs-SoCG-2016-35.pdf","checksum":"cee65b0e722d50f9d1cc70c90ec1d59b","date_updated":"2020-07-14T12:44:47Z","date_created":"2018-12-12T10:08:38Z"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2016-06-17","location":"Medford, MA, USA","start_date":"2016-06-14","name":"SoCG: Symposium on Computational Geometry"},"month":"06","alternative_title":["LIPIcs"],"status":"public","type":"conference","title":"On expansion and topological overlap","oa":1,"date_updated":"2023-09-27T12:29:56Z","pubrep_id":"623","has_accepted_license":"1","intvolume":"        51","scopus_import":1,"language":[{"iso":"eng"}]},{"_id":"1379","file_date_updated":"2020-07-14T12:44:47Z","doi":"10.4230/LIPIcs.SoCG.2016.24","citation":{"apa":"Burton, B., de Mesmay, A. N., &#38; 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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">https://doi.org/10.4230/LIPIcs.SoCG.2016.24</a>","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.","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:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">10.4230/LIPIcs.SoCG.2016.24</a>","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.","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.","mla":"Burton, Benjamin, et al. <i>Finding Non-Orientable Surfaces in 3-Manifolds</i>. Vol. 51, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016, p. 24.1-24.15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">10.4230/LIPIcs.SoCG.2016.24</a>.","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. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2016.24\">https://doi.org/10.4230/LIPIcs.SoCG.2016.24</a>."},"date_created":"2018-12-11T11:51:41Z","publist_id":"5832","year":"2016","related_material":{"record":[{"status":"public","relation":"later_version","id":"534"}]},"quality_controlled":"1","volume":51,"page":"24.1 - 24.15","department":[{"_id":"UlWa"}],"date_published":"2016-06-01T00:00:00Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing","publication_status":"published","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."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"language":[{"iso":"eng"}],"title":"Finding non-orientable surfaces in 3-manifolds","pubrep_id":"622","date_updated":"2023-02-23T12:23:20Z","oa":1,"has_accepted_license":"1","intvolume":"        51","scopus_import":1,"type":"conference","status":"public","alternative_title":["LIPIcs"],"author":[{"full_name":"Burton, Benjamin","first_name":"Benjamin","last_name":"Burton"},{"last_name":"De Mesmay","id":"3DB2F25C-F248-11E8-B48F-1D18A9856A87","first_name":"Arnaud N","full_name":"De Mesmay, Arnaud N"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"file":[{"file_size":574770,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"system","date_created":"2018-12-12T10:12:12Z","date_updated":"2020-07-14T12:44:47Z","file_name":"IST-2016-622-v1+1_LIPIcs-SoCG-2016-24.pdf","file_id":"4930","checksum":"f04248a61c24297cfabd30c5f8e0deb9"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"01","month":"06","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2016-06-14","location":"Medford, MA, USA","end_date":"2016-06-17"}},{"type":"conference","status":"public","alternative_title":["LIPIcs"],"month":"06","conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2016-06-14","location":"Medford, MA, USA","end_date":"2016-06-17"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"checksum":"92c0c3735fe908f8ded6e484005cb3b1","file_name":"IST-2016-621-v1+1_LIPIcs-SoCG-2016-51.pdf","file_id":"4791","date_updated":"2020-07-14T12:44:47Z","date_created":"2018-12-12T10:10:06Z","creator":"system","access_level":"open_access","relation":"main_file","file_size":622969,"content_type":"application/pdf"}],"day":"01","oa_version":"Published Version","author":[{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac","full_name":"Mabillard, Isaac"},{"full_name":"Wagner, Uli","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","intvolume":"        51","scopus_import":1,"date_updated":"2021-01-12T06:50:17Z","oa":1,"pubrep_id":"621","title":"Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range","date_published":"2016-06-01T00:00:00Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH","volume":51,"quality_controlled":"1","department":[{"_id":"UlWa"}],"page":"51.1 - 51.12","project":[{"grant_number":"PP00P2_138948","_id":"25FA3206-B435-11E9-9278-68D0E5697425","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"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."}],"publication_status":"published","doi":"10.4230/LIPIcs.SoCG.2016.51","_id":"1381","file_date_updated":"2020-07-14T12:44:47Z","year":"2016","citation":{"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>.","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.","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>","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>"},"date_created":"2018-12-11T11:51:41Z","publist_id":"5830"}]