[{"doi":"10.1016/j.jfa.2022.109441","language":[{"iso":"eng"}],"external_id":{"arxiv":["2006.09934"],"isi":["000781371300008"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","isi":1,"month":"06","publication_identifier":{"eissn":["1096-0783"],"issn":["0022-1236"]},"author":[{"full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov"},{"first_name":"Márton","last_name":"Naszódi","full_name":"Naszódi, Márton"}],"date_updated":"2023-08-02T14:51:11Z","date_created":"2022-03-20T23:01:38Z","volume":282,"acknowledgement":"G.I. was supported by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926. M.N. was supported by the National Research, Development and Innovation Fund (NRDI) grants K119670 and KKP-133864 as well as the Bolyai Scholarship of the Hungarian Academy of Sciences and the New National Excellence Programme and the TKP2020-NKA-06 program provided by the NRDI. ","year":"2022","publication_status":"published","publisher":"Elsevier","department":[{"_id":"UlWa"}],"file_date_updated":"2022-08-02T10:40:48Z","article_number":"109441","date_published":"2022-06-01T00:00:00Z","publication":"Journal of Functional Analysis","citation":{"mla":"Ivanov, Grigory, and Márton Naszódi. “Functional John Ellipsoids.” Journal of Functional Analysis, vol. 282, no. 11, 109441, Elsevier, 2022, doi:10.1016/j.jfa.2022.109441.","short":"G. Ivanov, M. Naszódi, Journal of Functional Analysis 282 (2022).","chicago":"Ivanov, Grigory, and Márton Naszódi. “Functional John Ellipsoids.” Journal of Functional Analysis. Elsevier, 2022. https://doi.org/10.1016/j.jfa.2022.109441.","ama":"Ivanov G, Naszódi M. Functional John ellipsoids. Journal of Functional Analysis. 2022;282(11). doi:10.1016/j.jfa.2022.109441","ista":"Ivanov G, Naszódi M. 2022. Functional John ellipsoids. Journal of Functional Analysis. 282(11), 109441.","ieee":"G. Ivanov and M. Naszódi, “Functional John ellipsoids,” Journal of Functional Analysis, vol. 282, no. 11. Elsevier, 2022.","apa":"Ivanov, G., & Naszódi, M. (2022). Functional John ellipsoids. Journal of Functional Analysis. Elsevier. https://doi.org/10.1016/j.jfa.2022.109441"},"article_type":"original","day":"01","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","scopus_import":"1","oa_version":"Published Version","file":[{"date_updated":"2022-08-02T10:40:48Z","date_created":"2022-08-02T10:40:48Z","success":1,"checksum":"1cf185e264e04c87cb1ce67a00db88ab","file_id":"11721","relation":"main_file","creator":"dernst","content_type":"application/pdf","file_size":734482,"file_name":"2022_JourFunctionalAnalysis_Ivanov.pdf","access_level":"open_access"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10887","status":"public","title":"Functional John ellipsoids","ddc":["510"],"intvolume":" 282","abstract":[{"lang":"eng","text":"We introduce a new way of representing logarithmically concave functions on Rd. It allows us to extend the notion of the largest volume ellipsoid contained in a convex body to the setting of logarithmically concave functions as follows. For every s>0, we define a class of non-negative functions on Rd derived from ellipsoids in Rd+1. For any log-concave function f on Rd , and any fixed s>0, we consider functions belonging to this class, and find the one with the largest integral under the condition that it is pointwise less than or equal to f, and we call it the John s-function of f. After establishing existence and uniqueness, we give a characterization of this function similar to the one given by John in his fundamental theorem. We find that John s-functions converge to characteristic functions of ellipsoids as s tends to zero and to Gaussian densities as s tends to infinity.\r\nAs an application, we prove a quantitative Helly type result: the integral of the pointwise minimum of any family of log-concave functions is at least a constant cd multiple of the integral of the pointwise minimum of a properly chosen subfamily of size 3d+2, where cd depends only on d."}],"issue":"11","type":"journal_article"},{"year":"2022","acknowledgement":"This is a full and revised version of [38] (on partial triangulations) in Proceedings of the 36th Annual International Symposium on Computational Geometry (SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt, Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on full triangulations. Research was supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681, and by IST Austria and Berlin Free University during a sabbatical stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger and Valentin Stoppiello for carefully reading earlier versions and for many helpful comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology Zürich","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"author":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"7807"},{"id":"7990","relation":"earlier_version","status":"public"}]},"date_created":"2023-01-12T12:02:28Z","date_updated":"2023-08-04T08:51:08Z","volume":68,"file_date_updated":"2023-01-23T11:10:03Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"isi":["000883222200003"]},"isi":1,"quality_controlled":"1","doi":"10.1007/s00454-022-00436-2","language":[{"iso":"eng"}],"month":"11","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"_id":"12129","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","ddc":["510"],"title":"Connectivity of triangulation flip graphs in the plane","intvolume":" 68","oa_version":"Published Version","file":[{"date_created":"2023-01-23T11:10:03Z","date_updated":"2023-01-23T11:10:03Z","success":1,"checksum":"307e879d09e52eddf5b225d0aaa9213a","file_id":"12345","relation":"main_file","creator":"dernst","file_size":1747581,"content_type":"application/pdf","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","access_level":"open_access"}],"type":"journal_article","abstract":[{"lang":"eng","text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations."}],"issue":"4","publication":"Discrete & Computational Geometry","citation":{"ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2","apa":"Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022.","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. 68(4), 1227–1284.","short":"U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” Discrete & Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00436-2."},"article_type":"original","page":"1227-1284","date_published":"2022-11-14T00:00:00Z","scopus_import":"1","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"day":"14","has_accepted_license":"1","article_processing_charge":"No"},{"date_updated":"2023-08-14T12:43:52Z","date_created":"2022-07-17T22:01:56Z","volume":68,"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"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"186"}]},"publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"acknowledgement":"We thank Zdeněk Dvořák, Xavier Goaoc, and Pavel Paták for helpful discussions. We also thank Bojan Mohar, Paul Seymour, Gelasio Salazar, Jim Geelen, and John Maharry for information about their unpublished results related to Conjecture 3.1. Finally we thank the reviewers for corrections and suggestions for improving the presentation.\r\nSupported by Austrian Science Fund (FWF): M2281-N35. Supported by project 19-04113Y of the Czech Science Foundation (GAČR), by the Czech-French collaboration project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM), and by Charles University project UNCE/SCI/004.","year":"2022","language":[{"iso":"eng"}],"doi":"10.1007/s00454-022-00412-w","quality_controlled":"1","isi":1,"project":[{"name":"Eliminating intersections in drawings of graphs","call_identifier":"FWF","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"oa":1,"external_id":{"arxiv":["1803.05085"],"isi":["000825014500001"]},"main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"month":"09","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"oa_version":"Preprint","status":"public","title":"The Z2-Genus of Kuratowski minors","intvolume":" 68","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11593","abstract":[{"lang":"eng","text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z2 -genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t×t grid or one of the following so-called t -Kuratowski graphs: K3,t, or t copies of K5 or K3,3 sharing at most two common vertices. We show that the Z2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani–Tutte theorem on orientable surfaces. We also obtain an analogous result for Euler genus and Euler Z2-genus of graphs."}],"type":"journal_article","date_published":"2022-09-01T00:00:00Z","article_type":"original","page":"425-447","publication":"Discrete and Computational Geometry","citation":{"ista":"Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 68, 425–447.","apa":"Fulek, R., & Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00412-w","ieee":"R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 425–447, 2022.","ama":"Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 2022;68:425-447. doi:10.1007/s00454-022-00412-w","chicago":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00412-w.","mla":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 425–47, doi:10.1007/s00454-022-00412-w.","short":"R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447."},"day":"01","article_processing_charge":"No","scopus_import":"1"},{"abstract":[{"lang":"eng","text":"Bundling crossings is a strategy which can enhance the readability of graph drawings. In this paper we consider bundlings for families of pseudosegments, i.e., simple curves such that any two have share at most one point at which they cross. Our main result is that there is a polynomial-time algorithm to compute an 8-approximation of the bundled crossing number of such instances (up to adding a term depending on the facial structure). This 8-approximation also holds for bundlings of good drawings of graphs. In the special case of circular drawings the approximation factor is 8 (no extra term), this improves upon the 10-approximation of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection graph of the pseudosegments is bipartite."}],"type":"conference","oa_version":"Preprint","intvolume":" 13174","title":"Approximating the bundled crossing number","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11185","article_processing_charge":"No","day":"16","series_title":"LNCS","scopus_import":"1","date_published":"2022-03-16T00:00:00Z","page":"383-395","citation":{"mla":"Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing Number.” WALCOM 2022: Algorithms and Computation, vol. 13174, Springer Nature, 2022, pp. 383–95, doi:10.1007/978-3-030-96731-4_31.","short":"A.M. Arroyo Guevara, S. Felsner, in:, WALCOM 2022: Algorithms and Computation, Springer Nature, 2022, pp. 383–395.","chicago":"Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled Crossing Number.” In WALCOM 2022: Algorithms and Computation, 13174:383–95. LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-030-96731-4_31.","ama":"Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In: WALCOM 2022: Algorithms and Computation. Vol 13174. LNCS. Springer Nature; 2022:383-395. doi:10.1007/978-3-030-96731-4_31","ista":"Arroyo Guevara AM, Felsner S. 2022. Approximating the bundled crossing number. WALCOM 2022: Algorithms and Computation. WALCOM: Algorithms and ComputationLNCS vol. 13174, 383–395.","apa":"Arroyo Guevara, A. M., & Felsner, S. (2022). Approximating the bundled crossing number. In WALCOM 2022: Algorithms and Computation (Vol. 13174, pp. 383–395). Jember, Indonesia: Springer Nature. https://doi.org/10.1007/978-3-030-96731-4_31","ieee":"A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,” in WALCOM 2022: Algorithms and Computation, Jember, Indonesia, 2022, vol. 13174, pp. 383–395."},"publication":"WALCOM 2022: Algorithms and Computation","ec_funded":1,"volume":13174,"date_created":"2022-04-17T22:01:47Z","date_updated":"2023-09-25T10:56:10Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"13969"}]},"author":[{"full_name":"Arroyo Guevara, Alan M","first_name":"Alan M","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670"},{"last_name":"Felsner","first_name":"Stefan","full_name":"Felsner, Stefan"}],"department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"published","year":"2022","acknowledgement":"This work was initiated during the Workshop on Geometric Graphs in November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during the workshop. The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska Curie grant agreement No 754411. The second author has been supported by the German Research Foundation DFG Project FE 340/12-1.","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783030967307"],"issn":["0302-9743"]},"month":"03","language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-96731-4_31","conference":{"name":"WALCOM: Algorithms and Computation","location":"Jember, Indonesia","start_date":"2022-03-24","end_date":"2022-03-26"},"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"quality_controlled":"1","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2109.14892","open_access":"1"}],"external_id":{"arxiv":["2109.14892"]},"oa":1},{"type":"journal_article","abstract":[{"text":"Expander graphs (sparse but highly connected graphs) have, since their inception, been the source of deep links between Mathematics and Computer Science as well as applications to other areas. In recent years, a fascinating theory of high-dimensional expanders has begun to emerge, which is still in a formative stage but has nonetheless already lead to a number of striking results. Unlike for graphs, in higher dimensions there is a rich array of non-equivalent notions of expansion (coboundary expansion, cosystolic expansion, topological expansion, spectral expansion, etc.), with differents strengths and applications. In this talk, we will survey this landscape of high-dimensional expansion, with a focus on two main results. First, we will present Gromov’s Topological Overlap Theorem, which asserts that coboundary expansion (a quantitative version of vanishing mod 2 cohomology) implies topological expansion (roughly, the property that for every map from a simplicial complex to a manifold of the same dimension, the images of a positive fraction of the simplices have a point in common). Second, we will outline a construction of bounded degree 2-dimensional topological expanders, due to Kaufman, Kazhdan, and Lubotzky.","lang":"eng"}],"status":"public","title":"High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)","publication_status":"published","publisher":"Societe Mathematique de France","intvolume":" 438","department":[{"_id":"UlWa"}],"_id":"14381","year":"2022","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2023-10-01T22:01:14Z","date_updated":"2023-10-03T08:04:03Z","volume":438,"oa_version":"None","author":[{"last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"scopus_import":"1","month":"01","day":"01","article_processing_charge":"No","publication_identifier":{"eissn":["2102-622X"],"issn":["0037-9484"]},"quality_controlled":"1","article_type":"original","page":"281-294","publication":"Bulletin de la Societe Mathematique de France","citation":{"ama":"Wagner U. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de la Societe Mathematique de France. 2022;438:281-294. doi:10.24033/ast.1188","ieee":"U. Wagner, “High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others),” Bulletin de la Societe Mathematique de France, vol. 438. Societe Mathematique de France, pp. 281–294, 2022.","apa":"Wagner, U. (2022). High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de La Societe Mathematique de France. Societe Mathematique de France. https://doi.org/10.24033/ast.1188","ista":"Wagner U. 2022. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de la Societe Mathematique de France. 438, 281–294.","short":"U. Wagner, Bulletin de La Societe Mathematique de France 438 (2022) 281–294.","mla":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” Bulletin de La Societe Mathematique de France, vol. 438, Societe Mathematique de France, 2022, pp. 281–94, doi:10.24033/ast.1188.","chicago":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” Bulletin de La Societe Mathematique de France. Societe Mathematique de France, 2022. https://doi.org/10.24033/ast.1188."},"language":[{"iso":"eng"}],"date_published":"2022-01-01T00:00:00Z","doi":"10.24033/ast.1188"},{"date_created":"2022-06-05T22:01:50Z","date_updated":"2023-10-18T06:58:03Z","volume":36,"author":[{"full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov"},{"full_name":"Naszodi, Marton","first_name":"Marton","last_name":"Naszodi"}],"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Society for Industrial and Applied Mathematics","acknowledgement":"G.I. acknowledges the financial support from the Ministry of Educational and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926. M.N. was supported by the National Research, Development and Innovation Fund (NRDI) grants K119670 and\r\nKKP-133864 as well as the Bolyai Scholarship of the Hungarian Academy of Sciences and the New National Excellence Programme and the TKP2020-NKA-06 program provided by the NRDI.","year":"2022","month":"04","publication_identifier":{"issn":["0895-4801"]},"language":[{"iso":"eng"}],"doi":"10.1137/21M1403308","isi":1,"quality_controlled":"1","oa":1,"external_id":{"isi":["000793158200002"],"arxiv":["2103.04122"]},"main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2103.04122","open_access":"1"}],"abstract":[{"text":"We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection of a family of convex sets to the intersection of a subfamily of a fixed size. As an application, we establish the following quantitative Helly-type result for the diameter. If $K$ is the intersection of finitely many convex bodies in $\\mathbb{R}^d$, then one can select $2d$ of these bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously known estimate, due to Brazitikos [Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25], is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$ conjectured by Bárány, Katchalski, and Pach [Proc. Amer. Math. Soc., 86 (1982), pp. 109--114] cannot be improved. The bounds above follow from our key result that concerns sparse approximation of a convex polytope by the convex hull of a well-chosen subset of its vertices: Assume that $Q \\subset {\\mathbb R}^d$ is a polytope whose centroid is the origin. Then there exist at most 2d vertices of $Q$ whose convex hull $Q^{\\prime \\prime}$ satisfies $Q \\subset - 8d^3 Q^{\\prime \\prime}.$","lang":"eng"}],"issue":"2","type":"journal_article","oa_version":"Preprint","title":"A quantitative Helly-type theorem: Containment in a homothet","status":"public","intvolume":" 36","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11435","day":"11","article_processing_charge":"No","scopus_import":"1","date_published":"2022-04-11T00:00:00Z","article_type":"original","page":"951-957","publication":"SIAM Journal on Discrete Mathematics","citation":{"ama":"Ivanov G, Naszodi M. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 2022;36(2):951-957. doi:10.1137/21M1403308","ista":"Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.","ieee":"G. Ivanov and M. Naszodi, “A quantitative Helly-type theorem: Containment in a homothet,” SIAM Journal on Discrete Mathematics, vol. 36, no. 2. Society for Industrial and Applied Mathematics, pp. 951–957, 2022.","apa":"Ivanov, G., & Naszodi, M. (2022). A quantitative Helly-type theorem: Containment in a homothet. SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1403308","mla":"Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” SIAM Journal on Discrete Mathematics, vol. 36, no. 2, Society for Industrial and Applied Mathematics, 2022, pp. 951–57, doi:10.1137/21M1403308.","short":"G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 951–957.","chicago":"Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/21M1403308."}},{"volume":12635,"date_updated":"2023-02-21T16:33:44Z","date_created":"2021-03-28T22:01:41Z","related_material":{"record":[{"id":"11938","status":"public","relation":"later_version"}]},"author":[{"full_name":"Aichholzer, Oswin","first_name":"Oswin","last_name":"Aichholzer"},{"orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","last_name":"Arroyo Guevara","first_name":"Alan M","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Masárová, Zuzana","first_name":"Zuzana","last_name":"Masárová","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"full_name":"Perz, Daniel","first_name":"Daniel","last_name":"Perz"},{"full_name":"Pilz, Alexander","first_name":"Alexander","last_name":"Pilz"},{"full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","first_name":"Josef","last_name":"Tkadlec"},{"last_name":"Vogtenhuber","first_name":"Birgit","full_name":"Vogtenhuber, Birgit"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"publisher":"Springer Nature","publication_status":"published","year":"2021","acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","ec_funded":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-030-68211-8_18","conference":{"location":"Yangon, Myanmar","start_date":"2021-02-28","end_date":"2021-03-02","name":"WALCOM: Algorithms and Computation"},"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Game Theory","call_identifier":"FWF","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"external_id":{"arxiv":["2101.03928"]},"publication_identifier":{"eissn":["16113349"],"isbn":["9783030682101"],"issn":["03029743"]},"month":"02","oa_version":"Preprint","intvolume":" 12635","status":"public","title":"On compatible matchings","user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","_id":"9296","abstract":[{"text":" matching is compatible to two or more labeled point sets of size n with labels {1,…,n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(logn) copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.","lang":"eng"}],"alternative_title":["LNCS"],"type":"conference","date_published":"2021-02-16T00:00:00Z","page":"221-233","citation":{"chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In 15th International Conference on Algorithms and Computation, 12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:10.1007/978-3-030-68211-8_18.","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18","ieee":"O. Aichholzer et al., “On compatible matchings,” in 15th International Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: 15th International Conference on Algorithms and Computation. Vol 12635. Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18"},"publication":"15th International Conference on Algorithms and Computation","article_processing_charge":"No","day":"16","scopus_import":"1"},{"scopus_import":"1","day":"01","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","publication":"Bulletin of the London Mathematical Society","citation":{"short":"G. Ivanov, Bulletin of the London Mathematical Society 53 (2021) 631–641.","mla":"Ivanov, Grigory. “No-Dimension Tverberg’s Theorem and Its Corollaries in Banach Spaces of Type P.” Bulletin of the London Mathematical Society, vol. 53, no. 2, London Mathematical Society, 2021, pp. 631–41, doi:10.1112/blms.12449.","chicago":"Ivanov, Grigory. “No-Dimension Tverberg’s Theorem and Its Corollaries in Banach Spaces of Type P.” Bulletin of the London Mathematical Society. London Mathematical Society, 2021. https://doi.org/10.1112/blms.12449.","ama":"Ivanov G. No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p. Bulletin of the London Mathematical Society. 2021;53(2):631-641. doi:10.1112/blms.12449","apa":"Ivanov, G. (2021). No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p. Bulletin of the London Mathematical Society. London Mathematical Society. https://doi.org/10.1112/blms.12449","ieee":"G. Ivanov, “No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p,” Bulletin of the London Mathematical Society, vol. 53, no. 2. London Mathematical Society, pp. 631–641, 2021.","ista":"Ivanov G. 2021. No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p. Bulletin of the London Mathematical Society. 53(2), 631–641."},"article_type":"original","page":"631-641","date_published":"2021-04-01T00:00:00Z","type":"journal_article","abstract":[{"text":"We continue our study of ‘no‐dimension’ analogues of basic theorems in combinatorial and convex geometry in Banach spaces. We generalize some results of the paper (Adiprasito, Bárány and Mustafa, ‘Theorems of Carathéodory, Helly, and Tverberg without dimension’, Proceedings of the Thirtieth Annual ACM‐SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, San Diego, California, 2019) 2350–2360) and prove no‐dimension versions of the colored Tverberg theorem, the selection lemma and the weak 𝜀 ‐net theorem in Banach spaces of type 𝑝>1 . To prove these results, we use the original ideas of Adiprasito, Bárány and Mustafa for the Euclidean case, our no‐dimension version of the Radon theorem and slightly modified version of the celebrated Maurey lemma.","lang":"eng"}],"issue":"2","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"9037","status":"public","title":"No-dimension Tverberg's theorem and its corollaries in Banach spaces of type p","ddc":["510"],"intvolume":" 53","file":[{"checksum":"e6ceaa6470d835eb4c211cbdd38fdfd1","success":1,"date_updated":"2021-08-06T09:59:45Z","date_created":"2021-08-06T09:59:45Z","relation":"main_file","file_id":"9796","content_type":"application/pdf","file_size":194550,"creator":"kschuh","access_level":"open_access","file_name":"2021_BLMS_Ivanov.pdf"}],"oa_version":"Published Version","month":"04","publication_identifier":{"issn":["00246093"],"eissn":["14692120"]},"oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"external_id":{"isi":["000607265100001"],"arxiv":["1912.08561"]},"isi":1,"quality_controlled":"1","doi":"10.1112/blms.12449","language":[{"iso":"eng"}],"file_date_updated":"2021-08-06T09:59:45Z","year":"2021","acknowledgement":"I wish to thank Imre Bárány for bringing the problem to my attention. I am grateful to Marton Naszódi and Igor Tsiutsiurupa for useful remarks and help with the text.\r\nThe author acknowledges the financial support from the Ministry of Educational and Science of the Russian Federation in the framework of MegaGrant no 075‐15‐2019‐1926.","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"London Mathematical Society","author":[{"first_name":"Grigory","last_name":"Ivanov","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory"}],"date_updated":"2023-08-07T13:35:20Z","date_created":"2021-01-24T23:01:08Z","volume":53},{"acknowledgement":"Research was supported by the Russian Foundation for Basic Research, project 18-01-00036A (Theorems 1.5 and 5.3) and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926 (Theorems 1.2 and 7.3).","year":"2021","publication_status":"published","publisher":"Elsevier","department":[{"_id":"UlWa"}],"author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","last_name":"Ivanov","first_name":"Grigory","full_name":"Ivanov, Grigory"}],"date_created":"2021-02-07T23:01:12Z","date_updated":"2023-08-07T13:40:37Z","volume":344,"article_number":"112312","external_id":{"arxiv":["1808.09165"],"isi":["000633365200001"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1808.09165","open_access":"1"}],"quality_controlled":"1","isi":1,"doi":"10.1016/j.disc.2021.112312","language":[{"iso":"eng"}],"month":"05","publication_identifier":{"issn":["0012365X"]},"_id":"9098","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","title":"On the volume of projections of the cross-polytope","intvolume":" 344","oa_version":"Preprint","type":"journal_article","abstract":[{"lang":"eng","text":"We study properties of the volume of projections of the n-dimensional\r\ncross-polytope $\\crosp^n = \\{ x \\in \\R^n \\mid |x_1| + \\dots + |x_n| \\leqslant 1\\}.$ We prove that the projection of $\\crosp^n$ onto a k-dimensional coordinate subspace has the maximum possible volume for k=2 and for k=3.\r\nWe obtain the exact lower bound on the volume of such a projection onto a two-dimensional plane. Also, we show that there exist local maxima which are not global ones for the volume of a projection of $\\crosp^n$ onto a k-dimensional subspace for any n>k⩾2."}],"issue":"5","publication":"Discrete Mathematics","citation":{"apa":"Ivanov, G. (2021). On the volume of projections of the cross-polytope. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2021.112312","ieee":"G. Ivanov, “On the volume of projections of the cross-polytope,” Discrete Mathematics, vol. 344, no. 5. Elsevier, 2021.","ista":"Ivanov G. 2021. On the volume of projections of the cross-polytope. Discrete Mathematics. 344(5), 112312.","ama":"Ivanov G. On the volume of projections of the cross-polytope. Discrete Mathematics. 2021;344(5). doi:10.1016/j.disc.2021.112312","chicago":"Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” Discrete Mathematics. Elsevier, 2021. https://doi.org/10.1016/j.disc.2021.112312.","short":"G. Ivanov, Discrete Mathematics 344 (2021).","mla":"Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” Discrete Mathematics, vol. 344, no. 5, 112312, Elsevier, 2021, doi:10.1016/j.disc.2021.112312."},"article_type":"original","date_published":"2021-05-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No"},{"ec_funded":1,"author":[{"last_name":"Arroyo Guevara","first_name":"Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Mcquillan, Dan","last_name":"Mcquillan","first_name":"Dan"},{"first_name":"R. Bruce","last_name":"Richter","full_name":"Richter, R. Bruce"},{"full_name":"Salazar, Gelasio","first_name":"Gelasio","last_name":"Salazar"},{"full_name":"Sullivan, Matthew","first_name":"Matthew","last_name":"Sullivan"}],"date_created":"2021-03-28T22:01:41Z","date_updated":"2023-08-07T14:26:15Z","volume":97,"year":"2021","acknowledgement":"We thank two reviewers for their corrections and suggestions on the original version of this\r\npaper. This project has received funding from NSERC Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg, Austria.","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Wiley","month":"03","publication_identifier":{"eissn":["1097-0118"],"issn":["0364-9024"]},"doi":"10.1002/jgt.22665","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/2002.02287","open_access":"1"}],"oa":1,"external_id":{"arxiv":["2002.02287"],"isi":["000631693200001"]},"quality_controlled":"1","isi":1,"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"abstract":[{"text":"Hill's Conjecture states that the crossing number cr(𝐾𝑛) of the complete graph 𝐾𝑛 in the plane (equivalently, the sphere) is 14⌊𝑛2⌋⌊𝑛−12⌋⌊𝑛−22⌋⌊𝑛−32⌋=𝑛4/64+𝑂(𝑛3) . Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely 𝑛4/64+𝑂(𝑛3) , thus matching asymptotically the conjectured value of cr(𝐾𝑛) . Let cr𝑃(𝐺) denote the crossing number of a graph 𝐺 in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of 𝐾𝑛 is (𝑛4/8𝜋2)+𝑂(𝑛3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if lim𝑛→∞ cr𝑃(𝐾𝑛)/𝑛4=1/8𝜋2 . We construct drawings of 𝐾𝑛 in the projective plane that disprove this.","lang":"eng"}],"issue":"3","type":"journal_article","oa_version":"Preprint","_id":"9295","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Drawings of complete graphs in the projective plane","status":"public","intvolume":" 97","day":"23","article_processing_charge":"No","scopus_import":"1","date_published":"2021-03-23T00:00:00Z","publication":"Journal of Graph Theory","citation":{"chicago":"Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar, and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” Journal of Graph Theory. Wiley, 2021. https://doi.org/10.1002/jgt.22665.","short":"A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan, Journal of Graph Theory 97 (2021) 426–440.","mla":"Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective Plane.” Journal of Graph Theory, vol. 97, no. 3, Wiley, 2021, pp. 426–40, doi:10.1002/jgt.22665.","ieee":"A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan, “Drawings of complete graphs in the projective plane,” Journal of Graph Theory, vol. 97, no. 3. Wiley, pp. 426–440, 2021.","apa":"Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., & Sullivan, M. (2021). Drawings of complete graphs in the projective plane. Journal of Graph Theory. Wiley. https://doi.org/10.1002/jgt.22665","ista":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440.","ama":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 2021;97(3):426-440. doi:10.1002/jgt.22665"},"article_type":"original","page":"426-440"},{"intvolume":" 35","status":"public","title":"Extending drawings of complete graphs into arrangements of pseudocircles","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"9468","oa_version":"Preprint","type":"journal_article","issue":"2","abstract":[{"lang":"eng","text":"Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\\gamma_e$ such that the only vertices in $\\gamma_e$ are the ends of $e$; (2) if $e\\ne f$, then $\\gamma_e\\cap\\gamma_f$ has precisely two crossings; and (3) if $e\\ne f$, then $e$ intersects $\\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.\r\n"}],"page":"1050-1076","article_type":"original","citation":{"ama":"Arroyo Guevara AM, Richter RB, Sunohara M. Extending drawings of complete graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics. 2021;35(2):1050-1076. doi:10.1137/20M1313234","ista":"Arroyo Guevara AM, Richter RB, Sunohara M. 2021. Extending drawings of complete graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics. 35(2), 1050–1076.","ieee":"A. M. Arroyo Guevara, R. B. Richter, and M. Sunohara, “Extending drawings of complete graphs into arrangements of pseudocircles,” SIAM Journal on Discrete Mathematics, vol. 35, no. 2. Society for Industrial and Applied Mathematics, pp. 1050–1076, 2021.","apa":"Arroyo Guevara, A. M., Richter, R. B., & Sunohara, M. (2021). Extending drawings of complete graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20M1313234","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” SIAM Journal on Discrete Mathematics, vol. 35, no. 2, Society for Industrial and Applied Mathematics, 2021, pp. 1050–76, doi:10.1137/20M1313234.","short":"A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete Mathematics 35 (2021) 1050–1076.","chicago":"Arroyo Guevara, Alan M, R. Bruce Richter, and Matthew Sunohara. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” SIAM Journal on Discrete Mathematics. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/20M1313234."},"publication":"SIAM Journal on Discrete Mathematics","date_published":"2021-05-20T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"20","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2021","volume":35,"date_updated":"2023-08-08T13:58:12Z","date_created":"2021-06-06T22:01:30Z","author":[{"full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","first_name":"Alan M","last_name":"Arroyo Guevara"},{"last_name":"Richter","first_name":"R. Bruce","full_name":"Richter, R. Bruce"},{"full_name":"Sunohara, Matthew","first_name":"Matthew","last_name":"Sunohara"}],"ec_funded":1,"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"isi":1,"quality_controlled":"1","oa":1,"external_id":{"arxiv":["2001.06053"],"isi":["000674142200022"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2001.06053"}],"language":[{"iso":"eng"}],"doi":"10.1137/20M1313234","publication_identifier":{"issn":["08954801"]},"month":"05"},{"date_published":"2021-05-31T00:00:00Z","citation":{"chicago":"Ivanov, Grigory, and Igor Tsiutsiurupa. “Functional Löwner Ellipsoids.” Journal of Geometric Analysis. Springer, 2021. https://doi.org/10.1007/s12220-021-00691-4.","short":"G. Ivanov, I. Tsiutsiurupa, Journal of Geometric Analysis 31 (2021) 11493–11528.","mla":"Ivanov, Grigory, and Igor Tsiutsiurupa. “Functional Löwner Ellipsoids.” Journal of Geometric Analysis, vol. 31, Springer, 2021, pp. 11493–528, doi:10.1007/s12220-021-00691-4.","ieee":"G. Ivanov and I. Tsiutsiurupa, “Functional Löwner ellipsoids,” Journal of Geometric Analysis, vol. 31. Springer, pp. 11493–11528, 2021.","apa":"Ivanov, G., & Tsiutsiurupa, I. (2021). Functional Löwner ellipsoids. Journal of Geometric Analysis. Springer. https://doi.org/10.1007/s12220-021-00691-4","ista":"Ivanov G, Tsiutsiurupa I. 2021. Functional Löwner ellipsoids. Journal of Geometric Analysis. 31, 11493–11528.","ama":"Ivanov G, Tsiutsiurupa I. Functional Löwner ellipsoids. Journal of Geometric Analysis. 2021;31:11493-11528. doi:10.1007/s12220-021-00691-4"},"publication":"Journal of Geometric Analysis","page":"11493-11528","article_type":"original","article_processing_charge":"No","day":"31","scopus_import":"1","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"9548","intvolume":" 31","title":"Functional Löwner ellipsoids","status":"public","abstract":[{"lang":"eng","text":"We extend the notion of the minimal volume ellipsoid containing a convex body in Rd to the setting of logarithmically concave functions. We consider a vast class of logarithmically concave functions whose superlevel sets are concentric ellipsoids. For a fixed function from this class, we consider the set of all its “affine” positions. For any log-concave function f on Rd, we consider functions belonging to this set of “affine” positions, and find the one with the minimal integral under the condition that it is pointwise greater than or equal to f. We study the properties of existence and uniqueness of the solution to this problem. For any s∈[0,+∞), we consider the construction dual to the recently defined John s-function (Ivanov and Naszódi in Functional John ellipsoids. arXiv preprint: arXiv:2006.09934, 2020). We prove that such a construction determines a unique function and call it the Löwner s-function of f. We study the Löwner s-functions as s tends to zero and to infinity. Finally, extending the notion of the outer volume ratio, we define the outer integral ratio of a log-concave function and give an asymptotically tight bound on it."}],"type":"journal_article","doi":"10.1007/s12220-021-00691-4","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/2008.09543","open_access":"1"}],"external_id":{"isi":["000656507500001"],"arxiv":["2008.09543"]},"oa":1,"quality_controlled":"1","isi":1,"publication_identifier":{"issn":["1050-6926"],"eissn":["1559-002X"]},"month":"05","author":[{"last_name":"Ivanov","first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory"},{"full_name":"Tsiutsiurupa, Igor","first_name":"Igor","last_name":"Tsiutsiurupa"}],"volume":31,"date_created":"2021-06-13T22:01:32Z","date_updated":"2023-08-08T14:04:49Z","year":"2021","acknowledgement":"The authors acknowledge the support of the grant of the Russian Government N 075-15-2019-1926.","department":[{"_id":"UlWa"}],"publisher":"Springer","publication_status":"published"},{"status":"public","title":"Rectifiable curves in proximally smooth sets","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10181","oa_version":"Published Version","type":"journal_article","abstract":[{"text":"In this article we study some geometric properties of proximally smooth sets. First, we introduce a modification of the metric projection and prove its existence. Then we provide an algorithm for constructing a rectifiable curve between two sufficiently close points of a proximally smooth set in a uniformly convex and uniformly smooth Banach space, with the moduli of smoothness and convexity of power type. Our algorithm returns a reasonably short curve between two sufficiently close points of a proximally smooth set, is iterative and uses our modification of the metric projection. We estimate the length of the constructed curve and its deviation from the segment with the same endpoints. These estimates coincide up to a constant factor with those for the geodesics in a proximally smooth set in a Hilbert space.","lang":"eng"}],"article_type":"original","publication":"Set-Valued and Variational Analysis","citation":{"chicago":"Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally Smooth Sets.” Set-Valued and Variational Analysis. Springer Nature, 2021. https://doi.org/10.1007/s11228-021-00612-1.","short":"G. Ivanov, M.S. Lopushanski, Set-Valued and Variational Analysis (2021).","mla":"Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally Smooth Sets.” Set-Valued and Variational Analysis, Springer Nature, 2021, doi:10.1007/s11228-021-00612-1.","apa":"Ivanov, G., & Lopushanski, M. S. (2021). Rectifiable curves in proximally smooth sets. Set-Valued and Variational Analysis. Springer Nature. https://doi.org/10.1007/s11228-021-00612-1","ieee":"G. Ivanov and M. S. Lopushanski, “Rectifiable curves in proximally smooth sets,” Set-Valued and Variational Analysis. Springer Nature, 2021.","ista":"Ivanov G, Lopushanski MS. 2021. Rectifiable curves in proximally smooth sets. Set-Valued and Variational Analysis.","ama":"Ivanov G, Lopushanski MS. Rectifiable curves in proximally smooth sets. Set-Valued and Variational Analysis. 2021. doi:10.1007/s11228-021-00612-1"},"date_published":"2021-10-09T00:00:00Z","scopus_import":"1","day":"09","article_processing_charge":"No","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","acknowledgement":"Theorem 2 was obtained at Steklov Mathematical Institute RAS and supported by Russian Science Foundation, grant N 19-11-00087.","year":"2021","date_created":"2021-10-24T22:01:35Z","date_updated":"2023-08-14T08:11:38Z","author":[{"full_name":"Ivanov, Grigory","last_name":"Ivanov","first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E"},{"last_name":"Lopushanski","first_name":"Mariana S.","full_name":"Lopushanski, Mariana S."}],"quality_controlled":"1","isi":1,"external_id":{"isi":["000705774800001"],"arxiv":["2012.10691"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.10691"}],"language":[{"iso":"eng"}],"doi":"10.1007/s11228-021-00612-1","month":"10","publication_identifier":{"issn":["0927-6947"],"eissn":["1877-0541"]}},{"scopus_import":"1","article_processing_charge":"No","day":"30","page":"501–534 ","article_type":"original","citation":{"chicago":"Avvakumov, Sergey, Isaac Mabillard, Arkadiy B. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” Israel Journal of Mathematics. Springer Nature, 2021. https://doi.org/10.1007/s11856-021-2216-z.","mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” Israel Journal of Mathematics, vol. 245, Springer Nature, 2021, pp. 501–534, doi:10.1007/s11856-021-2216-z.","short":"S. Avvakumov, I. Mabillard, A.B. Skopenkov, U. Wagner, Israel Journal of Mathematics 245 (2021) 501–534.","ista":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. 2021. Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. 245, 501–534.","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A. B., & Wagner, U. (2021). Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-021-2216-z","ieee":"S. Avvakumov, I. Mabillard, A. B. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections. III. Codimension 2,” Israel Journal of Mathematics, vol. 245. Springer Nature, pp. 501–534, 2021.","ama":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. 2021;245:501–534. doi:10.1007/s11856-021-2216-z"},"publication":"Israel Journal of Mathematics","date_published":"2021-10-30T00:00:00Z","type":"journal_article","abstract":[{"lang":"eng","text":"We study conditions under which a finite simplicial complex K can be mapped to ℝd without higher-multiplicity intersections. An almost r-embedding is a map f: K → ℝd such that the images of any r pairwise disjoint simplices of K do not have a common point. We show that if r is not a prime power and d ≥ 2r + 1, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost r-embedding of the (d +1)(r − 1)-simplex in ℝd. This improves on previous constructions of counterexamples (for d ≥ 3r) based on a series of papers by M. Özaydin, M. Gromov, P. Blagojević, F. Frick, G. Ziegler, and the second and fourth present authors.\r\n\r\nThe counterexamples are obtained by proving the following algebraic criterion in codimension 2: If r ≥ 3 and if K is a finite 2(r − 1)-complex, then there exists an almost r-embedding K → ℝ2r if and only if there exists a general position PL map f: K → ℝ2r such that the algebraic intersection number of the f-images of any r pairwise disjoint simplices of K is zero. This result can be restated in terms of a cohomological obstruction and extends an analogous codimension 3 criterion by the second and fourth authors. As another application, we classify ornaments f: S3 ⊔ S3 ⊔ S3 → ℝ5 up to ornament concordance.\r\n\r\nIt follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for r = 2 is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample."}],"intvolume":" 245","status":"public","title":"Eliminating higher-multiplicity intersections. III. Codimension 2","_id":"10220","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa_version":"Preprint","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"month":"10","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"isi":1,"quality_controlled":"1","external_id":{"isi":["000712942100013"],"arxiv":["1511.03501"]},"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1007/s11856-021-2216-z","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2021","acknowledgement":"Research supported by the Swiss National Science Foundation (Project SNSF-PP00P2-138948), by the Austrian Science Fund (FWF Project P31312-N35), by the Russian Foundation for Basic Research (Grants No. 15-01-06302 and 19-01-00169), by a Simons-IUM Fellowship, and by the D. Zimin Dynasty Foundation Grant. We would like to thank E. Alkin, A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful comments and discussions.","volume":245,"date_updated":"2023-08-14T11:43:55Z","date_created":"2021-11-07T23:01:24Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"8183"},{"id":"9308","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac","full_name":"Mabillard, Isaac"},{"last_name":"Skopenkov","first_name":"Arkadiy B.","full_name":"Skopenkov, Arkadiy B."},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}]},{"month":"01","publication_identifier":{"issn":["2299-3274"]},"language":[{"iso":"eng"}],"doi":"10.1515/agms-2020-0103","isi":1,"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2004.02674"],"isi":["000734286800001"]},"oa":1,"file_date_updated":"2022-03-18T09:31:59Z","date_created":"2022-03-18T09:25:14Z","date_updated":"2023-08-17T07:07:58Z","volume":9,"author":[{"first_name":"Grigory","last_name":"Ivanov","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory"},{"full_name":"Tsiutsiurupa, Igor","first_name":"Igor","last_name":"Tsiutsiurupa"}],"publication_status":"published","publisher":"De Gruyter","department":[{"_id":"UlWa"}],"acknowledgement":"The authors acknowledge the support of the grant of the Russian Government N 075-15-\r\n2019-1926. G.I.was supported also by the SwissNational Science Foundation grant 200021-179133. The authors are very grateful to the anonymous reviewer for valuable remarks.","year":"2021","day":"29","article_processing_charge":"No","has_accepted_license":"1","keyword":["Applied Mathematics","Geometry and Topology","Analysis"],"scopus_import":"1","date_published":"2021-01-29T00:00:00Z","article_type":"original","page":"1-18","publication":"Analysis and Geometry in Metric Spaces","citation":{"ama":"Ivanov G, Tsiutsiurupa I. On the volume of sections of the cube. Analysis and Geometry in Metric Spaces. 2021;9(1):1-18. doi:10.1515/agms-2020-0103","ieee":"G. Ivanov and I. Tsiutsiurupa, “On the volume of sections of the cube,” Analysis and Geometry in Metric Spaces, vol. 9, no. 1. De Gruyter, pp. 1–18, 2021.","apa":"Ivanov, G., & Tsiutsiurupa, I. (2021). On the volume of sections of the cube. Analysis and Geometry in Metric Spaces. De Gruyter. https://doi.org/10.1515/agms-2020-0103","ista":"Ivanov G, Tsiutsiurupa I. 2021. On the volume of sections of the cube. Analysis and Geometry in Metric Spaces. 9(1), 1–18.","short":"G. Ivanov, I. Tsiutsiurupa, Analysis and Geometry in Metric Spaces 9 (2021) 1–18.","mla":"Ivanov, Grigory, and Igor Tsiutsiurupa. “On the Volume of Sections of the Cube.” Analysis and Geometry in Metric Spaces, vol. 9, no. 1, De Gruyter, 2021, pp. 1–18, doi:10.1515/agms-2020-0103.","chicago":"Ivanov, Grigory, and Igor Tsiutsiurupa. “On the Volume of Sections of the Cube.” Analysis and Geometry in Metric Spaces. De Gruyter, 2021. https://doi.org/10.1515/agms-2020-0103."},"abstract":[{"lang":"eng","text":"We study the properties of the maximal volume k-dimensional sections of the n-dimensional cube [−1, 1]n. We obtain a first order necessary condition for a k-dimensional subspace to be a local maximizer of the volume of such sections, which we formulate in a geometric way. We estimate the length of the projection of a vector of the standard basis of Rn onto a k-dimensional subspace that maximizes the volume of the intersection. We \u001cnd the optimal upper bound on the volume of a planar section of the cube [−1, 1]n , n ≥ 2."}],"issue":"1","type":"journal_article","file":[{"file_id":"10857","relation":"main_file","date_created":"2022-03-18T09:31:59Z","date_updated":"2022-03-18T09:31:59Z","success":1,"checksum":"7e615ac8489f5eae580b6517debfdc53","file_name":"2021_AnalysisMetricSpaces_Ivanov.pdf","access_level":"open_access","creator":"dernst","file_size":789801,"content_type":"application/pdf"}],"oa_version":"Published Version","ddc":["510"],"status":"public","title":"On the volume of sections of the cube","intvolume":" 9","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10856"},{"type":"journal_article","abstract":[{"text":"A tight frame is the orthogonal projection of some orthonormal basis of Rn onto Rk. We show that a set of vectors is a tight frame if and only if the set of all cross products of these vectors is a tight frame. We reformulate a range of problems on the volume of projections (or sections) of regular polytopes in terms of tight frames and write a first-order necessary condition for local extrema of these problems. As applications, we prove new results for the problem of maximization of the volume of zonotopes.","lang":"eng"}],"issue":"4","title":"Tight frames and related geometric problems","status":"public","intvolume":" 64","_id":"10860","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Preprint","keyword":["General Mathematics","Tight frame","Grassmannian","zonotope"],"scopus_import":"1","day":"18","article_processing_charge":"No","article_type":"original","page":"942-963","publication":"Canadian Mathematical Bulletin","citation":{"chicago":"Ivanov, Grigory. “Tight Frames and Related Geometric Problems.” Canadian Mathematical Bulletin. Canadian Mathematical Society, 2021. https://doi.org/10.4153/s000843952000096x.","mla":"Ivanov, Grigory. “Tight Frames and Related Geometric Problems.” Canadian Mathematical Bulletin, vol. 64, no. 4, Canadian Mathematical Society, 2021, pp. 942–63, doi:10.4153/s000843952000096x.","short":"G. Ivanov, Canadian Mathematical Bulletin 64 (2021) 942–963.","ista":"Ivanov G. 2021. Tight frames and related geometric problems. Canadian Mathematical Bulletin. 64(4), 942–963.","ieee":"G. Ivanov, “Tight frames and related geometric problems,” Canadian Mathematical Bulletin, vol. 64, no. 4. Canadian Mathematical Society, pp. 942–963, 2021.","apa":"Ivanov, G. (2021). Tight frames and related geometric problems. Canadian Mathematical Bulletin. Canadian Mathematical Society. https://doi.org/10.4153/s000843952000096x","ama":"Ivanov G. Tight frames and related geometric problems. Canadian Mathematical Bulletin. 2021;64(4):942-963. doi:10.4153/s000843952000096x"},"date_published":"2021-12-18T00:00:00Z","publication_status":"published","publisher":"Canadian Mathematical Society","department":[{"_id":"UlWa"}],"acknowledgement":"The author was supported by the Swiss National Science Foundation grant 200021_179133. The author acknowledges the financial support from the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926.","year":"2021","date_updated":"2023-09-05T12:43:09Z","date_created":"2022-03-18T09:55:59Z","volume":64,"author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov","full_name":"Ivanov, Grigory"}],"month":"12","publication_identifier":{"eissn":["1496-4287"],"issn":["0008-4395"]},"isi":1,"quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1804.10055","open_access":"1"}],"external_id":{"arxiv":["1804.10055"],"isi":["000730165300021"]},"language":[{"iso":"eng"}],"doi":"10.4153/s000843952000096x"},{"author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský","first_name":"Marek","full_name":"Filakovský, Marek"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"},{"full_name":"Zhechev, Stephan Y","first_name":"Stephan Y","last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2021-01-12T08:15:38Z","date_created":"2020-05-10T22:00:48Z","volume":"2020-January","year":"2020","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"SIAM","conference":{"end_date":"2020-01-08","location":"Salt Lake City, UT, United States","start_date":"2020-01-05","name":"SODA: Symposium on Discrete Algorithms"},"doi":"10.1137/1.9781611975994.47","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.1137/1.9781611975994.47","open_access":"1"}],"oa":1,"quality_controlled":"1","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory"}],"month":"01","publication_identifier":{"isbn":["9781611975994"]},"oa_version":"Published Version","_id":"7806","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Embeddability of simplicial complexes is undecidable","abstract":[{"text":"We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.\r\nOur result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4.","lang":"eng"}],"type":"conference","date_published":"2020-01-01T00:00:00Z","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","citation":{"ista":"Filakovský M, Wagner U, Zhechev SY. 2020. Embeddability of simplicial complexes is undecidable. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 767–785.","ieee":"M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial complexes is undecidable,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 767–785.","apa":"Filakovský, M., Wagner, U., & Zhechev, S. Y. (2020). Embeddability of simplicial complexes is undecidable. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2020–January, pp. 767–785). Salt Lake City, UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.47","ama":"Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes is undecidable. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2020-January. SIAM; 2020:767-785. doi:10.1137/1.9781611975994.47","chicago":"Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of Simplicial Complexes Is Undecidable.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2020–January:767–85. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.47.","mla":"Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 767–85, doi:10.1137/1.9781611975994.47.","short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785."},"page":"767-785","day":"01","article_processing_charge":"No","scopus_import":1},{"scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","day":"01","citation":{"ista":"Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening flow. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.","apa":"Avvakumov, S., & Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.12","ieee":"S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.12","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.12.","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” 36th International Symposium on Computational Geometry, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.12.","short":"S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"publication":"36th International Symposium on Computational Geometry","date_published":"2020-06-01T00:00:00Z","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"lang":"eng","text":"We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between \"grid peeling\" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase."}],"intvolume":" 164","status":"public","title":"Homotopic curve shortening and the affine curve-shortening flow","ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7991","oa_version":"Published Version","file":[{"file_size":575896,"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","checksum":"6872df6549142f709fb6354a1b2f2c06","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T11:13:49Z","relation":"main_file","file_id":"8007"}],"publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"month":"06","project":[{"call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","external_id":{"arxiv":["1909.00263"]},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","short":"CC BY (3.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2020.12","conference":{"name":"SoCG: Symposium on Computational Geometry","location":"Zürich, Switzerland","start_date":"2020-06-22","end_date":"2020-06-26"},"article_number":"12:1 - 12:15","license":"https://creativecommons.org/licenses/by/3.0/","file_date_updated":"2020-07-14T12:48:06Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2020","volume":164,"date_updated":"2021-01-12T08:16:23Z","date_created":"2020-06-22T09:14:19Z","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"first_name":"Gabriel","last_name":"Nivasch","full_name":"Nivasch, Gabriel"}]},{"day":"01","has_accepted_license":"1","article_processing_charge":"No","scopus_import":"1","date_published":"2020-06-01T00:00:00Z","publication":"36th International Symposium on Computational Geometry","citation":{"ista":"Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 61:1-61:13.","apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ama":"Patakova Z. Bounding radon number via Betti numbers. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61","chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61.","mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 36th International Symposium on Computational Geometry, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61.","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020."},"abstract":[{"lang":"eng","text":"We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface."}],"alternative_title":["LIPIcs"],"type":"conference","file":[{"file_id":"8005","relation":"main_file","date_created":"2020-06-23T06:56:23Z","date_updated":"2020-07-14T12:48:06Z","checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","file_name":"2020_LIPIcsSoCG_Patakova_61.pdf","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_size":645421}],"oa_version":"Published Version","status":"public","title":"Bounding radon number via Betti numbers","ddc":["510"],"intvolume":" 164","_id":"7989","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"language":[{"iso":"eng"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2020-06-22","location":"Zürich, Switzerland","end_date":"2020-06-26"},"doi":"10.4230/LIPIcs.SoCG.2020.61","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"arxiv":["1908.01677"]},"file_date_updated":"2020-07-14T12:48:06Z","article_number":"61:1-61:13","date_created":"2020-06-22T09:14:18Z","date_updated":"2021-01-12T08:16:22Z","volume":164,"author":[{"full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"year":"2020"},{"year":"2020","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","last_name":"Tancer","first_name":"Martin"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"date_created":"2020-06-22T09:14:20Z","date_updated":"2021-01-12T08:16:23Z","volume":164,"article_number":"62:1 - 62:16","file_date_updated":"2020-07-14T12:48:06Z","external_id":{"arxiv":["2003.13536"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","conference":{"end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2020.62","language":[{"iso":"eng"}],"month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7992","title":"Barycentric cuts through a convex body","status":"public","ddc":["510"],"intvolume":" 164","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2020_LIPIcsSoCG_Patakova.pdf","creator":"dernst","content_type":"application/pdf","file_size":750318,"file_id":"8004","relation":"main_file","checksum":"ce1c9194139a664fb59d1efdfc88eaae","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:45:52Z"}],"type":"conference","alternative_title":["LIPIcs"],"abstract":[{"text":"Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.","lang":"eng"}],"publication":"36th International Symposium on Computational Geometry","citation":{"mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” 36th International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62","ista":"Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 62:1-62:16.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through a convex body. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.62"},"date_published":"2020-06-01T00:00:00Z","scopus_import":1,"day":"01","article_processing_charge":"No","has_accepted_license":"1"}]