[{"doi":"10.4230/LIPIcs.STACS.2024.34","oa_version":"Published Version","day":"01","scopus_import":"1","has_accepted_license":"1","volume":289,"conference":{"location":"Clermont-Ferrand, France","name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2024-03-12","end_date":"2024-03-14"},"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"department":[{"_id":"UlWa"}],"arxiv":1,"publication_status":"published","intvolume":"       289","citation":{"ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289."},"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["510"],"title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","corr_author":"1","alternative_title":["LIPIcs"],"_id":"15168","date_updated":"2026-04-07T12:36:50Z","month":"03","ec_funded":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","abstract":[{"text":"A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the \"linearly ordered chromatic number\" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).","lang":"eng"}],"file":[{"relation":"main_file","date_created":"2024-03-25T07:44:30Z","checksum":"0524d4189fd1ed08989546511343edf3","file_name":"2024_LIPICs_Filakovsky.pdf","content_type":"application/pdf","success":1,"creator":"dernst","access_level":"open_access","file_id":"15175","date_updated":"2024-03-25T07:44:30Z","file_size":927290}],"license":"https://creativecommons.org/licenses/by/4.0/","external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"20339"}]},"status":"public","date_created":"2024-03-24T23:00:59Z","date_published":"2024-03-01T00:00:00Z","article_processing_charge":"No","file_date_updated":"2024-03-25T07:44:30Z","acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","isi":1,"language":[{"iso":"eng"}],"year":"2024","publication":"41st International Symposium on Theoretical Aspects of Computer Science","publication_identifier":{"isbn":["9783959773119"],"eissn":["1868-8969"]},"author":[{"last_name":"Filakovský","full_name":"Filakovský, Marek","first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nakajima, Tamio Vesa","first_name":"Tamio Vesa","last_name":"Nakajima"},{"first_name":"Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","orcid":"0000-0003-1245-3456","full_name":"Opršal, Jakub","last_name":"Opršal"},{"full_name":"Tasinato, Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca","last_name":"Tasinato"},{"last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"article_number":"34","quality_controlled":"1"},{"article_type":"original","external_id":{"arxiv":["1909.07347"],"isi":["000840292800001"]},"date_published":"2023-04-01T00:00:00Z","date_created":"2022-08-28T22:02:01Z","article_processing_charge":"Yes (in subscription journal)","status":"public","file":[{"content_type":"application/pdf","success":1,"creator":"alisjak","access_level":"open_access","file_id":"12006","date_updated":"2022-08-29T11:23:15Z","file_size":1002218,"relation":"main_file","date_created":"2022-08-29T11:23:15Z","file_name":"2022_DiscreteandComputionalGeometry_Arroyo.pdf","checksum":"def7ae3b28d9fd6aec16450e40090302"}],"page":"745–770","abstract":[{"lang":"eng","text":"A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles."}],"quality_controlled":"1","author":[{"first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara"},{"full_name":"Klute, Fabian","first_name":"Fabian","last_name":"Klute"},{"last_name":"Parada","full_name":"Parada, Irene","first_name":"Irene"},{"first_name":"Birgit","full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber"},{"full_name":"Seidel, Raimund","first_name":"Raimund","last_name":"Seidel"},{"last_name":"Wiedera","first_name":"Tilo","full_name":"Wiedera, Tilo"}],"file_date_updated":"2022-08-29T11:23:15Z","acknowledgement":"This work was started during the 6th Austrian–Japanese–Mexican–Spanish Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants for the good atmosphere as well as discussions on the topic. Also, we thank Jan Kynčl for sending us remarks on a preliminary version of this work and an anonymous referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie grant agreement No 754411. Fabian Klute was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and by the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was also partially supported by the Independent Research Fund Denmark grant 2020-2023 (9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"isi":1,"language":[{"iso":"eng"}],"publication":"Discrete and Computational Geometry","year":"2023","intvolume":"        69","department":[{"_id":"UlWa"}],"arxiv":1,"publication_status":"published","publisher":"Springer Nature","citation":{"short":"A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera, Discrete and Computational Geometry 69 (2023) 745–770.","ama":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting one edge into a simple drawing is hard. <i>Discrete and Computational Geometry</i>. 2023;69:745–770. doi:<a href=\"https://doi.org/10.1007/s00454-022-00394-9\">10.1007/s00454-022-00394-9</a>","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber, Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00394-9\">https://doi.org/10.1007/s00454-022-00394-9</a>.","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” <i>Discrete and Computational Geometry</i>, vol. 69. Springer Nature, pp. 745–770, 2023.","ista":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. 2023. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 69, 745–770.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R., &#38; Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00394-9\">https://doi.org/10.1007/s00454-022-00394-9</a>","mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Discrete and Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 745–770, doi:<a href=\"https://doi.org/10.1007/s00454-022-00394-9\">10.1007/s00454-022-00394-9</a>."},"oa":1,"doi":"10.1007/s00454-022-00394-9","oa_version":"Published Version","day":"01","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"has_accepted_license":"1","scopus_import":"1","volume":69,"ec_funded":1,"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["510"],"title":"Inserting one edge into a simple drawing is hard","month":"04","_id":"11999","date_updated":"2025-04-14T07:43:59Z"},{"page":"433-457","abstract":[{"text":"Bundling crossings is a strategy which can enhance the readability\r\nof graph drawings. In this paper we consider good drawings, i.e., we require that\r\nany two edges have at most one common point which can be a common vertex or a\r\ncrossing. Our main result is that there is a polynomial-time algorithm to compute an\r\n8-approximation of the bundled crossing number of a good drawing with no toothed\r\nhole. In general the number of toothed holes has to be added to the 8-approximation.\r\nIn the special case of circular drawings the approximation factor is 8, this improves\r\nupon the 10-approximation of Fink et al. [14]. Our approach also works with the same\r\napproximation factor for families of pseudosegments, i.e., curves intersecting at most\r\nonce. We also show how to compute a 9/2-approximation when the intersection graph of\r\nthe pseudosegments is bipartite and has no toothed hole.","lang":"eng"}],"file":[{"relation":"main_file","date_created":"2023-08-07T08:00:48Z","file_name":"2023_JourGraphAlgorithms_Arroyo.pdf","checksum":"9c30d2b8e324cc1c904f2aeec92013a3","content_type":"application/pdf","access_level":"open_access","creator":"dernst","success":1,"file_id":"13979","file_size":865774,"date_updated":"2023-08-07T08:00:48Z"}],"article_type":"original","external_id":{"arxiv":["2109.14892"]},"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"11185"}]},"status":"public","date_created":"2023-08-06T22:01:11Z","date_published":"2023-07-01T00:00:00Z","article_processing_charge":"Yes","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 Sk lodowska-Curie grant agreement No 754411. The second author has been supported by the German Research Foundation DFG Project FE 340/12-1. An extended abstract of this paper has been published in the proceedings of WALCOM 2022 in the Springer LNCS series, vol. 13174, pages 383–395.","file_date_updated":"2023-08-07T08:00:48Z","year":"2023","language":[{"iso":"eng"}],"publication":"Journal of Graph Algorithms and Applications","publication_identifier":{"issn":["1526-1719"]},"author":[{"orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M","last_name":"Arroyo Guevara"},{"first_name":"Stefan","full_name":"Felsner, Stefan","last_name":"Felsner"}],"issue":"6","quality_controlled":"1","doi":"10.7155/jgaa.00629","oa_version":"Published Version","day":"01","has_accepted_license":"1","volume":27,"scopus_import":"1","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411"}],"department":[{"_id":"UlWa"}],"publication_status":"published","arxiv":1,"intvolume":"        27","citation":{"mla":"Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing Number.” <i>Journal of Graph Algorithms and Applications</i>, vol. 27, no. 6, Brown University, 2023, pp. 433–57, doi:<a href=\"https://doi.org/10.7155/jgaa.00629\">10.7155/jgaa.00629</a>.","ieee":"A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,” <i>Journal of Graph Algorithms and Applications</i>, vol. 27, no. 6. Brown University, pp. 433–457, 2023.","apa":"Arroyo Guevara, A. M., &#38; Felsner, S. (2023). Approximating the bundled crossing number. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00629\">https://doi.org/10.7155/jgaa.00629</a>","ista":"Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number. Journal of Graph Algorithms and Applications. 27(6), 433–457.","chicago":"Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled Crossing Number.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2023. <a href=\"https://doi.org/10.7155/jgaa.00629\">https://doi.org/10.7155/jgaa.00629</a>.","ama":"Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. <i>Journal of Graph Algorithms and Applications</i>. 2023;27(6):433-457. doi:<a href=\"https://doi.org/10.7155/jgaa.00629\">10.7155/jgaa.00629</a>","short":"A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications 27 (2023) 433–457."},"oa":1,"publisher":"Brown University","title":"Approximating the bundled crossing number","ddc":["510"],"corr_author":"1","_id":"13969","date_updated":"2025-09-10T09:35:55Z","month":"07","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article"},{"external_id":{"isi":["001081646400010"]},"article_type":"original","article_processing_charge":"Yes (via OA deal)","date_published":"2023-09-01T00:00:00Z","date_created":"2023-10-22T22:01:14Z","status":"public","file":[{"content_type":"application/pdf","success":1,"access_level":"open_access","creator":"dernst","file_id":"14475","date_updated":"2023-10-31T11:20:31Z","file_size":623787,"relation":"main_file","date_created":"2023-10-31T11:20:31Z","checksum":"fbb05619fe4b650f341cc730425dd9c3","file_name":"2023_IsraelJourMath_Wagner.pdf"}],"abstract":[{"lang":"eng","text":"We prove the following quantitative Borsuk–Ulam-type result (an equivariant analogue of Gromov’s Topological Overlap Theorem): Let X be a free ℤ/2-complex of dimension d with coboundary expansion at least ηk in dimension 0 ≤ k < d. Then for every equivariant map F: X →ℤ/2 ℝd, the fraction of d-simplices σ of X with 0 ∈ F (σ) is at least 2−d Π d−1k=0ηk.\r\n\r\nAs an application, we show that for every sufficiently thick d-dimensional spherical building Y and every map f: Y → ℝ2d, we have f(σ) ∩ f(τ) ≠ ∅ for a constant fraction μd > 0 of pairs {σ, τ} of d-simplices of Y. In particular, such complexes are non-embeddable into ℝ2d, which proves a conjecture of Tancer and Vorwerk for sufficiently thick spherical buildings.\r\n\r\nWe complement these results by upper bounds on the coboundary expansion of two families of simplicial complexes; this indicates some limitations to the bounds one can obtain by straighforward applications of the quantitative Borsuk–Ulam theorem. Specifically, we prove\r\n\r\n• an upper bound of (d + 1)/2d on the normalized (d − 1)-th coboundary expansion constant of complete (d + 1)-partite d-dimensional complexes (under a mild divisibility assumption on the sizes of the parts); and\r\n\r\n• an upper bound of (d + 1)/2d + ε on the normalized (d − 1)-th coboundary expansion of the d-dimensional spherical building associated with GLd+2(Fq) for any ε > 0 and sufficiently large q. This disproves, in a rather strong sense, a conjecture of Lubotzky, Meshulam and Mozes."}],"page":"675-717","quality_controlled":"1","author":[{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"},{"last_name":"Wild","id":"4C20D868-F248-11E8-B48F-1D18A9856A87","first_name":"Pascal","full_name":"Wild, Pascal"}],"issue":"2","file_date_updated":"2023-10-31T11:20:31Z","publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"language":[{"iso":"eng"}],"year":"2023","isi":1,"publication":"Israel Journal of Mathematics","intvolume":"       256","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","oa":1,"citation":{"ama":"Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. <i>Israel Journal of Mathematics</i>. 2023;256(2):675-717. doi:<a href=\"https://doi.org/10.1007/s11856-023-2521-9\">10.1007/s11856-023-2521-9</a>","short":"U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.","chicago":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s11856-023-2521-9\">https://doi.org/10.1007/s11856-023-2521-9</a>.","mla":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:<a href=\"https://doi.org/10.1007/s11856-023-2521-9\">10.1007/s11856-023-2521-9</a>.","ieee":"U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes,” <i>Israel Journal of Mathematics</i>, vol. 256, no. 2. Springer Nature, pp. 675–717, 2023.","apa":"Wagner, U., &#38; Wild, P. (2023). Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-023-2521-9\">https://doi.org/10.1007/s11856-023-2521-9</a>","ista":"Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717."},"day":"01","oa_version":"Published Version","doi":"10.1007/s11856-023-2521-9","volume":256,"has_accepted_license":"1","scopus_import":"1","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"corr_author":"1","ddc":["510"],"title":"Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes","month":"09","date_updated":"2024-10-09T21:07:12Z","_id":"14445"},{"corr_author":"1","title":"Functional John and Löwner conditions for pairs of log-concave functions","ddc":["510"],"month":"12","date_updated":"2025-09-09T14:08:25Z","_id":"14737","type":"journal_article","tmp":{"image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)","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"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","day":"01","doi":"10.1093/imrn/rnad210","has_accepted_license":"1","scopus_import":"1","volume":2023,"keyword":["General Mathematics"],"intvolume":"      2023","publication_status":"published","arxiv":1,"department":[{"_id":"UlWa"}],"publisher":"Oxford University Press","oa":1,"citation":{"short":"G. Ivanov, M. Naszódi, International Mathematics Research Notices 2023 (2023) 20613–20669.","ama":"Ivanov G, Naszódi M. Functional John and Löwner conditions for pairs of log-concave functions. <i>International Mathematics Research Notices</i>. 2023;2023(23):20613-20669. doi:<a href=\"https://doi.org/10.1093/imrn/rnad210\">10.1093/imrn/rnad210</a>","chicago":"Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions for Pairs of Log-Concave Functions.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2023. <a href=\"https://doi.org/10.1093/imrn/rnad210\">https://doi.org/10.1093/imrn/rnad210</a>.","ieee":"G. Ivanov and M. Naszódi, “Functional John and Löwner conditions for pairs of log-concave functions,” <i>International Mathematics Research Notices</i>, vol. 2023, no. 23. Oxford University Press, pp. 20613–20669, 2023.","ista":"Ivanov G, Naszódi M. 2023. Functional John and Löwner conditions for pairs of log-concave functions. International Mathematics Research Notices. 2023(23), 20613–20669.","apa":"Ivanov, G., &#38; Naszódi, M. (2023). Functional John and Löwner conditions for pairs of log-concave functions. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnad210\">https://doi.org/10.1093/imrn/rnad210</a>","mla":"Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions for Pairs of Log-Concave Functions.” <i>International Mathematics Research Notices</i>, vol. 2023, no. 23, Oxford University Press, 2023, pp. 20613–69, doi:<a href=\"https://doi.org/10.1093/imrn/rnad210\">10.1093/imrn/rnad210</a>."},"acknowledgement":"We thank Alexander Litvak for the many discussions on Theorem 1.1. Igor Tsiutsiurupa participated in the early stage of this project. To our deep regret, Igor chose another road for his life and stopped working with us.\r\nThis work was supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences [to M.N.]; the National Research, Development, and Innovation Fund (NRDI) [K119670 and K131529 to M.N.]; and the ÚNKP-22-5 New National Excellence Program of the Ministry for Innovation and Technology from the source of the NRDI [to M.N.].","file_date_updated":"2024-01-08T09:53:09Z","publication_identifier":{"eissn":["1687-0247"],"issn":["1073-7928"]},"year":"2023","isi":1,"publication":"International Mathematics Research Notices","language":[{"iso":"eng"}],"quality_controlled":"1","author":[{"full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov"},{"last_name":"Naszódi","first_name":"Márton","full_name":"Naszódi, Márton"}],"issue":"23","file":[{"file_id":"14738","date_updated":"2024-01-08T09:53:09Z","file_size":815777,"content_type":"application/pdf","success":1,"access_level":"open_access","creator":"dernst","date_created":"2024-01-08T09:53:09Z","checksum":"353666cea80633beb0f1ffd342dff6d4","file_name":"2023_IMRN_Ivanov.pdf","relation":"main_file"}],"abstract":[{"text":"John’s fundamental theorem characterizing the largest volume ellipsoid contained in a convex body $K$ in $\\mathbb{R}^{d}$ has seen several generalizations and extensions. One direction, initiated by V. Milman is to replace ellipsoids by positions (affine images) of another body $L$. Another, more recent direction is to consider logarithmically concave functions on $\\mathbb{R}^{d}$ instead of convex bodies: we designate some special, radially symmetric log-concave function $g$ as the analogue of the Euclidean ball, and want to find its largest integral position under the constraint that it is pointwise below some given log-concave function $f$. We follow both directions simultaneously: we consider the functional question, and allow essentially any meaningful function to play the role of $g$ above. Our general theorems jointly extend known results in both directions. The dual problem in the setting of convex bodies asks for the smallest volume ellipsoid, called Löwner’s ellipsoid, containing $K$. We consider the analogous problem for functions: we characterize the solutions of the optimization problem of finding a smallest integral position of some log-concave function $g$ under the constraint that it is pointwise above $f$. It turns out that in the functional setting, the relationship between the John and the Löwner problems is more intricate than it is in the setting of convex bodies.","lang":"eng"}],"page":"20613-20669","external_id":{"arxiv":["2212.11781"],"isi":["001184146800001"]},"license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","article_type":"original","article_processing_charge":"Yes (via OA deal)","date_created":"2024-01-08T09:48:56Z","date_published":"2023-12-01T00:00:00Z","status":"public"},{"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2003.11351"}],"day":"01","oa_version":"Preprint","doi":"10.1137/20m1378223","scopus_import":"1","volume":52,"project":[{"grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020"}],"publication_status":"published","arxiv":1,"department":[{"_id":"UlWa"}],"keyword":["General Mathematics","General Computer Science"],"intvolume":"        52","oa":1,"citation":{"mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>, vol. 52, no. 1, Society for Industrial and Applied Mathematics, 2023, pp. 38–79, doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>.","ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” <i>SIAM Journal on Computing</i>, vol. 52, no. 1. Society for Industrial and Applied Mathematics, pp. 38–79, 2023.","apa":"Krokhin, A., Opršal, J., Wrochna, M., &#38; Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>","ista":"Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.","chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>.","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. 2023;52(1):38-79. doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79."},"publisher":"Society for Industrial and Applied Mathematics","title":"Topology and adjunction in promise constraint satisfaction","date_updated":"2025-05-14T10:51:32Z","_id":"12563","month":"01","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","abstract":[{"text":"he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.","lang":"eng"}],"page":"38-79","external_id":{"arxiv":["2003.11351"],"isi":["000955000000001"]},"article_type":"original","status":"public","article_processing_charge":"No","date_created":"2023-02-16T07:03:52Z","date_published":"2023-01-01T00:00:00Z","acknowledgement":"Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Stanislav Živný was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper re\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","language":[{"iso":"eng"}],"publication":"SIAM Journal on Computing","year":"2023","isi":1,"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"issue":"1","author":[{"full_name":"Krokhin, Andrei","first_name":"Andrei","last_name":"Krokhin"},{"full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456","first_name":"Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","last_name":"Opršal"},{"full_name":"Wrochna, Marcin","first_name":"Marcin","last_name":"Wrochna"},{"first_name":"Stanislav","full_name":"Živný, Stanislav","last_name":"Živný"}],"quality_controlled":"1"},{"file":[{"relation":"main_file","date_created":"2023-04-17T08:10:28Z","file_name":"2022_DMTCS_Biniaz.pdf","checksum":"439102ea4f6e2aeefd7107dfb9ccf532","content_type":"application/pdf","creator":"dernst","access_level":"open_access","success":1,"file_id":"12844","file_size":2072197,"date_updated":"2023-04-17T08:10:28Z"}],"abstract":[{"lang":"eng","text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved."}],"date_published":"2023-01-18T00:00:00Z","date_created":"2023-04-16T22:01:08Z","article_processing_charge":"No","status":"public","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"7950"}]},"article_type":"original","external_id":{"arxiv":["1903.06981"]},"publication_identifier":{"issn":["1462-7264"],"eissn":["1365-8050"]},"year":"2023","publication":"Discrete Mathematics and Theoretical Computer Science","language":[{"iso":"eng"}],"file_date_updated":"2023-04-17T08:10:28Z","acknowledgement":"This work was begun at the University of Waterloo and was partially supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n","quality_controlled":"1","author":[{"first_name":"Ahmad","full_name":"Biniaz, Ahmad","last_name":"Biniaz"},{"full_name":"Jain, Kshitij","first_name":"Kshitij","last_name":"Jain"},{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","last_name":"Masárová"},{"first_name":"Tillmann","full_name":"Miltzow, Tillmann","last_name":"Miltzow"},{"full_name":"Mondal, Debajyoti","first_name":"Debajyoti","last_name":"Mondal"},{"last_name":"Naredla","full_name":"Naredla, Anurag Murty","first_name":"Anurag Murty"},{"last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"last_name":"Turcotte","full_name":"Turcotte, Alexi","first_name":"Alexi"}],"issue":"2","article_number":"9","scopus_import":"1","volume":24,"has_accepted_license":"1","doi":"10.46298/DMTCS.8383","day":"18","oa_version":"Published Version","publisher":"EPI Sciences","citation":{"short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science 24 (2023).","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. 2023;24(2). doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>","chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences, 2023. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:<a href=\"https://doi.org/10.46298/DMTCS.8383\">10.46298/DMTCS.8383</a>.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer Science</i>. EPI Sciences. <a href=\"https://doi.org/10.46298/DMTCS.8383\">https://doi.org/10.46298/DMTCS.8383</a>","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 24(2), 9.","ieee":"A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>Discrete Mathematics and Theoretical Computer Science</i>, vol. 24, no. 2. EPI Sciences, 2023."},"oa":1,"intvolume":"        24","department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"publication_status":"published","arxiv":1,"month":"01","_id":"12833","date_updated":"2025-01-20T14:05:09Z","title":"Token swapping on trees","ddc":["000"],"type":"journal_article","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"}},{"month":"07","_id":"13270","date_updated":"2024-10-09T21:06:01Z","corr_author":"1","ddc":["510"],"title":"Iterated medial triangle subdivision in surfaces of constant curvature","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":70,"scopus_import":"1","has_accepted_license":"1","doi":"10.1007/s00454-023-00500-5","day":"05","oa_version":"Published Version","publisher":"Springer Nature","citation":{"ieee":"F. R. Brunck, “Iterated medial triangle subdivision in surfaces of constant curvature,” <i>Discrete and Computational Geometry</i>, vol. 70, no. 3. Springer Nature, pp. 1059–1089, 2023.","apa":"Brunck, F. R. (2023). Iterated medial triangle subdivision in surfaces of constant curvature. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-023-00500-5\">https://doi.org/10.1007/s00454-023-00500-5</a>","ista":"Brunck FR. 2023. Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. 70(3), 1059–1089.","mla":"Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature.” <i>Discrete and Computational Geometry</i>, vol. 70, no. 3, Springer Nature, 2023, pp. 1059–89, doi:<a href=\"https://doi.org/10.1007/s00454-023-00500-5\">10.1007/s00454-023-00500-5</a>.","chicago":"Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-023-00500-5\">https://doi.org/10.1007/s00454-023-00500-5</a>.","ama":"Brunck FR. Iterated medial triangle subdivision in surfaces of constant curvature. <i>Discrete and Computational Geometry</i>. 2023;70(3):1059-1089. doi:<a href=\"https://doi.org/10.1007/s00454-023-00500-5\">10.1007/s00454-023-00500-5</a>","short":"F.R. Brunck, Discrete and Computational Geometry 70 (2023) 1059–1089."},"oa":1,"intvolume":"        70","department":[{"_id":"UlWa"}],"arxiv":1,"publication_status":"published","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"isi":1,"language":[{"iso":"eng"}],"publication":"Discrete and Computational Geometry","year":"2023","file_date_updated":"2024-01-29T11:15:22Z","acknowledgement":"Open access funding provided by the Institute of Science and Technology (IST Austria).","quality_controlled":"1","issue":"3","author":[{"last_name":"Brunck","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","first_name":"Florestan R","full_name":"Brunck, Florestan R"}],"file":[{"relation":"main_file","checksum":"865e68daafdd4edcfc280172ec50f5ea","file_name":"2023_DiscreteComputGeometry_Brunck.pdf","date_created":"2024-01-29T11:15:22Z","success":1,"creator":"dernst","access_level":"open_access","content_type":"application/pdf","date_updated":"2024-01-29T11:15:22Z","file_size":1466020,"file_id":"14897"}],"page":"1059-1089","abstract":[{"lang":"eng","text":"Consider a geodesic triangle on a surface of constant curvature and subdivide it recursively into four triangles by joining the midpoints of its edges. We show the existence of a uniform δ>0\r\n such that, at any step of the subdivision, all the triangle angles lie in the interval (δ,π−δ)\r\n. Additionally, we exhibit stabilising behaviours for both angles and lengths as this subdivision progresses."}],"date_published":"2023-07-05T00:00:00Z","date_created":"2023-07-23T22:01:14Z","article_processing_charge":"Yes (via OA deal)","status":"public","article_type":"original","external_id":{"arxiv":["2107.04112"],"isi":["001023742800003"]}},{"author":[{"last_name":"Dymond","first_name":"Michael","full_name":"Dymond, Michael"},{"last_name":"Kaluza","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","first_name":"Vojtech","full_name":"Kaluza, Vojtech","orcid":"0000-0002-2512-8698"}],"quality_controlled":"1","file_date_updated":"2021-07-14T07:41:50Z","acknowledgement":"This work was done while both authors were employed at the University of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35.","isi":1,"language":[{"iso":"eng"}],"year":"2023","publication":"Israel Journal of Mathematics","publication_identifier":{"eissn":["1565-8511"]},"article_type":"original","external_id":{"arxiv":["1903.05923"],"isi":["000904950300003"]},"status":"public","date_published":"2023-03-01T00:00:00Z","date_created":"2021-07-14T07:01:28Z","article_processing_charge":"No","page":"501-554","abstract":[{"lang":"eng","text":"In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice. We study weaker notions of equivalence of separated nets and demonstrate that such notions also give rise to distinct equivalence classes. Put differently, we find occurrences of particularly strong divergence of separated nets from the integer lattice. Our approach generalises that of Burago and Kleiner and McMullen which takes place largely in a continuous setting. Existence of irregular separated nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞). In the present work we obtain stronger types of non-realisable densities."}],"file":[{"content_type":"application/pdf","creator":"vkaluza","access_level":"open_access","file_id":"9653","date_updated":"2021-07-14T07:41:50Z","file_size":900422,"relation":"main_file","date_created":"2021-07-14T07:41:50Z","file_name":"separated_nets.pdf","checksum":"6fa0a3207dd1d6467c309fd1bcc867d1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","ddc":["515","516"],"title":"Highly irregular separated nets","_id":"9652","date_updated":"2023-08-14T11:26:34Z","month":"03","department":[{"_id":"UlWa"}],"arxiv":1,"publication_status":"published","intvolume":"       253","keyword":["Lipschitz","bilipschitz","bounded displacement","modulus of continuity","separated net","non-realisable density","Burago--Kleiner construction"],"citation":{"short":"M. Dymond, V. Kaluza, Israel Journal of Mathematics 253 (2023) 501–554.","ama":"Dymond M, Kaluza V. Highly irregular separated nets. <i>Israel Journal of Mathematics</i>. 2023;253:501-554. doi:<a href=\"https://doi.org/10.1007/s11856-022-2448-6\">10.1007/s11856-022-2448-6</a>","chicago":"Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s11856-022-2448-6\">https://doi.org/10.1007/s11856-022-2448-6</a>.","ieee":"M. Dymond and V. Kaluza, “Highly irregular separated nets,” <i>Israel Journal of Mathematics</i>, vol. 253. Springer Nature, pp. 501–554, 2023.","ista":"Dymond M, Kaluza V. 2023. Highly irregular separated nets. Israel Journal of Mathematics. 253, 501–554.","apa":"Dymond, M., &#38; Kaluza, V. (2023). Highly irregular separated nets. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-022-2448-6\">https://doi.org/10.1007/s11856-022-2448-6</a>","mla":"Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.” <i>Israel Journal of Mathematics</i>, vol. 253, Springer Nature, 2023, pp. 501–54, doi:<a href=\"https://doi.org/10.1007/s11856-022-2448-6\">10.1007/s11856-022-2448-6</a>."},"oa":1,"publisher":"Springer Nature","doi":"10.1007/s11856-022-2448-6","oa_version":"Submitted Version","day":"01","has_accepted_license":"1","volume":253,"scopus_import":"1"},{"year":"2023","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2791-4585"]},"supervisor":[{"last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"file_date_updated":"2023-08-03T15:28:55Z","author":[{"first_name":"Seyda","id":"8ba3170d-dc85-11ea-9058-c4251c96a6eb","orcid":"0009-0008-0457-9730","full_name":"Köse, Seyda","last_name":"Köse"}],"page":"26","abstract":[{"text":"The extension of extremal combinatorics to the setting of exterior algebra is a work\r\nin progress that gained attention recently. In this thesis, we study the combinatorial structure of exterior algebra by introducing a dictionary that translates the notions from the set systems into the framework of exterior algebra. We show both generalizations of celebrated Erdös--Ko--Rado theorem and Hilton--Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms.\r\n","lang":"eng"}],"file":[{"file_name":"Exterior Algebra and Combinatorics.zip","checksum":"96ee518d796d02af71395622c45de03c","date_created":"2023-07-31T10:16:32Z","relation":"source_file","date_updated":"2023-07-31T10:16:32Z","file_size":28684,"file_id":"13333","access_level":"closed","creator":"skoese","content_type":"application/x-zip-compressed"},{"relation":"main_file","date_created":"2023-08-03T15:28:55Z","checksum":"f610f4713f88bc477de576aaa46b114e","file_name":"thesis-pdfa.pdf","content_type":"application/pdf","success":1,"access_level":"open_access","creator":"skoese","file_id":"13480","date_updated":"2023-08-03T15:28:55Z","file_size":4953418}],"degree_awarded":"MS","status":"public","OA_place":"publisher","date_created":"2023-07-31T10:20:55Z","date_published":"2023-07-31T00:00:00Z","article_processing_charge":"No","related_material":{"record":[{"status":"public","id":"12680","relation":"part_of_dissertation"}]},"_id":"13331","date_updated":"2026-04-07T13:29:29Z","month":"07","ddc":["510","516"],"title":"Exterior algebra and combinatorics","corr_author":"1","alternative_title":["ISTA Master's Thesis"],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","type":"dissertation","has_accepted_license":"1","doi":"10.15479/at:ista:13331","oa_version":"Published Version","day":"31","citation":{"chicago":"Köse, Seyda. “Exterior Algebra and Combinatorics.” Institute of Science and Technology Austria, 2023. <a href=\"https://doi.org/10.15479/at:ista:13331\">https://doi.org/10.15479/at:ista:13331</a>.","ama":"Köse S. Exterior algebra and combinatorics. 2023. doi:<a href=\"https://doi.org/10.15479/at:ista:13331\">10.15479/at:ista:13331</a>","short":"S. Köse, Exterior Algebra and Combinatorics, Institute of Science and Technology Austria, 2023.","mla":"Köse, Seyda. <i>Exterior Algebra and Combinatorics</i>. Institute of Science and Technology Austria, 2023, doi:<a href=\"https://doi.org/10.15479/at:ista:13331\">10.15479/at:ista:13331</a>.","ieee":"S. Köse, “Exterior algebra and combinatorics,” Institute of Science and Technology Austria, 2023.","ista":"Köse S. 2023. Exterior algebra and combinatorics. Institute of Science and Technology Austria.","apa":"Köse, S. (2023). <i>Exterior algebra and combinatorics</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:13331\">https://doi.org/10.15479/at:ista:13331</a>"},"oa":1,"publisher":"Institute of Science and Technology Austria","department":[{"_id":"GradSch"},{"_id":"UlWa"}],"publication_status":"published"},{"scopus_import":"1","volume":346,"day":"01","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2201.10892","open_access":"1"}],"oa_version":"Preprint","doi":"10.1016/j.disc.2023.113363","publisher":"Elsevier","oa":1,"citation":{"ieee":"G. Ivanov and S. Köse, “Erdős-Ko-Rado and Hilton-Milner theorems for two-forms,” <i>Discrete Mathematics</i>, vol. 346, no. 6. Elsevier, 2023.","apa":"Ivanov, G., &#38; Köse, S. (2023). Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2023.113363\">https://doi.org/10.1016/j.disc.2023.113363</a>","ista":"Ivanov G, Köse S. 2023. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. 346(6), 113363.","mla":"Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” <i>Discrete Mathematics</i>, vol. 346, no. 6, 113363, Elsevier, 2023, doi:<a href=\"https://doi.org/10.1016/j.disc.2023.113363\">10.1016/j.disc.2023.113363</a>.","chicago":"Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” <i>Discrete Mathematics</i>. Elsevier, 2023. <a href=\"https://doi.org/10.1016/j.disc.2023.113363\">https://doi.org/10.1016/j.disc.2023.113363</a>.","short":"G. Ivanov, S. Köse, Discrete Mathematics 346 (2023).","ama":"Ivanov G, Köse S. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. <i>Discrete Mathematics</i>. 2023;346(6). doi:<a href=\"https://doi.org/10.1016/j.disc.2023.113363\">10.1016/j.disc.2023.113363</a>"},"intvolume":"       346","arxiv":1,"publication_status":"published","department":[{"_id":"UlWa"},{"_id":"GradSch"}],"month":"06","date_updated":"2026-04-07T13:29:28Z","_id":"12680","corr_author":"1","title":"Erdős-Ko-Rado and Hilton-Milner theorems for two-forms","type":"journal_article","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of  was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines.","lang":"eng"}],"article_processing_charge":"No","date_created":"2023-02-26T23:01:00Z","date_published":"2023-06-01T00:00:00Z","status":"public","related_material":{"record":[{"status":"public","id":"13331","relation":"dissertation_contains"}]},"external_id":{"arxiv":["2201.10892"],"isi":["001189844500001"]},"article_type":"letter_note","publication_identifier":{"issn":["0012-365X"]},"language":[{"iso":"eng"}],"isi":1,"publication":"Discrete Mathematics","year":"2023","quality_controlled":"1","article_number":"113363","issue":"6","author":[{"orcid":"0000-0002-5021-3982","full_name":"Ivanov, Grigory","first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","last_name":"Ivanov"},{"last_name":"Köse","orcid":"0009-0008-0457-9730","full_name":"Köse, Seyda","first_name":"Seyda","id":"8ba3170d-dc85-11ea-9058-c4251c96a6eb"}]},{"month":"09","_id":"11593","date_updated":"2025-04-14T13:52:37Z","title":"The Z2-Genus of Kuratowski minors","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs"}],"volume":68,"scopus_import":"1","doi":"10.1007/s00454-022-00412-w","day":"01","main_file_link":[{"url":"https://arxiv.org/abs/1803.05085","open_access":"1"}],"oa_version":"Preprint","publisher":"Springer Nature","citation":{"ama":"Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. <i>Discrete and Computational Geometry</i>. 2022;68:425-447. doi:<a href=\"https://doi.org/10.1007/s00454-022-00412-w\">10.1007/s00454-022-00412-w</a>","short":"R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.","chicago":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-022-00412-w\">https://doi.org/10.1007/s00454-022-00412-w</a>.","ista":"Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 68, 425–447.","ieee":"R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” <i>Discrete and Computational Geometry</i>, vol. 68. Springer Nature, pp. 425–447, 2022.","apa":"Fulek, R., &#38; Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00412-w\">https://doi.org/10.1007/s00454-022-00412-w</a>","mla":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” <i>Discrete and Computational Geometry</i>, vol. 68, Springer Nature, 2022, pp. 425–47, doi:<a href=\"https://doi.org/10.1007/s00454-022-00412-w\">10.1007/s00454-022-00412-w</a>."},"oa":1,"intvolume":"        68","department":[{"_id":"UlWa"}],"arxiv":1,"publication_status":"published","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"isi":1,"year":"2022","publication":"Discrete and Computational Geometry","language":[{"iso":"eng"}],"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.","quality_controlled":"1","author":[{"last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","first_name":"Radoslav","full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774"},{"last_name":"Kynčl","full_name":"Kynčl, Jan","first_name":"Jan"}],"page":"425-447","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."}],"date_created":"2022-07-17T22:01:56Z","date_published":"2022-09-01T00:00:00Z","article_processing_charge":"No","status":"public","related_material":{"record":[{"status":"public","id":"186","relation":"earlier_version"}]},"article_type":"original","external_id":{"isi":["000825014500001"],"arxiv":["1803.05085"]}},{"issue":"3","author":[{"first_name":"Andrei","full_name":"Krokhin, Andrei","last_name":"Krokhin"},{"id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub","orcid":"0000-0003-1245-3456","full_name":"Opršal, Jakub","last_name":"Opršal"}],"quality_controlled":"1","year":"2022","language":[{"iso":"eng"}],"publication":"ACM SIGLOG News","publication_identifier":{"issn":["2372-3491"]},"status":"public","article_processing_charge":"No","date_published":"2022-07-01T00:00:00Z","date_created":"2022-08-27T11:23:37Z","external_id":{"arxiv":["2208.13538"]},"article_type":"original","abstract":[{"lang":"eng","text":"The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been."}],"page":"30-59","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","date_updated":"2022-09-05T08:19:38Z","_id":"11991","month":"07","title":"An invitation to the promise constraint satisfaction problem","oa":1,"citation":{"mla":"Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint Satisfaction Problem.” <i>ACM SIGLOG News</i>, vol. 9, no. 3, Association for Computing Machinery, 2022, pp. 30–59, doi:<a href=\"https://doi.org/10.1145/3559736.3559740\">10.1145/3559736.3559740</a>.","ieee":"A. Krokhin and J. Opršal, “An invitation to the promise constraint satisfaction problem,” <i>ACM SIGLOG News</i>, vol. 9, no. 3. Association for Computing Machinery, pp. 30–59, 2022.","ista":"Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News. 9(3), 30–59.","apa":"Krokhin, A., &#38; Opršal, J. (2022). An invitation to the promise constraint satisfaction problem. <i>ACM SIGLOG News</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3559736.3559740\">https://doi.org/10.1145/3559736.3559740</a>","chicago":"Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint Satisfaction Problem.” <i>ACM SIGLOG News</i>. Association for Computing Machinery, 2022. <a href=\"https://doi.org/10.1145/3559736.3559740\">https://doi.org/10.1145/3559736.3559740</a>.","short":"A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.","ama":"Krokhin A, Opršal J. An invitation to the promise constraint satisfaction problem. <i>ACM SIGLOG News</i>. 2022;9(3):30-59. doi:<a href=\"https://doi.org/10.1145/3559736.3559740\">10.1145/3559736.3559740</a>"},"publisher":"Association for Computing Machinery","publication_status":"published","arxiv":1,"department":[{"_id":"UlWa"}],"intvolume":"         9","volume":9,"main_file_link":[{"url":"http://arxiv.org/abs/2208.13538","open_access":"1"}],"day":"01","oa_version":"Preprint","doi":"10.1145/3559736.3559740"},{"type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","month":"11","date_updated":"2025-07-10T11:54:56Z","_id":"12129","corr_author":"1","title":"Connectivity of triangulation flip graphs in the plane","ddc":["510"],"publisher":"Springer Nature","oa":1,"citation":{"chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. 2022;68(4):1227-1284. doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>","short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 68 (2022) 1227–1284.","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete &#38; Computational Geometry. 68(4), 1227–1284.","apa":"Wagner, U., &#38; Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>."},"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"intvolume":"        68","publication_status":"published","department":[{"_id":"UlWa"}],"has_accepted_license":"1","volume":68,"scopus_import":"1","day":"14","oa_version":"Published Version","doi":"10.1007/s00454-022-00436-2","quality_controlled":"1","issue":"4","author":[{"last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"},{"first_name":"Emo","full_name":"Welzl, Emo","last_name":"Welzl"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"language":[{"iso":"eng"}],"year":"2022","isi":1,"publication":"Discrete & Computational Geometry","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","file_date_updated":"2023-01-23T11:10:03Z","article_processing_charge":"No","date_created":"2023-01-12T12:02:28Z","date_published":"2022-11-14T00:00:00Z","status":"public","related_material":{"record":[{"status":"public","id":"7807","relation":"earlier_version"},{"id":"7990","status":"public","relation":"earlier_version"}]},"external_id":{"isi":["000883222200003"]},"article_type":"original","file":[{"access_level":"open_access","creator":"dernst","success":1,"content_type":"application/pdf","file_size":1747581,"date_updated":"2023-01-23T11:10:03Z","file_id":"12345","relation":"main_file","checksum":"307e879d09e52eddf5b225d0aaa9213a","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","date_created":"2023-01-23T11:10:03Z"}],"abstract":[{"text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.","lang":"eng"}],"page":"1227-1284"},{"author":[{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"quality_controlled":"1","isi":1,"publication":"Bulletin de la Societe Mathematique de France","language":[{"iso":"eng"}],"year":"2022","publication_identifier":{"issn":["0037-9484"],"eissn":["2102-622X"]},"status":"public","article_processing_charge":"No","date_published":"2022-01-01T00:00:00Z","date_created":"2023-10-01T22:01:14Z","external_id":{"isi":["000958364400007"]},"article_type":"original","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"}],"page":"281-294","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","type":"journal_article","date_updated":"2025-09-10T09:55:10Z","_id":"14381","month":"01","title":"High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)","corr_author":"1","citation":{"short":"U. Wagner, Bulletin de La Societe Mathematique de France 438 (2022) 281–294.","ama":"Wagner U. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). <i>Bulletin de la Societe Mathematique de France</i>. 2022;438:281-294. doi:<a href=\"https://doi.org/10.24033/ast.1188\">10.24033/ast.1188</a>","chicago":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” <i>Bulletin de La Societe Mathematique de France</i>. Societe Mathematique de France, 2022. <a href=\"https://doi.org/10.24033/ast.1188\">https://doi.org/10.24033/ast.1188</a>.","mla":"Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and Others).” <i>Bulletin de La Societe Mathematique de France</i>, vol. 438, Societe Mathematique de France, 2022, pp. 281–94, doi:<a href=\"https://doi.org/10.24033/ast.1188\">10.24033/ast.1188</a>.","ieee":"U. Wagner, “High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others),” <i>Bulletin de la Societe Mathematique de France</i>, vol. 438. Societe Mathematique de France, pp. 281–294, 2022.","ista":"Wagner U. 2022. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). Bulletin de la Societe Mathematique de France. 438, 281–294.","apa":"Wagner, U. (2022). High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others). <i>Bulletin de La Societe Mathematique de France</i>. Societe Mathematique de France. <a href=\"https://doi.org/10.24033/ast.1188\">https://doi.org/10.24033/ast.1188</a>"},"publisher":"Societe Mathematique de France","publication_status":"published","department":[{"_id":"UlWa"}],"intvolume":"       438","volume":438,"scopus_import":"1","day":"01","oa_version":"None","doi":"10.24033/ast.1188"},{"page":"1133-1154","abstract":[{"lang":"eng","text":"Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p0 is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n≥2, there are always at least three distinct barycentric cuts through the point p0∈K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p0 are guaranteed if n≥3."}],"article_type":"original","external_id":{"arxiv":["2003.13536"],"isi":["000750681500001"]},"status":"public","date_published":"2022-12-01T00:00:00Z","date_created":"2022-02-20T23:01:35Z","article_processing_charge":"No","acknowledgement":"The work by Zuzana Patáková has been partially supported by Charles University Research Center Program No. UNCE/SCI/022, and part of it was done during her research stay at IST Austria. The work by Martin Tancer is supported by the GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and UNCE/SCI/004.","year":"2022","publication":"Discrete and Computational Geometry","language":[{"iso":"eng"}],"isi":1,"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"last_name":"Patakova","first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683"},{"last_name":"Tancer","full_name":"Tancer, Martin","first_name":"Martin"},{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"}],"quality_controlled":"1","doi":"10.1007/s00454-021-00364-7","oa_version":"Preprint","day":"01","main_file_link":[{"url":"https://arxiv.org/abs/2003.13536","open_access":"1"}],"scopus_import":"1","volume":68,"department":[{"_id":"UlWa"}],"publication_status":"published","arxiv":1,"intvolume":"        68","citation":{"mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” <i>Discrete and Computational Geometry</i>, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:<a href=\"https://doi.org/10.1007/s00454-021-00364-7\">10.1007/s00454-021-00364-7</a>.","ista":"Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body. Discrete and Computational Geometry. 68, 1133–1154.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” <i>Discrete and Computational Geometry</i>, vol. 68. Springer Nature, pp. 1133–1154, 2022.","apa":"Patakova, Z., Tancer, M., &#38; Wagner, U. (2022). Barycentric cuts through a convex body. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-021-00364-7\">https://doi.org/10.1007/s00454-021-00364-7</a>","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-021-00364-7\">https://doi.org/10.1007/s00454-021-00364-7</a>.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. <i>Discrete and Computational Geometry</i>. 2022;68:1133-1154. doi:<a href=\"https://doi.org/10.1007/s00454-021-00364-7\">10.1007/s00454-021-00364-7</a>","short":"Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68 (2022) 1133–1154."},"oa":1,"publisher":"Springer Nature","title":"Barycentric cuts through a convex body","_id":"10776","date_updated":"2023-08-02T14:38:58Z","month":"12","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","type":"journal_article"},{"file":[{"file_id":"11721","date_updated":"2022-08-02T10:40:48Z","file_size":734482,"content_type":"application/pdf","success":1,"creator":"dernst","access_level":"open_access","date_created":"2022-08-02T10:40:48Z","file_name":"2022_JourFunctionalAnalysis_Ivanov.pdf","checksum":"1cf185e264e04c87cb1ce67a00db88ab","relation":"main_file"}],"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."}],"external_id":{"isi":["000781371300008"],"arxiv":["2006.09934"]},"article_type":"original","article_processing_charge":"Yes (via OA deal)","date_created":"2022-03-20T23:01:38Z","date_published":"2022-06-01T00:00:00Z","status":"public","file_date_updated":"2022-08-02T10:40:48Z","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. ","publication_identifier":{"eissn":["1096-0783"],"issn":["0022-1236"]},"isi":1,"year":"2022","language":[{"iso":"eng"}],"publication":"Journal of Functional Analysis","quality_controlled":"1","article_number":"109441","issue":"11","author":[{"first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov"},{"full_name":"Naszódi, Márton","first_name":"Márton","last_name":"Naszódi"}],"day":"01","oa_version":"Published Version","doi":"10.1016/j.jfa.2022.109441","has_accepted_license":"1","volume":282,"scopus_import":"1","intvolume":"       282","arxiv":1,"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Elsevier","oa":1,"citation":{"ama":"Ivanov G, Naszódi M. Functional John ellipsoids. <i>Journal of Functional Analysis</i>. 2022;282(11). doi:<a href=\"https://doi.org/10.1016/j.jfa.2022.109441\">10.1016/j.jfa.2022.109441</a>","short":"G. Ivanov, M. Naszódi, Journal of Functional Analysis 282 (2022).","chicago":"Ivanov, Grigory, and Márton Naszódi. “Functional John Ellipsoids.” <i>Journal of Functional Analysis</i>. Elsevier, 2022. <a href=\"https://doi.org/10.1016/j.jfa.2022.109441\">https://doi.org/10.1016/j.jfa.2022.109441</a>.","mla":"Ivanov, Grigory, and Márton Naszódi. “Functional John Ellipsoids.” <i>Journal of Functional Analysis</i>, vol. 282, no. 11, 109441, Elsevier, 2022, doi:<a href=\"https://doi.org/10.1016/j.jfa.2022.109441\">10.1016/j.jfa.2022.109441</a>.","ista":"Ivanov G, Naszódi M. 2022. Functional John ellipsoids. Journal of Functional Analysis. 282(11), 109441.","apa":"Ivanov, G., &#38; Naszódi, M. (2022). Functional John ellipsoids. <i>Journal of Functional Analysis</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jfa.2022.109441\">https://doi.org/10.1016/j.jfa.2022.109441</a>","ieee":"G. Ivanov and M. Naszódi, “Functional John ellipsoids,” <i>Journal of Functional Analysis</i>, vol. 282, no. 11. Elsevier, 2022."},"corr_author":"1","title":"Functional John ellipsoids","ddc":["510"],"month":"06","date_updated":"2024-10-09T21:01:51Z","_id":"10887","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8"},{"page":"383-395","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."}],"related_material":{"record":[{"status":"public","id":"13969","relation":"later_version"}]},"external_id":{"isi":["001435074700031"],"arxiv":["2109.14892"]},"date_published":"2022-03-16T00:00:00Z","date_created":"2022-04-17T22:01:47Z","article_processing_charge":"No","status":"public","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":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783030967307"]},"isi":1,"year":"2022","publication":"WALCOM 2022: Algorithms and Computation","language":[{"iso":"eng"}],"quality_controlled":"1","author":[{"last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Felsner, Stefan","first_name":"Stefan","last_name":"Felsner"}],"doi":"10.1007/978-3-030-96731-4_31","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2109.14892"}],"oa_version":"Preprint","day":"16","conference":{"name":"WALCOM: Algorithms and Computation","location":"Jember, Indonesia","start_date":"2022-03-24","end_date":"2022-03-26"},"project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"volume":13174,"scopus_import":"1","intvolume":"     13174","department":[{"_id":"UlWa"}],"arxiv":1,"publication_status":"published","publisher":"Springer Nature","citation":{"ama":"Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In: <i>WALCOM 2022: Algorithms and Computation</i>. Vol 13174. LNCS. Springer Nature; 2022:383-395. doi:<a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">10.1007/978-3-030-96731-4_31</a>","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 <i>WALCOM 2022: Algorithms and Computation</i>, 13174:383–95. LNCS. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">https://doi.org/10.1007/978-3-030-96731-4_31</a>.","mla":"Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing Number.” <i>WALCOM 2022: Algorithms and Computation</i>, vol. 13174, Springer Nature, 2022, pp. 383–95, doi:<a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">10.1007/978-3-030-96731-4_31</a>.","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., &#38; Felsner, S. (2022). Approximating the bundled crossing number. In <i>WALCOM 2022: Algorithms and Computation</i> (Vol. 13174, pp. 383–395). Jember, Indonesia: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-96731-4_31\">https://doi.org/10.1007/978-3-030-96731-4_31</a>","ieee":"A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,” in <i>WALCOM 2022: Algorithms and Computation</i>, Jember, Indonesia, 2022, vol. 13174, pp. 383–395."},"oa":1,"title":"Approximating the bundled crossing number","month":"03","_id":"11185","date_updated":"2025-09-10T09:35:56Z","ec_funded":1,"series_title":"LNCS","type":"conference","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"title":"A quantitative Helly-type theorem: Containment in a homothet","month":"04","date_updated":"2023-10-18T06:58:03Z","_id":"11435","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"11","oa_version":"Preprint","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2103.04122","open_access":"1"}],"doi":"10.1137/21M1403308","scopus_import":"1","volume":36,"intvolume":"        36","publication_status":"published","arxiv":1,"department":[{"_id":"UlWa"}],"publisher":"Society for Industrial and Applied Mathematics","oa":1,"citation":{"chicago":"Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2022. <a href=\"https://doi.org/10.1137/21M1403308\">https://doi.org/10.1137/21M1403308</a>.","short":"G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 951–957.","ama":"Ivanov G, Naszodi M. A quantitative Helly-type theorem: Containment in a homothet. <i>SIAM Journal on Discrete Mathematics</i>. 2022;36(2):951-957. doi:<a href=\"https://doi.org/10.1137/21M1403308\">10.1137/21M1403308</a>","apa":"Ivanov, G., &#38; Naszodi, M. (2022). A quantitative Helly-type theorem: Containment in a homothet. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/21M1403308\">https://doi.org/10.1137/21M1403308</a>","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,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 36, no. 2. Society for Industrial and Applied Mathematics, pp. 951–957, 2022.","mla":"Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment in a Homothet.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 36, no. 2, Society for Industrial and Applied Mathematics, 2022, pp. 951–57, doi:<a href=\"https://doi.org/10.1137/21M1403308\">10.1137/21M1403308</a>."},"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.","publication_identifier":{"issn":["0895-4801"]},"year":"2022","isi":1,"language":[{"iso":"eng"}],"publication":"SIAM Journal on Discrete Mathematics","quality_controlled":"1","author":[{"last_name":"Ivanov","full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory"},{"last_name":"Naszodi","first_name":"Marton","full_name":"Naszodi, Marton"}],"issue":"2","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"}],"page":"951-957","external_id":{"arxiv":["2103.04122"],"isi":["000793158200002"]},"article_type":"original","article_processing_charge":"No","date_published":"2022-04-11T00:00:00Z","date_created":"2022-06-05T22:01:50Z","status":"public"},{"publication_identifier":{"issn":["0927-6947"],"eissn":["1877-0541"]},"language":[{"iso":"eng"}],"publication":"Set-Valued and Variational Analysis","isi":1,"year":"2022","acknowledgement":"Theorem 2 was obtained at Steklov Mathematical Institute RAS and supported by Russian Science Foundation, grant N 19-11-00087.","quality_controlled":"1","author":[{"last_name":"Ivanov","first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory"},{"full_name":"Lopushanski, Mariana S.","first_name":"Mariana S.","last_name":"Lopushanski"}],"issue":"2","page":"657-675","abstract":[{"lang":"eng","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."}],"date_created":"2021-10-24T22:01:35Z","date_published":"2022-06-01T00:00:00Z","article_processing_charge":"No","status":"public","article_type":"original","external_id":{"arxiv":["2012.10691"],"isi":["000705774800001"]},"month":"06","_id":"10181","date_updated":"2024-05-22T09:23:37Z","title":"Rectifiable curves in proximally smooth sets","type":"journal_article","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","volume":30,"scopus_import":"1","doi":"10.1007/s11228-021-00612-1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2012.10691"}],"day":"01","oa_version":"Published Version","publisher":"Springer Nature","citation":{"mla":"Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally Smooth Sets.” <i>Set-Valued and Variational Analysis</i>, vol. 30, no. 2, Springer Nature, 2022, pp. 657–75, doi:<a href=\"https://doi.org/10.1007/s11228-021-00612-1\">10.1007/s11228-021-00612-1</a>.","apa":"Ivanov, G., &#38; Lopushanski, M. S. (2022). Rectifiable curves in proximally smooth sets. <i>Set-Valued and Variational Analysis</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11228-021-00612-1\">https://doi.org/10.1007/s11228-021-00612-1</a>","ista":"Ivanov G, Lopushanski MS. 2022. Rectifiable curves in proximally smooth sets. Set-Valued and Variational Analysis. 30(2), 657–675.","ieee":"G. Ivanov and M. S. Lopushanski, “Rectifiable curves in proximally smooth sets,” <i>Set-Valued and Variational Analysis</i>, vol. 30, no. 2. Springer Nature, pp. 657–675, 2022.","ama":"Ivanov G, Lopushanski MS. Rectifiable curves in proximally smooth sets. <i>Set-Valued and Variational Analysis</i>. 2022;30(2):657-675. doi:<a href=\"https://doi.org/10.1007/s11228-021-00612-1\">10.1007/s11228-021-00612-1</a>","short":"G. Ivanov, M.S. Lopushanski, Set-Valued and Variational Analysis 30 (2022) 657–675.","chicago":"Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally Smooth Sets.” <i>Set-Valued and Variational Analysis</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s11228-021-00612-1\">https://doi.org/10.1007/s11228-021-00612-1</a>."},"oa":1,"intvolume":"        30","department":[{"_id":"UlWa"}],"publication_status":"published","arxiv":1}]