---
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. ACM Transactions
on Computation Theory. 2026;18(2). doi:10.1145/3779121
apa: Filakovský, M., Nakajima, T. V., 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. Association for Computing Machinery.
https://doi.org/10.1145/3779121
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.” ACM Transactions on Computation Theory. Association for Computing
Machinery, 2026. https://doi.org/10.1145/3779121.
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,” ACM
Transactions on Computation Theory, 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.” ACM Transactions on Computation Theory, vol. 18,
no. 2, 10, Association for Computing Machinery, 2026, doi:10.1145/3779121.
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
license: https://creativecommons.org/licenses/by/4.0/
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
PlanS_conform: '1'
_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: Work by BA was 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. Research of BA also partially supported by ERC grant no. 882971,
“GeoScape,” and by the Erdős Center. Work by AB was supported by Australian Research
Council grant DP220102212. Work by IR was supported by a Tandon School of Engineering
Fellowship and by NSF Grant CCF-20-08551. 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. Discrete & Computational Geometry. 2026;75:1331-1355.
doi:10.1007/s00454-025-00739-0
apa: Aronov, B., Basit, A., Ramesh, I., Tasinato, G., & Wagner, U. (2026). Eight-partitioning
points in 3D, and efficiently too. Discrete & Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-025-00739-0
chicago: Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner.
“Eight-Partitioning Points in 3D, and Efficiently Too.” Discrete & Computational
Geometry. Springer Nature, 2026. https://doi.org/10.1007/s00454-025-00739-0.
ieee: B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning
points in 3D, and efficiently too,” Discrete & Computational Geometry,
vol. 75. Springer Nature, pp. 1331–1355, 2026.
ista: Aronov B, Basit A, Ramesh I, Tasinato G, Wagner U. 2026. Eight-partitioning
points in 3D, and efficiently too. Discrete & Computational Geometry. 75,
1331–1355.
mla: Aronov, Boris, et al. “Eight-Partitioning Points in 3D, and Efficiently Too.”
Discrete & Computational Geometry, vol. 75, Springer Nature, 2026,
pp. 1331–55, doi:10.1007/s00454-025-00739-0.
short: B. Aronov, A. Basit, I. Ramesh, G. Tasinato, U. Wagner, Discrete & Computational
Geometry 75 (2026) 1331–1355.
das_tickbox: '0'
date_created: 2025-06-22T22:02:07Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-07-29T13:13:17Z
day: '01'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.1007/s00454-025-00739-0
external_id:
arxiv:
- '2403.02627'
isi:
- '001506904300001'
file:
- access_level: open_access
checksum: a32774a0d14f46cafbd77bfb9d9ac4b6
content_type: application/pdf
creator: dernst
date_created: 2026-07-23T11:14:05Z
date_updated: 2026-07-23T11:14:05Z
file_id: '22395'
file_name: 2026_DiscreteCompGeom_Aronov.pdf
file_size: 525281
relation: main_file
success: 1
file_date_updated: 2026-07-23T11:14:05Z
has_accepted_license: '1'
intvolume: ' 75'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1331-1355
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
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
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 75
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '20004'
abstract:
- lang: eng
text: "A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize
McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due
to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level
in a simple arrangement of n hemispheres in S^d is maximized for arrangements
that are polar duals of neighborly d-polytopes. We prove this conjecture in the
case n = d+4. By Gale duality, this implies the following result about crossing
numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of
n unit vectors connected by spherical arcs), the number of crossings is at least
1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every
open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.\r\nMoreover,
we determine the space of all linear and affine relations that hold between the
face numbers of levels in simple arrangements of n hemispheres in S^d. This completes
a long line of research on such relations, answers a question posed by Andrzejak
and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville
relations generate all linear relations between the face numbers of simple polytopes
(which correspond to the 0-level).\r\nTo prove these results, we introduce the
notion of the g-matrix, which encodes the face numbers of levels in an arrangement
and generalizes the classical g-vector of a polytope."
alternative_title:
- LIPIcs
article_number: '75'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Elizaveta
full_name: Streltsova, Elizaveta
id: 57a170da-dc96-11ea-b7c8-ab3565071bf7
last_name: Streltsova
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix,
and applications to crossing numbers. In: 41st International Symposium on Computational
Geometry. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025.
doi:10.4230/LIPIcs.SoCG.2025.75'
apa: 'Streltsova, E., & Wagner, U. (2025). Levels in arrangements: Linear relations,
the g-matrix, and applications to crossing numbers. In 41st International Symposium
on Computational Geometry (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2025.75'
chicago: 'Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear
Relations, the g-Matrix, and Applications to Crossing Numbers.” In 41st International
Symposium on Computational Geometry, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SoCG.2025.75.'
ieee: 'E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the
g-matrix, and applications to crossing numbers,” in 41st International Symposium
on Computational Geometry, Kanazawa, Japan, 2025, vol. 332.'
ista: 'Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the
g-matrix, and applications to crossing numbers. 41st International Symposium on
Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol.
332, 75.'
mla: 'Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations,
the g-Matrix, and Applications to Crossing Numbers.” 41st International Symposium
on Computational Geometry, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.SoCG.2025.75.'
short: E. Streltsova, U. Wagner, in:, 41st International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-06-27
location: Kanazawa, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2025-06-23
corr_author: '1'
das_tickbox: '1'
date_created: 2025-07-13T22:01:22Z
date_published: 2025-06-20T00:00:00Z
date_updated: 2026-07-07T13:03:16Z
day: '20'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2025.75
external_id:
arxiv:
- '2504.07752'
- '2504.07770'
file:
- access_level: open_access
checksum: a8f7feb1aa3b896e31195841a989d622
content_type: application/pdf
creator: dernst
date_created: 2025-07-14T07:11:04Z
date_updated: 2025-07-14T07:11:04Z
file_id: '20015'
file_name: 2025_LIPIcs.SoCG_Streltsova.pdf
file_size: 952807
relation: main_file
success: 1
file_date_updated: 2025-07-14T07:11:04Z
has_accepted_license: '1'
intvolume: ' 332'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 41st International Symposium on Computational Geometry
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959773706'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Levels in arrangements: Linear relations, the g-matrix, and applications to
crossing numbers'
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: 332
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: Proceedings of the 57th Annual ACM Symposium on Theory
of Computing. Association for Computing Machinery; 2025:72-83. doi:10.1145/3717823.3718154'
apa: 'Avvakumov, S., Filakovský, M., Opršal, J., Tasinato, G., & Wagner, U.
(2025). Hardness of 4-colouring G-colourable graphs. In Proceedings of the
57th Annual ACM Symposium on Theory of Computing (pp. 72–83). Prague, Czechia:
Association for Computing Machinery. https://doi.org/10.1145/3717823.3718154'
chicago: Avvakumov, Sergey, Marek Filakovský, Jakub Opršal, Gianluca Tasinato, and
Uli Wagner. “Hardness of 4-Colouring G-Colourable Graphs.” In Proceedings of
the 57th Annual ACM Symposium on Theory of Computing, 72–83. Association for
Computing Machinery, 2025. https://doi.org/10.1145/3717823.3718154.
ieee: S. Avvakumov, M. Filakovský, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of 4-colouring G-colourable graphs,” in Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, 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.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 72–83, doi:10.1145/3717823.3718154.
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-07-29T13:13:17Z
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: repository
OA_type: green
_id: '13974'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition
X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common
point. In this paper, we prove a trengthening of this theorem that guarantees
a partition which, in addition to the above, has the property that the boundaries
of full-dimensional convex hulls have pairwise nonempty intersections. Possible
generalizations and algorithmic aspects are also discussed. As a concrete application,
we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint
triangles that are pairwise crossing, meaning that their boundaries have pairwise
nonempty intersections; this number is clearly best possible. A previous result
of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result
generalizes to a result about simplices in Rd, d≥2.
acknowledgement: "Part of the research leading to this paper was done during the 16th
Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018.
We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte
Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank
Stefan Felsner and Manfred Scheucher for finding, communicating the example from
Sect. 3.3, and the kind permission to include their visualization of the point set.
We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful
comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund
(FWF), Project M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility
Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P.
Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation
(GAČR)."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem.
Discrete and Computational Geometry. 2024;72:831-848. doi:10.1007/s00454-023-00532-x
apa: Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2024).
The crossing Tverberg theorem. Discrete and Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-023-00532-x
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry.
Springer Nature, 2024. https://doi.org/10.1007/s00454-023-00532-x.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” Discrete and Computational Geometry, vol. 72. Springer
Nature, pp. 831–848, 2024.
ista: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2024. The crossing Tverberg
theorem. Discrete and Computational Geometry. 72, 831–848.
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational
Geometry, vol. 72, Springer Nature, 2024, pp. 831–48, doi:10.1007/s00454-023-00532-x.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational
Geometry 72 (2024) 831–848.
date_created: 2023-08-06T22:01:12Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-04-14T13:52:36Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-023-00532-x
external_id:
arxiv:
- '1812.04911'
isi:
- '001038546500001'
intvolume: ' 72'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1812.04911
month: '09'
oa: 1
oa_version: Preprint
page: 831-848
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '6647'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The crossing Tverberg theorem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 72
year: '2024'
...
---
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: 40th International Symposium on Computational
Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:8:1-8:15.
doi:10.4230/LIPIcs.SoCG.2024.8'
apa: 'Aronov, B., Basit, A., Ramesh, I., Tasinato, G., & Wagner, U. (2024).
Eight-partitioning points in 3D, and efficiently too. In 40th International
Symposium on Computational Geometry (Vol. 293, p. 8:1-8:15). Athens, Greece:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.8'
chicago: Aronov, Boris, Abdul Basit, Indu Ramesh, Gianluca Tasinato, and Uli Wagner.
“Eight-Partitioning Points in 3D, and Efficiently Too.” In 40th International
Symposium on Computational Geometry, 293:8:1-8:15. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.8.
ieee: B. Aronov, A. Basit, I. Ramesh, G. Tasinato, and U. Wagner, “Eight-partitioning
points in 3D, and efficiently too,” in 40th International Symposium on Computational
Geometry, 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.”
40th International Symposium on Computational Geometry, vol. 293, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 8:1-8:15, doi:10.4230/LIPIcs.SoCG.2024.8.
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-07-23T11:14:45Z
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: 41st International
Symposium on Theoretical Aspects of Computer Science. Vol 289. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.STACS.2024.34'
apa: 'Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U.
(2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.
In 41st International Symposium on Theoretical Aspects of Computer Science
(Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.STACS.2024.34'
chicago: Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato,
and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform
Hypergraphs.” In 41st International Symposium on Theoretical Aspects of Computer
Science, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.STACS.2024.34.
ieee: M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in 41st
International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand,
France, 2024, vol. 289.
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.” 41st International Symposium on Theoretical Aspects
of Computer Science, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.STACS.2024.34.
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-29T13:13:17Z
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: '22247'
relation: later_version
status: public
- id: '20339'
relation: dissertation_contains
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'
...
---
_id: '14445'
abstract:
- lang: eng
text: "We prove the following quantitative Borsuk–Ulam-type result (an equivariant
analogue of Gromov’s Topological Overlap Theorem): Let X be a free ℤ/2-complex
of dimension d with coboundary expansion at least ηk in dimension 0 ≤ k < d. Then
for every equivariant map F: X →ℤ/2 ℝd, the fraction of d-simplices σ of X with
0 ∈ F (σ) is at least 2−d Π d−1k=0ηk.\r\n\r\nAs an application, we show that for
every sufficiently thick d-dimensional spherical building Y and every map f: Y
→ ℝ2d, we have f(σ) ∩ f(τ) ≠ ∅ for a constant fraction μd > 0 of pairs {σ, τ}
of d-simplices of Y. In particular, such complexes are non-embeddable into ℝ2d,
which proves a conjecture of Tancer and Vorwerk for sufficiently thick spherical
buildings.\r\n\r\nWe complement these results by upper bounds on the coboundary
expansion of two families of simplicial complexes; this indicates some limitations
to the bounds one can obtain by straighforward applications of the quantitative
Borsuk–Ulam theorem. Specifically, we prove\r\n\r\n• an upper bound of (d + 1)/2d
on the normalized (d − 1)-th coboundary expansion constant of complete (d + 1)-partite
d-dimensional complexes (under a mild divisibility assumption on the sizes of
the parts); and\r\n\r\n• an upper bound of (d + 1)/2d + ε on the normalized (d
− 1)-th coboundary expansion of the d-dimensional spherical building associated
with GLd+2(Fq) for any ε > 0 and sufficiently large q. This disproves, in a rather
strong sense, a conjecture of Lubotzky, Meshulam and Mozes."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Pascal
full_name: Wild, Pascal
id: 4C20D868-F248-11E8-B48F-1D18A9856A87
last_name: Wild
citation:
ama: Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers
of simplicial complexes. Israel Journal of Mathematics. 2023;256(2):675-717.
doi:10.1007/s11856-023-2521-9
apa: Wagner, U., & Wild, P. (2023). Coboundary expansion, equivariant overlap,
and crossing numbers of simplicial complexes. Israel Journal of Mathematics.
Springer Nature. https://doi.org/10.1007/s11856-023-2521-9
chicago: Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap,
and Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics.
Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2521-9.
ieee: U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing
numbers of simplicial complexes,” Israel Journal of Mathematics, vol. 256,
no. 2. Springer Nature, pp. 675–717, 2023.
ista: Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing
numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717.
mla: Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and
Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics,
vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:10.1007/s11856-023-2521-9.
short: U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.
corr_author: '1'
date_created: 2023-10-22T22:01:14Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2024-10-09T21:07:12Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s11856-023-2521-9
external_id:
isi:
- '001081646400010'
file:
- access_level: open_access
checksum: fbb05619fe4b650f341cc730425dd9c3
content_type: application/pdf
creator: dernst
date_created: 2023-10-31T11:20:31Z
date_updated: 2023-10-31T11:20:31Z
file_id: '14475'
file_name: 2023_IsraelJourMath_Wagner.pdf
file_size: 623787
relation: main_file
success: 1
file_date_updated: 2023-10-31T11:20:31Z
has_accepted_license: '1'
intvolume: ' 256'
isi: 1
issue: '2'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 675-717
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Coboundary expansion, equivariant overlap, and crossing numbers of simplicial
complexes
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: 256
year: '2023'
...
---
_id: '12129'
abstract:
- lang: eng
text: 'Given a finite point set P in general position in the plane, a full triangulation
of P is a maximal straight-line embedded plane graph on P. A partial triangulation
of P is a full triangulation of some subset P′ of P containing all extreme points
in P. A bistellar flip on a partial triangulation either flips an edge (called
edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as
vertex of degree 3. The bistellar flip graph has all partial triangulations as
vertices, and a pair of partial triangulations is adjacent if they can be obtained
from one another by a bistellar flip. The edge flip graph is defined with full
triangulations as vertices, and edge flips determining the adjacencies. Lawson
showed in the early seventies that these graphs are connected. The goal of this
paper is to investigate the structure of these graphs, with emphasis on their
vertex connectivity. For sets P of n points in the plane in general position,
we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar
flip graph is (n−3)-vertex connected; both results are tight. The latter bound
matches the situation for the subfamily of regular triangulations (i.e., partial
triangulations obtained by lifting the points to 3-space and projecting back the
lower convex hull), where (n−3)-vertex connectivity has been known since the late
eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky
and Balinski’s Theorem. For the edge flip-graph, we additionally show that the
vertex connectivity is at least as large as (and hence equal to) the minimum degree
(i.e., the minimum number of flippable edges in any full triangulation), provided
that n is large enough. Our methods also yield several other results: (i) The
edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products
of associahedra) and the bistellar flip graph can be covered by graphs of polytopes
of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation
is regular, if it has distance n−3 in the Hasse diagram of the partial order of
partial subdivisions from the trivial subdivision. (iii) All partial triangulations
of a point set are regular iff the partial order of partial subdivisions has height
n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations
and such that every proper subset has only regular triangulations, i.e., there
are no small certificates for the existence of non-regular triangulations.'
acknowledgement: "This is a full and revised version of [38] (on partial triangulations)
in Proceedings of the 36th Annual International Symposium on Computational Geometry
(SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings
of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis
research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt,
Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on
full triangulations. Research was supported by the Swiss National Science Foundation
within the collaborative DACH project Arrangements and Drawings as SNSF Project
200021E-171681, and by IST Austria and Berlin Free University during a sabbatical
stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco
Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger
and Valentin Stoppiello for carefully reading earlier versions and for many helpful
comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology
Zürich"
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane.
Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2
apa: Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs
in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2
chicago: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane.” Discrete & Computational Geometry. Springer Nature,
2022. https://doi.org/10.1007/s00454-022-00436-2.
ieee: U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer
Nature, pp. 1227–1284, 2022.
ista: Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the
plane. Discrete & Computational Geometry. 68(4), 1227–1284.
mla: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the
Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer
Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.
short: U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.
corr_author: '1'
date_created: 2023-01-12T12:02:28Z
date_published: 2022-11-14T00:00:00Z
date_updated: 2025-07-10T11:54:56Z
day: '14'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00436-2
external_id:
isi:
- '000883222200003'
file:
- access_level: open_access
checksum: 307e879d09e52eddf5b225d0aaa9213a
content_type: application/pdf
creator: dernst
date_created: 2023-01-23T11:10:03Z
date_updated: 2023-01-23T11:10:03Z
file_id: '12345'
file_name: 2022_DiscreteCompGeometry_Wagner.pdf
file_size: 1747581
relation: main_file
success: 1
file_date_updated: 2023-01-23T11:10:03Z
has_accepted_license: '1'
intvolume: ' 68'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1227-1284
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '7807'
relation: earlier_version
status: public
- id: '7990'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Connectivity of triangulation flip graphs in the plane
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '14381'
abstract:
- lang: eng
text: Expander graphs (sparse but highly connected graphs) have, since their inception,
been the source of deep links between Mathematics and Computer Science as well
as applications to other areas. In recent years, a fascinating theory of high-dimensional
expanders has begun to emerge, which is still in a formative stage but has nonetheless
already lead to a number of striking results. Unlike for graphs, in higher dimensions
there is a rich array of non-equivalent notions of expansion (coboundary expansion,
cosystolic expansion, topological expansion, spectral expansion, etc.), with differents
strengths and applications. In this talk, we will survey this landscape of high-dimensional
expansion, with a focus on two main results. First, we will present Gromov’s Topological
Overlap Theorem, which asserts that coboundary expansion (a quantitative version
of vanishing mod 2 cohomology) implies topological expansion (roughly, the property
that for every map from a simplicial complex to a manifold of the same dimension,
the images of a positive fraction of the simplices have a point in common). Second,
we will outline a construction of bounded degree 2-dimensional topological expanders,
due to Kaufman, Kazhdan, and Lubotzky.
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Wagner U. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky,
and others). Bulletin de la Societe Mathematique de France. 2022;438:281-294.
doi:10.24033/ast.1188
apa: Wagner, U. (2022). High-dimensional expanders (after Gromov, Kaufman, Kazhdan,
Lubotzky, and others). Bulletin de La Societe Mathematique de France. Societe
Mathematique de France. https://doi.org/10.24033/ast.1188
chicago: Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan,
Lubotzky, and Others).” Bulletin de La Societe Mathematique de France.
Societe Mathematique de France, 2022. https://doi.org/10.24033/ast.1188.
ieee: U. Wagner, “High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky,
and others),” Bulletin de la Societe Mathematique de France, vol. 438.
Societe Mathematique de France, pp. 281–294, 2022.
ista: Wagner U. 2022. High-dimensional expanders (after Gromov, Kaufman, Kazhdan,
Lubotzky, and others). Bulletin de la Societe Mathematique de France. 438, 281–294.
mla: Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky,
and Others).” Bulletin de La Societe Mathematique de France, vol. 438,
Societe Mathematique de France, 2022, pp. 281–94, doi:10.24033/ast.1188.
short: U. Wagner, Bulletin de La Societe Mathematique de France 438 (2022) 281–294.
corr_author: '1'
date_created: 2023-10-01T22:01:14Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2025-09-10T09:55:10Z
day: '01'
department:
- _id: UlWa
doi: 10.24033/ast.1188
external_id:
isi:
- '000958364400007'
intvolume: ' 438'
isi: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 281-294
publication: Bulletin de la Societe Mathematique de France
publication_identifier:
eissn:
- 2102-622X
issn:
- 0037-9484
publication_status: published
publisher: Societe Mathematique de France
quality_controlled: '1'
scopus_import: '1'
status: public
title: High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 438
year: '2022'
...
---
_id: '10776'
abstract:
- lang: eng
text: 'Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior).
Given a point p in the interior of K, a hyperplane h passing through p is called
barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question
whether, for every K, there exists an interior point p through which there are
at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly
resolved affirmatively by showing that this is the case if p=p0 is the point of
maximal depth in K. However, while working on a related question, we noticed that
one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample;
this re-opens Grünbaum’s question. It follows from known results that for n≥2,
there are always at least three distinct barycentric cuts through the point p0∈K
of maximal depth. Using tools related to Morse theory we are able to improve this
bound: four distinct barycentric cuts through p0 are guaranteed if n≥3.'
acknowledgement: The work by Zuzana Patáková has been partially supported by Charles
University Research Center Program No. UNCE/SCI/022, and part of it was done during
her research stay at IST Austria. The work by Martin Tancer is supported by the
GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and
UNCE/SCI/004.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Zuzana
full_name: Patakova, Zuzana
id: 48B57058-F248-11E8-B48F-1D18A9856A87
last_name: Patakova
orcid: 0000-0002-3975-1683
- first_name: Martin
full_name: Tancer, Martin
last_name: Tancer
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. Discrete
and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7
apa: Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through
a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7
chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022.
https://doi.org/10.1007/s00454-021-00364-7.
ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
body,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp.
1133–1154, 2022.
ista: Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body.
Discrete and Computational Geometry. 68, 1133–1154.
mla: Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” Discrete
and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.
short: Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68
(2022) 1133–1154.
date_created: 2022-02-20T23:01:35Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-02T14:38:58Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-021-00364-7
external_id:
arxiv:
- '2003.13536'
isi:
- '000750681500001'
intvolume: ' 68'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2003.13536
month: '12'
oa: 1
oa_version: Preprint
page: 1133-1154
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Barycentric cuts through a convex body
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '10220'
abstract:
- lang: eng
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."
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
orcid: 0000-0002-7840-5062
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: Arkadiy B.
full_name: Skopenkov, Arkadiy B.
last_name: Skopenkov
- 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, Mabillard I, Skopenkov AB, Wagner U. Eliminating higher-multiplicity
intersections. III. Codimension 2. Israel Journal of Mathematics. 2021;245:501–534.
doi:10.1007/s11856-021-2216-z
apa: Avvakumov, S., Mabillard, I., Skopenkov, A. B., & Wagner, U. (2021). Eliminating
higher-multiplicity intersections. III. Codimension 2. Israel Journal of Mathematics.
Springer Nature. https://doi.org/10.1007/s11856-021-2216-z
chicago: Avvakumov, Sergey, Isaac Mabillard, Arkadiy B. Skopenkov, and Uli Wagner.
“Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” Israel
Journal of Mathematics. Springer Nature, 2021. https://doi.org/10.1007/s11856-021-2216-z.
ieee: S. Avvakumov, I. Mabillard, A. B. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity
intersections. III. Codimension 2,” Israel Journal of Mathematics, vol.
245. Springer Nature, pp. 501–534, 2021.
ista: Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. 2021. Eliminating higher-multiplicity
intersections. III. Codimension 2. Israel Journal of Mathematics. 245, 501–534.
mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections. III.
Codimension 2.” Israel Journal of Mathematics, vol. 245, Springer Nature,
2021, pp. 501–534, doi:10.1007/s11856-021-2216-z.
short: S. Avvakumov, I. Mabillard, A.B. Skopenkov, U. Wagner, Israel Journal of
Mathematics 245 (2021) 501–534.
corr_author: '1'
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-30T00:00:00Z
date_updated: 2025-07-02T10:54:52Z
day: '30'
department:
- _id: UlWa
doi: 10.1007/s11856-021-2216-z
external_id:
arxiv:
- '1511.03501'
isi:
- '000712942100013'
intvolume: ' 245'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1511.03501
month: '10'
oa: 1
oa_version: Preprint
page: '501–534 '
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '9308'
relation: earlier_version
status: public
- id: '8183'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Eliminating higher-multiplicity intersections. III. Codimension 2
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 245
year: '2021'
...
---
_id: '7806'
abstract:
- lang: eng
text: "We consider the following decision problem EMBEDk→d in computational topology
(where k ≤ d are fixed positive integers): Given a finite simplicial complex K
of dimension k, does there exist a (piecewise-linear) embedding of K into ℝd?\r\nThe
special case EMBED1→2 is graph planarity, which is decidable in linear time, as
shown by Hopcroft and Tarjan. In higher dimensions, EMBED2→3 and EMBED3→3 are
known to be decidable (as well as NP-hard), and recent results of Čadek et al.
in computational homotopy theory, in combination with the classical Haefliger–Weber
theorem in geometric topology, imply that EMBEDk→d can be solved in polynomial
time for any fixed pair (k, d) of dimensions in the so-called metastable range
.\r\nHere, by contrast, we prove that EMBEDk→d is algorithmically undecidable
for almost all pairs of dimensions outside the metastable range, namely for .
This almost completely resolves the decidability vs. undecidability of EMBEDk→d
in higher dimensions and establishes a sharp dichotomy between polynomial-time
solvability and undecidability.\r\nOur result complements (and in a wide range
of dimensions strengthens) earlier results of Matoušek, Tancer, and the second
author, who showed that EMBEDk→d is undecidable for 4 ≤ k ϵ {d – 1, d}, and NP-hard
for all remaining pairs (k, d) outside the metastable range and satisfying d ≥
4."
article_processing_charge: No
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Stephan Y
full_name: Zhechev, Stephan Y
id: 3AA52972-F248-11E8-B48F-1D18A9856A87
last_name: Zhechev
citation:
ama: 'Filakovský M, Wagner U, Zhechev SY. Embeddability of simplicial complexes
is undecidable. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. Vol 2020-January. SIAM; 2020:767-785. doi:10.1137/1.9781611975994.47'
apa: 'Filakovský, M., Wagner, U., & Zhechev, S. Y. (2020). Embeddability of
simplicial complexes is undecidable. In Proceedings of the Annual ACM-SIAM
Symposium on Discrete Algorithms (Vol. 2020–January, pp. 767–785). Salt Lake
City, UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.47'
chicago: Filakovský, Marek, Uli Wagner, and Stephan Y Zhechev. “Embeddability of
Simplicial Complexes Is Undecidable.” In Proceedings of the Annual ACM-SIAM
Symposium on Discrete Algorithms, 2020–January:767–85. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.47.
ieee: M. Filakovský, U. Wagner, and S. Y. Zhechev, “Embeddability of simplicial
complexes is undecidable,” in Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January,
pp. 767–785.
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.”
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol.
2020–January, SIAM, 2020, pp. 767–85, doi:10.1137/1.9781611975994.47.
short: M. Filakovský, U. Wagner, S.Y. Zhechev, in:, Proceedings of the Annual ACM-SIAM
Symposium on Discrete Algorithms, SIAM, 2020, pp. 767–785.
conference:
end_date: 2020-01-08
location: Salt Lake City, UT, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2020-01-05
date_created: 2020-05-10T22:00:48Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2026-06-18T19:27:16Z
day: '01'
ddc:
- '500'
department:
- _id: UlWa
doi: 10.1137/1.9781611975994.47
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1137/1.9781611975994.47
month: '01'
oa: 1
oa_version: Published Version
page: 767-785
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611975994'
publication_status: published
publisher: SIAM
quality_controlled: '1'
scopus_import: '1'
status: public
title: Embeddability of simplicial complexes is undecidable
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-January
year: '2020'
...
---
_id: '7807'
abstract:
- lang: eng
text: "In a straight-line embedded triangulation of a point set P in the plane,
removing an inner edge and—provided the resulting quadrilateral is convex—adding
the other diagonal is called an edge flip. The (edge) flip graph has all triangulations
as vertices, and a pair of triangulations is adjacent if they can be obtained
from each other by an edge flip. The goal of this paper is to contribute to a
better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor
sets in general position, it is known that every triangulation allows at least
edge flips (a tight bound) which gives the minimum degree of any flip graph for
n points. We show that for every point set P in general position, the flip graph
is at least -vertex connected. Somewhat more strongly, we show that the vertex
connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum
number of flippable edges in any triangulation of P, provided P is large enough.
Finally, we exhibit some of the geometry of the flip graph by showing that the
flip graph can be covered by 1-skeletons of polytopes of dimension (products of
associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be
shown for the bistellar flip graph of partial triangulations, i.e. the set of
all triangulations of subsets of P which contain all extreme points of P. This
will be treated separately in a second part."
article_processing_charge: No
arxiv: 1
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: 'Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane
(Part I: Edge flips). In: Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. Vol 2020-January. SIAM; 2020:2823-2841. doi:10.1137/1.9781611975994.172'
apa: 'Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs
in the plane (Part I: Edge flips). In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms (Vol. 2020–January, pp. 2823–2841). Salt Lake City,
UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.172'
chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane (Part I: Edge Flips).” In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, 2020–January:2823–41. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.172.'
ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane (Part I: Edge flips),” in Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January,
pp. 2823–2841.'
ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.'
mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
the Plane (Part I: Edge Flips).” Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:10.1137/1.9781611975994.172.'
short: U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on
Discrete Algorithms, SIAM, 2020, pp. 2823–2841.
conference:
end_date: 2020-01-08
location: Salt Lake City, UT, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2020-01-05
date_created: 2020-05-10T22:00:48Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2024-10-09T21:03:33Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/1.9781611975994.172
external_id:
arxiv:
- '2003.13557'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1137/1.9781611975994.172
month: '01'
oa: 1
oa_version: Submitted Version
page: 2823-2841
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611975994'
publication_status: published
publisher: SIAM
quality_controlled: '1'
related_material:
record:
- id: '12129'
relation: later_version
status: public
scopus_import: 1
status: public
title: 'Connectivity of triangulation flip graphs in the plane (Part I: Edge flips)'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2020-January
year: '2020'
...
---
_id: '7990'
abstract:
- lang: eng
text: 'Given a finite point set P in general position in the plane, a full triangulation
is a maximal straight-line embedded plane graph on P. A partial triangulation
on P is a full triangulation of some subset P'' of P containing all extreme points
in P. A bistellar flip on a partial triangulation either flips an edge, removes
a non-extreme point of degree 3, or adds a point in P ⧵ P'' as vertex of degree
3. The bistellar flip graph has all partial triangulations as vertices, and a
pair of partial triangulations is adjacent if they can be obtained from one another
by a bistellar flip. The goal of this paper is to investigate the structure of
this graph, with emphasis on its connectivity. For sets P of n points in general
position, we show that the bistellar flip graph is (n-3)-connected, thereby answering,
for sets in general position, an open questions raised in a book (by De Loera,
Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches
the situation for the subfamily of regular triangulations (i.e., partial triangulations
obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity
has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov,
Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results
(see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph
can be covered by graphs of polytopes of dimension n-3 (products of secondary
polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in
the Hasse diagram of the partial order of partial subdivisions from the trivial
subdivision. (iii) All partial triangulations are regular iff the trivial subdivision
has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily
large sets P with non-regular partial triangulations, while every proper subset
has only regular triangulations, i.e., there are no small certificates for the
existence of non-regular partial triangulations (answering a question by F. Santos
in the unexpected direction).'
alternative_title:
- LIPIcs
article_number: 67:1 - 67:16
article_processing_charge: No
arxiv: 1
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: 'Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane
(Part II: Bistellar flips). In: 36th International Symposium on Computational
Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
doi:10.4230/LIPIcs.SoCG.2020.67'
apa: 'Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs
in the plane (Part II: Bistellar flips). In 36th International Symposium on
Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl -
Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.67'
chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane (Part II: Bistellar Flips).” In 36th International Symposium on
Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.67.'
ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane (Part II: Bistellar flips),” in 36th International Symposium on Computational
Geometry, Zürich, Switzerland, 2020, vol. 164.'
ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
plane (Part II: Bistellar flips). 36th International Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 67:1-67:16.'
mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
the Plane (Part II: Bistellar Flips).” 36th International Symposium on Computational
Geometry, vol. 164, 67:1-67:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.67.'
short: U. Wagner, E. Welzl, in:, 36th International Symposium on Computational Geometry,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-06-26
location: Zürich, Switzerland
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:56Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.67
external_id:
arxiv:
- '2003.13557'
file:
- access_level: open_access
checksum: 3f6925be5f3dcdb3b14cab92f410edf7
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T06:37:27Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8003'
file_name: 2020_LIPIcsSoCG_Wagner.pdf
file_size: 793187
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771436'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '12129'
relation: later_version
status: public
scopus_import: '1'
status: public
title: 'Connectivity of triangulation flip graphs in the plane (Part II: Bistellar
flips)'
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: 164
year: '2020'
...
---
_id: '7992'
abstract:
- lang: eng
text: 'Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior).
Given a point p in the interior of K, a hyperplane h passing through p is called
barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question
whether, for every K, there exists an interior point p through which there are
at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly
resolved affirmatively by showing that this is the case if p=p₀ is the point of
maximal depth in K. However, while working on a related question, we noticed that
one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample;
this re-opens Grünbaum’s question. It follows from known results that for n ≥
2, there are always at least three distinct barycentric cuts through the point
p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve
this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3.'
alternative_title:
- LIPIcs
article_number: 62:1 - 62:16
article_processing_charge: No
arxiv: 1
author:
- first_name: Zuzana
full_name: Patakova, Zuzana
id: 48B57058-F248-11E8-B48F-1D18A9856A87
last_name: Patakova
orcid: 0000-0002-3975-1683
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In:
36th International Symposium on Computational Geometry. Vol 164. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62'
apa: 'Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through
a convex body. In 36th International Symposium on Computational Geometry
(Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.SoCG.2020.62'
chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
a Convex Body.” In 36th International Symposium on Computational Geometry,
Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62.
ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
body,” in 36th International Symposium on Computational Geometry, Zürich,
Switzerland, 2020, vol. 164.
ista: 'Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body.
36th International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 164, 62:1-62:16.'
mla: Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” 36th
International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.
short: Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational
Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
end_date: 2020-06-26
location: Zürich, Switzerland
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2020-06-22
corr_author: '1'
date_created: 2020-06-22T09:14:20Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2025-07-10T11:54:57Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.62
external_id:
arxiv:
- '2003.13536'
file:
- access_level: open_access
checksum: ce1c9194139a664fb59d1efdfc88eaae
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T06:45:52Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8004'
file_name: 2020_LIPIcsSoCG_Patakova.pdf
file_size: 750318
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771436'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Barycentric cuts through a convex body
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: 164
year: '2020'
...
---
_id: '9308'
acknowledgement: This research was carried out with the support of the Russian Foundation
for Basic Research(grant no. 19-01-00169)
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
orcid: 0000-0002-7840-5062
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: A. B.
full_name: Skopenkov, A. B.
last_name: Skopenkov
citation:
ama: Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. Eliminating higher-multiplicity
intersections, III. Codimension 2. Russian Mathematical Surveys. 2020;75(6):1156-1158.
doi:10.1070/RM9943
apa: Avvakumov, S., Wagner, U., Mabillard, I., & Skopenkov, A. B. (2020). Eliminating
higher-multiplicity intersections, III. Codimension 2. Russian Mathematical
Surveys. IOP Publishing. https://doi.org/10.1070/RM9943
chicago: Avvakumov, Sergey, Uli Wagner, Isaac Mabillard, and A. B. Skopenkov. “Eliminating
Higher-Multiplicity Intersections, III. Codimension 2.” Russian Mathematical
Surveys. IOP Publishing, 2020. https://doi.org/10.1070/RM9943.
ieee: S. Avvakumov, U. Wagner, I. Mabillard, and A. B. Skopenkov, “Eliminating higher-multiplicity
intersections, III. Codimension 2,” Russian Mathematical Surveys, vol.
75, no. 6. IOP Publishing, pp. 1156–1158, 2020.
ista: Avvakumov S, Wagner U, Mabillard I, Skopenkov AB. 2020. Eliminating higher-multiplicity
intersections, III. Codimension 2. Russian Mathematical Surveys. 75(6), 1156–1158.
mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections, III.
Codimension 2.” Russian Mathematical Surveys, vol. 75, no. 6, IOP Publishing,
2020, pp. 1156–58, doi:10.1070/RM9943.
short: S. Avvakumov, U. Wagner, I. Mabillard, A.B. Skopenkov, Russian Mathematical
Surveys 75 (2020) 1156–1158.
date_created: 2021-04-04T22:01:22Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2025-07-02T10:54:51Z
day: '01'
department:
- _id: UlWa
doi: 10.1070/RM9943
external_id:
arxiv:
- '1511.03501'
isi:
- '000625983100001'
intvolume: ' 75'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1511.03501
month: '12'
oa: 1
oa_version: Preprint
page: 1156-1158
publication: Russian Mathematical Surveys
publication_identifier:
issn:
- 0036-0279
publication_status: published
publisher: IOP Publishing
quality_controlled: '1'
related_material:
record:
- id: '10220'
relation: later_version
status: public
- id: '8183'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Eliminating higher-multiplicity intersections, III. Codimension 2
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 75
year: '2020'
...
---
_id: '5986'
abstract:
- lang: eng
text: "Given a triangulation of a point set in the plane, a flip deletes an edge
e whose removal leaves a convex quadrilateral, and replaces e by the opposite
diagonal of the quadrilateral. It is well known that any triangulation of a point
set can be reconfigured to any other triangulation by some sequence of flips.
We explore this question in the setting where each edge of a triangulation has
a label, and a flip transfers the label of the removed edge to the new edge. It
is not true that every labelled triangulation of a point set can be reconfigured
to every other labelled triangulation via a sequence of flips, but we characterize
when this is possible. There is an obvious necessary condition: for each label
l, if edge e has label l in the first triangulation and edge f has label l in
the second triangulation, then there must be some sequence of flips that moves
label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot
formulated the Orbit Conjecture, which states that this necessary condition is
also sufficient, i.e. that all labels can be simultaneously mapped to their destination
if and only if each label individually can be mapped to its destination. We prove
this conjecture. Furthermore, we give a polynomial-time algorithm (with \U0001D442(\U0001D45B8)
being a crude bound on the run-time) to find a sequence of flips to reconfigure
one labelled triangulation to another, if such a sequence exists, and we prove
an upper bound of \U0001D442(\U0001D45B7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges
on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional
ball (this follows from a result of Orden and Santos; we give a different proof
based on a shelling argument). The dual cell complex of this simplicial ball,
called the flip complex, has the usual flip graph as its 1-skeleton. We use properties
of the 2-skeleton of the flip complex to prove the Orbit Conjecture."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Anna
full_name: Lubiw, Anna
last_name: Lubiw
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898.
doi:10.1007/s00454-018-0035-8
apa: Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture
for flipping edge-labelled triangulations. Discrete & Computational Geometry.
Springer Nature. https://doi.org/10.1007/s00454-018-0035-8
chicago: Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture
for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry.
Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.
ieee: A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for
flipping edge-labelled triangulations,” Discrete & Computational Geometry,
vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.
ista: Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping
edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.
mla: Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled
Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4,
Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.
short: A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61
(2019) 880–898.
corr_author: '1'
date_created: 2019-02-14T11:54:08Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2026-04-08T07:23:01Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
doi: 10.1007/s00454-018-0035-8
external_id:
arxiv:
- '1710.02741'
isi:
- '000466130000009'
file:
- access_level: open_access
checksum: e1bff88f1d77001b53b78c485ce048d7
content_type: application/pdf
creator: dernst
date_created: 2019-02-14T11:57:22Z
date_updated: 2020-07-14T12:47:14Z
file_id: '5988'
file_name: 2018_DiscreteGeometry_Lubiw.pdf
file_size: 556276
relation: main_file
file_date_updated: 2020-07-14T12:47:14Z
has_accepted_license: '1'
intvolume: ' 61'
isi: 1
issue: '4'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 880-898
project:
- _id: B67AFEDC-15C9-11EA-A837-991A96BB2854
name: IST Austria Open Access Fund
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '683'
relation: earlier_version
status: public
- id: '7944'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: A proof of the orbit conjecture for flipping edge-labelled triangulations
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 61
year: '2019'
...
---
_id: '6647'
abstract:
- lang: eng
text: The Tverberg theorem is one of the cornerstones of discrete geometry. It states
that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition
X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r,
all share a common point. In this paper, we prove a strengthening of this theorem
that guarantees a partition which, in addition to the above, has the property
that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections.
Possible generalizations and algorithmic aspects are also discussed. As a concrete
application, we show that any n points in the plane in general position span floor[n/3]
vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries
have pairwise nonempty intersections; this number is clearly best possible. A
previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing
triangles. Our result generalizes to a result about simplices in R^d,d >=2.
alternative_title:
- LIPIcs
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Bernd
full_name: Gärtner, Bernd
last_name: Gärtner
- first_name: Andrey
full_name: Kupavskii, Andrey
last_name: Kupavskii
- first_name: Pavel
full_name: Valtr, Pavel
last_name: Valtr
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg
theorem. In: 35th International Symposium on Computational Geometry. Vol
129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:38:1-38:13. doi:10.4230/LIPICS.SOCG.2019.38'
apa: 'Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2019).
The crossing Tverberg theorem. In 35th International Symposium on Computational
Geometry (Vol. 129, p. 38:1-38:13). Portland, OR, United States: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.SOCG.2019.38'
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” In 35th International Symposium on
Computational Geometry, 129:38:1-38:13. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019. https://doi.org/10.4230/LIPICS.SOCG.2019.38.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” in 35th International Symposium on Computational Geometry,
Portland, OR, United States, 2019, vol. 129, p. 38:1-38:13.
ista: 'Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2019. The crossing Tverberg
theorem. 35th International Symposium on Computational Geometry. SoCG 2019: Symposium
on Computational Geometry, LIPIcs, vol. 129, 38:1-38:13.'
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” 35th International
Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2019, p. 38:1-38:13, doi:10.4230/LIPICS.SOCG.2019.38.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, in:, 35th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2019, p. 38:1-38:13.
conference:
end_date: 2019-06-21
location: Portland, OR, United States
name: 'SoCG 2019: Symposium on Computational Geometry'
start_date: 2019-06-18
corr_author: '1'
date_created: 2019-07-17T10:35:04Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2025-04-14T13:52:36Z
day: '01'
ddc:
- '000'
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPICS.SOCG.2019.38
external_id:
arxiv:
- '1812.04911'
file:
- access_level: open_access
checksum: d6d017f8b41291b94d102294fa96ae9c
content_type: application/pdf
creator: dernst
date_created: 2019-07-24T06:54:52Z
date_updated: 2020-07-14T12:47:35Z
file_id: '6667'
file_name: 2019_LIPICS_Fulek.pdf
file_size: 559837
relation: main_file
file_date_updated: 2020-07-14T12:47:35Z
has_accepted_license: '1'
intvolume: ' 129'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 38:1-38:13
project:
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: 35th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771047'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '13974'
relation: later_version
status: public
scopus_import: 1
status: public
title: The crossing Tverberg theorem
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: 129
year: '2019'
...
---
_id: '7093'
abstract:
- lang: eng
text: "In graph theory, as well as in 3-manifold topology, there exist several width-type
parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold
is. These parameters, such as pathwidth or treewidth for graphs, or the concept
of thin position for 3-manifolds, play an important role when studying algorithmic
problems; in particular, there is a variety of problems in computational 3-manifold
topology - some of them known to be computationally hard in general - that become
solvable in polynomial time as soon as the dual graph of the input triangulation
has bounded treewidth.\r\nIn view of these algorithmic results, it is natural
to ask whether every 3-manifold admits a triangulation of bounded treewidth. We
show that this is not the case, i.e., that there exists an infinite family of
closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth
(the latter implies the former, but we present two separate proofs).\r\nWe derive
these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann,
Schultens and Saito by exhibiting explicit connections between the topology of
a 3-manifold M on the one hand and width-type parameters of the dual graphs of
triangulations of M on the other hand, answering a question that had been raised
repeatedly by researchers in computational 3-manifold topology. In particular,
we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has
a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M
is at most 18(k+1) (resp. 4(3k+1))."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds.
Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5
apa: Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated
3-manifolds. Journal of Computational Geometry. Computational Geometry
Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5
chicago: Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of
Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational
Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.
ieee: K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,”
Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry
Laborartoy, pp. 70–98, 2019.
ista: Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds.
Journal of Computational Geometry. 10(2), 70–98.
mla: Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal
of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy,
2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.
short: K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019)
70–98.
date_created: 2019-11-23T12:14:09Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2026-04-08T07:21:27Z
day: '01'
ddc:
- '514'
department:
- _id: UlWa
doi: 10.20382/JOGC.V10I2A5
external_id:
arxiv:
- '1712.00434'
file:
- access_level: open_access
checksum: c872d590d38d538404782bca20c4c3f5
content_type: application/pdf
creator: khuszar
date_created: 2019-11-23T12:35:16Z
date_updated: 2020-07-14T12:47:49Z
file_id: '7094'
file_name: 479-1917-1-PB.pdf
file_size: 857590
relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
intvolume: ' 10'
issue: '2'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 70–98
publication: Journal of Computational Geometry
publication_identifier:
issn:
- 1920-180X
publication_status: published
publisher: Computational Geometry Laborartoy
quality_controlled: '1'
related_material:
record:
- id: '285'
relation: earlier_version
status: public
- id: '8032'
relation: part_of_dissertation
status: public
scopus_import: '1'
status: public
title: On the treewidth of triangulated 3-manifolds
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10
year: '2019'
...