---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22247'
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)."
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"
article_number: '10'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Tamio Vesa
  full_name: Nakajima, Tamio Vesa
  last_name: Nakajima
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly
    ordered 4-colouring of 3-colourable 3-uniform hypergraphs. <i>ACM Transactions
    on Computation Theory</i>. 2026;18(2). 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>
  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>.
  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.
  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.
  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>.
  short: M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, ACM Transactions
    on Computation Theory 18 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-05T22:01:37Z
date_published: 2026-05-04T00:00:00Z
date_updated: 2026-07-06T09:06:29Z
day: '04'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.1145/3779121
ec_funded: 1
external_id:
  arxiv:
  - '2312.12981'
file:
- access_level: open_access
  checksum: 0399ab94085878fc810084845eabd627
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-06T09:03:02Z
  date_updated: 2026-07-06T09:03:02Z
  file_id: '22252'
  file_name: 2026_TransactionsGraphics_Filakovsky.pdf
  file_size: 941518
  relation: main_file
  success: 1
file_date_updated: 2026-07-06T09:03:02Z
has_accepted_license: '1'
intvolume: '        18'
issue: '2'
keyword:
- Constraint satisfaction problem
- hypergraph colouring
- promise problem
- topological methods
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: ACM Transactions on Computation Theory
publication_identifier:
  eissn:
  - 1942-3462
  issn:
  - 1942-3454
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '15168'
    relation: earlier_version
    status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
tmp:
  image: /images/cc_by.png
  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)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 18
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19860'
abstract:
- lang: eng
  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)."
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.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Boris
  full_name: Aronov, Boris
  last_name: Aronov
- first_name: Abdul
  full_name: Basit, Abdul
  last_name: Basit
- first_name: Indu
  full_name: Ramesh, Indu
  last_name: Ramesh
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  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>
  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>
  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.
  ista: Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2025. Eight-partitioning
    points in 3D, and efficiently too. Discrete &#38; Computational Geometry.
  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>.
  short: B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, Discrete &#38; Computational
    Geometry (2025).
date_created: 2025-06-22T22:02:07Z
date_published: 2025-06-12T00:00:00Z
date_updated: 2026-06-18T18:18:28Z
day: '12'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.1007/s00454-025-00739-0
external_id:
  arxiv:
  - '2403.02627'
  isi:
  - '001506904300001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00454-025-00739-0
month: '06'
oa: 1
oa_version: Published Version
publication: Discrete & Computational Geometry
publication_identifier:
  eissn:
  - 1432-0444
  issn:
  - 0179-5376
publication_status: epub_ahead
publisher: Springer Nature
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
scopus_import: '1'
status: public
title: Eight-partitioning points in 3D, and efficiently too
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20008'
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.'
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.
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  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>'
  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>'
  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.
  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.'
  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.
conference:
  end_date: 2025-06-27
  location: Prague, Czechia
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2026-04-07T12:36:50Z
day: '15'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1145/3717823.3718154
ec_funded: 1
file:
- access_level: open_access
  checksum: 2c9ae7ad0102c41124976f4cb5182760
  content_type: application/pdf
  creator: dernst
  date_created: 2025-07-14T06:42:58Z
  date_updated: 2025-07-14T06:42:58Z
  file_id: '20013'
  file_name: 2025_STOC_Avvakumov.pdf
  file_size: 940827
  relation: main_file
  success: 1
file_date_updated: 2025-07-14T06:42:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 72-83
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9798400715105'
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
  record:
  - id: '20339'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Hardness of 4-colouring G-colourable graphs
tmp:
  image: /images/cc_by.png
  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)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
_id: '20339'
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"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
citation:
  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>'
  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>'
  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.'
  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.'
  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>.'
  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.'
corr_author: '1'
date_created: 2025-09-10T12:17:55Z
date_published: 2025-09-10T00:00:00Z
date_updated: 2026-06-18T18:18:27Z
day: '10'
ddc:
- '516'
degree_awarded: PhD
department:
- _id: GradSch
- _id: UlWa
doi: 10.15479/AT-ISTA-20339
file:
- access_level: closed
  checksum: ae097a515b9bb4d4b025ca854ae2ed76
  content_type: application/x-zip-compressed
  creator: gtasinat
  date_created: 2025-09-11T12:24:12Z
  date_updated: 2025-09-11T12:24:12Z
  file_id: '20344'
  file_name: thesis-source.zip
  file_size: 2218562
  relation: source_file
- access_level: open_access
  checksum: 04b2e016409e52167ce42b0eef839fbf
  content_type: application/pdf
  creator: gtasinat
  date_created: 2025-09-11T12:26:14Z
  date_updated: 2025-09-11T12:26:14Z
  file_id: '20345'
  file_name: 2025_Tasinato_Gianluca_Thesis.pdf
  file_size: 10071982
  relation: main_file
  success: 1
file_date_updated: 2025-09-11T12:26:14Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: '106'
publication_identifier:
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '20008'
    relation: part_of_dissertation
    status: public
  - id: '15168'
    relation: part_of_dissertation
    status: public
  - id: '19860'
    relation: part_of_dissertation
    status: public
status: public
supervisor:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
title: 'Topological methods in discrete geometry and theoretical computer science
  : Measure partitioning and constraint satisfaction problems'
tmp:
  image: /images/cc_by_nc_sa.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
    BY-NC-SA 4.0)
  short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '18917'
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})."
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."
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Boris
  full_name: Aronov, Boris
  last_name: Aronov
- first_name: Abdul
  full_name: Basit, Abdul
  last_name: Basit
- first_name: Indu
  full_name: Ramesh, Indu
  last_name: Ramesh
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2024-06-14
  location: Athens, Greece
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2024-06-11
corr_author: '1'
date_created: 2025-01-27T14:19:17Z
date_published: 2024-06-06T00:00:00Z
date_updated: 2026-06-18T18:18:27Z
day: '06'
ddc:
- '510'
department:
- _id: UlWa
- _id: GradSch
doi: 10.4230/LIPIcs.SoCG.2024.8
external_id:
  arxiv:
  - '2403.02627'
file:
- access_level: open_access
  checksum: 443aa29ea5d948e917cfccd681dcf176
  content_type: application/pdf
  creator: dernst
  date_created: 2025-01-27T14:17:37Z
  date_updated: 2025-01-27T14:17:37Z
  file_id: '18918'
  file_name: 2024_LIPICs_Aronov.pdf
  file_size: 880725
  relation: main_file
  success: 1
file_date_updated: 2025-01-27T14:17:37Z
has_accepted_license: '1'
intvolume: '       293'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 8:1-8:15
publication: 40th International Symposium on Computational Geometry
publication_identifier:
  isbn:
  - '9783959773164'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '19860'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Eight-partitioning points in 3D, and efficiently too
tmp:
  image: /images/cc_by.png
  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)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 293
year: '2024'
...
---
_id: '15168'
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).'
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)."
alternative_title:
- LIPIcs
article_number: '34'
article_processing_charge: No
arxiv: 1
author:
- first_name: Marek
  full_name: Filakovský, Marek
  id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
  last_name: Filakovský
- first_name: Tamio Vesa
  full_name: Nakajima, Tamio Vesa
  last_name: Nakajima
- first_name: Jakub
  full_name: Opršal, Jakub
  id: ec596741-c539-11ec-b829-c79322a91242
  last_name: Opršal
  orcid: 0000-0003-1245-3456
- first_name: Gianluca
  full_name: Tasinato, Gianluca
  id: 0433290C-AF8F-11E9-A4C7-F729E6697425
  last_name: Tasinato
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly
    ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: <i>41st International
    Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2024. doi:<a href="https://doi.org/10.4230/LIPIcs.STACS.2024.34">10.4230/LIPIcs.STACS.2024.34</a>'
  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>'
  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>.
  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.'
  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>.
  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.
conference:
  end_date: 2024-03-14
  location: Clermont-Ferrand, France
  name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
  start_date: 2024-03-12
corr_author: '1'
date_created: 2024-03-24T23:00:59Z
date_published: 2024-03-01T00:00:00Z
date_updated: 2026-07-06T09:06:29Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.STACS.2024.34
ec_funded: 1
external_id:
  arxiv:
  - '2312.12981'
  isi:
  - '001300393400034'
file:
- access_level: open_access
  checksum: 0524d4189fd1ed08989546511343edf3
  content_type: application/pdf
  creator: dernst
  date_created: 2024-03-25T07:44:30Z
  date_updated: 2024-03-25T07:44:30Z
  file_id: '15175'
  file_name: 2024_LIPICs_Filakovsky.pdf
  file_size: 927290
  relation: main_file
  success: 1
file_date_updated: 2024-03-25T07:44:30Z
has_accepted_license: '1'
intvolume: '       289'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: 41st International Symposium on Theoretical Aspects of Computer Science
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959773119'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '20339'
    relation: dissertation_contains
    status: public
  - id: '22247'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
tmp:
  image: /images/cc_by.png
  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)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 289
year: '2024'
...