[{"month":"08","language":[{"iso":"eng"}],"OA_place":"publisher","publisher":"Institute of Science and Technology Austria","article_processing_charge":"No","date_published":"2022-08-11T00:00:00Z","citation":{"ama":"Wild P. High-dimensional expansion and crossing numbers of simplicial complexes. 2022. doi:<a href=\"https://doi.org/10.15479/at:ista:11777\">10.15479/at:ista:11777</a>","ieee":"P. Wild, “High-dimensional expansion and crossing numbers of simplicial complexes,” Institute of Science and Technology Austria, 2022.","chicago":"Wild, Pascal. “High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes.” Institute of Science and Technology Austria, 2022. <a href=\"https://doi.org/10.15479/at:ista:11777\">https://doi.org/10.15479/at:ista:11777</a>.","mla":"Wild, Pascal. <i>High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes</i>. Institute of Science and Technology Austria, 2022, doi:<a href=\"https://doi.org/10.15479/at:ista:11777\">10.15479/at:ista:11777</a>.","ista":"Wild P. 2022. High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology Austria.","apa":"Wild, P. (2022). <i>High-dimensional expansion and crossing numbers of simplicial complexes</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:11777\">https://doi.org/10.15479/at:ista:11777</a>","short":"P. Wild, High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes, Institute of Science and Technology Austria, 2022."},"type":"dissertation","day":"11","doi":"10.15479/at:ista:11777","date_created":"2022-08-10T15:51:19Z","has_accepted_license":"1","status":"public","ddc":["500","516","514"],"corr_author":"1","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-021-3"]},"title":"High-dimensional expansion and crossing numbers of simplicial complexes","department":[{"_id":"GradSch"},{"_id":"UlWa"}],"abstract":[{"lang":"eng","text":"In this dissertation we study coboundary expansion of simplicial complex with a view of giving geometric applications.\r\nOur main novel tool is an equivariant version of Gromov's celebrated Topological Overlap Theorem. The equivariant topological overlap theorem leads to various geometric applications including a quantitative non-embeddability result for sufficiently thick buildings (which partially resolves a conjecture of Tancer and Vorwerk) and an improved lower bound on the pair-crossing number of (bounded degree) expander graphs. Additionally, we will give new proofs for several known lower bounds for geometric problems such as the number of Tverberg partitions or the crossing number of complete bipartite graphs.\r\nFor the aforementioned applications one is naturally lead to study expansion properties of joins of simplicial complexes. In the presence of a special certificate for expansion (as it is the case, e.g., for spherical buildings), the join of two expanders is an expander. On the flip-side, we report quite some evidence that coboundary expansion exhibits very non-product-like behaviour under taking joins. For instance, we exhibit infinite families of graphs $(G_n)_{n\\in \\mathbb{N}}$ and $(H_n)_{n\\in\\mathbb{N}}$ whose join $G_n*H_n$ has expansion of lower order than the product of the expansion constant of the graphs. Moreover, we show an upper bound of $(d+1)/2^d$ on the normalized coboundary expansion constants for the complete multipartite complex $[n]^{*(d+1)}$ (under a mild divisibility condition on $n$).\r\nVia the probabilistic method the latter result extends to an upper bound of $(d+1)/2^d+\\varepsilon$ on the coboundary expansion constant of the spherical building associated with $\\mathrm{PGL}_{d+2}(\\mathbb{F}_q)$ for any $\\varepsilon>0$ and sufficiently large $q=q(\\varepsilon)$. This disproves a conjecture of Lubotzky, Meshulam and Mozes -- in a rather strong sense.\r\nBy improving on existing lower bounds we make further progress towards closing the gap between the known lower and upper bounds on the coboundary expansion constants of $[n]^{*(d+1)}$. The best improvements we achieve using computer-aided proofs and flag algebras. The exact value even for the complete $3$-partite $2$-dimensional complex $[n]^{*3}$ remains unknown but we are happy to conjecture a precise value for every $n$. %Moreover, we show that a previously shown lower bound on the expansion constant of the spherical building associated with $\\mathrm{PGL}_{2}(\\mathbb{F}_q)$ is not tight.\r\nIn a loosely structured, last chapter of this thesis we collect further smaller observations related to expansion. We point out a link between discrete Morse theory and a technique for showing coboundary expansion, elaborate a bit on the hardness of computing coboundary expansion constants, propose a new criterion for coboundary expansion (in a very dense setting) and give one way of making the folklore result that expansion of links is a necessary condition for a simplicial complex to be an expander precise."}],"author":[{"id":"4C20D868-F248-11E8-B48F-1D18A9856A87","full_name":"Wild, Pascal","last_name":"Wild","first_name":"Pascal"}],"oa":1,"page":"170","oa_version":"Published Version","_id":"11777","ec_funded":1,"project":[{"name":"International IST Doctoral Program","call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"publication_status":"published","year":"2022","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","file":[{"file_id":"11780","content_type":"text/x-python","relation":"supplementary_material","file_size":16828,"date_updated":"2022-08-10T15:34:04Z","file_name":"flags.py","date_created":"2022-08-10T15:34:04Z","description":"Code for computer-assisted proofs in Section 8.4.7 in Thesis","checksum":"f5f3af1fb7c8a24b71ddc88ad7f7c5b4","creator":"pwild","access_level":"open_access"},{"file_size":12226,"date_updated":"2022-08-10T15:34:10Z","relation":"supplementary_material","file_id":"11781","content_type":"text/x-c++src","file_name":"lowerbound.cpp","creator":"pwild","checksum":"1f7c12dfe3bdaa9b147e4fbc3d34e3d5","date_created":"2022-08-10T15:34:10Z","description":"Code for proof of Lemma 8.20 in Thesis","access_level":"open_access"},{"creator":"pwild","date_created":"2022-08-10T15:34:17Z","description":"Code for proof of Proposition 7.9 in Thesis","checksum":"4cf81455c49e5dec3b9b2e3980137eeb","access_level":"open_access","date_updated":"2022-08-10T15:34:17Z","file_size":3240,"content_type":"text/x-python","file_id":"11782","relation":"supplementary_material","file_name":"upperbound.py"},{"creator":"pwild","date_created":"2022-08-11T16:08:33Z","checksum":"4e96575b10cbe4e0d0db2045b2847774","access_level":"open_access","file_size":5086282,"date_updated":"2022-08-11T16:08:33Z","file_id":"11809","content_type":"application/pdf","relation":"main_file","title":"High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes","file_name":"finalthesisPascalWildPDFA.pdf"},{"content_type":"application/zip","file_id":"11810","relation":"source_file","date_updated":"2022-08-11T16:09:19Z","file_size":18150068,"file_name":"ThesisSubmission.zip","date_created":"2022-08-11T16:09:19Z","checksum":"92d94842a1fb6dca5808448137573b2e","creator":"pwild","access_level":"closed"}],"supervisor":[{"last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"file_date_updated":"2022-08-11T16:09:19Z","degree_awarded":"PhD","alternative_title":["ISTA Thesis"],"date_updated":"2026-04-07T14:18:26Z"},{"month":"06","publisher":"Brown University","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","publication":"Journal of Graph Algorithms and Applications","citation":{"mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:<a href=\"https://doi.org/10.7155/jgaa.00591\">10.7155/jgaa.00591</a>.","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” <i>Journal of Graph Algorithms and Applications</i>, vol. 26, no. 2. Brown University, pp. 225–240, 2022.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” <i>Journal of Graph Algorithms and Applications</i>. Brown University, 2022. <a href=\"https://doi.org/10.7155/jgaa.00591\">https://doi.org/10.7155/jgaa.00591</a>.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. 2022;26(2):225-240. doi:<a href=\"https://doi.org/10.7155/jgaa.00591\">10.7155/jgaa.00591</a>","short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022) 225–240.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. <i>Journal of Graph Algorithms and Applications</i>. Brown University. <a href=\"https://doi.org/10.7155/jgaa.00591\">https://doi.org/10.7155/jgaa.00591</a>","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and Applications. 26(2), 225–240."},"date_published":"2022-06-01T00:00:00Z","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"intvolume":"        26","day":"01","type":"journal_article","acknowledgement":"A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","doi":"10.7155/jgaa.00591","date_created":"2022-08-21T22:01:56Z","arxiv":1,"status":"public","has_accepted_license":"1","scopus_import":"1","publication_identifier":{"issn":["1526-1719"]},"ddc":["000"],"corr_author":"1","title":"On compatible matchings","issue":"2","department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"abstract":[{"text":"A matching is compatible to two or more labeled point sets of size n with labels {1, . . . , n} if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled sets of n points in convex position there exists a compatible matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound, we use probabilistic arguments to show that for any ℓ given sets of n points there exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges. Finally, we show that Θ(log n) copies of any set of n points are necessary and sufficient for the existence of labelings of these point sets such that any compatible matching consists only of a single edge.","lang":"eng"}],"external_id":{"arxiv":["2101.03928"]},"author":[{"last_name":"Aichholzer","first_name":"Oswin","full_name":"Aichholzer, Oswin"},{"first_name":"Alan M","last_name":"Arroyo Guevara","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Masárová","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322"},{"full_name":"Parada, Irene","first_name":"Irene","last_name":"Parada"},{"full_name":"Perz, Daniel","last_name":"Perz","first_name":"Daniel"},{"full_name":"Pilz, Alexander","first_name":"Alexander","last_name":"Pilz"},{"first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vogtenhuber, Birgit","first_name":"Birgit","last_name":"Vogtenhuber"}],"oa":1,"article_type":"original","page":"225-240","oa_version":"Published Version","ec_funded":1,"_id":"11938","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"name":"Mathematics, Computer Science","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407","name":"Game Theory"}],"publication_status":"published","volume":26,"year":"2022","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"9296"}]},"file":[{"file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","file_id":"11940","content_type":"application/pdf","relation":"main_file","date_updated":"2022-08-22T06:42:42Z","file_size":694538,"access_level":"open_access","date_created":"2022-08-22T06:42:42Z","checksum":"dc6e255e3558faff924fd9e370886c11","creator":"dernst","success":1}],"file_date_updated":"2022-08-22T06:42:42Z","date_updated":"2026-04-16T09:18:20Z"},{"date_updated":"2022-09-05T08:19:38Z","year":"2022","volume":9,"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"30-59","article_type":"original","oa":1,"_id":"11991","oa_version":"Preprint","department":[{"_id":"UlWa"}],"external_id":{"arxiv":["2208.13538"]},"author":[{"first_name":"Andrei","last_name":"Krokhin","full_name":"Krokhin, Andrei"},{"last_name":"Opršal","first_name":"Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456"}],"abstract":[{"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.","lang":"eng"}],"publication_identifier":{"issn":["2372-3491"]},"title":"An invitation to the promise constraint satisfaction problem","issue":"3","type":"journal_article","day":"01","status":"public","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/2208.13538"}],"date_created":"2022-08-27T11:23:37Z","arxiv":1,"doi":"10.1145/3559736.3559740","citation":{"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>","ista":"Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News. 9(3), 30–59.","short":"A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.","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.","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>.","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>","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>."},"date_published":"2022-07-01T00:00:00Z","intvolume":"         9","publisher":"Association for Computing Machinery","language":[{"iso":"eng"}],"month":"07","publication":"ACM SIGLOG News","quality_controlled":"1","article_processing_charge":"No"},{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"scopus_import":"1","corr_author":"1","ddc":["510"],"issue":"4","title":"Connectivity of triangulation flip graphs in the plane","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","type":"journal_article","day":"14","status":"public","has_accepted_license":"1","doi":"10.1007/s00454-022-00436-2","date_created":"2023-01-12T12:02:28Z","citation":{"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>.","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>","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.","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>.","short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 68 (2022) 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>","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete &#38; Computational Geometry. 68(4), 1227–1284."},"date_published":"2022-11-14T00:00:00Z","intvolume":"        68","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publisher":"Springer Nature","language":[{"iso":"eng"}],"month":"11","publication":"Discrete & Computational Geometry","quality_controlled":"1","article_processing_charge":"No","file_date_updated":"2023-01-23T11:10:03Z","date_updated":"2025-07-10T11:54:56Z","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"volume":68,"year":"2022","publication_status":"published","related_material":{"record":[{"id":"7807","relation":"earlier_version","status":"public"},{"id":"7990","status":"public","relation":"earlier_version"}]},"file":[{"access_level":"open_access","checksum":"307e879d09e52eddf5b225d0aaa9213a","date_created":"2023-01-23T11:10:03Z","success":1,"creator":"dernst","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","relation":"main_file","file_id":"12345","content_type":"application/pdf","file_size":1747581,"date_updated":"2023-01-23T11:10:03Z"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"article_type":"original","page":"1227-1284","oa":1,"_id":"12129","oa_version":"Published Version","department":[{"_id":"UlWa"}],"external_id":{"isi":["000883222200003"]},"author":[{"last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"abstract":[{"lang":"eng","text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations."}]},{"publication":"Bulletin de la Societe Mathematique de France","quality_controlled":"1","article_processing_charge":"No","publisher":"Societe Mathematique de France","language":[{"iso":"eng"}],"month":"01","intvolume":"       438","citation":{"short":"U. Wagner, Bulletin de La Societe Mathematique de France 438 (2022) 281–294.","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>","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.","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>.","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>"},"date_published":"2022-01-01T00:00:00Z","status":"public","date_created":"2023-10-01T22:01:14Z","doi":"10.24033/ast.1188","day":"01","type":"journal_article","title":"High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)","scopus_import":"1","publication_identifier":{"eissn":["2102-622X"],"issn":["0037-9484"]},"corr_author":"1","external_id":{"isi":["000958364400007"]},"author":[{"last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"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"}],"department":[{"_id":"UlWa"}],"_id":"14381","oa_version":"None","article_type":"original","page":"281-294","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"year":"2022","volume":438,"publication_status":"published","date_updated":"2025-09-10T09:55:10Z"},{"has_accepted_license":"1","status":"public","doi":"10.4230/LIPIcs.ESA.2022.3","arxiv":1,"date_created":"2024-05-29T06:27:16Z","acknowledgement":"g Anna Lubiw: Supported by the Natural Sciences and Engineering Research Council of\r\nCanada (NSERC). Jayson Lynch: Supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). Zuzana Masárová: Supported by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. Virginia Vassilevska Williams: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-1514339 and CCF-1909429, a BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship.\r\nNicole Wein: Supported by a grant to DIMACS from the Simons Foundation (820931). This work was done while the author was at MIT.\r\nThis research was initiated at the 34th Bellairs Winter Workshop on Computational Geometry, co-organized by Erik Demaine and Godfried Toussaint, held on March 22–29,\r\n2019 in Holetown, Barbados. We thank the other participants of that workshop for providing a\r\nstimulating research environment.","type":"conference","day":"01","title":"Hardness of token swapping on trees","corr_author":"1","ddc":["510"],"scopus_import":"1","publication":"30th Annual European Symposium on Algorithms","article_processing_charge":"Yes","quality_controlled":"1","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"09","article_number":"3","intvolume":"       244","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"start_date":"2022-09-05","location":"Berlin/Potsdam, Germany","end_date":"2022-09-09","name":"ESA: European Symposium on Algorithms"},"date_published":"2022-09-01T00:00:00Z","citation":{"short":"O. Aichholzer, E.D. Demaine, M. Korman, A. Lubiw, J. Lynch, Z. Masárová, M. Rudoy, V. Vassilevska Williams, N. Wein, in:, 30th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ista":"Aichholzer O, Demaine ED, Korman M, Lubiw A, Lynch J, Masárová Z, Rudoy M, Vassilevska Williams V, Wein N. 2022. Hardness of token swapping on trees. 30th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 244, 3.","apa":"Aichholzer, O., Demaine, E. D., Korman, M., Lubiw, A., Lynch, J., Masárová, Z., … Wein, N. (2022). Hardness of token swapping on trees. In <i>30th Annual European Symposium on Algorithms</i> (Vol. 244). Berlin/Potsdam, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2022.3\">https://doi.org/10.4230/LIPIcs.ESA.2022.3</a>","mla":"Aichholzer, Oswin, et al. “Hardness of Token Swapping on Trees.” <i>30th Annual European Symposium on Algorithms</i>, vol. 244, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2022.3\">10.4230/LIPIcs.ESA.2022.3</a>.","ama":"Aichholzer O, Demaine ED, Korman M, et al. Hardness of token swapping on trees. In: <i>30th Annual European Symposium on Algorithms</i>. Vol 244. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2022.3\">10.4230/LIPIcs.ESA.2022.3</a>","chicago":"Aichholzer, Oswin, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. “Hardness of Token Swapping on Trees.” In <i>30th Annual European Symposium on Algorithms</i>, Vol. 244. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2022.3\">https://doi.org/10.4230/LIPIcs.ESA.2022.3</a>.","ieee":"O. Aichholzer <i>et al.</i>, “Hardness of token swapping on trees,” in <i>30th Annual European Symposium on Algorithms</i>, Berlin/Potsdam, Germany, 2022, vol. 244."},"file":[{"file_name":"2022_LIPIcS_Aichholzer.pdf","relation":"main_file","content_type":"application/pdf","file_id":"17420","date_updated":"2024-08-12T08:51:44Z","file_size":1406071,"access_level":"open_access","checksum":"a1fbd3e7baad510fbcb998cf4a7d9f7f","date_created":"2024-08-12T08:51:44Z","success":1,"creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":244,"year":"2022","publication_status":"published","date_updated":"2025-04-15T07:16:56Z","alternative_title":["LIPIcs"],"file_date_updated":"2024-08-12T08:51:44Z","author":[{"full_name":"Aichholzer, Oswin","last_name":"Aichholzer","first_name":"Oswin"},{"last_name":"Demaine","first_name":"Erik D.","full_name":"Demaine, Erik D."},{"first_name":"Matias","last_name":"Korman","full_name":"Korman, Matias"},{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"full_name":"Lynch, Jayson","first_name":"Jayson","last_name":"Lynch"},{"orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová"},{"full_name":"Rudoy, Mikhail","last_name":"Rudoy","first_name":"Mikhail"},{"full_name":"Vassilevska Williams, Virginia","last_name":"Vassilevska Williams","first_name":"Virginia"},{"full_name":"Wein, Nicole","first_name":"Nicole","last_name":"Wein"}],"external_id":{"arxiv":["2103.06707"]},"abstract":[{"text":"Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the tokens at the two endpoints of an edge of the graph. In parallel token swapping, the goal is to use the fewest rounds, each of which consists of one or more swaps on the edges of a matching. We prove that both of these problems remain NP-hard when the graph is restricted to be a tree. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. Previous work establishes NP-completeness on general graphs (for both problems), constant-factor approximation algorithms, and some poly-time exact algorithms for simple graph classes such as cliques, stars, paths, and cycles. Sequential and parallel token swapping on trees were first studied over thirty years ago (as \"sorting with a transposition tree\") and over twenty-five years ago (as \"routing permutations via matchings\"), yet their complexities were previously unknown. We also show limitations on approximation of sequential token swapping on trees: we identify a broad class of algorithms that encompass all three known polynomial-time algorithms that achieve the best known approximation factor (which is 2) and show that no such algorithm can achieve an approximation factor less than 2.","lang":"eng"}],"department":[{"_id":"HeEd"},{"_id":"UlWa"}],"_id":"17084","project":[{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","call_identifier":"FWF","name":"Mathematics, Computer Science"}],"oa_version":"Published Version","oa":1},{"has_accepted_license":"1","status":"public","doi":"10.1112/blms.12449","arxiv":1,"date_created":"2021-01-24T23:01:08Z","acknowledgement":"I wish to thank Imre Bárány for bringing the problem to my attention. I am grateful to Marton Naszódi and Igor Tsiutsiurupa for useful remarks and help with the text.\r\nThe author acknowledges the financial support from the Ministry of Educational and Science of the Russian Federation in the framework of MegaGrant no 075‐15‐2019‐1926.","type":"journal_article","day":"01","title":"No-dimension Tverberg's theorem and its corollaries in Banach spaces of type p","issue":"2","ddc":["510"],"publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]},"scopus_import":"1","publication":"Bulletin of the London Mathematical Society","article_processing_charge":"Yes (via OA deal)","quality_controlled":"1","language":[{"iso":"eng"}],"publisher":"London Mathematical Society","month":"04","intvolume":"        53","tmp":{"short":"CC BY-NC-ND (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","image":"/images/cc_by_nc_nd.png"},"date_published":"2021-04-01T00:00:00Z","citation":{"ama":"Ivanov G. No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p. <i>Bulletin of the London Mathematical Society</i>. 2021;53(2):631-641. doi:<a href=\"https://doi.org/10.1112/blms.12449\">10.1112/blms.12449</a>","ieee":"G. Ivanov, “No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p,” <i>Bulletin of the London Mathematical Society</i>, vol. 53, no. 2. London Mathematical Society, pp. 631–641, 2021.","chicago":"Ivanov, Grigory. “No-Dimension Tverberg’s Theorem and Its Corollaries in Banach Spaces of Type P.” <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society, 2021. <a href=\"https://doi.org/10.1112/blms.12449\">https://doi.org/10.1112/blms.12449</a>.","mla":"Ivanov, Grigory. “No-Dimension Tverberg’s Theorem and Its Corollaries in Banach Spaces of Type P.” <i>Bulletin of the London Mathematical Society</i>, vol. 53, no. 2, London Mathematical Society, 2021, pp. 631–41, doi:<a href=\"https://doi.org/10.1112/blms.12449\">10.1112/blms.12449</a>.","ista":"Ivanov G. 2021. No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p. Bulletin of the London Mathematical Society. 53(2), 631–641.","apa":"Ivanov, G. (2021). No-dimension Tverberg’s theorem and its corollaries in Banach spaces of type p. <i>Bulletin of the London Mathematical Society</i>. London Mathematical Society. <a href=\"https://doi.org/10.1112/blms.12449\">https://doi.org/10.1112/blms.12449</a>","short":"G. Ivanov, Bulletin of the London Mathematical Society 53 (2021) 631–641."},"file":[{"access_level":"open_access","creator":"kschuh","success":1,"date_created":"2021-08-06T09:59:45Z","checksum":"e6ceaa6470d835eb4c211cbdd38fdfd1","file_name":"2021_BLMS_Ivanov.pdf","date_updated":"2021-08-06T09:59:45Z","file_size":194550,"content_type":"application/pdf","file_id":"9796","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"year":"2021","volume":53,"publication_status":"published","date_updated":"2025-07-10T12:01:31Z","file_date_updated":"2021-08-06T09:59:45Z","author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov","first_name":"Grigory"}],"external_id":{"arxiv":["1912.08561"],"isi":["000607265100001"]},"abstract":[{"text":"We continue our study of ‘no‐dimension’ analogues of basic theorems in combinatorial and convex geometry in Banach spaces. We generalize some results of the paper (Adiprasito, Bárány and Mustafa, ‘Theorems of Carathéodory, Helly, and Tverberg without dimension’, Proceedings of the Thirtieth Annual ACM‐SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, San Diego, California, 2019) 2350–2360) and prove no‐dimension versions of the colored Tverberg theorem, the selection lemma and the weak  𝜀 ‐net theorem in Banach spaces of type  𝑝>1 . To prove these results, we use the original ideas of Adiprasito, Bárány and Mustafa for the Euclidean case, our no‐dimension version of the Radon theorem and slightly modified version of the celebrated Maurey lemma.","lang":"eng"}],"department":[{"_id":"UlWa"}],"_id":"9037","oa_version":"Published Version","page":"631-641","article_type":"original","oa":1},{"month":"05","publisher":"Elsevier","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","publication":"Discrete Mathematics","citation":{"ista":"Ivanov G. 2021. On the volume of projections of the cross-polytope. Discrete Mathematics. 344(5), 112312.","apa":"Ivanov, G. (2021). On the volume of projections of the cross-polytope. <i>Discrete Mathematics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.disc.2021.112312\">https://doi.org/10.1016/j.disc.2021.112312</a>","short":"G. Ivanov, Discrete Mathematics 344 (2021).","ama":"Ivanov G. On the volume of projections of the cross-polytope. <i>Discrete Mathematics</i>. 2021;344(5). doi:<a href=\"https://doi.org/10.1016/j.disc.2021.112312\">10.1016/j.disc.2021.112312</a>","chicago":"Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” <i>Discrete Mathematics</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.disc.2021.112312\">https://doi.org/10.1016/j.disc.2021.112312</a>.","ieee":"G. Ivanov, “On the volume of projections of the cross-polytope,” <i>Discrete Mathematics</i>, vol. 344, no. 5. Elsevier, 2021.","mla":"Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” <i>Discrete Mathematics</i>, vol. 344, no. 5, 112312, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.disc.2021.112312\">10.1016/j.disc.2021.112312</a>."},"date_published":"2021-05-01T00:00:00Z","article_number":"112312","intvolume":"       344","type":"journal_article","day":"01","acknowledgement":"Research was supported by the Russian Foundation for Basic Research, project 18-01-00036A (Theorems 1.5 and 5.3) and by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926 (Theorems 1.2 and 7.3).","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1808.09165"}],"arxiv":1,"date_created":"2021-02-07T23:01:12Z","doi":"10.1016/j.disc.2021.112312","status":"public","publication_identifier":{"issn":["0012-365X"]},"scopus_import":"1","issue":"5","title":"On the volume of projections of the cross-polytope","department":[{"_id":"UlWa"}],"abstract":[{"text":"We study properties of the volume of projections of the n-dimensional\r\ncross-polytope $\\crosp^n = \\{ x \\in \\R^n \\mid |x_1| + \\dots + |x_n| \\leqslant 1\\}.$ We prove that the projection of $\\crosp^n$ onto a k-dimensional coordinate subspace has the maximum possible volume for k=2 and for k=3.\r\nWe obtain the exact lower bound on the volume of such a projection onto a two-dimensional plane. Also, we show that there exist local maxima which are not global ones for the volume of a projection of $\\crosp^n$ onto a k-dimensional subspace for any n>k⩾2.","lang":"eng"}],"external_id":{"isi":["000633365200001"],"arxiv":["1808.09165"]},"author":[{"last_name":"Ivanov","first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory"}],"oa":1,"article_type":"original","oa_version":"Preprint","_id":"9098","publication_status":"published","year":"2021","volume":344,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"date_updated":"2025-07-10T12:01:36Z"},{"date_updated":"2025-04-14T07:43:51Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"publication_status":"published","volume":97,"year":"2021","oa_version":"Preprint","_id":"9295","project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020"}],"ec_funded":1,"oa":1,"page":"426-440","article_type":"original","abstract":[{"text":"Hill's Conjecture states that the crossing number  cr(𝐾𝑛)  of the complete graph  𝐾𝑛  in the plane (equivalently, the sphere) is  14⌊𝑛2⌋⌊𝑛−12⌋⌊𝑛−22⌋⌊𝑛−32⌋=𝑛4/64+𝑂(𝑛3) . Moon proved that the expected number of crossings in a spherical drawing in which the points are randomly distributed and joined by geodesics is precisely  𝑛4/64+𝑂(𝑛3) , thus matching asymptotically the conjectured value of  cr(𝐾𝑛) . Let  cr𝑃(𝐺)  denote the crossing number of a graph  𝐺  in the projective plane. Recently, Elkies proved that the expected number of crossings in a naturally defined random projective plane drawing of  𝐾𝑛  is  (𝑛4/8𝜋2)+𝑂(𝑛3) . In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked if  lim𝑛→∞ cr𝑃(𝐾𝑛)/𝑛4=1/8𝜋2 . We construct drawings of  𝐾𝑛  in the projective plane that disprove this.","lang":"eng"}],"author":[{"last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670"},{"full_name":"Mcquillan, Dan","first_name":"Dan","last_name":"Mcquillan"},{"full_name":"Richter, R. Bruce","last_name":"Richter","first_name":"R. Bruce"},{"first_name":"Gelasio","last_name":"Salazar","full_name":"Salazar, Gelasio"},{"full_name":"Sullivan, Matthew","last_name":"Sullivan","first_name":"Matthew"}],"external_id":{"isi":["000631693200001"],"arxiv":["2002.02287"]},"department":[{"_id":"UlWa"}],"title":"Drawings of complete graphs in the projective plane","issue":"3","publication_identifier":{"issn":["0364-9024"],"eissn":["1097-0118"]},"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/2002.02287","open_access":"1"}],"arxiv":1,"date_created":"2021-03-28T22:01:41Z","doi":"10.1002/jgt.22665","status":"public","day":"23","type":"journal_article","acknowledgement":"We thank two reviewers for their corrections and suggestions on the original version of this\r\npaper. This project has received funding from NSERC Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg, Austria.","intvolume":"        97","date_published":"2021-03-23T00:00:00Z","citation":{"chicago":"Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar, and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>.","ieee":"A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan, “Drawings of complete graphs in the projective plane,” <i>Journal of Graph Theory</i>, vol. 97, no. 3. Wiley, pp. 426–440, 2021.","ama":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. 2021;97(3):426-440. doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>","mla":"Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective Plane.” <i>Journal of Graph Theory</i>, vol. 97, no. 3, Wiley, 2021, pp. 426–40, doi:<a href=\"https://doi.org/10.1002/jgt.22665\">10.1002/jgt.22665</a>.","apa":"Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., &#38; Sullivan, M. (2021). Drawings of complete graphs in the projective plane. <i>Journal of Graph Theory</i>. Wiley. <a href=\"https://doi.org/10.1002/jgt.22665\">https://doi.org/10.1002/jgt.22665</a>","ista":"Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440.","short":"A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan, Journal of Graph Theory 97 (2021) 426–440."},"article_processing_charge":"No","quality_controlled":"1","publication":"Journal of Graph Theory","month":"03","language":[{"iso":"eng"}],"publisher":"Wiley"},{"abstract":[{"text":" matching is compatible to two or more labeled point sets of size n with labels   {1,…,n}  if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of n points there exists a compatible matching with   ⌊2n−−√⌋  edges. More generally, for any   ℓ  labeled point sets we construct compatible matchings of size   Ω(n1/ℓ) . As a corresponding upper bound, we use probabilistic arguments to show that for any   ℓ  given sets of n points there exists a labeling of each set such that the largest compatible matching has   O(n2/(ℓ+1))  edges. Finally, we show that   Θ(logn)  copies of any set of n points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.","lang":"eng"}],"author":[{"first_name":"Oswin","last_name":"Aichholzer","full_name":"Aichholzer, Oswin"},{"id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","first_name":"Alan M"},{"orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová"},{"full_name":"Parada, Irene","first_name":"Irene","last_name":"Parada"},{"last_name":"Perz","first_name":"Daniel","full_name":"Perz, Daniel"},{"first_name":"Alexander","last_name":"Pilz","full_name":"Pilz, Alexander"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","last_name":"Tkadlec"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"}],"external_id":{"isi":["001435069600018"],"arxiv":["2101.03928"]},"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"oa_version":"Preprint","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"call_identifier":"FWF","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"},{"grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"call_identifier":"FWF","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory"}],"_id":"9296","ec_funded":1,"oa":1,"page":"221-233","isi":1,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","related_material":{"record":[{"id":"11938","status":"public","relation":"later_version"}]},"publication_status":"published","year":"2021","volume":12635,"date_updated":"2026-04-16T09:18:21Z","alternative_title":["LNCS"],"article_processing_charge":"No","quality_controlled":"1","publication":"15th International Conference on Algorithms and Computation","month":"02","language":[{"iso":"eng"}],"publisher":"Springer Nature","intvolume":"     12635","date_published":"2021-02-16T00:00:00Z","citation":{"short":"O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz, J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and Computation, Springer Nature, 2021, pp. 221–233.","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In <i>15th International Conference on Algorithms and Computation</i> (Vol. 12635, pp. 221–233). Yangon, Myanmar: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>","ista":"Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol. 12635, 221–233.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>15th International Conference on Algorithms and Computation</i>, vol. 12635, Springer Nature, 2021, pp. 221–33, doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>.","chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” In <i>15th International Conference on Algorithms and Computation</i>, 12635:221–33. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">https://doi.org/10.1007/978-3-030-68211-8_18</a>.","ieee":"O. Aichholzer <i>et al.</i>, “On compatible matchings,” in <i>15th International Conference on Algorithms and Computation</i>, Yangon, Myanmar, 2021, vol. 12635, pp. 221–233.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. In: <i>15th International Conference on Algorithms and Computation</i>. Vol 12635. Springer Nature; 2021:221-233. doi:<a href=\"https://doi.org/10.1007/978-3-030-68211-8_18\">10.1007/978-3-030-68211-8_18</a>"},"conference":{"location":"Yangon, Myanmar","start_date":"2021-02-28","name":"WALCOM: Algorithms and Computation","end_date":"2021-03-02"},"doi":"10.1007/978-3-030-68211-8_18","arxiv":1,"date_created":"2021-03-28T22:01:41Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2101.03928"}],"status":"public","type":"conference","day":"16","acknowledgement":"A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411. Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23 (RiSE).","title":"On compatible matchings","publication_identifier":{"eisbn":["9783030682118"],"isbn":["9783030682101"],"eissn":["1611-3349"],"issn":["0302-9743"]},"scopus_import":"1"},{"title":"Eliminating higher-multiplicity intersections. III. Codimension 2","scopus_import":"1","publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"corr_author":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"doi":"10.1007/s11856-021-2216-z","arxiv":1,"date_created":"2021-11-07T23:01:24Z","status":"public","day":"30","type":"journal_article","acknowledgement":"Research supported by the Swiss National Science Foundation (Project SNSF-PP00P2-138948), by the Austrian Science Fund (FWF Project P31312-N35), by the Russian Foundation for Basic Research (Grants No. 15-01-06302 and 19-01-00169), by a Simons-IUM Fellowship, and by the D. Zimin Dynasty Foundation Grant. We would like to thank E. Alkin, A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner and anonymous referees for helpful comments and discussions.","intvolume":"       245","citation":{"mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” <i>Israel Journal of Mathematics</i>, vol. 245, Springer Nature, 2021, pp. 501–534, doi:<a href=\"https://doi.org/10.1007/s11856-021-2216-z\">10.1007/s11856-021-2216-z</a>.","ama":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. Eliminating higher-multiplicity intersections. III. Codimension 2. <i>Israel Journal of Mathematics</i>. 2021;245:501–534. doi:<a href=\"https://doi.org/10.1007/s11856-021-2216-z\">10.1007/s11856-021-2216-z</a>","chicago":"Avvakumov, Sergey, Isaac Mabillard, Arkadiy B. Skopenkov, and Uli Wagner. “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s11856-021-2216-z\">https://doi.org/10.1007/s11856-021-2216-z</a>.","ieee":"S. Avvakumov, I. Mabillard, A. B. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity intersections. III. Codimension 2,” <i>Israel Journal of Mathematics</i>, vol. 245. Springer Nature, pp. 501–534, 2021.","short":"S. Avvakumov, I. Mabillard, A.B. Skopenkov, U. Wagner, Israel Journal of Mathematics 245 (2021) 501–534.","ista":"Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. 2021. Eliminating higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics. 245, 501–534.","apa":"Avvakumov, S., Mabillard, I., Skopenkov, A. B., &#38; Wagner, U. (2021). Eliminating higher-multiplicity intersections. III. Codimension 2. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11856-021-2216-z\">https://doi.org/10.1007/s11856-021-2216-z</a>"},"date_published":"2021-10-30T00:00:00Z","quality_controlled":"1","article_processing_charge":"No","publication":"Israel Journal of Mathematics","month":"10","publisher":"Springer Nature","language":[{"iso":"eng"}],"date_updated":"2025-07-02T10:54:52Z","isi":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","related_material":{"record":[{"id":"9308","status":"public","relation":"earlier_version"},{"id":"8183","status":"public","relation":"earlier_version"}]},"publication_status":"published","volume":245,"year":"2021","oa_version":"Preprint","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312","call_identifier":"FWF"}],"_id":"10220","oa":1,"page":"501–534 ","article_type":"original","abstract":[{"text":"We study conditions under which a finite simplicial complex K can be mapped to ℝd without higher-multiplicity intersections. An almost r-embedding is a map f: K → ℝd such that the images of any r pairwise disjoint simplices of K do not have a common point. We show that if r is not a prime power and d ≥ 2r + 1, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost r-embedding of the (d +1)(r − 1)-simplex in ℝd. This improves on previous constructions of counterexamples (for d ≥ 3r) based on a series of papers by M. Özaydin, M. Gromov, P. Blagojević, F. Frick, G. Ziegler, and the second and fourth present authors.\r\n\r\nThe counterexamples are obtained by proving the following algebraic criterion in codimension 2: If r ≥ 3 and if K is a finite 2(r − 1)-complex, then there exists an almost r-embedding K → ℝ2r if and only if there exists a general position PL map f: K → ℝ2r such that the algebraic intersection number of the f-images of any r pairwise disjoint simplices of K is zero. This result can be restated in terms of a cohomological obstruction and extends an analogous codimension 3 criterion by the second and fourth authors. As another application, we classify ornaments f: S3 ⊔ S3 ⊔ S3 → ℝ5 up to ornament concordance.\r\n\r\nIt follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for r = 2 is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample.","lang":"eng"}],"external_id":{"isi":["000712942100013"],"arxiv":["1511.03501"]},"author":[{"first_name":"Sergey","last_name":"Avvakumov","orcid":"0000-0002-7840-5062","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Mabillard","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac"},{"first_name":"Arkadiy B.","last_name":"Skopenkov","full_name":"Skopenkov, Arkadiy B."},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli"}],"department":[{"_id":"UlWa"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"publication_status":"published","year":"2021","volume":35,"date_updated":"2025-04-14T07:43:46Z","abstract":[{"text":"Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical” drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $\\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no three on a great circle---and the edges of $G$ are shortest-arcs in $\\mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $\\gamma_e$ such that the only vertices in $\\gamma_e$ are the ends of $e$; (2) if $e\\ne f$, then $\\gamma_e\\cap\\gamma_f$ has precisely two crossings; and (3) if $e\\ne f$, then $e$ intersects $\\gamma_f$ at most once, in either a crossing or an end of $e$. We use properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that for the complete graph, properties (1)--(3) are equivalent to the same three properties but with “precisely two crossings” in (2) replaced by “at most two crossings.” The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs (coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.\r\n","lang":"eng"}],"external_id":{"isi":["000674142200022"],"arxiv":["2001.06053"]},"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":"R. Bruce","last_name":"Richter","full_name":"Richter, R. Bruce"},{"full_name":"Sunohara, Matthew","last_name":"Sunohara","first_name":"Matthew"}],"department":[{"_id":"UlWa"}],"oa_version":"Preprint","_id":"9468","project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"ec_funded":1,"oa":1,"page":"1050-1076","article_type":"original","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2001.06053"}],"doi":"10.1137/20M1313234","date_created":"2021-06-06T22:01:30Z","arxiv":1,"status":"public","day":"20","type":"journal_article","issue":"2","title":"Extending drawings of complete graphs into arrangements of pseudocircles","scopus_import":"1","publication_identifier":{"issn":["0895-4801"]},"quality_controlled":"1","article_processing_charge":"No","publication":"SIAM Journal on Discrete Mathematics","month":"05","publisher":"Society for Industrial and Applied Mathematics","language":[{"iso":"eng"}],"intvolume":"        35","citation":{"ista":"Arroyo Guevara AM, Richter RB, Sunohara M. 2021. Extending drawings of complete graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics. 35(2), 1050–1076.","apa":"Arroyo Guevara, A. M., Richter, R. B., &#38; Sunohara, M. (2021). Extending drawings of complete graphs into arrangements of pseudocircles. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20M1313234\">https://doi.org/10.1137/20M1313234</a>","short":"A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete Mathematics 35 (2021) 1050–1076.","ama":"Arroyo Guevara AM, Richter RB, Sunohara M. Extending drawings of complete graphs into arrangements of pseudocircles. <i>SIAM Journal on Discrete Mathematics</i>. 2021;35(2):1050-1076. doi:<a href=\"https://doi.org/10.1137/20M1313234\">10.1137/20M1313234</a>","ieee":"A. M. Arroyo Guevara, R. B. Richter, and M. Sunohara, “Extending drawings of complete graphs into arrangements of pseudocircles,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 35, no. 2. Society for Industrial and Applied Mathematics, pp. 1050–1076, 2021.","chicago":"Arroyo Guevara, Alan M, R. Bruce Richter, and Matthew Sunohara. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/20M1313234\">https://doi.org/10.1137/20M1313234</a>.","mla":"Arroyo Guevara, Alan M., et al. “Extending Drawings of Complete Graphs into Arrangements of Pseudocircles.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 35, no. 2, Society for Industrial and Applied Mathematics, 2021, pp. 1050–76, doi:<a href=\"https://doi.org/10.1137/20M1313234\">10.1137/20M1313234</a>."},"date_published":"2021-05-20T00:00:00Z"},{"department":[{"_id":"UlWa"}],"external_id":{"isi":["000656507500001"],"arxiv":["2008.09543"]},"author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov","first_name":"Grigory"},{"full_name":"Tsiutsiurupa, Igor","last_name":"Tsiutsiurupa","first_name":"Igor"}],"abstract":[{"text":"We extend the notion of the minimal volume ellipsoid containing a convex body in Rd to the setting of logarithmically concave functions. We consider a vast class of logarithmically concave functions whose superlevel sets are concentric ellipsoids. For a fixed function from this class, we consider the set of all its “affine” positions. For any log-concave function f on Rd, we consider functions belonging to this set of “affine” positions, and find the one with the minimal integral under the condition that it is pointwise greater than or equal to f. We study the properties of existence and uniqueness of the solution to this problem. For any s∈[0,+∞), we consider the construction dual to the recently defined John s-function (Ivanov and Naszódi in Functional John ellipsoids. arXiv preprint: arXiv:2006.09934, 2020). We prove that such a construction determines a unique function and call it the Löwner s-function of f. We study the Löwner s-functions as s tends to zero and to infinity. Finally, extending the notion of the outer volume ratio, we define the outer integral ratio of a log-concave function and give an asymptotically tight bound on it.","lang":"eng"}],"article_type":"original","page":"11493-11528","oa":1,"_id":"9548","oa_version":"Preprint","year":"2021","volume":31,"publication_status":"published","isi":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2023-08-08T14:04:49Z","publisher":"Springer","language":[{"iso":"eng"}],"month":"05","publication":"Journal of Geometric Analysis","quality_controlled":"1","article_processing_charge":"No","citation":{"short":"G. Ivanov, I. Tsiutsiurupa, Journal of Geometric Analysis 31 (2021) 11493–11528.","ista":"Ivanov G, Tsiutsiurupa I. 2021. Functional Löwner ellipsoids. Journal of Geometric Analysis. 31, 11493–11528.","apa":"Ivanov, G., &#38; Tsiutsiurupa, I. (2021). Functional Löwner ellipsoids. <i>Journal of Geometric Analysis</i>. Springer. <a href=\"https://doi.org/10.1007/s12220-021-00691-4\">https://doi.org/10.1007/s12220-021-00691-4</a>","mla":"Ivanov, Grigory, and Igor Tsiutsiurupa. “Functional Löwner Ellipsoids.” <i>Journal of Geometric Analysis</i>, vol. 31, Springer, 2021, pp. 11493–528, doi:<a href=\"https://doi.org/10.1007/s12220-021-00691-4\">10.1007/s12220-021-00691-4</a>.","ama":"Ivanov G, Tsiutsiurupa I. Functional Löwner ellipsoids. <i>Journal of Geometric Analysis</i>. 2021;31:11493-11528. doi:<a href=\"https://doi.org/10.1007/s12220-021-00691-4\">10.1007/s12220-021-00691-4</a>","chicago":"Ivanov, Grigory, and Igor Tsiutsiurupa. “Functional Löwner Ellipsoids.” <i>Journal of Geometric Analysis</i>. Springer, 2021. <a href=\"https://doi.org/10.1007/s12220-021-00691-4\">https://doi.org/10.1007/s12220-021-00691-4</a>.","ieee":"G. Ivanov and I. Tsiutsiurupa, “Functional Löwner ellipsoids,” <i>Journal of Geometric Analysis</i>, vol. 31. Springer, pp. 11493–11528, 2021."},"date_published":"2021-05-31T00:00:00Z","intvolume":"        31","acknowledgement":"The authors acknowledge the support of the grant of the Russian Government N 075-15-2019-1926.","type":"journal_article","day":"31","status":"public","date_created":"2021-06-13T22:01:32Z","arxiv":1,"doi":"10.1007/s12220-021-00691-4","main_file_link":[{"url":"https://arxiv.org/abs/2008.09543","open_access":"1"}],"publication_identifier":{"eissn":["1559-002X"],"issn":["1050-6926"]},"scopus_import":"1","title":"Functional Löwner ellipsoids"},{"language":[{"iso":"eng"}],"publisher":"De Gruyter","month":"01","publication":"Analysis and Geometry in Metric Spaces","article_processing_charge":"No","quality_controlled":"1","date_published":"2021-01-29T00:00:00Z","citation":{"short":"G. Ivanov, I. Tsiutsiurupa, Analysis and Geometry in Metric Spaces 9 (2021) 1–18.","ista":"Ivanov G, Tsiutsiurupa I. 2021. On the volume of sections of the cube. Analysis and Geometry in Metric Spaces. 9(1), 1–18.","apa":"Ivanov, G., &#38; Tsiutsiurupa, I. (2021). On the volume of sections of the cube. <i>Analysis and Geometry in Metric Spaces</i>. De Gruyter. <a href=\"https://doi.org/10.1515/agms-2020-0103\">https://doi.org/10.1515/agms-2020-0103</a>","mla":"Ivanov, Grigory, and Igor Tsiutsiurupa. “On the Volume of Sections of the Cube.” <i>Analysis and Geometry in Metric Spaces</i>, vol. 9, no. 1, De Gruyter, 2021, pp. 1–18, doi:<a href=\"https://doi.org/10.1515/agms-2020-0103\">10.1515/agms-2020-0103</a>.","ama":"Ivanov G, Tsiutsiurupa I. On the volume of sections of the cube. <i>Analysis and Geometry in Metric Spaces</i>. 2021;9(1):1-18. doi:<a href=\"https://doi.org/10.1515/agms-2020-0103\">10.1515/agms-2020-0103</a>","chicago":"Ivanov, Grigory, and Igor Tsiutsiurupa. “On the Volume of Sections of the Cube.” <i>Analysis and Geometry in Metric Spaces</i>. De Gruyter, 2021. <a href=\"https://doi.org/10.1515/agms-2020-0103\">https://doi.org/10.1515/agms-2020-0103</a>.","ieee":"G. Ivanov and I. Tsiutsiurupa, “On the volume of sections of the cube,” <i>Analysis and Geometry in Metric Spaces</i>, vol. 9, no. 1. De Gruyter, pp. 1–18, 2021."},"intvolume":"         9","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"acknowledgement":"The authors acknowledge the support of the grant of the Russian Government N 075-15-\r\n2019-1926. G.I.was supported also by the SwissNational Science Foundation grant 200021-179133. The authors are very grateful to the anonymous reviewer for valuable remarks.","type":"journal_article","day":"29","has_accepted_license":"1","status":"public","date_created":"2022-03-18T09:25:14Z","arxiv":1,"doi":"10.1515/agms-2020-0103","ddc":["510"],"scopus_import":"1","publication_identifier":{"issn":["2299-3274"]},"issue":"1","title":"On the volume of sections of the cube","department":[{"_id":"UlWa"}],"author":[{"full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","last_name":"Ivanov"},{"full_name":"Tsiutsiurupa, Igor","first_name":"Igor","last_name":"Tsiutsiurupa"}],"external_id":{"arxiv":["2004.02674"],"isi":["000734286800001"]},"abstract":[{"text":"We study the properties of the maximal volume k-dimensional sections of the n-dimensional cube [−1, 1]n. We obtain a first order necessary condition for a k-dimensional subspace to be a local maximizer of the volume of such sections, which we formulate in a geometric way. We estimate the length of the projection of a vector of the standard basis of Rn onto a k-dimensional subspace that maximizes the volume of the intersection. We \u001cnd the optimal upper bound on the volume of a planar section of the cube [−1, 1]n , n ≥ 2.","lang":"eng"}],"article_type":"original","page":"1-18","oa":1,"_id":"10856","oa_version":"Published Version","year":"2021","volume":9,"publication_status":"published","file":[{"file_name":"2021_AnalysisMetricSpaces_Ivanov.pdf","date_updated":"2022-03-18T09:31:59Z","file_size":789801,"content_type":"application/pdf","file_id":"10857","relation":"main_file","access_level":"open_access","creator":"dernst","success":1,"date_created":"2022-03-18T09:31:59Z","checksum":"7e615ac8489f5eae580b6517debfdc53"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"file_date_updated":"2022-03-18T09:31:59Z","date_updated":"2023-08-17T07:07:58Z","keyword":["Applied Mathematics","Geometry and Topology","Analysis"]},{"oa_version":"Preprint","_id":"10860","oa":1,"page":"942-963","article_type":"original","abstract":[{"lang":"eng","text":"A tight frame is the orthogonal projection of some orthonormal basis of Rn onto Rk. We show that a set of vectors is a tight frame if and only if the set of all cross products of these vectors is a tight frame. We reformulate a range of problems on the volume of projections (or sections) of regular polytopes in terms of tight frames and write a first-order necessary condition for local extrema of these problems. As applications, we prove new results for the problem of maximization of the volume of zonotopes."}],"author":[{"first_name":"Grigory","last_name":"Ivanov","full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E"}],"external_id":{"arxiv":["1804.10055"],"isi":["000730165300021"]},"department":[{"_id":"UlWa"}],"keyword":["General Mathematics","Tight frame","Grassmannian","zonotope"],"date_updated":"2024-10-09T21:01:50Z","isi":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","year":"2021","volume":64,"intvolume":"        64","date_published":"2021-12-18T00:00:00Z","citation":{"ista":"Ivanov G. 2021. Tight frames and related geometric problems. Canadian Mathematical Bulletin. 64(4), 942–963.","apa":"Ivanov, G. (2021). Tight frames and related geometric problems. <i>Canadian Mathematical Bulletin</i>. Canadian Mathematical Society. <a href=\"https://doi.org/10.4153/s000843952000096x\">https://doi.org/10.4153/s000843952000096x</a>","short":"G. Ivanov, Canadian Mathematical Bulletin 64 (2021) 942–963.","ama":"Ivanov G. Tight frames and related geometric problems. <i>Canadian Mathematical Bulletin</i>. 2021;64(4):942-963. doi:<a href=\"https://doi.org/10.4153/s000843952000096x\">10.4153/s000843952000096x</a>","ieee":"G. Ivanov, “Tight frames and related geometric problems,” <i>Canadian Mathematical Bulletin</i>, vol. 64, no. 4. Canadian Mathematical Society, pp. 942–963, 2021.","chicago":"Ivanov, Grigory. “Tight Frames and Related Geometric Problems.” <i>Canadian Mathematical Bulletin</i>. Canadian Mathematical Society, 2021. <a href=\"https://doi.org/10.4153/s000843952000096x\">https://doi.org/10.4153/s000843952000096x</a>.","mla":"Ivanov, Grigory. “Tight Frames and Related Geometric Problems.” <i>Canadian Mathematical Bulletin</i>, vol. 64, no. 4, Canadian Mathematical Society, 2021, pp. 942–63, doi:<a href=\"https://doi.org/10.4153/s000843952000096x\">10.4153/s000843952000096x</a>."},"article_processing_charge":"No","quality_controlled":"1","publication":"Canadian Mathematical Bulletin","month":"12","language":[{"iso":"eng"}],"publisher":"Canadian Mathematical Society","issue":"4","title":"Tight frames and related geometric problems","corr_author":"1","publication_identifier":{"eissn":["1496-4287"],"issn":["0008-4395"]},"scopus_import":"1","doi":"10.4153/s000843952000096x","main_file_link":[{"url":"https://arxiv.org/abs/1804.10055","open_access":"1"}],"date_created":"2022-03-18T09:55:59Z","arxiv":1,"status":"public","day":"18","type":"journal_article","acknowledgement":"The author was supported by the Swiss National Science Foundation grant 200021_179133. The author acknowledges the financial support from the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926."},{"department":[{"_id":"UlWa"}],"author":[{"first_name":"Alan M","last_name":"Arroyo Guevara","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klute, Fabian","first_name":"Fabian","last_name":"Klute"},{"last_name":"Parada","first_name":"Irene","full_name":"Parada, Irene"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"full_name":"Vogtenhuber, Birgit","first_name":"Birgit","last_name":"Vogtenhuber"},{"full_name":"Wiedera, Tilo","first_name":"Tilo","last_name":"Wiedera"}],"external_id":{"isi":["001299688100026"]},"abstract":[{"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.","lang":"eng"}],"page":"325-338","ec_funded":1,"_id":"8732","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"oa_version":"None","year":"2020","volume":12301,"publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","isi":1,"alternative_title":["LNCS"],"date_updated":"2026-04-16T10:22:35Z","language":[{"iso":"eng"}],"publisher":"Springer Nature","month":"10","publication":"Graph-Theoretic Concepts in Computer Science","article_processing_charge":"No","quality_controlled":"1","conference":{"name":"WG: Workshop on Graph-Theoretic Concepts in Computer Science","end_date":"2020-06-26","location":"Leeds, United Kingdom","start_date":"2020-06-24"},"date_published":"2020-10-09T00:00:00Z","citation":{"apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B., &#38; Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In <i>Graph-Theoretic Concepts in Computer Science</i> (Vol. 12301, pp. 325–338). Leeds, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">https://doi.org/10.1007/978-3-030-60440-0_26</a>","ista":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. 2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science, LNCS, vol. 12301, 325–338.","short":"A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera, in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp. 325–338.","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” In <i>Graph-Theoretic Concepts in Computer Science</i>, 12301:325–38. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">https://doi.org/10.1007/978-3-030-60440-0_26</a>.","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” in <i>Graph-Theoretic Concepts in Computer Science</i>, Leeds, United Kingdom, 2020, vol. 12301, pp. 325–338.","ama":"Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T. Inserting one edge into a simple drawing is hard. In: <i>Graph-Theoretic Concepts in Computer Science</i>. Vol 12301. Springer Nature; 2020:325-338. doi:<a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">10.1007/978-3-030-60440-0_26</a>","mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” <i>Graph-Theoretic Concepts in Computer Science</i>, vol. 12301, Springer Nature, 2020, pp. 325–38, doi:<a href=\"https://doi.org/10.1007/978-3-030-60440-0_26\">10.1007/978-3-030-60440-0_26</a>."},"intvolume":"     12301","type":"conference","day":"09","status":"public","doi":"10.1007/978-3-030-60440-0_26","date_created":"2020-11-06T08:45:03Z","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030604394"],"eissn":["1611-3349"],"eisbn":["9783030604400"]},"scopus_import":"1","title":"Inserting one edge into a simple drawing is hard"},{"date_updated":"2025-07-02T10:54:51Z","publication_status":"published","year":"2020","volume":75,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"related_material":{"record":[{"id":"10220","status":"public","relation":"later_version"},{"relation":"earlier_version","status":"public","id":"8183"}]},"oa":1,"page":"1156-1158","article_type":"original","oa_version":"Preprint","_id":"9308","department":[{"_id":"UlWa"}],"external_id":{"arxiv":["1511.03501"],"isi":["000625983100001"]},"author":[{"orcid":"0000-0002-7840-5062","full_name":"Avvakumov, Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov"},{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mabillard, Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","first_name":"Isaac","last_name":"Mabillard"},{"last_name":"Skopenkov","first_name":"A. B.","full_name":"Skopenkov, A. B."}],"scopus_import":"1","publication_identifier":{"issn":["0036-0279"]},"issue":"6","title":"Eliminating higher-multiplicity intersections, III. Codimension 2","day":"01","type":"journal_article","acknowledgement":"This research was carried out with the support of the Russian Foundation for Basic Research(grant no. 19-01-00169)","doi":"10.1070/RM9943","date_created":"2021-04-04T22:01:22Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1511.03501"}],"arxiv":1,"status":"public","citation":{"mla":"Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6, IOP Publishing, 2020, pp. 1156–58, doi:<a href=\"https://doi.org/10.1070/RM9943\">10.1070/RM9943</a>.","ieee":"S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity intersections, III. Codimension 2,” <i>Russian Mathematical Surveys</i>, vol. 75, no. 6. IOP Publishing, pp. 1156–1158, 2020.","chicago":"Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating Higher-Multiplicity Intersections, III. Codimension 2.” <i>Russian Mathematical Surveys</i>. IOP Publishing, 2020. <a href=\"https://doi.org/10.1070/RM9943\">https://doi.org/10.1070/RM9943</a>.","ama":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. 2020;75(6):1156-1158. doi:<a href=\"https://doi.org/10.1070/RM9943\">10.1070/RM9943</a>","short":"S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical Surveys 75 (2020) 1156–1158.","ista":"Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.","apa":"Avvakumov, S., Wagner, U., Mabillard, I., &#38; Skopenkov, A. B. (2020). Eliminating higher-multiplicity intersections, III. Codimension 2. <i>Russian Mathematical Surveys</i>. IOP Publishing. <a href=\"https://doi.org/10.1070/RM9943\">https://doi.org/10.1070/RM9943</a>"},"date_published":"2020-12-01T00:00:00Z","intvolume":"        75","month":"12","publisher":"IOP Publishing","language":[{"iso":"eng"}],"quality_controlled":"1","article_processing_charge":"No","publication":"Russian Mathematical Surveys"},{"publication_identifier":{"isbn":["9781611975994"]},"scopus_import":"1","ddc":["500"],"title":"Embeddability of simplicial complexes is undecidable","type":"conference","day":"01","status":"public","date_created":"2020-05-10T22:00:48Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.47"}],"doi":"10.1137/1.9781611975994.47","conference":{"start_date":"2020-01-05","location":"Salt Lake City, UT, United States","end_date":"2020-01-08","name":"SODA: Symposium on Discrete Algorithms"},"citation":{"ama":"Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes is undecidable. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:767-785. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>","chicago":"Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of Simplicial Complexes Is Undecidable.” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:767–85. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>.","ieee":"M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial complexes is undecidable,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 767–785.","mla":"Filakovský, Marek, et al. “Embeddability of Simplicial Complexes Is Undecidable.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 767–85, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.47\">10.1137/1.9781611975994.47</a>.","ista":"Filakovský M, Wagner U, Zhechev SY. 2020. Embeddability of simplicial complexes is undecidable. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 767–785.","apa":"Filakovský, M., Wagner, U., &#38; Zhechev, S. Y. (2020). Embeddability of simplicial complexes is undecidable. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 767–785). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.47\">https://doi.org/10.1137/1.9781611975994.47</a>","short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785."},"date_published":"2020-01-01T00:00:00Z","publisher":"SIAM","language":[{"iso":"eng"}],"month":"01","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","quality_controlled":"1","article_processing_charge":"No","date_updated":"2026-06-18T19:27:16Z","volume":"2020-January","year":"2020","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"767-785","oa":1,"_id":"7806","project":[{"call_identifier":"FWF","grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"}],"oa_version":"Published Version","department":[{"_id":"UlWa"}],"author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","full_name":"Filakovský, Marek","last_name":"Filakovský","first_name":"Marek"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli"},{"id":"3AA52972-F248-11E8-B48F-1D18A9856A87","full_name":"Zhechev, Stephan Y","last_name":"Zhechev","first_name":"Stephan Y"}],"abstract":[{"lang":"eng","text":"We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.\r\nOur result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4."}]},{"status":"public","arxiv":1,"doi":"10.1137/1.9781611975994.172","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611975994.172"}],"date_created":"2020-05-10T22:00:48Z","type":"conference","day":"01","title":"Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)","publication_identifier":{"isbn":["9781611975994"]},"scopus_import":1,"publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","quality_controlled":"1","article_processing_charge":"No","publisher":"SIAM","language":[{"iso":"eng"}],"month":"01","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2020-01-08","start_date":"2020-01-05","location":"Salt Lake City, UT, United States"},"citation":{"short":"U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2823–2841.","apa":"Wagner, U., &#38; Welzl, E. (2020). Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2020–January, pp. 2823–2841). Salt Lake City, UT, United States: SIAM. <a href=\"https://doi.org/10.1137/1.9781611975994.172\">https://doi.org/10.1137/1.9781611975994.172</a>","ista":"Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:<a href=\"https://doi.org/10.1137/1.9781611975994.172\">10.1137/1.9781611975994.172</a>.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane (Part I: Edge flips). In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2020-January. SIAM; 2020:2823-2841. doi:<a href=\"https://doi.org/10.1137/1.9781611975994.172\">10.1137/1.9781611975994.172</a>","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane (Part I: Edge Flips).” In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2020–January:2823–41. SIAM, 2020. <a href=\"https://doi.org/10.1137/1.9781611975994.172\">https://doi.org/10.1137/1.9781611975994.172</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane (Part I: Edge flips),” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Salt Lake City, UT, United States, 2020, vol. 2020–January, pp. 2823–2841."},"date_published":"2020-01-01T00:00:00Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"12129"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2020","volume":"2020-January","publication_status":"published","date_updated":"2024-10-09T21:03:33Z","external_id":{"arxiv":["2003.13557"]},"author":[{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"abstract":[{"text":"In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part.","lang":"eng"}],"department":[{"_id":"UlWa"}],"_id":"7807","oa_version":"Submitted Version","page":"2823-2841","oa":1},{"degree_awarded":"PhD","file_date_updated":"2020-07-14T12:48:05Z","supervisor":[{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"}],"alternative_title":["ISTA Thesis"],"keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"date_updated":"2026-04-08T07:23:01Z","publication_status":"published","year":"2020","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"7950"},{"id":"5986","status":"public","relation":"part_of_dissertation"}]},"file":[{"file_name":"THESIS_Zuzka_Masarova.pdf","content_type":"application/pdf","file_id":"7945","relation":"main_file","file_size":13661779,"date_updated":"2020-07-14T12:48:05Z","access_level":"open_access","date_created":"2020-06-08T00:34:00Z","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","creator":"zmasarov"},{"file_id":"7946","content_type":"application/zip","relation":"source_file","file_size":32184006,"date_updated":"2020-07-14T12:48:05Z","file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","date_created":"2020-06-08T00:35:30Z","checksum":"45341a35b8f5529c74010b7af43ac188","creator":"zmasarov","access_level":"closed"}],"oa":1,"page":"160","oa_version":"Published Version","_id":"7944","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"abstract":[{"text":"This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars.","lang":"eng"}],"author":[{"orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová"}],"publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-005-3"]},"corr_author":"1","ddc":["516","514"],"title":"Reconfiguration problems","type":"dissertation","day":"09","date_created":"2020-06-08T00:49:46Z","doi":"10.15479/AT:ISTA:7944","has_accepted_license":"1","status":"public","citation":{"apa":"Masárová, Z. (2020). <i>Reconfiguration problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>","ista":"Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.","short":"Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.","ama":"Masárová Z. Reconfiguration problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>","ieee":"Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.","chicago":"Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>.","mla":"Masárová, Zuzana. <i>Reconfiguration Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>."},"date_published":"2020-06-09T00:00:00Z","tmp":{"name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","image":"/images/cc_by_sa.png","short":"CC BY-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode"},"month":"06","license":"https://creativecommons.org/licenses/by-sa/4.0/","OA_place":"publisher","publisher":"Institute of Science and Technology Austria","language":[{"iso":"eng"}],"article_processing_charge":"No"}]