[{"status":"public","publication_status":"published","file":[{"content_type":"application/pdf","success":1,"file_name":"2026_TransactionsGraphics_Filakovsky.pdf","date_created":"2026-07-06T09:03:02Z","checksum":"0399ab94085878fc810084845eabd627","file_size":941518,"date_updated":"2026-07-06T09:03:02Z","relation":"main_file","creator":"dernst","file_id":"22252","access_level":"open_access"}],"abstract":[{"lang":"eng","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)."}],"das_tickbox":"0","intvolume":"        18","PlanS_conform":"1","article_processing_charge":"Yes","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","has_accepted_license":"1","year":"2026","scopus_import":"1","publication":"ACM Transactions on Computation Theory","day":"04","supplementarymaterial":"no","volume":18,"article_number":"10","department":[{"_id":"UlWa"}],"arxiv":1,"OA_type":"gold","ec_funded":1,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"article_type":"original","date_updated":"2026-07-06T09:06:29Z","researchdata_availability":"no","oa":1,"keyword":["Constraint satisfaction problem","hypergraph colouring","promise problem","topological methods"],"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","issue":"2","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.","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>.","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>","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>.","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."},"author":[{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Filakovský, Marek","last_name":"Filakovský"},{"last_name":"Nakajima","full_name":"Nakajima, Tamio Vesa","first_name":"Tamio Vesa"},{"last_name":"Opršal","full_name":"Opršal, Jakub","first_name":"Jakub","orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242"},{"last_name":"Tasinato","full_name":"Tasinato, Gianluca","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568"}],"OA_place":"publisher","_id":"22247","date_created":"2026-07-05T22:01:37Z","oa_version":"Published Version","month":"05","ddc":["500"],"publication_identifier":{"issn":["1942-3454"],"eissn":["1942-3462"]},"project":[{"grant_number":"P31312","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"external_id":{"arxiv":["2312.12981"]},"type":"journal_article","file_date_updated":"2026-07-06T09:03:02Z","doi":"10.1145/3779121","related_material":{"record":[{"status":"public","id":"15168","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"date_published":"2026-05-04T00:00:00Z","publisher":"Association for Computing Machinery"},{"OA_place":"publisher","_id":"19860","acknowledgement":"BA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work. Open Access funding enabled and organized by CAUL and its Member Institutions.","citation":{"mla":"Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>Discrete &#38; Computational Geometry</i>, Springer Nature, 2025, doi:<a href=\"https://doi.org/10.1007/s00454-025-00739-0\">10.1007/s00454-025-00739-0</a>.","apa":"Aronov, B., Basit, A., Ramesh, I., Tasinato, G., &#38; Wagner, U. (2025). Eight-partitioning points in 3D, and efficiently too. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-025-00739-0\">https://doi.org/10.1007/s00454-025-00739-0</a>","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2025. Eight-partitioning points in 3D, and efficiently too. Discrete &#38; Computational Geometry.","ama":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. Eight-partitioning points in 3D, and efficiently too. <i>Discrete &#38; Computational Geometry</i>. 2025. doi:<a href=\"https://doi.org/10.1007/s00454-025-00739-0\">10.1007/s00454-025-00739-0</a>","chicago":"Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s00454-025-00739-0\">https://doi.org/10.1007/s00454-025-00739-0</a>.","ieee":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning points in 3D, and efficiently too,” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2025.","short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, Discrete &#38; Computational Geometry (2025)."},"author":[{"full_name":"Aronov, Boris","first_name":"Boris","last_name":"Aronov"},{"full_name":"Basit, Abdul","first_name":"Abdul","last_name":"Basit"},{"full_name":"Ramesh, Indu","first_name":"Indu","last_name":"Ramesh"},{"last_name":"Tasinato","full_name":"Tasinato, Gianluca","first_name":"Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner"}],"date_updated":"2026-06-18T18:18:28Z","article_type":"original","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","related_material":{"link":[{"relation":"erratum","url":"https://doi.org/10.1007/s00454-025-00759-w"}],"record":[{"id":"18917","relation":"earlier_version","status":"public"},{"id":"20339","relation":"dissertation_contains","status":"public"}]},"language":[{"iso":"eng"}],"date_published":"2025-06-12T00:00:00Z","publisher":"Springer Nature","type":"journal_article","doi":"10.1007/s00454-025-00739-0","ddc":["500"],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"external_id":{"isi":["001506904300001"],"arxiv":["2403.02627"]},"date_created":"2025-06-22T22:02:07Z","oa_version":"Published Version","month":"06","article_processing_charge":"Yes (via OA deal)","status":"public","isi":1,"abstract":[{"text":"An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R^3\r\n consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R^3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R^3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R^3 (with prescribed normal direction of one of the planes) in time O(n^7/3). A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).","lang":"eng"}],"publication_status":"epub_ahead","OA_type":"hybrid","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00454-025-00739-0"}],"department":[{"_id":"UlWa"}],"publication":"Discrete & Computational Geometry","day":"12","title":"Eight-partitioning points in 3D, and efficiently too","scopus_import":"1","year":"2025"},{"date_published":"2025-06-15T00:00:00Z","publisher":"Association for Computing Machinery","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"20339","relation":"dissertation_contains","status":"public"}]},"doi":"10.1145/3717823.3718154","file_date_updated":"2025-07-14T06:42:58Z","conference":{"start_date":"2025-06-23","name":"STOC: Symposium on Theory of Computing","end_date":"2025-06-27","location":"Prague, Czechia"},"type":"conference","project":[{"call_identifier":"FWF","grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","_id":"26611F5C-B435-11E9-9278-68D0E5697425"},{"call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"ddc":["000"],"publication_identifier":{"isbn":["9798400715105"],"issn":["0737-8017"]},"month":"06","date_created":"2025-07-13T22:01:23Z","oa_version":"Published Version","_id":"20008","OA_place":"publisher","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7840-5062","full_name":"Avvakumov, Sergey","first_name":"Sergey","last_name":"Avvakumov"},{"id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","full_name":"Filakovský, Marek","last_name":"Filakovský"},{"id":"ec596741-c539-11ec-b829-c79322a91242","last_name":"Opršal","full_name":"Opršal, Jakub","first_name":"Jakub","orcid":"0000-0003-1245-3456"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","full_name":"Tasinato, Gianluca","first_name":"Gianluca","last_name":"Tasinato"},{"first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"citation":{"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>.","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>","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.","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>","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>.","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.","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."},"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.","oa":1,"date_updated":"2026-04-07T12:36:50Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"corr_author":"1","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"OA_type":"hybrid","department":[{"_id":"UlWa"}],"day":"15","publication":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing","scopus_import":"1","year":"2025","title":"Hardness of 4-colouring G-colourable graphs","has_accepted_license":"1","page":"72-83","article_processing_charge":"Yes (in subscription journal)","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."}],"file":[{"file_id":"20013","creator":"dernst","access_level":"open_access","file_name":"2025_STOC_Avvakumov.pdf","date_created":"2025-07-14T06:42:58Z","content_type":"application/pdf","success":1,"relation":"main_file","date_updated":"2025-07-14T06:42:58Z","file_size":940827,"checksum":"2c9ae7ad0102c41124976f4cb5182760"}],"publication_status":"published","status":"public"},{"article_processing_charge":"No","page":"106","abstract":[{"lang":"eng","text":"This thesis investigates the interplay between algebraic and topological methods and combinatorial problems, focusing on approximate graph colourings and mass partitioning. The unifying theme throughout the dissertation is the use of continuous maps and symmetry constraints to extract combinatorial insights.\r\n\r\nWe first explore approximate graph colouring problems and more generally promise constraint satisfaction problems. Using tools from equivariant topology in combination with the general theory of polymorphism of a promise constraint satisfaction problem, we establish hardness for specific types of approximations.\r\n\r\nIn the second part, we address mass partitioning problems, where one seeks to divide geometric objects or measures in Euclidean space into parts of equal size using hyperplanes. Employing techniques from topological combinatorics (configuration space/test map setup and Borsuk–Ulam type theorems), we both obtain a new equipartitioning result in the and provide a fast algorithm for computing equipartitioning of point sets in 3D.\r\n"}],"publication_status":"published","file":[{"access_level":"closed","creator":"gtasinat","file_id":"20344","checksum":"ae097a515b9bb4d4b025ca854ae2ed76","file_size":2218562,"relation":"source_file","date_updated":"2025-09-11T12:24:12Z","content_type":"application/x-zip-compressed","date_created":"2025-09-11T12:24:12Z","file_name":"thesis-source.zip"},{"creator":"gtasinat","file_id":"20345","access_level":"open_access","success":1,"content_type":"application/pdf","file_name":"2025_Tasinato_Gianluca_Thesis.pdf","date_created":"2025-09-11T12:26:14Z","checksum":"04b2e016409e52167ce42b0eef839fbf","relation":"main_file","file_size":10071982,"date_updated":"2025-09-11T12:26:14Z"}],"status":"public","department":[{"_id":"GradSch"},{"_id":"UlWa"}],"alternative_title":["ISTA Thesis"],"degree_awarded":"PhD","year":"2025","title":"Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems","has_accepted_license":"1","day":"10","author":[{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca","full_name":"Tasinato, Gianluca","last_name":"Tasinato"}],"citation":{"mla":"Tasinato, Gianluca. <i>Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20339\">10.15479/AT-ISTA-20339</a>.","apa":"Tasinato, G. (2025). <i>Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20339\">https://doi.org/10.15479/AT-ISTA-20339</a>","ista":"Tasinato G. 2025. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. Institute of Science and Technology Austria.","ama":"Tasinato G. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20339\">10.15479/AT-ISTA-20339</a>","chicago":"Tasinato, Gianluca. “Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20339\">https://doi.org/10.15479/AT-ISTA-20339</a>.","ieee":"G. Tasinato, “Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems,” Institute of Science and Technology Austria, 2025.","short":"G. Tasinato, Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems, Institute of Science and Technology Austria, 2025."},"_id":"20339","OA_place":"publisher","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","supervisor":[{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"oa":1,"tmp":{"name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode"},"date_updated":"2026-06-18T18:18:27Z","doi":"10.15479/AT-ISTA-20339","file_date_updated":"2025-09-11T12:26:14Z","type":"dissertation","date_published":"2025-09-10T00:00:00Z","publisher":"Institute of Science and Technology Austria","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"20008","relation":"part_of_dissertation","status":"public"},{"status":"public","id":"15168","relation":"part_of_dissertation"},{"id":"19860","relation":"part_of_dissertation","status":"public"}]},"month":"09","date_created":"2025-09-10T12:17:55Z","oa_version":"Published Version","ddc":["516"],"publication_identifier":{"issn":["2663-337X"]}},{"volume":293,"department":[{"_id":"UlWa"},{"_id":"GradSch"}],"OA_type":"gold","arxiv":1,"has_accepted_license":"1","title":"Eight-partitioning points in 3D, and efficiently too","scopus_import":"1","year":"2024","publication":"40th International Symposium on Computational Geometry","day":"06","article_processing_charge":"Yes","page":"8:1-8:15","status":"public","file":[{"relation":"main_file","date_updated":"2025-01-27T14:17:37Z","file_size":880725,"checksum":"443aa29ea5d948e917cfccd681dcf176","file_name":"2024_LIPICs_Aronov.pdf","date_created":"2025-01-27T14:17:37Z","content_type":"application/pdf","success":1,"access_level":"open_access","file_id":"18918","creator":"dernst"}],"abstract":[{"lang":"eng","text":"An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument.\r\nWe prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction.\r\nMoreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2})."}],"publication_status":"published","intvolume":"       293","type":"conference","file_date_updated":"2025-01-27T14:17:37Z","conference":{"start_date":"2024-06-11","name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14","location":"Athens, Greece"},"doi":"10.4230/LIPIcs.SoCG.2024.8","related_material":{"record":[{"id":"19860","relation":"later_version","status":"public"}]},"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2024-06-06T00:00:00Z","date_created":"2025-01-27T14:19:17Z","oa_version":"Published Version","month":"06","publication_identifier":{"isbn":["9783959773164"]},"ddc":["510"],"external_id":{"arxiv":["2403.02627"]},"acknowledgement":"Aronov, Boris: Work has been supported by NSF grants CCF 15-40656 and CCF 20-08551, and by grant 2014/170 from the US-Israel Binational Science Foundation. Part of this research was conducted while BA was visiting ISTA in the summers of 2022 and 2023. The visit of BA to ISTA in the summer of 2022 was supported by an ISTA Visiting Professorship.\r\nBasit, Abdul: Work has been supported by Australian Research Council grant DP220102212.\r\nRamesh, Indu: Work supported by a Tandon School of Engineering Fellowship and by NSF Grant CCF-20-08551.\r\nBA and AB would like to thank William Steiger for insightful initial discussions of the problems addressed in this work.","citation":{"short":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15.","ieee":"B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning points in 3D, and efficiently too,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293, p. 8:1-8:15.","ama":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. Eight-partitioning points in 3D, and efficiently too. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:8:1-8:15. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>","ista":"Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2024. Eight-partitioning points in 3D, and efficiently too. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 293, 8:1-8:15.","chicago":"Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner. “Eight-Partitioning Points in 3D, and Efficiently Too.” In <i>40th International Symposium on Computational Geometry</i>, 293:8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>.","mla":"Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">10.4230/LIPIcs.SoCG.2024.8</a>.","apa":"Aronov, B., Basit, A., Ramesh, I., Tasinato, G., &#38; Wagner, U. (2024). Eight-partitioning points in 3D, and efficiently too. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293, p. 8:1-8:15). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.8\">https://doi.org/10.4230/LIPIcs.SoCG.2024.8</a>"},"author":[{"last_name":"Aronov","first_name":"Boris","full_name":"Aronov, Boris"},{"last_name":"Basit","full_name":"Basit, Abdul","first_name":"Abdul"},{"last_name":"Ramesh","first_name":"Indu","full_name":"Ramesh, Indu"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato","first_name":"Gianluca","full_name":"Tasinato, Gianluca"},{"orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"OA_place":"publisher","_id":"18917","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_updated":"2026-06-18T18:18:27Z","oa":1},{"date_created":"2024-03-24T23:00:59Z","oa_version":"Published Version","month":"03","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"ddc":["510"],"project":[{"_id":"26611F5C-B435-11E9-9278-68D0E5697425","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","grant_number":"P31312"},{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"external_id":{"arxiv":["2312.12981"],"isi":["001300393400034"]},"type":"conference","file_date_updated":"2024-03-25T07:44:30Z","conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2024-03-12","location":"Clermont-Ferrand, France","end_date":"2024-03-14"},"doi":"10.4230/LIPIcs.STACS.2024.34","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"20339"},{"id":"22247","relation":"later_version","status":"public"}]},"language":[{"iso":"eng"}],"date_published":"2024-03-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_updated":"2026-07-06T09:06:29Z","oa":1,"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).","citation":{"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.","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.","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.","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>","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>.","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>","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>."},"author":[{"last_name":"Filakovský","first_name":"Marek","full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Nakajima","first_name":"Tamio Vesa","full_name":"Nakajima, Tamio Vesa"},{"orcid":"0000-0003-1245-3456","full_name":"Opršal, Jakub","first_name":"Jakub","last_name":"Opršal","id":"ec596741-c539-11ec-b829-c79322a91242"},{"id":"0433290C-AF8F-11E9-A4C7-F729E6697425","last_name":"Tasinato","first_name":"Gianluca","full_name":"Tasinato, Gianluca"},{"orcid":"0000-0002-1494-0568","first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"_id":"15168","has_accepted_license":"1","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","scopus_import":"1","year":"2024","publication":"41st International Symposium on Theoretical Aspects of Computer Science","day":"01","article_number":"34","volume":289,"department":[{"_id":"UlWa"}],"arxiv":1,"ec_funded":1,"alternative_title":["LIPIcs"],"isi":1,"status":"public","publication_status":"published","file":[{"file_size":927290,"date_updated":"2024-03-25T07:44:30Z","relation":"main_file","checksum":"0524d4189fd1ed08989546511343edf3","date_created":"2024-03-25T07:44:30Z","file_name":"2024_LIPICs_Filakovsky.pdf","success":1,"content_type":"application/pdf","access_level":"open_access","file_id":"15175","creator":"dernst"}],"abstract":[{"lang":"eng","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)."}],"intvolume":"       289","article_processing_charge":"No"}]