[{"doi":"10.1145/3779121","article_type":"original","acknowledgement":"This research was supported by the Charles University project PRIMUS/21/SCI/014, by the Ministry of Education, Youth\r\nand Sports of the Czech Republic under the project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229), and by the\r\nAustrian Science Fund (FWF project P31312-N35). This research was funded by UKRI EP/X024431/1 and by a Clarendon\r\nFund Scholarship. This project has received funding from the European Union’s Horizon 2020 research and innovation\r\nprogramme under the Marie Skłodowska-Curie Grant Agreement No 101034413.\r\n","date_created":"2026-07-05T22:01:37Z","external_id":{"arxiv":["2312.12981"]},"ec_funded":1,"_id":"22247","citation":{"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,” <i>ACM Transactions on Computation Theory</i>, vol. 18, no. 2. Association for Computing Machinery, 2026.","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. <i>ACM Transactions on Computation Theory</i>. 2026;18(2). doi:<a href=\"https://doi.org/10.1145/3779121\">10.1145/3779121</a>","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.” <i>ACM Transactions on Computation Theory</i>. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3779121\">https://doi.org/10.1145/3779121</a>.","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, ACM Transactions on Computation Theory 18 (2026).","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>ACM Transactions on Computation Theory</i>, vol. 18, no. 2, 10, Association for Computing Machinery, 2026, doi:<a href=\"https://doi.org/10.1145/3779121\">10.1145/3779121</a>.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2026. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. ACM Transactions on Computation Theory. 18(2), 10.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2026). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. <i>ACM Transactions on Computation Theory</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3779121\">https://doi.org/10.1145/3779121</a>"},"article_processing_charge":"Yes","researchdata_availability":"no","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).\r\nHere, 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"}],"scopus_import":"1","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"15168"}]},"date_updated":"2026-07-06T09:06:29Z","year":"2026","department":[{"_id":"UlWa"}],"month":"05","publication_identifier":{"issn":["1942-3454"],"eissn":["1942-3462"]},"type":"journal_article","OA_type":"gold","day":"04","license":"https://creativecommons.org/licenses/by/4.0/","publication":"ACM Transactions on Computation Theory","file":[{"success":1,"checksum":"0399ab94085878fc810084845eabd627","access_level":"open_access","file_id":"22252","date_created":"2026-07-06T09:03:02Z","content_type":"application/pdf","file_size":941518,"date_updated":"2026-07-06T09:03:02Z","creator":"dernst","relation":"main_file","file_name":"2026_TransactionsGraphics_Filakovsky.pdf"}],"publisher":"Association for Computing Machinery","date_published":"2026-05-04T00:00:00Z","article_number":"10","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory"},{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}],"oa":1,"status":"public","ddc":["500"],"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"},"OA_place":"publisher","supplementarymaterial":"no","issue":"2","intvolume":"        18","has_accepted_license":"1","das_tickbox":"0","author":[{"first_name":"Marek","full_name":"Filakovský, Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nakajima","first_name":"Tamio Vesa","full_name":"Nakajima, Tamio Vesa"},{"orcid":"0000-0003-1245-3456","last_name":"Opršal","id":"ec596741-c539-11ec-b829-c79322a91242","first_name":"Jakub","full_name":"Opršal, Jakub"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato","full_name":"Tasinato, Gianluca","first_name":"Gianluca"},{"orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli"}],"volume":18,"oa_version":"Published Version","PlanS_conform":"1","language":[{"iso":"eng"}],"keyword":["Constraint satisfaction problem","hypergraph colouring","promise problem","topological methods"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"corr_author":"1","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","publication_status":"published","file_date_updated":"2026-07-06T09:03:02Z","quality_controlled":"1"},{"corr_author":"1","title":"Hardness of 4-colouring G-colourable graphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"72-83","language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","file_date_updated":"2025-07-14T06:42:58Z","publication_status":"published","OA_place":"publisher","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"},"status":"public","ddc":["000"],"oa":1,"author":[{"last_name":"Avvakumov","orcid":"0000-0002-7840-5062","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","full_name":"Avvakumov, Sergey"},{"full_name":"Filakovský, Marek","first_name":"Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","last_name":"Filakovský"},{"id":"ec596741-c539-11ec-b829-c79322a91242","orcid":"0000-0003-1245-3456","last_name":"Opršal","full_name":"Opršal, Jakub","first_name":"Jakub"},{"last_name":"Tasinato","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca","full_name":"Tasinato, Gianluca"},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"has_accepted_license":"1","OA_type":"hybrid","type":"conference","publication_identifier":{"issn":["0737-8017"],"isbn":["9798400715105"]},"department":[{"_id":"UlWa"}],"month":"06","year":"2025","date_published":"2025-06-15T00:00:00Z","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"},{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"publisher":"Association for Computing Machinery","file":[{"checksum":"2c9ae7ad0102c41124976f4cb5182760","access_level":"open_access","success":1,"content_type":"application/pdf","file_id":"20013","date_created":"2025-07-14T06:42:58Z","creator":"dernst","relation":"main_file","file_size":940827,"date_updated":"2025-07-14T06:42:58Z","file_name":"2025_STOC_Avvakumov.pdf"}],"publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","day":"15","article_processing_charge":"Yes (in subscription journal)","citation":{"mla":"Avvakumov, Sergey, et al. “Hardness of 4-Colouring G-Colourable Graphs.” <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Association for Computing Machinery, 2025, pp. 72–83, doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>.","ista":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. 2025. Hardness of 4-colouring G-colourable graphs. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 72–83.","chicago":"Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, 72–83. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>.","ieee":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of 4-colouring G-colourable graphs,” in <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>, Prague, Czechia, 2025, pp. 72–83.","ama":"Avvakumov S, Filakovský M, Opršal J, Tasinato G, Wagner U. Hardness of 4-colouring G-colourable graphs. In: <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i>. Association for Computing Machinery; 2025:72-83. doi:<a href=\"https://doi.org/10.1145/3717823.3718154\">10.1145/3717823.3718154</a>","short":"S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, U. Wagner, in:, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp. 72–83.","apa":"Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., &#38; Wagner, U. (2025). Hardness of 4-colouring G-colourable graphs. In <i>Proceedings of the 57th Annual ACM Symposium on Theory of Computing</i> (pp. 72–83). Prague, Czechia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3717823.3718154\">https://doi.org/10.1145/3717823.3718154</a>"},"_id":"20008","acknowledgement":"This research was supported by the Austrian Science Fund (FWF project P31312-N35) and by project MSCAfellow5_MUNI (CZ.02.01.01/00/22_010/0003229) financed by the Ministry of Education, Youth and Sports of the Czech Republic. This project has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.","date_created":"2025-07-13T22:01:23Z","ec_funded":1,"doi":"10.1145/3717823.3718154","conference":{"start_date":"2025-06-23","location":"Prague, Czechia","end_date":"2025-06-27","name":"STOC: Symposium on Theory of Computing"},"date_updated":"2026-07-29T13:13:17Z","related_material":{"record":[{"id":"20339","relation":"dissertation_contains","status":"public"}]},"scopus_import":"1","abstract":[{"lang":"eng","text":"We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory."}]},{"doi":"10.4230/LIPIcs.STACS.2024.34","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).","external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"date_created":"2024-03-24T23:00:59Z","ec_funded":1,"citation":{"mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>.","ista":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.","ieee":"M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289.","chicago":"Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","ama":"Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>","short":"M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>"},"_id":"15168","article_processing_charge":"No","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"}],"scopus_import":"1","related_material":{"record":[{"id":"22247","relation":"later_version","status":"public"},{"status":"public","relation":"dissertation_contains","id":"20339"}]},"conference":{"end_date":"2024-03-14","name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2024-03-12","location":"Clermont-Ferrand, France"},"date_updated":"2026-07-29T13:13:17Z","month":"03","department":[{"_id":"UlWa"}],"year":"2024","type":"conference","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"day":"01","alternative_title":["LIPIcs"],"file":[{"date_created":"2024-03-25T07:44:30Z","file_id":"15175","content_type":"application/pdf","success":1,"access_level":"open_access","checksum":"0524d4189fd1ed08989546511343edf3","file_name":"2024_LIPICs_Filakovsky.pdf","file_size":927290,"date_updated":"2024-03-25T07:44:30Z","creator":"dernst","relation":"main_file"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"41st International Symposium on Theoretical Aspects of Computer Science","article_number":"34","date_published":"2024-03-01T00:00:00Z","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"}],"oa":1,"status":"public","ddc":["510"],"isi":1,"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":"       289","has_accepted_license":"1","author":[{"last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Filakovský, Marek"},{"first_name":"Tamio Vesa","full_name":"Nakajima, Tamio Vesa","last_name":"Nakajima"},{"id":"ec596741-c539-11ec-b829-c79322a91242","orcid":"0000-0003-1245-3456","last_name":"Opršal","full_name":"Opršal, Jakub","first_name":"Jakub"},{"full_name":"Tasinato, Gianluca","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato"},{"first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":289,"oa_version":"Published Version","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","corr_author":"1","arxiv":1,"file_date_updated":"2024-03-25T07:44:30Z","publication_status":"published","quality_controlled":"1"},{"oa_version":"Preprint","volume":245,"arxiv":1,"title":"Eliminating higher-multiplicity intersections. III. Codimension 2","corr_author":"1","page":"501–534 ","language":[{"iso":"eng"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication_status":"published","quality_controlled":"1","oa":1,"isi":1,"status":"public","intvolume":"       245","author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7840-5062","last_name":"Avvakumov"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","full_name":"Mabillard, Isaac","first_name":"Isaac"},{"last_name":"Skopenkov","first_name":"Arkadiy B.","full_name":"Skopenkov, Arkadiy B."},{"first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"year":"2021","month":"10","department":[{"_id":"UlWa"}],"publication_identifier":{"issn":["0021-2172"],"eissn":["1565-8511"]},"type":"journal_article","day":"30","date_published":"2021-10-30T00:00:00Z","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory"}],"publication":"Israel Journal of Mathematics","publisher":"Springer Nature","article_type":"original","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.","date_created":"2021-11-07T23:01:24Z","external_id":{"arxiv":["1511.03501"],"isi":["000712942100013"]},"doi":"10.1007/s11856-021-2216-z","article_processing_charge":"No","_id":"10220","citation":{"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.","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>.","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>","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>.","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>"},"main_file_link":[{"url":"https://arxiv.org/abs/1511.03501","open_access":"1"}],"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"}],"date_updated":"2025-07-02T10:54:52Z","scopus_import":"1","related_material":{"record":[{"id":"9308","status":"public","relation":"earlier_version"},{"relation":"earlier_version","status":"public","id":"8183"}]}},{"date_updated":"2026-06-18T19:27:16Z","conference":{"start_date":"2020-01-05","location":"Salt Lake City, UT, United States","end_date":"2020-01-08","name":"SODA: Symposium on Discrete Algorithms"},"scopus_import":"1","abstract":[{"text":"We consider the following decision problem EMBEDk→d in computational topology (where k ≤ d are fixed positive integers): Given a finite simplicial complex K of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe special case EMBED1→2 is graph planarity, which is decidable in linear time, as shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are known to be decidable (as well as NP-hard), and recent results of Čadek et al. in computational homotopy theory, in combination with the classical Haefliger–Weber theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial time for any fixed pair (k, d) of dimensions in the so-called metastable range .\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable for almost all pairs of dimensions outside the metastable range, namely for . This almost completely resolves the decidability vs. undecidability of EMBEDk→d in higher dimensions and establishes a sharp dichotomy between polynomial-time solvability and undecidability.\r\nOur result complements (and in a wide range of dimensions strengthens) earlier results of Matoušek, Tancer, and the second author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard for all remaining pairs (k, d) outside the metastable range and satisfying d ≥ 4.","lang":"eng"}],"article_processing_charge":"No","_id":"7806","main_file_link":[{"url":"https://doi.org/10.1137/1.9781611975994.47","open_access":"1"}],"citation":{"short":"M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785.","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>","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.","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>.","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.","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>.","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>"},"date_created":"2020-05-10T22:00:48Z","doi":"10.1137/1.9781611975994.47","project":[{"grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"date_published":"2020-01-01T00:00:00Z","publication":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms","publisher":"SIAM","day":"01","publication_identifier":{"isbn":["9781611975994"]},"type":"conference","year":"2020","month":"01","department":[{"_id":"UlWa"}],"author":[{"last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Filakovský, Marek"},{"full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568"},{"first_name":"Stephan Y","full_name":"Zhechev, Stephan Y","last_name":"Zhechev","id":"3AA52972-F248-11E8-B48F-1D18A9856A87"}],"ddc":["500"],"status":"public","oa":1,"quality_controlled":"1","publication_status":"published","title":"Embeddability of simplicial complexes is undecidable","page":"767-785","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","volume":"2020-January"},{"day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"file":[{"file_size":575896,"date_updated":"2020-07-14T12:48:06Z","creator":"dernst","relation":"main_file","file_name":"2020_LIPIcsSoCG_Avvakumov.pdf","access_level":"open_access","checksum":"6872df6549142f709fb6354a1b2f2c06","date_created":"2020-06-23T11:13:49Z","file_id":"8007","content_type":"application/pdf"}],"publication":"36th International Symposium on Computational Geometry","license":"https://creativecommons.org/licenses/by/3.0/","date_published":"2020-06-01T00:00:00Z","project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","grant_number":"P31312"}],"article_number":"12:1 - 12:15","month":"06","department":[{"_id":"UlWa"}],"year":"2020","type":"conference","publication_identifier":{"isbn":["9783959771436"],"issn":["1868-8969"]},"abstract":[{"text":"We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between \"grid peeling\" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.","lang":"eng"}],"scopus_import":"1","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22"},"date_updated":"2025-07-10T11:54:56Z","doi":"10.4230/LIPIcs.SoCG.2020.12","date_created":"2020-06-22T09:14:19Z","external_id":{"arxiv":["1909.00263"]},"citation":{"ama":"Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening flow. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>","ieee":"S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening flow,” in <i>36th International Symposium on Computational Geometry</i>, Zürich, Switzerland, 2020, vol. 164.","chicago":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>.","short":"S. Avvakumov, G. Nivasch, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the Affine Curve-Shortening Flow.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">10.4230/LIPIcs.SoCG.2020.12</a>.","ista":"Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening flow. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.","apa":"Avvakumov, S., &#38; Nivasch, G. (2020). Homotopic curve shortening and the affine curve-shortening flow. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.12\">https://doi.org/10.4230/LIPIcs.SoCG.2020.12</a>"},"_id":"7991","article_processing_charge":"No","file_date_updated":"2020-07-14T12:48:06Z","publication_status":"published","quality_controlled":"1","volume":164,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"title":"Homotopic curve shortening and the affine curve-shortening flow","arxiv":1,"intvolume":"       164","has_accepted_license":"1","author":[{"last_name":"Avvakumov","orcid":"0000-0002-7840-5062","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","full_name":"Avvakumov, Sergey"},{"last_name":"Nivasch","full_name":"Nivasch, Gabriel","first_name":"Gabriel"}],"oa":1,"ddc":["510"],"status":"public","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","short":"CC BY (3.0)"}},{"abstract":[{"lang":"eng","text":"This paper presents two algorithms. The first decides the existence of a pointed homotopy between given simplicial maps 𝑓,𝑔:𝑋→𝑌, and the second computes the group [𝛴𝑋,𝑌]∗ of pointed homotopy classes of maps from a suspension; in both cases, the target Y is assumed simply connected. More generally, these algorithms work relative to 𝐴⊆𝑋."}],"scopus_import":"1","date_updated":"2025-07-10T11:53:32Z","doi":"10.1007/s10208-019-09419-x","date_created":"2019-06-16T21:59:14Z","external_id":{"arxiv":["1312.2337"],"isi":["000522437400004"]},"article_type":"original","citation":{"apa":"Filakovský, M., &#38; Vokřínek, L. (2020). Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>","ista":"Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic viewpoint. Foundations of Computational Mathematics. 20, 311–330.","mla":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>, vol. 20, Springer Nature, 2020, pp. 311–30, doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>.","short":"M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020) 311–330.","ama":"Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint. <i>Foundations of Computational Mathematics</i>. 2020;20:311-330. doi:<a href=\"https://doi.org/10.1007/s10208-019-09419-x\">10.1007/s10208-019-09419-x</a>","ieee":"M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic viewpoint,” <i>Foundations of Computational Mathematics</i>, vol. 20. Springer Nature, pp. 311–330, 2020.","chicago":"Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic Viewpoint.” <i>Foundations of Computational Mathematics</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s10208-019-09419-x\">https://doi.org/10.1007/s10208-019-09419-x</a>."},"main_file_link":[{"url":"https://arxiv.org/abs/1312.2337","open_access":"1"}],"_id":"6563","article_processing_charge":"No","day":"01","publisher":"Springer Nature","publication":"Foundations of Computational Mathematics","project":[{"grant_number":"P31312","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory"}],"date_published":"2020-04-01T00:00:00Z","department":[{"_id":"UlWa"}],"month":"04","year":"2020","type":"journal_article","publication_identifier":{"eissn":["1615-3383"],"issn":["1615-3375"]},"intvolume":"        20","author":[{"first_name":"Marek","full_name":"Filakovský, Marek","last_name":"Filakovský","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Vokřínek","first_name":"Lukas","full_name":"Vokřínek, Lukas"}],"oa":1,"status":"public","isi":1,"publication_status":"published","quality_controlled":"1","volume":20,"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"page":"311-330","title":"Are two given maps homotopic? An algorithmic viewpoint","arxiv":1},{"article_processing_charge":"No","status":"public","_id":"8182","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.12628"}],"citation":{"ista":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. arXiv, 1910.12628.","mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>ArXiv</i>, 1910.12628, doi:<a href=\"https://doi.org/10.48550/arXiv.1910.12628\">10.48550/arXiv.1910.12628</a>.","chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.1910.12628\">https://doi.org/10.48550/arXiv.1910.12628</a>.","ieee":"S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and the mapping degree,” <i>arXiv</i>. .","ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.1910.12628\">10.48550/arXiv.1910.12628</a>","short":"S. Avvakumov, S. Kudrya, ArXiv (n.d.).","apa":"Avvakumov, S., &#38; Kudrya, S. (n.d.). Vanishing of all equivariant obstructions and the mapping degree. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.1910.12628\">https://doi.org/10.48550/arXiv.1910.12628</a>"},"external_id":{"arxiv":["1910.12628"]},"date_created":"2020-07-30T10:45:08Z","doi":"10.48550/arXiv.1910.12628","oa":1,"date_updated":"2026-04-08T07:25:54Z","author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7840-5062","last_name":"Avvakumov"},{"first_name":"Sergey","full_name":"Kudrya, Sergey","last_name":"Kudrya","id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67"}],"related_material":{"record":[{"id":"11446","status":"public","relation":"later_version"},{"status":"public","relation":"dissertation_contains","id":"8156"}]},"abstract":[{"text":"Suppose that $n\\neq p^k$ and $n\\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\\mathfrak S_n$ there exists an $\\mathfrak S_n$-equivariant map $X \\to\r\n{\\mathbb R}^n$ whose image avoids the diagonal $\\{(x,x\\dots,x)\\in {\\mathbb R}^n|x\\in {\\mathbb R}\\}$.\r\n  Previously, the special cases of this statement for certain $X$ were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We\r\ntake a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of $\\mathfrak S_n$-equivariant maps from the boundary\r\n$\\partial\\Delta^{n-1}$ of $(n-1)$-simplex to itself.  Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result  applying it to one such question, a specific instance of envy-free division problem.","lang":"eng"}],"arxiv":1,"title":"Vanishing of all equivariant obstructions and the mapping degree","corr_author":"1","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"preprint","oa_version":"Preprint","year":"2019","month":"10","department":[{"_id":"UlWa"}],"project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"}],"article_number":"1910.12628","date_published":"2019-10-28T00:00:00Z","publication":"arXiv","day":"28","publication_status":"draft"},{"citation":{"apa":"Avvakumov, S., Karasev, R., &#38; Skopenkov, A. (n.d.). Stronger counterexamples to the topological Tverberg conjecture. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.1908.08731\">https://doi.org/10.48550/arXiv.1908.08731</a>","chicago":"Avvakumov, Sergey, R. Karasev, and A. Skopenkov. “Stronger Counterexamples to the Topological Tverberg Conjecture.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.1908.08731\">https://doi.org/10.48550/arXiv.1908.08731</a>.","ieee":"S. Avvakumov, R. Karasev, and A. Skopenkov, “Stronger counterexamples to the topological Tverberg conjecture,” <i>arXiv</i>. .","short":"S. Avvakumov, R. Karasev, A. Skopenkov, ArXiv (n.d.).","ama":"Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological Tverberg conjecture. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.1908.08731\">10.48550/arXiv.1908.08731</a>","ista":"Avvakumov S, Karasev R, Skopenkov A. Stronger counterexamples to the topological Tverberg conjecture. arXiv, 1908.08731.","mla":"Avvakumov, Sergey, et al. “Stronger Counterexamples to the Topological Tverberg Conjecture.” <i>ArXiv</i>, 1908.08731, doi:<a href=\"https://doi.org/10.48550/arXiv.1908.08731\">10.48550/arXiv.1908.08731</a>."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.08731"}],"status":"public","_id":"8184","isi":1,"article_processing_charge":"No","oa":1,"doi":"10.48550/arXiv.1908.08731","acknowledgement":"We would like to thank F. Frick for helpful discussions","external_id":{"arxiv":["1908.08731"],"isi":["000986519600004"]},"date_created":"2020-07-30T10:45:34Z","related_material":{"record":[{"id":"8156","status":"public","relation":"dissertation_contains"}]},"author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7840-5062","last_name":"Avvakumov","full_name":"Avvakumov, Sergey","first_name":"Sergey"},{"first_name":"R.","full_name":"Karasev, R.","last_name":"Karasev"},{"full_name":"Skopenkov, A.","first_name":"A.","last_name":"Skopenkov"}],"date_updated":"2026-04-08T07:25:54Z","abstract":[{"lang":"eng","text":"Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l\r\nd + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps. "}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"preprint","language":[{"iso":"eng"}],"title":"Stronger counterexamples to the topological Tverberg conjecture","arxiv":1,"department":[{"_id":"UlWa"}],"month":"08","year":"2019","oa_version":"Preprint","publication":"arXiv","date_published":"2019-08-23T00:00:00Z","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory"}],"article_number":"1908.08731","publication_status":"draft","day":"23"},{"language":[{"iso":"eng"}],"type":"preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"corr_author":"1","title":"Envy-free division using mapping degree","year":"2019","department":[{"_id":"UlWa"}],"month":"07","oa_version":"Preprint","publication":"arXiv","project":[{"name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425","grant_number":"P31312"}],"article_number":"1907.11183","date_published":"2019-07-25T00:00:00Z","publication_status":"draft","day":"25","status":"public","_id":"8185","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1907.11183"}],"citation":{"apa":"Avvakumov, S., &#38; Karasev, R. (n.d.). Envy-free division using mapping degree. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.1907.11183\">https://doi.org/10.48550/arXiv.1907.11183</a>","mla":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” <i>ArXiv</i>, 1907.11183, doi:<a href=\"https://doi.org/10.48550/arXiv.1907.11183\">10.48550/arXiv.1907.11183</a>.","ista":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.","ieee":"S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” <i>arXiv</i>. .","ama":"Avvakumov S, Karasev R. Envy-free division using mapping degree. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.1907.11183\">10.48550/arXiv.1907.11183</a>","chicago":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.1907.11183\">https://doi.org/10.48550/arXiv.1907.11183</a>.","short":"S. Avvakumov, R. Karasev, ArXiv (n.d.)."},"article_processing_charge":"No","doi":"10.48550/arXiv.1907.11183","oa":1,"external_id":{"arxiv":["1907.11183"]},"date_created":"2020-07-30T10:45:51Z","related_material":{"link":[{"url":"https://doi.org/10.1112/mtk.12059","relation":"later_version"}],"record":[{"id":"8156","status":"public","relation":"dissertation_contains"}]},"date_updated":"2026-04-08T07:25:54Z","author":[{"full_name":"Avvakumov, Sergey","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","last_name":"Avvakumov","orcid":"0000-0002-7840-5062"},{"last_name":"Karasev","full_name":"Karasev, Roman","first_name":"Roman"}],"abstract":[{"text":"In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition.\r\n  We follow Erel Segal-Halevi, Fr\\'ed\\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment\r\npartition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.","lang":"eng"}]}]