[{"department":[{"_id":"UlWa"},{"_id":"HeEd"}],"date_updated":"2024-01-29T09:45:06Z","type":"conference","conference":{"name":"GD: Graph Drawing and Network Visualization","start_date":"2023-09-20","location":"Isola delle Femmine, Palermo, Italy","end_date":"2023-09-22"},"status":"public","_id":"14888","volume":14466,"publication_identifier":{"issn":["0302-9743"],"isbn":["9783031492747"],"eissn":["1611-3349"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2202.12175"}],"month":"01","intvolume":" 14466","abstract":[{"text":"A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inserting a single additional curve. This turns out to be NP-hard; however, it becomes tractable when the number of popular faces is small: We present a probabilistic FPT-approach in the number of popular faces.","lang":"eng"}],"oa_version":"Preprint","author":[{"first_name":"Phoebe","last_name":"De Nooijer","full_name":"De Nooijer, Phoebe"},{"last_name":"Terziadis","full_name":"Terziadis, Soeren","first_name":"Soeren"},{"first_name":"Alexandra","last_name":"Weinberger","full_name":"Weinberger, Alexandra"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","first_name":"Zuzana","last_name":"Masárová","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana"},{"full_name":"Mchedlidze, Tamara","last_name":"Mchedlidze","first_name":"Tamara"},{"first_name":"Maarten","full_name":"Löffler, Maarten","last_name":"Löffler"},{"first_name":"Günter","full_name":"Rote, Günter","last_name":"Rote"}],"external_id":{"arxiv":["2202.12175"]},"article_processing_charge":"No","title":"Removing popular faces in curve arrangements","citation":{"chicago":"De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová, Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve Arrangements.” In 31st International Symposium on Graph Drawing and Network Visualization, 14466:18–33. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49275-4_2.","ista":"De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LNCS, vol. 14466, 18–33.","mla":"De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.” 31st International Symposium on Graph Drawing and Network Visualization, vol. 14466, Springer Nature, 2024, pp. 18–33, doi:10.1007/978-3-031-49275-4_2.","short":"P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M. Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2024, pp. 18–33.","ieee":"P. De Nooijer et al., “Removing popular faces in curve arrangements,” in 31st International Symposium on Graph Drawing and Network Visualization, Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.","ama":"De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve arrangements. In: 31st International Symposium on Graph Drawing and Network Visualization. Vol 14466. Springer Nature; 2024:18-33. doi:10.1007/978-3-031-49275-4_2","apa":"De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T., Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements. In 31st International Symposium on Graph Drawing and Network Visualization (Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-49275-4_2"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"18-33","doi":"10.1007/978-3-031-49275-4_2","date_published":"2024-01-06T00:00:00Z","date_created":"2024-01-28T23:01:43Z","year":"2024","day":"06","publication":"31st International Symposium on Graph Drawing and Network Visualization","publisher":"Springer Nature","quality_controlled":"1","oa":1,"acknowledgement":"This work was initiated at the 16th European Research Week on Geometric Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF): W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035]. A preliminary version of this work has been presented at the 38th European Workshop on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper, which includes appendices but is otherwise identical, is available as a technical report [10]."},{"ddc":["510"],"date_updated":"2024-03-25T07:45:54Z","department":[{"_id":"UlWa"}],"file_date_updated":"2024-03-25T07:44:30Z","_id":"15168","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2024-03-12","location":"Clermont-Ferrand, France","end_date":"2024-03-14"},"type":"conference","language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"0524d4189fd1ed08989546511343edf3","file_id":"15175","success":1,"creator":"dernst","date_updated":"2024-03-25T07:44:30Z","file_size":927290,"date_created":"2024-03-25T07:44:30Z","file_name":"2024_LIPICs_Filakovsky.pdf"}],"publication_status":"published","publication_identifier":{"isbn":["9783959773119"],"eissn":["1868-8969"]},"license":"https://creativecommons.org/licenses/by/4.0/","ec_funded":1,"volume":289,"oa_version":"Published Version","abstract":[{"text":"A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the \"linearly ordered chromatic number\" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).","lang":"eng"}],"intvolume":" 289","month":"03","alternative_title":["LIPIcs"],"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” 41st International Symposium on Theoretical Aspects of Computer Science, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.STACS.2024.34.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2024.34","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: 41st International Symposium on Theoretical Aspects of Computer Science. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.STACS.2024.34","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in 41st International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand, France, 2024, vol. 289.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In 41st International Symposium on Theoretical Aspects of Computer Science, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.STACS.2024.34.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34."},"title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","article_processing_charge":"No","external_id":{"arxiv":["2312.12981"]},"author":[{"first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský","full_name":"Filakovský, Marek"},{"full_name":"Nakajima, Tamio Vesa","last_name":"Nakajima","first_name":"Tamio Vesa"},{"id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub","last_name":"Opršal","orcid":"0000-0003-1245-3456","full_name":"Opršal, Jakub"},{"first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","full_name":"Tasinato, Gianluca","last_name":"Tasinato"},{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"article_number":"34","project":[{"call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312"},{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"publication":"41st International Symposium on Theoretical Aspects of Computer Science","day":"01","year":"2024","has_accepted_license":"1","date_created":"2024-03-24T23:00:59Z","doi":"10.4230/LIPIcs.STACS.2024.34","date_published":"2024-03-01T00:00:00Z","acknowledgement":"Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35).","oa":1,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"oa_version":"Preprint","abstract":[{"lang":"eng","text":"he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems."}],"intvolume":" 52","month":"01","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2003.11351"}],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"ec_funded":1,"volume":52,"issue":"1","_id":"12563","keyword":["General Mathematics","General Computer Science"],"status":"public","article_type":"original","type":"journal_article","date_updated":"2023-08-01T13:11:30Z","department":[{"_id":"UlWa"}],"acknowledgement":"Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Stanislav Živný was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper re\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","oa":1,"publisher":"Society for Industrial & Applied Mathematics","quality_controlled":"1","publication":"SIAM Journal on Computing","day":"01","year":"2023","isi":1,"date_created":"2023-02-16T07:03:52Z","date_published":"2023-01-01T00:00:00Z","doi":"10.1137/20m1378223","page":"38-79","project":[{"grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.","ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” SIAM Journal on Computing, vol. 52, no. 1. Society for Industrial & Applied Mathematics, pp. 38–79, 2023.","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 2023;52(1):38-79. doi:10.1137/20m1378223","apa":"Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/20m1378223","mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing, vol. 52, no. 1, Society for Industrial & Applied Mathematics, 2023, pp. 38–79, doi:10.1137/20m1378223.","ista":"Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.","chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2023. https://doi.org/10.1137/20m1378223."},"title":"Topology and adjunction in promise constraint satisfaction","article_processing_charge":"No","external_id":{"arxiv":["2003.11351"],"isi":["000955000000001"]},"author":[{"full_name":"Krokhin, Andrei","last_name":"Krokhin","first_name":"Andrei"},{"full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456","last_name":"Opršal","id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub"},{"first_name":"Marcin","last_name":"Wrochna","full_name":"Wrochna, Marcin"},{"first_name":"Stanislav","last_name":"Živný","full_name":"Živný, Stanislav"}]},{"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice. We study weaker notions of equivalence of separated nets and demonstrate that such notions also give rise to distinct equivalence classes. Put differently, we find occurrences of particularly strong divergence of separated nets from the integer lattice. Our approach generalises that of Burago and Kleiner and McMullen which takes place largely in a continuous setting. Existence of irregular separated nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞). In the present work we obtain stronger types of non-realisable densities."}],"month":"03","intvolume":" 253","scopus_import":"1","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"6fa0a3207dd1d6467c309fd1bcc867d1","file_id":"9653","date_updated":"2021-07-14T07:41:50Z","file_size":900422,"creator":"vkaluza","date_created":"2021-07-14T07:41:50Z","file_name":"separated_nets.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1565-8511"]},"publication_status":"published","volume":253,"_id":"9652","status":"public","keyword":["Lipschitz","bilipschitz","bounded displacement","modulus of continuity","separated net","non-realisable density","Burago--Kleiner construction"],"type":"journal_article","article_type":"original","ddc":["515","516"],"date_updated":"2023-08-14T11:26:34Z","department":[{"_id":"UlWa"}],"file_date_updated":"2021-07-14T07:41:50Z","acknowledgement":"This work was done while both authors were employed at the University of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35.","publisher":"Springer Nature","quality_controlled":"1","oa":1,"day":"01","publication":"Israel Journal of Mathematics","isi":1,"has_accepted_license":"1","year":"2023","doi":"10.1007/s11856-022-2448-6","date_published":"2023-03-01T00:00:00Z","date_created":"2021-07-14T07:01:28Z","page":"501-554","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Dymond M, Kaluza V. 2023. Highly irregular separated nets. Israel Journal of Mathematics. 253, 501–554.","chicago":"Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.” Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-022-2448-6.","ieee":"M. Dymond and V. Kaluza, “Highly irregular separated nets,” Israel Journal of Mathematics, vol. 253. Springer Nature, pp. 501–554, 2023.","short":"M. Dymond, V. Kaluza, Israel Journal of Mathematics 253 (2023) 501–554.","apa":"Dymond, M., & Kaluza, V. (2023). Highly irregular separated nets. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-022-2448-6","ama":"Dymond M, Kaluza V. Highly irregular separated nets. Israel Journal of Mathematics. 2023;253:501-554. doi:10.1007/s11856-022-2448-6","mla":"Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.” Israel Journal of Mathematics, vol. 253, Springer Nature, 2023, pp. 501–54, doi:10.1007/s11856-022-2448-6."},"title":"Highly irregular separated nets","author":[{"last_name":"Dymond","full_name":"Dymond, Michael","first_name":"Michael"},{"id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","first_name":"Vojtech","full_name":"Kaluza, Vojtech","orcid":"0000-0002-2512-8698","last_name":"Kaluza"}],"article_processing_charge":"No","external_id":{"arxiv":["1903.05923"],"isi":["000904950300003"]}},{"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"}],"oa_version":"Published Version","scopus_import":"1","month":"04","intvolume":" 69","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"def7ae3b28d9fd6aec16450e40090302","file_id":"12006","success":1,"date_updated":"2022-08-29T11:23:15Z","file_size":1002218,"creator":"alisjak","date_created":"2022-08-29T11:23:15Z","file_name":"2022_DiscreteandComputionalGeometry_Arroyo.pdf"}],"language":[{"iso":"eng"}],"volume":69,"ec_funded":1,"_id":"11999","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-08-14T12:51:25Z","ddc":["510"],"department":[{"_id":"UlWa"}],"file_date_updated":"2022-08-29T11:23:15Z","acknowledgement":"This work was started during the 6th Austrian–Japanese–Mexican–Spanish Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants for the good atmosphere as well as discussions on the topic. Also, we thank Jan Kynčl for sending us remarks on a preliminary version of this work and an anonymous referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie grant agreement No 754411. Fabian Klute was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and by the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was also partially supported by the Independent Research Fund Denmark grant 2020-2023 (9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.","publisher":"Springer Nature","quality_controlled":"1","oa":1,"has_accepted_license":"1","isi":1,"year":"2023","day":"01","publication":"Discrete and Computational Geometry","page":"745–770","doi":"10.1007/s00454-022-00394-9","date_published":"2023-04-01T00:00:00Z","date_created":"2022-08-28T22:02:01Z","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"citation":{"mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” Discrete and Computational Geometry, vol. 69, Springer Nature, 2023, pp. 745–770, doi:10.1007/s00454-022-00394-9.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R., & Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00394-9","ama":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 2023;69:745–770. doi:10.1007/s00454-022-00394-9","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” Discrete and Computational Geometry, vol. 69. Springer Nature, pp. 745–770, 2023.","short":"A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera, Discrete and Computational Geometry 69 (2023) 745–770.","chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber, Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00394-9.","ista":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. 2023. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 69, 745–770."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara"},{"first_name":"Fabian","full_name":"Klute, Fabian","last_name":"Klute"},{"first_name":"Irene","full_name":"Parada, Irene","last_name":"Parada"},{"last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit","first_name":"Birgit"},{"last_name":"Seidel","full_name":"Seidel, Raimund","first_name":"Raimund"},{"last_name":"Wiedera","full_name":"Wiedera, Tilo","first_name":"Tilo"}],"external_id":{"arxiv":["1909.07347"],"isi":["000840292800001"]},"article_processing_charge":"Yes (in subscription journal)","title":"Inserting one edge into a simple drawing is hard"},{"publication_identifier":{"issn":["1526-1719"]},"publication_status":"published","file":[{"file_id":"13979","checksum":"9c30d2b8e324cc1c904f2aeec92013a3","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2023-08-07T08:00:48Z","file_name":"2023_JourGraphAlgorithms_Arroyo.pdf","creator":"dernst","date_updated":"2023-08-07T08:00:48Z","file_size":865774}],"language":[{"iso":"eng"}],"issue":"6","volume":27,"related_material":{"record":[{"relation":"earlier_version","id":"11185","status":"public"}]},"ec_funded":1,"abstract":[{"lang":"eng","text":"Bundling crossings is a strategy which can enhance the readability\r\nof graph drawings. In this paper we consider good drawings, i.e., we require that\r\nany two edges have at most one common point which can be a common vertex or a\r\ncrossing. Our main result is that there is a polynomial-time algorithm to compute an\r\n8-approximation of the bundled crossing number of a good drawing with no toothed\r\nhole. In general the number of toothed holes has to be added to the 8-approximation.\r\nIn the special case of circular drawings the approximation factor is 8, this improves\r\nupon the 10-approximation of Fink et al. [14]. Our approach also works with the same\r\napproximation factor for families of pseudosegments, i.e., curves intersecting at most\r\nonce. We also show how to compute a 9/2-approximation when the intersection graph of\r\nthe pseudosegments is bipartite and has no toothed hole."}],"oa_version":"Published Version","scopus_import":"1","month":"07","intvolume":" 27","date_updated":"2023-09-25T10:56:10Z","ddc":["510"],"file_date_updated":"2023-08-07T08:00:48Z","department":[{"_id":"UlWa"}],"_id":"13969","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","has_accepted_license":"1","year":"2023","day":"01","publication":"Journal of Graph Algorithms and Applications","page":"433-457","doi":"10.7155/jgaa.00629","date_published":"2023-07-01T00:00:00Z","date_created":"2023-08-06T22:01:11Z","acknowledgement":"This work was initiated during the Workshop on Geometric Graphs in November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during the workshop. The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 754411. The second author has been supported by the German Research Foundation DFG Project FE 340/12-1. An extended abstract of this paper has been published in the proceedings of WALCOM 2022 in the Springer LNCS series, vol. 13174, pages 383–395.","quality_controlled":"1","publisher":"Brown University","oa":1,"citation":{"ista":"Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number. Journal of Graph Algorithms and Applications. 27(6), 433–457.","chicago":"Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled Crossing Number.” Journal of Graph Algorithms and Applications. Brown University, 2023. https://doi.org/10.7155/jgaa.00629.","ama":"Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. Journal of Graph Algorithms and Applications. 2023;27(6):433-457. doi:10.7155/jgaa.00629","apa":"Arroyo Guevara, A. M., & Felsner, S. (2023). Approximating the bundled crossing number. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00629","short":"A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications 27 (2023) 433–457.","ieee":"A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,” Journal of Graph Algorithms and Applications, vol. 27, no. 6. Brown University, pp. 433–457, 2023.","mla":"Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing Number.” Journal of Graph Algorithms and Applications, vol. 27, no. 6, Brown University, 2023, pp. 433–57, doi:10.7155/jgaa.00629."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Arroyo Guevara, Alan M","orcid":"0000-0003-2401-8670","last_name":"Arroyo Guevara","first_name":"Alan M","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Felsner, Stefan","last_name":"Felsner","first_name":"Stefan"}],"article_processing_charge":"Yes","external_id":{"arxiv":["2109.14892"]},"title":"Approximating the bundled crossing number","project":[{"call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}]},{"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"ista":"Köse S. 2023. Exterior algebra and combinatorics. Institute of Science and Technology Austria.","chicago":"Köse, Seyda. “Exterior Algebra and Combinatorics.” Institute of Science and Technology Austria, 2023. https://doi.org/10.15479/at:ista:13331.","ieee":"S. Köse, “Exterior algebra and combinatorics,” Institute of Science and Technology Austria, 2023.","short":"S. Köse, Exterior Algebra and Combinatorics, Institute of Science and Technology Austria, 2023.","ama":"Köse S. Exterior algebra and combinatorics. 2023. doi:10.15479/at:ista:13331","apa":"Köse, S. (2023). Exterior algebra and combinatorics. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:13331","mla":"Köse, Seyda. Exterior Algebra and Combinatorics. Institute of Science and Technology Austria, 2023, doi:10.15479/at:ista:13331."},"title":"Exterior algebra and combinatorics","author":[{"last_name":"Köse","full_name":"Köse, Seyda","id":"8ba3170d-dc85-11ea-9058-c4251c96a6eb","first_name":"Seyda"}],"article_processing_charge":"No","day":"31","has_accepted_license":"1","year":"2023","doi":"10.15479/at:ista:13331","date_published":"2023-07-31T00:00:00Z","date_created":"2023-07-31T10:20:55Z","page":"26","publisher":"Institute of Science and Technology Austria","oa":1,"ddc":["510","516"],"supervisor":[{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"date_updated":"2023-10-04T11:54:56Z","department":[{"_id":"GradSch"},{"_id":"UlWa"}],"file_date_updated":"2023-08-03T15:28:55Z","_id":"13331","status":"public","type":"dissertation","file":[{"content_type":"application/x-zip-compressed","access_level":"closed","relation":"source_file","checksum":"96ee518d796d02af71395622c45de03c","file_id":"13333","date_updated":"2023-07-31T10:16:32Z","file_size":28684,"creator":"skoese","date_created":"2023-07-31T10:16:32Z","file_name":"Exterior Algebra and Combinatorics.zip"},{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"f610f4713f88bc477de576aaa46b114e","file_id":"13480","success":1,"creator":"skoese","date_updated":"2023-08-03T15:28:55Z","file_size":4953418,"date_created":"2023-08-03T15:28:55Z","file_name":"thesis-pdfa.pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2791-4585"]},"degree_awarded":"MS","publication_status":"published","related_material":{"record":[{"relation":"part_of_dissertation","id":"12680","status":"public"}]},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"The extension of extremal combinatorics to the setting of exterior algebra is a work\r\nin progress that gained attention recently. In this thesis, we study the combinatorial structure of exterior algebra by introducing a dictionary that translates the notions from the set systems into the framework of exterior algebra. We show both generalizations of celebrated Erdös--Ko--Rado theorem and Hilton--Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms.\r\n"}],"month":"07","alternative_title":["ISTA Master's Thesis"]},{"doi":"10.1016/j.disc.2023.113363","date_published":"2023-06-01T00:00:00Z","date_created":"2023-02-26T23:01:00Z","year":"2023","day":"01","publication":"Discrete Mathematics","quality_controlled":"1","publisher":"Elsevier","oa":1,"author":[{"first_name":"Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","full_name":"Ivanov, Grigory","last_name":"Ivanov"},{"full_name":"Köse, Seyda","last_name":"Köse","first_name":"Seyda","id":"8ba3170d-dc85-11ea-9058-c4251c96a6eb"}],"article_processing_charge":"No","external_id":{"arxiv":["2201.10892"]},"title":"Erdős-Ko-Rado and Hilton-Milner theorems for two-forms","citation":{"mla":"Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” Discrete Mathematics, vol. 346, no. 6, 113363, Elsevier, 2023, doi:10.1016/j.disc.2023.113363.","apa":"Ivanov, G., & Köse, S. (2023). Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2023.113363","ama":"Ivanov G, Köse S. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. 2023;346(6). doi:10.1016/j.disc.2023.113363","short":"G. Ivanov, S. Köse, Discrete Mathematics 346 (2023).","ieee":"G. Ivanov and S. Köse, “Erdős-Ko-Rado and Hilton-Milner theorems for two-forms,” Discrete Mathematics, vol. 346, no. 6. Elsevier, 2023.","chicago":"Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems for Two-Forms.” Discrete Mathematics. Elsevier, 2023. https://doi.org/10.1016/j.disc.2023.113363.","ista":"Ivanov G, Köse S. 2023. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete Mathematics. 346(6), 113363."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"113363","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"13331"}]},"volume":346,"issue":"6","publication_identifier":{"issn":["0012-365X"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.2201.10892","open_access":"1"}],"month":"06","intvolume":" 346","abstract":[{"lang":"eng","text":"The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines."}],"oa_version":"Preprint","department":[{"_id":"UlWa"},{"_id":"GradSch"}],"date_updated":"2023-10-04T11:54:57Z","article_type":"letter_note","type":"journal_article","status":"public","_id":"12680"},{"status":"public","type":"journal_article","article_type":"original","_id":"14660","department":[{"_id":"UlWa"}],"title":"Quantitative Steinitz theorem: A polynomial bound","external_id":{"arxiv":["2212.04308"]},"article_processing_charge":"Yes (via OA deal)","author":[{"id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory","full_name":"Ivanov, Grigory","last_name":"Ivanov"},{"first_name":"Márton","last_name":"Naszódi","full_name":"Naszódi, Márton"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Ivanov G, Naszódi M. Quantitative Steinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society. 2023. doi:10.1112/blms.12965","apa":"Ivanov, G., & Naszódi, M. (2023). Quantitative Steinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society. London Mathematical Society. https://doi.org/10.1112/blms.12965","short":"G. Ivanov, M. Naszódi, Bulletin of the London Mathematical Society (2023).","ieee":"G. Ivanov and M. Naszódi, “Quantitative Steinitz theorem: A polynomial bound,” Bulletin of the London Mathematical Society. London Mathematical Society, 2023.","mla":"Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial Bound.” Bulletin of the London Mathematical Society, London Mathematical Society, 2023, doi:10.1112/blms.12965.","ista":"Ivanov G, Naszódi M. 2023. Quantitative Steinitz theorem: A polynomial bound. Bulletin of the London Mathematical Society.","chicago":"Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial Bound.” Bulletin of the London Mathematical Society. London Mathematical Society, 2023. https://doi.org/10.1112/blms.12965."},"date_updated":"2023-12-11T10:03:54Z","month":"12","main_file_link":[{"open_access":"1","url":" https://doi.org/10.1112/blms.12965"}],"oa":1,"publisher":"London Mathematical Society","quality_controlled":"1","scopus_import":"1","acknowledgement":"M.N. was supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences aswell as the National Research, Development and Innovation Fund (NRDI) grants K119670 andK131529, and the ÚNKP-22-5 New National Excellence Program of the Ministry for Innovationand Technology from the source of the NRDI as well as the ELTE TKP 2021-NKTA-62 fundingscheme","oa_version":"Published Version","abstract":[{"text":"The classical Steinitz theorem states that if the origin belongs to the interior of the convex hull of a set 𝑆⊂ℝ𝑑, then there are at most 2𝑑 points of 𝑆 whose convex hull contains the origin in the interior. Bárány, Katchalski,and Pach proved the following quantitative version of Steinitz’s theorem. Let 𝑄 be a convex polytope in ℝ𝑑 containing the standard Euclidean unit ball 𝐁𝑑. Then there exist at most 2𝑑 vertices of 𝑄 whose convex hull 𝑄′ satisfies 𝑟𝐁𝑑⊂𝑄′ with 𝑟⩾𝑑−2𝑑. They conjectured that 𝑟⩾𝑐𝑑−1∕2 holds with a universal constant 𝑐>0. We prove 𝑟⩾15𝑑2, the first polynomial lower bound on 𝑟. Furthermore, we show that 𝑟 is not greater than 2/√𝑑.","lang":"eng"}],"date_created":"2023-12-10T23:00:58Z","doi":"10.1112/blms.12965","date_published":"2023-12-04T00:00:00Z","language":[{"iso":"eng"}],"publication":"Bulletin of the London Mathematical Society","day":"04","publication_status":"epub_ahead","year":"2023","publication_identifier":{"issn":["0024-6093"],"eissn":["1469-2120"]}},{"_id":"13974","article_type":"original","type":"journal_article","status":"public","date_updated":"2023-12-13T12:03:35Z","department":[{"_id":"UlWa"}],"abstract":[{"lang":"eng","text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1812.04911","open_access":"1"}],"month":"07","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"epub_ahead","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"6647","status":"public"}]},"project":[{"call_identifier":"FWF","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs"}],"citation":{"mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” Discrete and Computational Geometry. Springer Nature, 2023.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00532-x","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2023). The crossing Tverberg theorem. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00532-x","chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00532-x.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gärtner","full_name":"Gärtner, Bernd","first_name":"Bernd"},{"full_name":"Kupavskii, Andrey","last_name":"Kupavskii","first_name":"Andrey"},{"last_name":"Valtr","full_name":"Valtr, Pavel","first_name":"Pavel"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"}],"external_id":{"isi":["001038546500001"],"arxiv":["1812.04911"]},"article_processing_charge":"No","title":"The crossing Tverberg theorem","acknowledgement":"Part of the research leading to this paper was done during the 16th Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018. We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank Stefan Felsner and Manfred Scheucher for finding, communicating the example from Sect. 3.3, and the kind permission to include their visualization of the point set. We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund (FWF), Project M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P. Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation (GAČR).","publisher":"Springer Nature","quality_controlled":"1","oa":1,"isi":1,"year":"2023","day":"27","publication":"Discrete and Computational Geometry","date_published":"2023-07-27T00:00:00Z","doi":"10.1007/s00454-023-00532-x","date_created":"2023-08-06T22:01:12Z"},{"_id":"14445","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","date_updated":"2023-12-13T13:09:07Z","ddc":["510"],"file_date_updated":"2023-10-31T11:20:31Z","department":[{"_id":"UlWa"}],"abstract":[{"lang":"eng","text":"We prove the following quantitative Borsuk–Ulam-type result (an equivariant analogue of Gromov’s Topological Overlap Theorem): Let X be a free ℤ/2-complex of dimension d with coboundary expansion at least ηk in dimension 0 ≤ k < d. Then for every equivariant map F: X →ℤ/2 ℝd, the fraction of d-simplices σ of X with 0 ∈ F (σ) is at least 2−d Π d−1k=0ηk.\r\n\r\nAs an application, we show that for every sufficiently thick d-dimensional spherical building Y and every map f: Y → ℝ2d, we have f(σ) ∩ f(τ) ≠ ∅ for a constant fraction μd > 0 of pairs {σ, τ} of d-simplices of Y. In particular, such complexes are non-embeddable into ℝ2d, which proves a conjecture of Tancer and Vorwerk for sufficiently thick spherical buildings.\r\n\r\nWe complement these results by upper bounds on the coboundary expansion of two families of simplicial complexes; this indicates some limitations to the bounds one can obtain by straighforward applications of the quantitative Borsuk–Ulam theorem. Specifically, we prove\r\n\r\n• an upper bound of (d + 1)/2d on the normalized (d − 1)-th coboundary expansion constant of complete (d + 1)-partite d-dimensional complexes (under a mild divisibility assumption on the sizes of the parts); and\r\n\r\n• an upper bound of (d + 1)/2d + ε on the normalized (d − 1)-th coboundary expansion of the d-dimensional spherical building associated with GLd+2(Fq) for any ε > 0 and sufficiently large q. This disproves, in a rather strong sense, a conjecture of Lubotzky, Meshulam and Mozes."}],"oa_version":"Published Version","scopus_import":"1","month":"09","intvolume":" 256","publication_identifier":{"eissn":["1565-8511"],"issn":["0021-2172"]},"publication_status":"published","file":[{"creator":"dernst","file_size":623787,"date_updated":"2023-10-31T11:20:31Z","file_name":"2023_IsraelJourMath_Wagner.pdf","date_created":"2023-10-31T11:20:31Z","relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"checksum":"fbb05619fe4b650f341cc730425dd9c3","file_id":"14475"}],"language":[{"iso":"eng"}],"issue":"2","volume":256,"citation":{"chicago":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2521-9.","ista":"Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717.","mla":"Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:10.1007/s11856-023-2521-9.","ieee":"U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes,” Israel Journal of Mathematics, vol. 256, no. 2. Springer Nature, pp. 675–717, 2023.","short":"U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.","apa":"Wagner, U., & Wild, P. (2023). Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-023-2521-9","ama":"Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes. Israel Journal of Mathematics. 2023;256(2):675-717. doi:10.1007/s11856-023-2521-9"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"},{"full_name":"Wild, Pascal","last_name":"Wild","id":"4C20D868-F248-11E8-B48F-1D18A9856A87","first_name":"Pascal"}],"external_id":{"isi":["001081646400010"]},"article_processing_charge":"Yes (via OA deal)","title":"Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes","quality_controlled":"1","publisher":"Springer Nature","oa":1,"isi":1,"has_accepted_license":"1","year":"2023","day":"01","publication":"Israel Journal of Mathematics","page":"675-717","date_published":"2023-09-01T00:00:00Z","doi":"10.1007/s11856-023-2521-9","date_created":"2023-10-22T22:01:14Z"},{"publication_identifier":{"eissn":["1365-8050"],"issn":["1462-7264"]},"publication_status":"published","file":[{"date_updated":"2023-04-17T08:10:28Z","file_size":2072197,"creator":"dernst","date_created":"2023-04-17T08:10:28Z","file_name":"2022_DMTCS_Biniaz.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"439102ea4f6e2aeefd7107dfb9ccf532","file_id":"12844","success":1}],"language":[{"iso":"eng"}],"volume":24,"related_material":{"record":[{"status":"public","id":"7950","relation":"earlier_version"}]},"issue":"2","abstract":[{"text":"The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.","lang":"eng"}],"oa_version":"Published Version","scopus_import":"1","month":"01","intvolume":" 24","date_updated":"2024-01-04T12:42:09Z","ddc":["000"],"file_date_updated":"2023-04-17T08:10:28Z","department":[{"_id":"KrCh"},{"_id":"HeEd"},{"_id":"UlWa"}],"_id":"12833","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","has_accepted_license":"1","year":"2023","day":"18","publication":"Discrete Mathematics and Theoretical Computer Science","date_published":"2023-01-18T00:00:00Z","doi":"10.46298/DMTCS.8383","date_created":"2023-04-16T22:01:08Z","acknowledgement":"This work was begun at the University of Waterloo and was partially supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n","publisher":"EPI Sciences","quality_controlled":"1","oa":1,"citation":{"chicago":"Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science. EPI Sciences, 2023. https://doi.org/10.46298/DMTCS.8383.","ista":"Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 24(2), 9.","mla":"Biniaz, Ahmad, et al. “Token Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:10.46298/DMTCS.8383.","apa":"Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte, A. (2023). Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. EPI Sciences. https://doi.org/10.46298/DMTCS.8383","ama":"Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. Discrete Mathematics and Theoretical Computer Science. 2023;24(2). doi:10.46298/DMTCS.8383","ieee":"A. Biniaz et al., “Token swapping on trees,” Discrete Mathematics and Theoretical Computer Science, vol. 24, no. 2. EPI Sciences, 2023.","short":"A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science 24 (2023)."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Biniaz","full_name":"Biniaz, Ahmad","first_name":"Ahmad"},{"first_name":"Kshitij","full_name":"Jain, Kshitij","last_name":"Jain"},{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Tillmann","last_name":"Miltzow","full_name":"Miltzow, Tillmann"},{"first_name":"Debajyoti","last_name":"Mondal","full_name":"Mondal, Debajyoti"},{"full_name":"Naredla, Anurag Murty","last_name":"Naredla","first_name":"Anurag Murty"},{"full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"first_name":"Alexi","full_name":"Turcotte, Alexi","last_name":"Turcotte"}],"article_processing_charge":"No","external_id":{"arxiv":["1903.06981"]},"title":"Token swapping on trees","article_number":"9"},{"publication_status":"published","publication_identifier":{"issn":["1073-7928"],"eissn":["1687-0247"]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"353666cea80633beb0f1ffd342dff6d4","file_id":"14738","success":1,"creator":"dernst","date_updated":"2024-01-08T09:53:09Z","file_size":815777,"date_created":"2024-01-08T09:53:09Z","file_name":"2023_IMRN_Ivanov.pdf"}],"license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","volume":2023,"issue":"23","abstract":[{"text":"John’s fundamental theorem characterizing the largest volume ellipsoid contained in a convex body $K$ in $\\mathbb{R}^{d}$ has seen several generalizations and extensions. One direction, initiated by V. Milman is to replace ellipsoids by positions (affine images) of another body $L$. Another, more recent direction is to consider logarithmically concave functions on $\\mathbb{R}^{d}$ instead of convex bodies: we designate some special, radially symmetric log-concave function $g$ as the analogue of the Euclidean ball, and want to find its largest integral position under the constraint that it is pointwise below some given log-concave function $f$. We follow both directions simultaneously: we consider the functional question, and allow essentially any meaningful function to play the role of $g$ above. Our general theorems jointly extend known results in both directions. The dual problem in the setting of convex bodies asks for the smallest volume ellipsoid, called Löwner’s ellipsoid, containing $K$. We consider the analogous problem for functions: we characterize the solutions of the optimization problem of finding a smallest integral position of some log-concave function $g$ under the constraint that it is pointwise above $f$. It turns out that in the functional setting, the relationship between the John and the Löwner problems is more intricate than it is in the setting of convex bodies.","lang":"eng"}],"oa_version":"Published Version","intvolume":" 2023","month":"12","date_updated":"2024-01-08T09:57:25Z","ddc":["510"],"file_date_updated":"2024-01-08T09:53:09Z","department":[{"_id":"UlWa"}],"_id":"14737","tmp":{"short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"article_type":"original","type":"journal_article","keyword":["General Mathematics"],"status":"public","year":"2023","has_accepted_license":"1","publication":"International Mathematics Research Notices","day":"01","page":"20613-20669","date_created":"2024-01-08T09:48:56Z","date_published":"2023-12-01T00:00:00Z","doi":"10.1093/imrn/rnad210","acknowledgement":"We thank Alexander Litvak for the many discussions on Theorem 1.1. Igor Tsiutsiurupa participated in the early stage of this project. To our deep regret, Igor chose another road for his life and stopped working with us.\r\nThis work was supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences [to M.N.]; the National Research, Development, and Innovation Fund (NRDI) [K119670 and K131529 to M.N.]; and the ÚNKP-22-5 New National Excellence Program of the Ministry for Innovation and Technology from the source of the NRDI [to M.N.].","oa":1,"quality_controlled":"1","publisher":"Oxford University Press","citation":{"ista":"Ivanov G, Naszódi M. 2023. Functional John and Löwner conditions for pairs of log-concave functions. International Mathematics Research Notices. 2023(23), 20613–20669.","chicago":"Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions for Pairs of Log-Concave Functions.” International Mathematics Research Notices. Oxford University Press, 2023. https://doi.org/10.1093/imrn/rnad210.","ama":"Ivanov G, Naszódi M. Functional John and Löwner conditions for pairs of log-concave functions. International Mathematics Research Notices. 2023;2023(23):20613-20669. doi:10.1093/imrn/rnad210","apa":"Ivanov, G., & Naszódi, M. (2023). Functional John and Löwner conditions for pairs of log-concave functions. International Mathematics Research Notices. Oxford University Press. https://doi.org/10.1093/imrn/rnad210","short":"G. Ivanov, M. Naszódi, International Mathematics Research Notices 2023 (2023) 20613–20669.","ieee":"G. Ivanov and M. Naszódi, “Functional John and Löwner conditions for pairs of log-concave functions,” International Mathematics Research Notices, vol. 2023, no. 23. Oxford University Press, pp. 20613–20669, 2023.","mla":"Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions for Pairs of Log-Concave Functions.” International Mathematics Research Notices, vol. 2023, no. 23, Oxford University Press, 2023, pp. 20613–69, doi:10.1093/imrn/rnad210."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"Yes (via OA deal)","external_id":{"arxiv":["2212.11781"]},"author":[{"last_name":"Ivanov","full_name":"Ivanov, Grigory","id":"87744F66-5C6F-11EA-AFE0-D16B3DDC885E","first_name":"Grigory"},{"first_name":"Márton","last_name":"Naszódi","full_name":"Naszódi, Márton"}],"title":"Functional John and Löwner conditions for pairs of log-concave functions"},{"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence."}],"month":"11","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s10711-023-00862-3"}],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"epub_ahead","publication_identifier":{"eissn":["1572-9168"],"issn":["0046-5755"]},"_id":"9651","status":"public","type":"journal_article","article_type":"original","date_updated":"2024-01-11T13:06:32Z","department":[{"_id":"UlWa"}],"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was started while both authors were employed at the University of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35. It was continued when the first named author was employed at University of Leipzig and the second named author was employed at Institute of Science and Technology of Austria, where he was supported by an IST Fellowship.","oa":1,"quality_controlled":"1","publisher":"Springer Nature","publication":"Geometriae Dedicata","day":"17","year":"2023","isi":1,"date_created":"2021-07-14T07:01:27Z","date_published":"2023-11-17T00:00:00Z","doi":"10.1007/s10711-023-00862-3","article_number":"15","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect to Displacement Equivalence.” Geometriae Dedicata. Springer Nature, 2023. https://doi.org/10.1007/s10711-023-00862-3.","ista":"Dymond M, Kaluza V. 2023. Divergence of separated nets with respect to displacement equivalence. Geometriae Dedicata., 15.","mla":"Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect to Displacement Equivalence.” Geometriae Dedicata, 15, Springer Nature, 2023, doi:10.1007/s10711-023-00862-3.","ama":"Dymond M, Kaluza V. Divergence of separated nets with respect to displacement equivalence. Geometriae Dedicata. 2023. doi:10.1007/s10711-023-00862-3","apa":"Dymond, M., & Kaluza, V. (2023). Divergence of separated nets with respect to displacement equivalence. Geometriae Dedicata. Springer Nature. https://doi.org/10.1007/s10711-023-00862-3","short":"M. Dymond, V. Kaluza, Geometriae Dedicata (2023).","ieee":"M. Dymond and V. Kaluza, “Divergence of separated nets with respect to displacement equivalence,” Geometriae Dedicata. Springer Nature, 2023."},"title":"Divergence of separated nets with respect to displacement equivalence","article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["001105681500001"],"arxiv":["2102.13046"]},"author":[{"full_name":"Dymond, Michael","last_name":"Dymond","first_name":"Michael"},{"orcid":"0000-0002-2512-8698","full_name":"Kaluza, Vojtech","last_name":"Kaluza","id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","first_name":"Vojtech"}]},{"quality_controlled":"1","publisher":"Springer Nature","oa":1,"acknowledgement":"Open access funding provided by the Institute of Science and Technology (IST Austria).","doi":"10.1007/s00454-023-00500-5","date_published":"2023-07-05T00:00:00Z","date_created":"2023-07-23T22:01:14Z","page":"1059-1089","day":"05","publication":"Discrete and Computational Geometry","has_accepted_license":"1","isi":1,"year":"2023","title":"Iterated medial triangle subdivision in surfaces of constant curvature","author":[{"last_name":"Brunck","full_name":"Brunck, Florestan R","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","first_name":"Florestan R"}],"external_id":{"isi":["001023742800003"],"arxiv":["2107.04112"]},"article_processing_charge":"Yes (via OA deal)","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature.” Discrete and Computational Geometry, vol. 70, no. 3, Springer Nature, 2023, pp. 1059–89, doi:10.1007/s00454-023-00500-5.","short":"F.R. Brunck, Discrete and Computational Geometry 70 (2023) 1059–1089.","ieee":"F. R. Brunck, “Iterated medial triangle subdivision in surfaces of constant curvature,” Discrete and Computational Geometry, vol. 70, no. 3. Springer Nature, pp. 1059–1089, 2023.","apa":"Brunck, F. R. (2023). Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00500-5","ama":"Brunck FR. Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. 2023;70(3):1059-1089. doi:10.1007/s00454-023-00500-5","chicago":"Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00500-5.","ista":"Brunck FR. 2023. Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. 70(3), 1059–1089."},"month":"07","intvolume":" 70","scopus_import":"1","oa_version":"Published Version","abstract":[{"text":"Consider a geodesic triangle on a surface of constant curvature and subdivide it recursively into four triangles by joining the midpoints of its edges. We show the existence of a uniform δ>0\r\n such that, at any step of the subdivision, all the triangle angles lie in the interval (δ,π−δ)\r\n. Additionally, we exhibit stabilising behaviours for both angles and lengths as this subdivision progresses.","lang":"eng"}],"volume":70,"issue":"3","file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","success":1,"file_id":"14897","checksum":"865e68daafdd4edcfc280172ec50f5ea","creator":"dernst","file_size":1466020,"date_updated":"2024-01-29T11:15:22Z","file_name":"2023_DiscreteComputGeometry_Brunck.pdf","date_created":"2024-01-29T11:15:22Z"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"13270","file_date_updated":"2024-01-29T11:15:22Z","department":[{"_id":"UlWa"}],"ddc":["510"],"date_updated":"2024-01-29T11:16:16Z"},{"oa":1,"quality_controlled":"1","publisher":"Association for Computing Machinery","year":"2022","publication":"ACM SIGLOG News","day":"01","page":"30-59","date_created":"2022-08-27T11:23:37Z","doi":"10.1145/3559736.3559740","date_published":"2022-07-01T00:00:00Z","citation":{"chicago":"Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint Satisfaction Problem.” ACM SIGLOG News. Association for Computing Machinery, 2022. https://doi.org/10.1145/3559736.3559740.","ista":"Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News. 9(3), 30–59.","mla":"Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint Satisfaction Problem.” ACM SIGLOG News, vol. 9, no. 3, Association for Computing Machinery, 2022, pp. 30–59, doi:10.1145/3559736.3559740.","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,” ACM SIGLOG News, vol. 9, no. 3. Association for Computing Machinery, pp. 30–59, 2022.","ama":"Krokhin A, Opršal J. An invitation to the promise constraint satisfaction problem. ACM SIGLOG News. 2022;9(3):30-59. doi:10.1145/3559736.3559740","apa":"Krokhin, A., & Opršal, J. (2022). An invitation to the promise constraint satisfaction problem. ACM SIGLOG News. Association for Computing Machinery. https://doi.org/10.1145/3559736.3559740"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","external_id":{"arxiv":["2208.13538"]},"author":[{"last_name":"Krokhin","full_name":"Krokhin, Andrei","first_name":"Andrei"},{"last_name":"Opršal","orcid":"0000-0003-1245-3456","full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub"}],"title":"An invitation to the promise constraint satisfaction problem","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"}],"oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/2208.13538","open_access":"1"}],"intvolume":" 9","month":"07","publication_status":"published","publication_identifier":{"issn":["2372-3491"]},"language":[{"iso":"eng"}],"volume":9,"issue":"3","_id":"11991","type":"journal_article","article_type":"original","status":"public","date_updated":"2022-09-05T08:19:38Z","department":[{"_id":"UlWa"}]},{"project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"}],"citation":{"chicago":"Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada, Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible Matchings.” Journal of Graph Algorithms and Applications. Brown University, 2022. https://doi.org/10.7155/jgaa.00591.","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.","mla":"Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.","ama":"Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings. Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591","apa":"Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D., Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591","ieee":"O. Aichholzer et al., “On compatible matchings,” Journal of Graph Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240, 2022.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","external_id":{"arxiv":["2101.03928"]},"author":[{"last_name":"Aichholzer","full_name":"Aichholzer, Oswin","first_name":"Oswin"},{"orcid":"0000-0003-2401-8670","full_name":"Arroyo Guevara, Alan M","last_name":"Arroyo Guevara","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","first_name":"Alan M"},{"last_name":"Masárová","orcid":"0000-0002-6660-1322","full_name":"Masárová, Zuzana","first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"last_name":"Perz","full_name":"Perz, Daniel","first_name":"Daniel"},{"full_name":"Pilz, Alexander","last_name":"Pilz","first_name":"Alexander"},{"first_name":"Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","full_name":"Tkadlec, Josef","orcid":"0000-0002-1097-9684"},{"full_name":"Vogtenhuber, Birgit","last_name":"Vogtenhuber","first_name":"Birgit"}],"title":"On compatible matchings","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).","oa":1,"publisher":"Brown University","quality_controlled":"1","year":"2022","has_accepted_license":"1","publication":"Journal of Graph Algorithms and Applications","day":"01","page":"225-240","date_created":"2022-08-21T22:01:56Z","doi":"10.7155/jgaa.00591","date_published":"2022-06-01T00:00:00Z","_id":"11938","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","article_type":"original","status":"public","date_updated":"2023-02-23T13:54:21Z","ddc":["000"],"department":[{"_id":"UlWa"},{"_id":"HeEd"},{"_id":"KrCh"}],"file_date_updated":"2022-08-22T06:42:42Z","abstract":[{"lang":"eng","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."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 26","month":"06","publication_status":"published","publication_identifier":{"issn":["1526-1719"]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_id":"11940","checksum":"dc6e255e3558faff924fd9e370886c11","file_size":694538,"date_updated":"2022-08-22T06:42:42Z","creator":"dernst","file_name":"2022_JourGraphAlgorithmsApplic_Aichholzer.pdf","date_created":"2022-08-22T06:42:42Z"}],"ec_funded":1,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"9296"}]},"issue":"2","volume":26},{"supervisor":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"date_updated":"2023-06-22T09:56:36Z","ddc":["500","516","514"],"department":[{"_id":"GradSch"},{"_id":"UlWa"}],"file_date_updated":"2022-08-11T16:09:19Z","_id":"11777","type":"dissertation","status":"public","publication_identifier":{"isbn":["978-3-99078-021-3"],"issn":["2663-337X"]},"publication_status":"published","degree_awarded":"PhD","file":[{"relation":"supplementary_material","access_level":"open_access","description":"Code for computer-assisted proofs in Section 8.4.7 in Thesis","content_type":"text/x-python","checksum":"f5f3af1fb7c8a24b71ddc88ad7f7c5b4","file_id":"11780","creator":"pwild","file_size":16828,"date_updated":"2022-08-10T15:34:04Z","file_name":"flags.py","date_created":"2022-08-10T15:34:04Z"},{"creator":"pwild","date_updated":"2022-08-10T15:34:10Z","file_size":12226,"date_created":"2022-08-10T15:34:10Z","file_name":"lowerbound.cpp","access_level":"open_access","relation":"supplementary_material","content_type":"text/x-c++src","description":"Code for proof of Lemma 8.20 in Thesis","file_id":"11781","checksum":"1f7c12dfe3bdaa9b147e4fbc3d34e3d5"},{"file_name":"upperbound.py","date_created":"2022-08-10T15:34:17Z","creator":"pwild","file_size":3240,"date_updated":"2022-08-10T15:34:17Z","file_id":"11782","checksum":"4cf81455c49e5dec3b9b2e3980137eeb","relation":"supplementary_material","access_level":"open_access","description":"Code for proof of Proposition 7.9 in Thesis","content_type":"text/x-python"},{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"4e96575b10cbe4e0d0db2045b2847774","file_id":"11809","file_size":5086282,"date_updated":"2022-08-11T16:08:33Z","creator":"pwild","file_name":"finalthesisPascalWildPDFA.pdf","title":"High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes","date_created":"2022-08-11T16:08:33Z"},{"date_created":"2022-08-11T16:09:19Z","file_name":"ThesisSubmission.zip","creator":"pwild","date_updated":"2022-08-11T16:09:19Z","file_size":18150068,"file_id":"11810","checksum":"92d94842a1fb6dca5808448137573b2e","access_level":"closed","relation":"source_file","content_type":"application/zip"}],"language":[{"iso":"eng"}],"ec_funded":1,"abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"month":"08","citation":{"apa":"Wild, P. (2022). High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology. https://doi.org/10.15479/at:ista:11777","ama":"Wild P. High-dimensional expansion and crossing numbers of simplicial complexes. 2022. doi:10.15479/at:ista:11777","short":"P. Wild, High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes, Institute of Science and Technology, 2022.","ieee":"P. Wild, “High-dimensional expansion and crossing numbers of simplicial complexes,” Institute of Science and Technology, 2022.","mla":"Wild, Pascal. High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes. Institute of Science and Technology, 2022, doi:10.15479/at:ista:11777.","ista":"Wild P. 2022. High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology.","chicago":"Wild, Pascal. “High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes.” Institute of Science and Technology, 2022. https://doi.org/10.15479/at:ista:11777."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","author":[{"last_name":"Wild","full_name":"Wild, Pascal","id":"4C20D868-F248-11E8-B48F-1D18A9856A87","first_name":"Pascal"}],"article_processing_charge":"No","title":"High-dimensional expansion and crossing numbers of simplicial complexes","project":[{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","grant_number":"665385"}],"has_accepted_license":"1","year":"2022","day":"11","page":"170","doi":"10.15479/at:ista:11777","date_published":"2022-08-11T00:00:00Z","date_created":"2022-08-10T15:51:19Z","publisher":"Institute of Science and Technology","oa":1},{"citation":{"ista":"Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 42, 1317–1345.","chicago":"Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” Combinatorica. Springer Nature, 2022. https://doi.org/10.1007/s00493-021-4443-7.","short":"V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.","ieee":"V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations of graphs,” Combinatorica, vol. 42. Springer Nature, pp. 1317–1345, 2022.","ama":"Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. 2022;42:1317-1345. doi:10.1007/s00493-021-4443-7","apa":"Kaluza, V., & Tancer, M. (2022). Even maps, the Colin de Verdière number and representations of graphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4443-7","mla":"Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number and Representations of Graphs.” Combinatorica, vol. 42, Springer Nature, 2022, pp. 1317–45, doi:10.1007/s00493-021-4443-7."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","author":[{"id":"21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E","first_name":"Vojtech","last_name":"Kaluza","full_name":"Kaluza, Vojtech","orcid":"0000-0002-2512-8698"},{"first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin","orcid":"0000-0002-1191-6714","last_name":"Tancer"}],"external_id":{"isi":["000798210100003"],"arxiv":["1907.05055"]},"article_processing_charge":"No","title":"Even maps, the Colin de Verdière number and representations of graphs","acknowledgement":"V. K. gratefully acknowledges the support of Austrian Science Fund (FWF): P 30902-N35. This work was done mostly while he was employed at the University of Innsbruck. During the early stage of this research, V. K. was partially supported by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University project UNCE/SCI/004.","quality_controlled":"1","publisher":"Springer Nature","oa":1,"isi":1,"year":"2022","day":"01","publication":"Combinatorica","page":"1317-1345","date_published":"2022-12-01T00:00:00Z","doi":"10.1007/s00493-021-4443-7","date_created":"2021-11-25T13:49:16Z","_id":"10335","article_type":"original","type":"journal_article","status":"public","date_updated":"2023-08-02T06:43:27Z","ddc":["514","516"],"department":[{"_id":"UlWa"}],"abstract":[{"text":"Van der Holst and Pendavingh introduced a graph parameter σ, which coincides with the more famous Colin de Verdière graph parameter μ for small values. However, the definition of a is much more geometric/topological directly reflecting embeddability properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G) for any graph G. We confirm this conjecture. As far as we know, this is the first topological upper bound on σ(G) which is, in general, tight.\r\nEquality between μ and σ does not hold in general as van der Holst and Pendavingh showed that there is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8. We also prove that, in general, the gap can be large: The incidence graphs Hq of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2.","lang":"eng"}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":" https://doi.org/10.48550/arXiv.1907.05055","open_access":"1"}],"month":"12","intvolume":" 42","publication_identifier":{"issn":["0209-9683"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":42},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-021-00364-7.","ista":"Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body. Discrete and Computational Geometry. 68, 1133–1154.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 1133–1154, 2022.","short":"Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68 (2022) 1133–1154.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. Discrete and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7"},"title":"Barycentric cuts through a convex body","author":[{"first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana","last_name":"Patakova"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"No","external_id":{"arxiv":["2003.13536"],"isi":["000750681500001"]},"day":"01","publication":"Discrete and Computational Geometry","isi":1,"year":"2022","date_published":"2022-12-01T00:00:00Z","doi":"10.1007/s00454-021-00364-7","date_created":"2022-02-20T23:01:35Z","page":"1133-1154","acknowledgement":"The work by Zuzana Patáková has been partially supported by Charles University Research Center Program No. UNCE/SCI/022, and part of it was done during her research stay at IST Austria. The work by Martin Tancer is supported by the GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and UNCE/SCI/004.","quality_controlled":"1","publisher":"Springer Nature","oa":1,"date_updated":"2023-08-02T14:38:58Z","department":[{"_id":"UlWa"}],"_id":"10776","status":"public","type":"journal_article","article_type":"original","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","volume":68,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p0 is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n≥2, there are always at least three distinct barycentric cuts through the point p0∈K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p0 are guaranteed if n≥3."}],"month":"12","intvolume":" 68","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/2003.13536","open_access":"1"}]}]