---
_id: '14888'
abstract:
- lang: eng
text: 'A face in a curve arrangement is called popular if it is bounded by the same
curve multiple times. Motivated by the automatic generation of curved nonogram
puzzles, we investigate possibilities to eliminate the popular faces in an arrangement
by inserting a single additional curve. This turns out to be NP-hard; however,
it becomes tractable when the number of popular faces is small: We present a probabilistic
FPT-approach in the number of popular faces.'
acknowledgement: 'This work was initiated at the 16th European Research Week on Geometric
Graphs in Strobl in 2019. A.W. is supported by the Austrian Science Fund (FWF):
W1230. S.T. has been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT19035].
A preliminary version of this work has been presented at the 38th European Workshop
on Computational Geometry (EuroCG 2022) in Perugia [9]. A full version of this paper,
which includes appendices but is otherwise identical, is available as a technical
report [10].'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Phoebe
full_name: De Nooijer, Phoebe
last_name: De Nooijer
- first_name: Soeren
full_name: Terziadis, Soeren
last_name: Terziadis
- first_name: Alexandra
full_name: Weinberger, Alexandra
last_name: Weinberger
- 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: Tamara
full_name: Mchedlidze, Tamara
last_name: Mchedlidze
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- first_name: Günter
full_name: Rote, Günter
last_name: Rote
citation:
ama: 'De Nooijer P, Terziadis S, Weinberger A, et al. Removing popular faces in curve
arrangements. In: 31st International Symposium on Graph Drawing and Network
Visualization. Vol 14466. Springer Nature; 2024:18-33. doi:10.1007/978-3-031-49275-4_2'
apa: 'De Nooijer, P., Terziadis, S., Weinberger, A., Masárová, Z., Mchedlidze, T.,
Löffler, M., & Rote, G. (2024). Removing popular faces in curve arrangements.
In 31st International Symposium on Graph Drawing and Network Visualization
(Vol. 14466, pp. 18–33). Isola delle Femmine, Palermo, Italy: Springer Nature.
https://doi.org/10.1007/978-3-031-49275-4_2'
chicago: De Nooijer, Phoebe, Soeren Terziadis, Alexandra Weinberger, Zuzana Masárová,
Tamara Mchedlidze, Maarten Löffler, and Günter Rote. “Removing Popular Faces in Curve
Arrangements.” In 31st International Symposium on Graph Drawing and Network
Visualization, 14466:18–33. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-49275-4_2.
ieee: P. De Nooijer et al., “Removing popular faces in curve arrangements,”
in 31st International Symposium on Graph Drawing and Network Visualization,
Isola delle Femmine, Palermo, Italy, 2024, vol. 14466, pp. 18–33.
ista: 'De Nooijer P, Terziadis S, Weinberger A, Masárová Z, Mchedlidze T, Löffler
M, Rote G. 2024. Removing popular faces in curve arrangements. 31st International
Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network
Visualization, LNCS, vol. 14466, 18–33.'
mla: De Nooijer, Phoebe, et al. “Removing Popular Faces in Curve Arrangements.”
31st International Symposium on Graph Drawing and Network Visualization,
vol. 14466, Springer Nature, 2024, pp. 18–33, doi:10.1007/978-3-031-49275-4_2.
short: P. De Nooijer, S. Terziadis, A. Weinberger, Z. Masárová, T. Mchedlidze, M.
Löffler, G. Rote, in:, 31st International Symposium on Graph Drawing and Network
Visualization, Springer Nature, 2024, pp. 18–33.
conference:
end_date: 2023-09-22
location: Isola delle Femmine, Palermo, Italy
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2023-09-20
date_created: 2024-01-28T23:01:43Z
date_published: 2024-01-06T00:00:00Z
date_updated: 2024-01-29T09:45:06Z
day: '06'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1007/978-3-031-49275-4_2
external_id:
arxiv:
- '2202.12175'
intvolume: ' 14466'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2202.12175
month: '01'
oa: 1
oa_version: Preprint
page: 18-33
publication: 31st International Symposium on Graph Drawing and Network Visualization
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031492747'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Removing popular faces in curve arrangements
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14466
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
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
date_created: 2024-03-24T23:00:59Z
date_published: 2024-03-01T00:00:00Z
date_updated: 2024-03-25T07:45:54Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.STACS.2024.34
ec_funded: 1
external_id:
arxiv:
- '2312.12981'
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'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
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'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 289
year: '2024'
...
---
_id: '12563'
abstract:
- lang: eng
text: 'he approximate graph coloring problem, whose complexity is unresolved in
most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable,
where c≥k. This problem naturally generalizes to promise graph homomorphism problems
and further to promise constraint satisfaction problems. The complexity of these
problems has recently been studied through an algebraic approach. In this paper,
we introduce two new techniques to analyze the complexity of promise CSPs: one
is based on topology and the other on adjunction. We apply these techniques, together
with the previously introduced algebraic approach, to obtain new unconditional
NP-hardness results for a significant class of approximate graph coloring and
promise graph homomorphism problems.'
acknowledgement: "Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant
EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No 101034413. Stanislav Živný was supported by a Royal Society University Research
Fellowship. This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 714532). The paper re\x1Eects only the authors’ views and not
the views of the ERC or the European Commission. "
article_processing_charge: No
article_type: original
author:
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- 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: Marcin
full_name: Wrochna, Marcin
last_name: Wrochna
- first_name: Stanislav
full_name: Živný, Stanislav
last_name: Živný
citation:
ama: Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise
constraint satisfaction. SIAM Journal on Computing. 2023;52(1):38-79. doi:10.1137/20m1378223
apa: Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and
adjunction in promise constraint satisfaction. SIAM Journal on Computing.
Society for Industrial & Applied Mathematics. https://doi.org/10.1137/20m1378223
chicago: Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology
and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing.
Society for Industrial & Applied Mathematics, 2023. https://doi.org/10.1137/20m1378223.
ieee: A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction
in promise constraint satisfaction,” SIAM Journal on Computing, vol. 52,
no. 1. Society for Industrial & Applied Mathematics, pp. 38–79, 2023.
ista: Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in
promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.
mla: Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.”
SIAM Journal on Computing, vol. 52, no. 1, Society for Industrial &
Applied Mathematics, 2023, pp. 38–79, doi:10.1137/20m1378223.
short: A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52
(2023) 38–79.
date_created: 2023-02-16T07:03:52Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-08-01T13:11:30Z
day: '01'
department:
- _id: UlWa
doi: 10.1137/20m1378223
ec_funded: 1
external_id:
arxiv:
- '2003.11351'
isi:
- '000955000000001'
intvolume: ' 52'
isi: 1
issue: '1'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2003.11351
month: '01'
oa: 1
oa_version: Preprint
page: 38-79
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: SIAM Journal on Computing
publication_identifier:
eissn:
- 1095-7111
issn:
- 0097-5397
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topology and adjunction in promise constraint satisfaction
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 52
year: '2023'
...
---
_id: '9652'
abstract:
- lang: eng
text: In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated
nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice.
We study weaker notions of equivalence of separated nets and demonstrate that
such notions also give rise to distinct equivalence classes. Put differently,
we find occurrences of particularly strong divergence of separated nets from the
integer lattice. Our approach generalises that of Burago and Kleiner and McMullen
which takes place largely in a continuous setting. Existence of irregular separated
nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞).
In the present work we obtain stronger types of non-realisable densities.
acknowledgement: 'This work was done while both authors were employed at the University
of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35.'
article_processing_charge: No
article_type: original
author:
- first_name: Michael
full_name: Dymond, Michael
last_name: Dymond
- first_name: Vojtech
full_name: Kaluza, Vojtech
id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
last_name: Kaluza
orcid: 0000-0002-2512-8698
citation:
ama: Dymond M, Kaluza V. Highly irregular separated nets. Israel Journal of Mathematics.
2023;253:501-554. doi:10.1007/s11856-022-2448-6
apa: Dymond, M., & Kaluza, V. (2023). Highly irregular separated nets. Israel
Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-022-2448-6
chicago: Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.”
Israel Journal of Mathematics. Springer Nature, 2023. https://doi.org/10.1007/s11856-022-2448-6.
ieee: M. Dymond and V. Kaluza, “Highly irregular separated nets,” Israel Journal
of Mathematics, vol. 253. Springer Nature, pp. 501–554, 2023.
ista: Dymond M, Kaluza V. 2023. Highly irregular separated nets. Israel Journal
of Mathematics. 253, 501–554.
mla: Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.” Israel
Journal of Mathematics, vol. 253, Springer Nature, 2023, pp. 501–54, doi:10.1007/s11856-022-2448-6.
short: M. Dymond, V. Kaluza, Israel Journal of Mathematics 253 (2023) 501–554.
date_created: 2021-07-14T07:01:28Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-14T11:26:34Z
day: '01'
ddc:
- '515'
- '516'
department:
- _id: UlWa
doi: 10.1007/s11856-022-2448-6
external_id:
arxiv:
- '1903.05923'
isi:
- '000904950300003'
file:
- access_level: open_access
checksum: 6fa0a3207dd1d6467c309fd1bcc867d1
content_type: application/pdf
creator: vkaluza
date_created: 2021-07-14T07:41:50Z
date_updated: 2021-07-14T07:41:50Z
file_id: '9653'
file_name: separated_nets.pdf
file_size: 900422
relation: main_file
file_date_updated: 2021-07-14T07:41:50Z
has_accepted_license: '1'
intvolume: ' 253'
isi: 1
keyword:
- Lipschitz
- bilipschitz
- bounded displacement
- modulus of continuity
- separated net
- non-realisable density
- Burago--Kleiner construction
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 501-554
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Highly irregular separated nets
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 253
year: '2023'
...
---
_id: '11999'
abstract:
- lang: eng
text: 'A simple drawing D(G) of a graph G is one where each pair of edges share
at most one point: either a common endpoint or a proper crossing. An edge e in
the complement of G can be inserted into D(G) if there exists a simple drawing
of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is
rectilinear (pseudolinear), that is, the edges can be extended into an arrangement
of lines (pseudolines), then any edge in the complement of G can be inserted.
In contrast, we show that it is NP-complete to decide whether one edge can be
inserted into a simple drawing. This remains true even if we assume that the drawing
is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles.
On the positive side, we show that, given an arrangement of pseudocircles A and
a pseudosegment σ, it can be decided in polynomial time whether there exists a
pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles.'
acknowledgement: 'This work was started during the 6th Austrian–Japanese–Mexican–Spanish
Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants
for the good atmosphere as well as discussions on the topic. Also, we thank Jan
Kynčl for sending us remarks on a preliminary version of this work and an anonymous
referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie
grant agreement No 754411. Fabian Klute was partially supported by the Netherlands
Organisation for Scientific Research (NWO) under project no. 612.001.651 and by
the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were
partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was
also partially supported by the Independent Research Fund Denmark grant 2020-2023
(9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded
by the Ministry of Universities of Spain and the European Union (NextGenerationEU).
Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.'
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Fabian
full_name: Klute, Fabian
last_name: Klute
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Tilo
full_name: Wiedera, Tilo
last_name: Wiedera
citation:
ama: Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting
one edge into a simple drawing is hard. Discrete and Computational Geometry.
2023;69:745–770. doi:10.1007/s00454-022-00394-9
apa: Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R.,
& Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. Discrete
and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00394-9
chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber,
Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is
Hard.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00394-9.
ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and
T. Wiedera, “Inserting one edge into a simple drawing is hard,” Discrete and
Computational Geometry, vol. 69. Springer Nature, pp. 745–770, 2023.
ista: Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T.
2023. Inserting one edge into a simple drawing is hard. Discrete and Computational
Geometry. 69, 745–770.
mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is
Hard.” Discrete and Computational Geometry, vol. 69, Springer Nature, 2023,
pp. 745–770, doi:10.1007/s00454-022-00394-9.
short: A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera,
Discrete and Computational Geometry 69 (2023) 745–770.
date_created: 2022-08-28T22:02:01Z
date_published: 2023-04-01T00:00:00Z
date_updated: 2023-08-14T12:51:25Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00394-9
ec_funded: 1
external_id:
arxiv:
- '1909.07347'
isi:
- '000840292800001'
file:
- access_level: open_access
checksum: def7ae3b28d9fd6aec16450e40090302
content_type: application/pdf
creator: alisjak
date_created: 2022-08-29T11:23:15Z
date_updated: 2022-08-29T11:23:15Z
file_id: '12006'
file_name: 2022_DiscreteandComputionalGeometry_Arroyo.pdf
file_size: 1002218
relation: main_file
success: 1
file_date_updated: 2022-08-29T11:23:15Z
has_accepted_license: '1'
intvolume: ' 69'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 745–770
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
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: Inserting one edge into a simple drawing is hard
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: 69
year: '2023'
...
---
_id: '13969'
abstract:
- lang: eng
text: "Bundling crossings is a strategy which can enhance the readability\r\nof
graph drawings. In this paper we consider good drawings, i.e., we require that\r\nany
two edges have at most one common point which can be a common vertex or a\r\ncrossing.
Our main result is that there is a polynomial-time algorithm to compute an\r\n8-approximation
of the bundled crossing number of a good drawing with no toothed\r\nhole. In general
the number of toothed holes has to be added to the 8-approximation.\r\nIn the
special case of circular drawings the approximation factor is 8, this improves\r\nupon
the 10-approximation of Fink et al. [14]. Our approach also works with the same\r\napproximation
factor for families of pseudosegments, i.e., curves intersecting at most\r\nonce.
We also show how to compute a 9/2-approximation when the intersection graph of\r\nthe
pseudosegments is bipartite and has no toothed hole."
acknowledgement: This work was initiated during the Workshop on Geometric Graphs in
November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian
Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during
the workshop. The first author has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement
No 754411. The second author has been supported by the German Research Foundation
DFG Project FE 340/12-1. An extended abstract of this paper has been published in
the proceedings of WALCOM 2022 in the Springer LNCS series, vol. 13174, pages 383–395.
article_processing_charge: Yes
article_type: original
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Stefan
full_name: Felsner, Stefan
last_name: Felsner
citation:
ama: Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. Journal
of Graph Algorithms and Applications. 2023;27(6):433-457. doi:10.7155/jgaa.00629
apa: Arroyo Guevara, A. M., & Felsner, S. (2023). Approximating the bundled
crossing number. Journal of Graph Algorithms and Applications. Brown University.
https://doi.org/10.7155/jgaa.00629
chicago: Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
Crossing Number.” Journal of Graph Algorithms and Applications. Brown University,
2023. https://doi.org/10.7155/jgaa.00629.
ieee: A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,”
Journal of Graph Algorithms and Applications, vol. 27, no. 6. Brown University,
pp. 433–457, 2023.
ista: Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number.
Journal of Graph Algorithms and Applications. 27(6), 433–457.
mla: Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
Number.” Journal of Graph Algorithms and Applications, vol. 27, no. 6,
Brown University, 2023, pp. 433–57, doi:10.7155/jgaa.00629.
short: A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications
27 (2023) 433–457.
date_created: 2023-08-06T22:01:11Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.7155/jgaa.00629
ec_funded: 1
external_id:
arxiv:
- '2109.14892'
file:
- access_level: open_access
checksum: 9c30d2b8e324cc1c904f2aeec92013a3
content_type: application/pdf
creator: dernst
date_created: 2023-08-07T08:00:48Z
date_updated: 2023-08-07T08:00:48Z
file_id: '13979'
file_name: 2023_JourGraphAlgorithms_Arroyo.pdf
file_size: 865774
relation: main_file
success: 1
file_date_updated: 2023-08-07T08:00:48Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '6'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 433-457
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
record:
- id: '11185'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Approximating the bundled crossing number
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: 27
year: '2023'
...
---
_id: '13331'
abstract:
- lang: eng
text: "The extension of extremal combinatorics to the setting of exterior algebra
is a work\r\nin progress that gained attention recently. In this thesis, we study
the combinatorial structure of exterior algebra by introducing a dictionary that
translates the notions from the set systems into the framework of exterior algebra.
We show both generalizations of celebrated Erdös--Ko--Rado theorem and Hilton--Milner
theorem to the setting of exterior algebra in the simplest non-trivial case of
two-forms.\r\n"
alternative_title:
- ISTA Master's Thesis
article_processing_charge: No
author:
- first_name: Seyda
full_name: Köse, Seyda
id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb
last_name: Köse
citation:
ama: Köse S. Exterior algebra and combinatorics. 2023. doi:10.15479/at:ista:13331
apa: Köse, S. (2023). Exterior algebra and combinatorics. Institute of Science
and Technology Austria. https://doi.org/10.15479/at:ista:13331
chicago: Köse, Seyda. “Exterior Algebra and Combinatorics.” Institute of Science
and Technology Austria, 2023. https://doi.org/10.15479/at:ista:13331.
ieee: S. Köse, “Exterior algebra and combinatorics,” Institute of Science and Technology
Austria, 2023.
ista: Köse S. 2023. Exterior algebra and combinatorics. Institute of Science and
Technology Austria.
mla: Köse, Seyda. Exterior Algebra and Combinatorics. Institute of Science
and Technology Austria, 2023, doi:10.15479/at:ista:13331.
short: S. Köse, Exterior Algebra and Combinatorics, Institute of Science and Technology
Austria, 2023.
date_created: 2023-07-31T10:20:55Z
date_published: 2023-07-31T00:00:00Z
date_updated: 2023-10-04T11:54:56Z
day: '31'
ddc:
- '510'
- '516'
degree_awarded: MS
department:
- _id: GradSch
- _id: UlWa
doi: 10.15479/at:ista:13331
file:
- access_level: closed
checksum: 96ee518d796d02af71395622c45de03c
content_type: application/x-zip-compressed
creator: skoese
date_created: 2023-07-31T10:16:32Z
date_updated: 2023-07-31T10:16:32Z
file_id: '13333'
file_name: Exterior Algebra and Combinatorics.zip
file_size: 28684
relation: source_file
- access_level: open_access
checksum: f610f4713f88bc477de576aaa46b114e
content_type: application/pdf
creator: skoese
date_created: 2023-08-03T15:28:55Z
date_updated: 2023-08-03T15:28:55Z
file_id: '13480'
file_name: thesis-pdfa.pdf
file_size: 4953418
relation: main_file
success: 1
file_date_updated: 2023-08-03T15:28:55Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '26'
publication_identifier:
issn:
- 2791-4585
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '12680'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
title: Exterior algebra and combinatorics
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2023'
...
---
_id: '12680'
abstract:
- lang: eng
text: The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting
family of r-element subsets of was extended to the setting of exterior algebra
in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not
been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado
theorem and the characterization of the equality case therein, as well as those
of the Hilton–Milner theorem to the setting of exterior algebra in the simplest
non-trivial case of two-forms follow from a folklore puzzle about possible arrangements
of an intersecting family of lines.
article_number: '113363'
article_processing_charge: No
article_type: letter_note
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Seyda
full_name: Köse, Seyda
id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb
last_name: Köse
citation:
ama: Ivanov G, Köse S. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms. Discrete
Mathematics. 2023;346(6). doi:10.1016/j.disc.2023.113363
apa: Ivanov, G., & Köse, S. (2023). Erdős-Ko-Rado and Hilton-Milner theorems
for two-forms. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2023.113363
chicago: Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems
for Two-Forms.” Discrete Mathematics. Elsevier, 2023. https://doi.org/10.1016/j.disc.2023.113363.
ieee: G. Ivanov and S. Köse, “Erdős-Ko-Rado and Hilton-Milner theorems for two-forms,”
Discrete Mathematics, vol. 346, no. 6. Elsevier, 2023.
ista: Ivanov G, Köse S. 2023. Erdős-Ko-Rado and Hilton-Milner theorems for two-forms.
Discrete Mathematics. 346(6), 113363.
mla: Ivanov, Grigory, and Seyda Köse. “Erdős-Ko-Rado and Hilton-Milner Theorems
for Two-Forms.” Discrete Mathematics, vol. 346, no. 6, 113363, Elsevier,
2023, doi:10.1016/j.disc.2023.113363.
short: G. Ivanov, S. Köse, Discrete Mathematics 346 (2023).
date_created: 2023-02-26T23:01:00Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2023-10-04T11:54:57Z
day: '01'
department:
- _id: UlWa
- _id: GradSch
doi: 10.1016/j.disc.2023.113363
external_id:
arxiv:
- '2201.10892'
intvolume: ' 346'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2201.10892'
month: '06'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '13331'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Erdős-Ko-Rado and Hilton-Milner theorems for two-forms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 346
year: '2023'
...
---
_id: '14660'
abstract:
- lang: eng
text: "The classical Steinitz theorem states that if the origin belongs to the interior
of the convex hull of a set \U0001D446⊂ℝ\U0001D451, then there are at most 2\U0001D451
points of \U0001D446 whose convex hull contains the origin in the interior. Bárány,
Katchalski,and Pach proved the following quantitative version of Steinitz’s theorem.
Let \U0001D444 be a convex polytope in ℝ\U0001D451 containing the standard Euclidean
unit ball \U0001D401\U0001D451. Then there exist at most 2\U0001D451 vertices
of \U0001D444 whose convex hull \U0001D444′ satisfies \U0001D45F\U0001D401\U0001D451⊂\U0001D444′
with \U0001D45F⩾\U0001D451−2\U0001D451. They conjectured that \U0001D45F⩾\U0001D450\U0001D451−1∕2
holds with a universal constant \U0001D450>0. We prove \U0001D45F⩾15\U0001D4512,
the first polynomial lower bound on \U0001D45F. Furthermore, we show that \U0001D45F
is not greater than 2/√\U0001D451."
acknowledgement: M.N. was supported by the János Bolyai Scholarship of the Hungarian
Academy of Sciences aswell as the National Research, Development and Innovation
Fund (NRDI) grants K119670 andK131529, and the ÚNKP-22-5 New National Excellence
Program of the Ministry for Innovationand Technology from the source of the NRDI
as well as the ELTE TKP 2021-NKTA-62 fundingscheme
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Márton
full_name: Naszódi, Márton
last_name: Naszódi
citation:
ama: 'Ivanov G, Naszódi M. Quantitative Steinitz theorem: A polynomial bound. Bulletin
of the London Mathematical Society. 2023. doi:10.1112/blms.12965'
apa: 'Ivanov, G., & Naszódi, M. (2023). Quantitative Steinitz theorem: A polynomial
bound. Bulletin of the London Mathematical Society. London Mathematical
Society. https://doi.org/10.1112/blms.12965'
chicago: 'Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A
Polynomial Bound.” Bulletin of the London Mathematical Society. London
Mathematical Society, 2023. https://doi.org/10.1112/blms.12965.'
ieee: 'G. Ivanov and M. Naszódi, “Quantitative Steinitz theorem: A polynomial bound,”
Bulletin of the London Mathematical Society. London Mathematical Society,
2023.'
ista: 'Ivanov G, Naszódi M. 2023. Quantitative Steinitz theorem: A polynomial bound.
Bulletin of the London Mathematical Society.'
mla: 'Ivanov, Grigory, and Márton Naszódi. “Quantitative Steinitz Theorem: A Polynomial
Bound.” Bulletin of the London Mathematical Society, London Mathematical
Society, 2023, doi:10.1112/blms.12965.'
short: G. Ivanov, M. Naszódi, Bulletin of the London Mathematical Society (2023).
date_created: 2023-12-10T23:00:58Z
date_published: 2023-12-04T00:00:00Z
date_updated: 2023-12-11T10:03:54Z
day: '04'
department:
- _id: UlWa
doi: 10.1112/blms.12965
external_id:
arxiv:
- '2212.04308'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.1112/blms.12965'
month: '12'
oa: 1
oa_version: Published Version
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- 1469-2120
issn:
- 0024-6093
publication_status: epub_ahead
publisher: London Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Quantitative Steinitz theorem: A polynomial bound'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_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
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. 2023. doi:10.1007/s00454-023-00532-x
apa: Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2023).
The crossing Tverberg theorem. Discrete and Computational Geometry. Springer
Nature. https://doi.org/10.1007/s00454-023-00532-x
chicago: Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli
Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry.
Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00532-x.
ieee: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing
Tverberg theorem,” Discrete and Computational Geometry. Springer Nature,
2023.
ista: Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg
theorem. Discrete and Computational Geometry.
mla: Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational
Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.
short: R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational
Geometry (2023).
date_created: 2023-08-06T22:01:12Z
date_published: 2023-07-27T00:00:00Z
date_updated: 2023-12-13T12:03:35Z
day: '27'
department:
- _id: UlWa
doi: 10.1007/s00454-023-00532-x
external_id:
arxiv:
- '1812.04911'
isi:
- '001038546500001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1812.04911
month: '07'
oa: 1
oa_version: Preprint
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: epub_ahead
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
year: '2023'
...
---
_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.
date_created: 2023-10-22T22:01:14Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2023-12-13T13:09:07Z
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: '12833'
abstract:
- lang: eng
text: 'The input to the token swapping problem is a graph with vertices v1, v2,
. . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal
is to get token i to vertex vi for all i= 1, . . . , n using a minimum number
of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token
swapping on a tree, also known as “sorting with a transposition tree,” is not
known to be in P nor NP-complete. We present some partial results: 1. An optimum
swap sequence may need to perform a swap on a leaf vertex that has the correct
token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that
fixes happy leaves—as all known approximation algorithms for the problem do—has
approximation factor at least 4/3. Furthermore, the two best-known 2-approximation
algorithms have approximation factor exactly 2. 3. A generalized problem—weighted
coloured token swapping—is NP-complete on trees, but solvable in polynomial time
on paths and stars. In this version, tokens and vertices have colours, and colours
have weights. The goal is to get every token to a vertex of the same colour, and
the cost of a swap is the sum of the weights of the two tokens involved.'
acknowledgement: "This work was begun at the University of Waterloo and was partially
supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n"
article_number: '9'
article_processing_charge: No
article_type: original
author:
- first_name: Ahmad
full_name: Biniaz, Ahmad
last_name: Biniaz
- first_name: Kshitij
full_name: Jain, Kshitij
last_name: Jain
- 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: Tillmann
full_name: Miltzow, Tillmann
last_name: Miltzow
- first_name: Debajyoti
full_name: Mondal, Debajyoti
last_name: Mondal
- first_name: Anurag Murty
full_name: Naredla, Anurag Murty
last_name: Naredla
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Alexi
full_name: Turcotte, Alexi
last_name: Turcotte
citation:
ama: Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. Discrete Mathematics
and Theoretical Computer Science. 2023;24(2). doi:10.46298/DMTCS.8383
apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
A. (2023). Token swapping on trees. Discrete Mathematics and Theoretical Computer
Science. EPI Sciences. https://doi.org/10.46298/DMTCS.8383
chicago: Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow,
Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token
Swapping on Trees.” Discrete Mathematics and Theoretical Computer Science.
EPI Sciences, 2023. https://doi.org/10.46298/DMTCS.8383.
ieee: A. Biniaz et al., “Token swapping on trees,” Discrete Mathematics
and Theoretical Computer Science, vol. 24, no. 2. EPI Sciences, 2023.
ista: Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec
J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical
Computer Science. 24(2), 9.
mla: Biniaz, Ahmad, et al. “Token Swapping on Trees.” Discrete Mathematics and
Theoretical Computer Science, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:10.46298/DMTCS.8383.
short: A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla,
J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science
24 (2023).
date_created: 2023-04-16T22:01:08Z
date_published: 2023-01-18T00:00:00Z
date_updated: 2024-01-04T12:42:09Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
- _id: UlWa
doi: 10.46298/DMTCS.8383
external_id:
arxiv:
- '1903.06981'
file:
- access_level: open_access
checksum: 439102ea4f6e2aeefd7107dfb9ccf532
content_type: application/pdf
creator: dernst
date_created: 2023-04-17T08:10:28Z
date_updated: 2023-04-17T08:10:28Z
file_id: '12844'
file_name: 2022_DMTCS_Biniaz.pdf
file_size: 2072197
relation: main_file
success: 1
file_date_updated: 2023-04-17T08:10:28Z
has_accepted_license: '1'
intvolume: ' 24'
issue: '2'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics and Theoretical Computer Science
publication_identifier:
eissn:
- 1365-8050
issn:
- 1462-7264
publication_status: published
publisher: EPI Sciences
quality_controlled: '1'
related_material:
record:
- id: '7950'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Token swapping on trees
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2023'
...
---
_id: '14737'
abstract:
- lang: eng
text: 'John’s fundamental theorem characterizing the largest volume ellipsoid contained
in a convex body $K$ in $\mathbb{R}^{d}$ has seen several generalizations and
extensions. One direction, initiated by V. Milman is to replace ellipsoids by
positions (affine images) of another body $L$. Another, more recent direction
is to consider logarithmically concave functions on $\mathbb{R}^{d}$ instead of
convex bodies: we designate some special, radially symmetric log-concave function
$g$ as the analogue of the Euclidean ball, and want to find its largest integral
position under the constraint that it is pointwise below some given log-concave
function $f$. We follow both directions simultaneously: we consider the functional
question, and allow essentially any meaningful function to play the role of $g$
above. Our general theorems jointly extend known results in both directions. The
dual problem in the setting of convex bodies asks for the smallest volume ellipsoid,
called Löwner’s ellipsoid, containing $K$. We consider the analogous problem for
functions: we characterize the solutions of the optimization problem of finding
a smallest integral position of some log-concave function $g$ under the constraint
that it is pointwise above $f$. It turns out that in the functional setting, the
relationship between the John and the Löwner problems is more intricate than it
is in the setting of convex bodies.'
acknowledgement: "We thank Alexander Litvak for the many discussions on Theorem 1.1.
Igor Tsiutsiurupa participated in the early stage of this project. To our deep regret,
Igor chose another road for his life and stopped working with us.\r\nThis work was
supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences [to
M.N.]; the National Research, Development, and Innovation Fund (NRDI) [K119670 and
K131529 to M.N.]; and the ÚNKP-22-5 New National Excellence Program of the Ministry
for Innovation and Technology from the source of the NRDI [to M.N.]."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Márton
full_name: Naszódi, Márton
last_name: Naszódi
citation:
ama: Ivanov G, Naszódi M. Functional John and Löwner conditions for pairs of log-concave
functions. International Mathematics Research Notices. 2023;2023(23):20613-20669.
doi:10.1093/imrn/rnad210
apa: Ivanov, G., & Naszódi, M. (2023). Functional John and Löwner conditions
for pairs of log-concave functions. International Mathematics Research Notices.
Oxford University Press. https://doi.org/10.1093/imrn/rnad210
chicago: Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions
for Pairs of Log-Concave Functions.” International Mathematics Research Notices.
Oxford University Press, 2023. https://doi.org/10.1093/imrn/rnad210.
ieee: G. Ivanov and M. Naszódi, “Functional John and Löwner conditions for pairs
of log-concave functions,” International Mathematics Research Notices,
vol. 2023, no. 23. Oxford University Press, pp. 20613–20669, 2023.
ista: Ivanov G, Naszódi M. 2023. Functional John and Löwner conditions for pairs
of log-concave functions. International Mathematics Research Notices. 2023(23),
20613–20669.
mla: Ivanov, Grigory, and Márton Naszódi. “Functional John and Löwner Conditions
for Pairs of Log-Concave Functions.” International Mathematics Research Notices,
vol. 2023, no. 23, Oxford University Press, 2023, pp. 20613–69, doi:10.1093/imrn/rnad210.
short: G. Ivanov, M. Naszódi, International Mathematics Research Notices 2023 (2023)
20613–20669.
date_created: 2024-01-08T09:48:56Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2024-01-08T09:57:25Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1093/imrn/rnad210
external_id:
arxiv:
- '2212.11781'
file:
- access_level: open_access
checksum: 353666cea80633beb0f1ffd342dff6d4
content_type: application/pdf
creator: dernst
date_created: 2024-01-08T09:53:09Z
date_updated: 2024-01-08T09:53:09Z
file_id: '14738'
file_name: 2023_IMRN_Ivanov.pdf
file_size: 815777
relation: main_file
success: 1
file_date_updated: 2024-01-08T09:53:09Z
has_accepted_license: '1'
intvolume: ' 2023'
issue: '23'
keyword:
- General Mathematics
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '12'
oa: 1
oa_version: Published Version
page: 20613-20669
publication: International Mathematics Research Notices
publication_identifier:
eissn:
- 1687-0247
issn:
- 1073-7928
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
status: public
title: Functional John and Löwner conditions for pairs of log-concave functions
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...
---
_id: '9651'
abstract:
- lang: eng
text: We introduce a hierachy of equivalence relations on the set of separated nets
of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞).
Two separated nets are called ϕ-displacement equivalent if, roughly speaking,
there is a bijection between them which, for large radii R, displaces points of
norm at most R by something of order at most ϕ(R). We show that the spectrum of
ϕ-displacement equivalence spans from the established notion of bounded displacement
equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation,
coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between
the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown
to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞.
We further undertake a comparison of our notion of ϕ-displacement equivalence
with previously studied relations on separated nets. Particular attention is given
to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz
equivalence.
acknowledgement: 'Open access funding provided by Institute of Science and Technology
(IST Austria). This work was started while both authors were employed at the University
of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35.
It was continued when the first named author was employed at University of Leipzig
and the second named author was employed at Institute of Science and Technology
of Austria, where he was supported by an IST Fellowship.'
article_number: '15'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Michael
full_name: Dymond, Michael
last_name: Dymond
- first_name: Vojtech
full_name: Kaluza, Vojtech
id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
last_name: Kaluza
orcid: 0000-0002-2512-8698
citation:
ama: Dymond M, Kaluza V. Divergence of separated nets with respect to displacement
equivalence. Geometriae Dedicata. 2023. doi:10.1007/s10711-023-00862-3
apa: Dymond, M., & Kaluza, V. (2023). Divergence of separated nets with respect
to displacement equivalence. Geometriae Dedicata. Springer Nature. https://doi.org/10.1007/s10711-023-00862-3
chicago: Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with
Respect to Displacement Equivalence.” Geometriae Dedicata. Springer Nature,
2023. https://doi.org/10.1007/s10711-023-00862-3.
ieee: M. Dymond and V. Kaluza, “Divergence of separated nets with respect to displacement
equivalence,” Geometriae Dedicata. Springer Nature, 2023.
ista: Dymond M, Kaluza V. 2023. Divergence of separated nets with respect to displacement
equivalence. Geometriae Dedicata., 15.
mla: Dymond, Michael, and Vojtech Kaluza. “Divergence of Separated Nets with Respect
to Displacement Equivalence.” Geometriae Dedicata, 15, Springer Nature,
2023, doi:10.1007/s10711-023-00862-3.
short: M. Dymond, V. Kaluza, Geometriae Dedicata (2023).
date_created: 2021-07-14T07:01:27Z
date_published: 2023-11-17T00:00:00Z
date_updated: 2024-01-11T13:06:32Z
day: '17'
department:
- _id: UlWa
doi: 10.1007/s10711-023-00862-3
external_id:
arxiv:
- '2102.13046'
isi:
- '001105681500001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s10711-023-00862-3
month: '11'
oa: 1
oa_version: Published Version
publication: Geometriae Dedicata
publication_identifier:
eissn:
- 1572-9168
issn:
- 0046-5755
publication_status: epub_ahead
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Divergence of separated nets with respect to displacement equivalence
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '13270'
abstract:
- lang: eng
text: "Consider a geodesic triangle on a surface of constant curvature and subdivide
it recursively into four triangles by joining the midpoints of its edges. We show
the existence of a uniform δ>0\r\n such that, at any step of the subdivision,
all the triangle angles lie in the interval (δ,π−δ)\r\n. Additionally, we exhibit
stabilising behaviours for both angles and lengths as this subdivision progresses."
acknowledgement: Open access funding provided by the Institute of Science and Technology
(IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Florestan R
full_name: Brunck, Florestan R
id: 6ab6e556-f394-11eb-9cf6-9dfb78f00d8d
last_name: Brunck
citation:
ama: Brunck FR. Iterated medial triangle subdivision in surfaces of constant curvature.
Discrete and Computational Geometry. 2023;70(3):1059-1089. doi:10.1007/s00454-023-00500-5
apa: Brunck, F. R. (2023). Iterated medial triangle subdivision in surfaces of constant
curvature. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00500-5
chicago: Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces
of Constant Curvature.” Discrete and Computational Geometry. Springer Nature,
2023. https://doi.org/10.1007/s00454-023-00500-5.
ieee: F. R. Brunck, “Iterated medial triangle subdivision in surfaces of constant
curvature,” Discrete and Computational Geometry, vol. 70, no. 3. Springer
Nature, pp. 1059–1089, 2023.
ista: Brunck FR. 2023. Iterated medial triangle subdivision in surfaces of constant
curvature. Discrete and Computational Geometry. 70(3), 1059–1089.
mla: Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant
Curvature.” Discrete and Computational Geometry, vol. 70, no. 3, Springer
Nature, 2023, pp. 1059–89, doi:10.1007/s00454-023-00500-5.
short: F.R. Brunck, Discrete and Computational Geometry 70 (2023) 1059–1089.
date_created: 2023-07-23T22:01:14Z
date_published: 2023-07-05T00:00:00Z
date_updated: 2024-01-29T11:16:16Z
day: '05'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-023-00500-5
external_id:
arxiv:
- '2107.04112'
isi:
- '001023742800003'
file:
- access_level: open_access
checksum: 865e68daafdd4edcfc280172ec50f5ea
content_type: application/pdf
creator: dernst
date_created: 2024-01-29T11:15:22Z
date_updated: 2024-01-29T11:15:22Z
file_id: '14897'
file_name: 2023_DiscreteComputGeometry_Brunck.pdf
file_size: 1466020
relation: main_file
success: 1
file_date_updated: 2024-01-29T11:15:22Z
has_accepted_license: '1'
intvolume: ' 70'
isi: 1
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 1059-1089
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: Iterated medial triangle subdivision in surfaces of constant curvature
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: 70
year: '2023'
...
---
_id: '11991'
abstract:
- lang: eng
text: The study of the complexity of the constraint satisfaction problem (CSP),
centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in
the last two decades. After a long concerted effort and many partial results,
the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and
Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP,
has started to gain prominence. In this survey, we explain the importance of promise
CSP and highlight many new very interesting features that the study of promise
CSP has brought to light. The complexity classification quest for the promise
CSP is wide open, and we argue that, despite the promise CSP being more general,
this quest is rather more accessible to a wide range of researchers than the dichotomy-led
study of the CSP has been.
article_processing_charge: No
article_type: original
author:
- first_name: Andrei
full_name: Krokhin, Andrei
last_name: Krokhin
- first_name: Jakub
full_name: Opršal, Jakub
id: ec596741-c539-11ec-b829-c79322a91242
last_name: Opršal
orcid: 0000-0003-1245-3456
citation:
ama: Krokhin A, Opršal J. An invitation to the promise constraint satisfaction problem.
ACM SIGLOG News. 2022;9(3):30-59. doi:10.1145/3559736.3559740
apa: Krokhin, A., & Opršal, J. (2022). An invitation to the promise constraint
satisfaction problem. ACM SIGLOG News. Association for Computing Machinery.
https://doi.org/10.1145/3559736.3559740
chicago: Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint
Satisfaction Problem.” ACM SIGLOG News. Association for Computing Machinery,
2022. https://doi.org/10.1145/3559736.3559740.
ieee: A. Krokhin and J. Opršal, “An invitation to the promise constraint satisfaction
problem,” ACM SIGLOG News, vol. 9, no. 3. Association for Computing Machinery,
pp. 30–59, 2022.
ista: Krokhin A, Opršal J. 2022. An invitation to the promise constraint satisfaction
problem. ACM SIGLOG News. 9(3), 30–59.
mla: Krokhin, Andrei, and Jakub Opršal. “An Invitation to the Promise Constraint
Satisfaction Problem.” ACM SIGLOG News, vol. 9, no. 3, Association for
Computing Machinery, 2022, pp. 30–59, doi:10.1145/3559736.3559740.
short: A. Krokhin, J. Opršal, ACM SIGLOG News 9 (2022) 30–59.
date_created: 2022-08-27T11:23:37Z
date_published: 2022-07-01T00:00:00Z
date_updated: 2022-09-05T08:19:38Z
day: '01'
department:
- _id: UlWa
doi: 10.1145/3559736.3559740
external_id:
arxiv:
- '2208.13538'
intvolume: ' 9'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/2208.13538
month: '07'
oa: 1
oa_version: Preprint
page: 30-59
publication: ACM SIGLOG News
publication_identifier:
issn:
- 2372-3491
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: An invitation to the promise constraint satisfaction problem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2022'
...
---
_id: '11938'
abstract:
- lang: eng
text: A matching is compatible to two or more labeled point sets of size n with
labels {1, . . . , n} if its straight-line drawing on each of these point sets
is crossing-free. We study the maximum number of edges in a matching compatible
to two or more labeled point sets in general position in the plane. We show that
for any two labeled sets of n points in convex position there exists a compatible
matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets
we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound,
we use probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1))
edges. Finally, we show that Θ(log n) copies of any set of n points are necessary
and sufficient for the existence of labelings of these point sets such that any
compatible matching consists only of a single edge.
acknowledgement: 'A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
article_processing_charge: No
article_type: original
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- 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: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591
apa: Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph
Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” Journal of Graph Algorithms and Applications. Brown University,
2022. https://doi.org/10.7155/jgaa.00591.
ieee: O. Aichholzer et al., “On compatible matchings,” Journal of Graph
Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240,
2022.
ista: Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and
Applications. 26(2), 225–240.
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms
and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022)
225–240.
date_created: 2022-08-21T22:01:56Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-02-23T13:54:21Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.7155/jgaa.00591
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
file:
- access_level: open_access
checksum: dc6e255e3558faff924fd9e370886c11
content_type: application/pdf
creator: dernst
date_created: 2022-08-22T06:42:42Z
date_updated: 2022-08-22T06:42:42Z
file_id: '11940'
file_name: 2022_JourGraphAlgorithmsApplic_Aichholzer.pdf
file_size: 694538
relation: main_file
success: 1
file_date_updated: 2022-08-22T06:42:42Z
has_accepted_license: '1'
intvolume: ' 26'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 225-240
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
record:
- id: '9296'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
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: 26
year: '2022'
...
---
_id: '11777'
abstract:
- lang: eng
text: "In this dissertation we study coboundary expansion of simplicial complex
with a view of giving geometric applications.\r\nOur main novel tool is an equivariant
version of Gromov's celebrated Topological Overlap Theorem. The equivariant topological
overlap theorem leads to various geometric applications including a quantitative
non-embeddability result for sufficiently thick buildings (which partially resolves
a conjecture of Tancer and Vorwerk) and an improved lower bound on the pair-crossing
number of (bounded degree) expander graphs. Additionally, we will give new proofs
for several known lower bounds for geometric problems such as the number of Tverberg
partitions or the crossing number of complete bipartite graphs.\r\nFor the aforementioned
applications one is naturally lead to study expansion properties of joins of simplicial
complexes. In the presence of a special certificate for expansion (as it is the
case, e.g., for spherical buildings), the join of two expanders is an expander.
On the flip-side, we report quite some evidence that coboundary expansion exhibits
very non-product-like behaviour under taking joins. For instance, we exhibit infinite
families of graphs $(G_n)_{n\\in \\mathbb{N}}$ and $(H_n)_{n\\in\\mathbb{N}}$
whose join $G_n*H_n$ has expansion of lower order than the product of the expansion
constant of the graphs. Moreover, we show an upper bound of $(d+1)/2^d$ on the
normalized coboundary expansion constants for the complete multipartite complex
$[n]^{*(d+1)}$ (under a mild divisibility condition on $n$).\r\nVia the probabilistic
method the latter result extends to an upper bound of $(d+1)/2^d+\\varepsilon$
on the coboundary expansion constant of the spherical building associated with
$\\mathrm{PGL}_{d+2}(\\mathbb{F}_q)$ for any $\\varepsilon>0$ and sufficiently
large $q=q(\\varepsilon)$. This disproves a conjecture of Lubotzky, Meshulam and
Mozes -- in a rather strong sense.\r\nBy improving on existing lower bounds we
make further progress towards closing the gap between the known lower and upper
bounds on the coboundary expansion constants of $[n]^{*(d+1)}$. The best improvements
we achieve using computer-aided proofs and flag algebras. The exact value even
for the complete $3$-partite $2$-dimensional complex $[n]^{*3}$ remains unknown
but we are happy to conjecture a precise value for every $n$. %Moreover, we show
that a previously shown lower bound on the expansion constant of the spherical
building associated with $\\mathrm{PGL}_{2}(\\mathbb{F}_q)$ is not tight.\r\nIn
a loosely structured, last chapter of this thesis we collect further smaller observations
related to expansion. We point out a link between discrete Morse theory and a
technique for showing coboundary expansion, elaborate a bit on the hardness of
computing coboundary expansion constants, propose a new criterion for coboundary
expansion (in a very dense setting) and give one way of making the folklore result
that expansion of links is a necessary condition for a simplicial complex to be
an expander precise."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Pascal
full_name: Wild, Pascal
id: 4C20D868-F248-11E8-B48F-1D18A9856A87
last_name: Wild
citation:
ama: Wild P. High-dimensional expansion and crossing numbers of simplicial complexes.
2022. doi:10.15479/at:ista:11777
apa: Wild, P. (2022). High-dimensional expansion and crossing numbers of simplicial
complexes. Institute of Science and Technology. https://doi.org/10.15479/at:ista:11777
chicago: Wild, Pascal. “High-Dimensional Expansion and Crossing Numbers of Simplicial
Complexes.” Institute of Science and Technology, 2022. https://doi.org/10.15479/at:ista:11777.
ieee: P. Wild, “High-dimensional expansion and crossing numbers of simplicial complexes,”
Institute of Science and Technology, 2022.
ista: Wild P. 2022. High-dimensional expansion and crossing numbers of simplicial
complexes. Institute of Science and Technology.
mla: Wild, Pascal. High-Dimensional Expansion and Crossing Numbers of Simplicial
Complexes. Institute of Science and Technology, 2022, doi:10.15479/at:ista:11777.
short: P. Wild, High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes,
Institute of Science and Technology, 2022.
date_created: 2022-08-10T15:51:19Z
date_published: 2022-08-11T00:00:00Z
date_updated: 2023-06-22T09:56:36Z
day: '11'
ddc:
- '500'
- '516'
- '514'
degree_awarded: PhD
department:
- _id: GradSch
- _id: UlWa
doi: 10.15479/at:ista:11777
ec_funded: 1
file:
- access_level: open_access
checksum: f5f3af1fb7c8a24b71ddc88ad7f7c5b4
content_type: text/x-python
creator: pwild
date_created: 2022-08-10T15:34:04Z
date_updated: 2022-08-10T15:34:04Z
description: Code for computer-assisted proofs in Section 8.4.7 in Thesis
file_id: '11780'
file_name: flags.py
file_size: 16828
relation: supplementary_material
- access_level: open_access
checksum: 1f7c12dfe3bdaa9b147e4fbc3d34e3d5
content_type: text/x-c++src
creator: pwild
date_created: 2022-08-10T15:34:10Z
date_updated: 2022-08-10T15:34:10Z
description: Code for proof of Lemma 8.20 in Thesis
file_id: '11781'
file_name: lowerbound.cpp
file_size: 12226
relation: supplementary_material
- access_level: open_access
checksum: 4cf81455c49e5dec3b9b2e3980137eeb
content_type: text/x-python
creator: pwild
date_created: 2022-08-10T15:34:17Z
date_updated: 2022-08-10T15:34:17Z
description: Code for proof of Proposition 7.9 in Thesis
file_id: '11782'
file_name: upperbound.py
file_size: 3240
relation: supplementary_material
- access_level: open_access
checksum: 4e96575b10cbe4e0d0db2045b2847774
content_type: application/pdf
creator: pwild
date_created: 2022-08-11T16:08:33Z
date_updated: 2022-08-11T16:08:33Z
file_id: '11809'
file_name: finalthesisPascalWildPDFA.pdf
file_size: 5086282
relation: main_file
title: High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes
- access_level: closed
checksum: 92d94842a1fb6dca5808448137573b2e
content_type: application/zip
creator: pwild
date_created: 2022-08-11T16:09:19Z
date_updated: 2022-08-11T16:09:19Z
file_id: '11810'
file_name: ThesisSubmission.zip
file_size: 18150068
relation: source_file
file_date_updated: 2022-08-11T16:09:19Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '170'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication_identifier:
isbn:
- 978-3-99078-021-3
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
title: High-dimensional expansion and crossing numbers of simplicial complexes
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2022'
...
---
_id: '10335'
abstract:
- lang: eng
text: "Van der Holst and Pendavingh introduced a graph parameter σ, which coincides
with the more famous Colin de Verdière graph parameter μ for small values. However,
the definition of a is much more geometric/topological directly reflecting embeddability
properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G)
for any graph G. We confirm this conjecture. As far as we know, this is the first
topological upper bound on σ(G) which is, in general, tight.\r\nEquality between
μ and σ does not hold in general as van der Holst and Pendavingh showed that there
is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much
smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8.
We also prove that, in general, the gap can be large: The incidence graphs Hq
of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2."
acknowledgement: 'V. K. gratefully acknowledges the support of Austrian Science Fund
(FWF): P 30902-N35. This work was done mostly while he was employed at the University
of Innsbruck. During the early stage of this research, V. K. was partially supported
by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y
of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University
project UNCE/SCI/004.'
article_processing_charge: No
article_type: original
author:
- first_name: Vojtech
full_name: Kaluza, Vojtech
id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
last_name: Kaluza
orcid: 0000-0002-2512-8698
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
citation:
ama: Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations
of graphs. Combinatorica. 2022;42:1317-1345. doi:10.1007/s00493-021-4443-7
apa: Kaluza, V., & Tancer, M. (2022). Even maps, the Colin de Verdière number
and representations of graphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4443-7
chicago: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
and Representations of Graphs.” Combinatorica. Springer Nature, 2022. https://doi.org/10.1007/s00493-021-4443-7.
ieee: V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations
of graphs,” Combinatorica, vol. 42. Springer Nature, pp. 1317–1345, 2022.
ista: Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations
of graphs. Combinatorica. 42, 1317–1345.
mla: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
and Representations of Graphs.” Combinatorica, vol. 42, Springer Nature,
2022, pp. 1317–45, doi:10.1007/s00493-021-4443-7.
short: V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.
date_created: 2021-11-25T13:49:16Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-02T06:43:27Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.1007/s00493-021-4443-7
external_id:
arxiv:
- '1907.05055'
isi:
- '000798210100003'
intvolume: ' 42'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1907.05055'
month: '12'
oa: 1
oa_version: Preprint
page: 1317-1345
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Even maps, the Colin de Verdière number and representations of graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
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
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: '10887'
abstract:
- lang: eng
text: "We introduce a new way of representing logarithmically concave functions
on Rd. It allows us to extend the notion of the largest volume ellipsoid contained
in a convex body to the setting of logarithmically concave functions as follows.
For every s>0, we define a class of non-negative functions on Rd derived from
ellipsoids in Rd+1. For any log-concave function f on Rd , and any fixed s>0,
we consider functions belonging to this class, and find the one with the largest
integral under the condition that it is pointwise less than or equal to f, and
we call it the John s-function of f. After establishing existence and uniqueness,
we give a characterization of this function similar to the one given by John in
his fundamental theorem. We find that John s-functions converge to characteristic
functions of ellipsoids as s tends to zero and to Gaussian densities as s tends
to infinity.\r\nAs an application, we prove a quantitative Helly type result:
the integral of the pointwise minimum of any family of log-concave functions is
at least a constant cd multiple of the integral of the pointwise minimum of a
properly chosen subfamily of size 3d+2, where cd depends only on d."
acknowledgement: 'G.I. was supported by the Ministry of Education and Science of the
Russian Federation in the framework of MegaGrant no 075-15-2019-1926. M.N. was supported
by the National Research, Development and Innovation Fund (NRDI) grants K119670
and KKP-133864 as well as the Bolyai Scholarship of the Hungarian Academy of Sciences
and the New National Excellence Programme and the TKP2020-NKA-06 program provided
by the NRDI. '
article_number: '109441'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Márton
full_name: Naszódi, Márton
last_name: Naszódi
citation:
ama: Ivanov G, Naszódi M. Functional John ellipsoids. Journal of Functional Analysis.
2022;282(11). doi:10.1016/j.jfa.2022.109441
apa: Ivanov, G., & Naszódi, M. (2022). Functional John ellipsoids. Journal
of Functional Analysis. Elsevier. https://doi.org/10.1016/j.jfa.2022.109441
chicago: Ivanov, Grigory, and Márton Naszódi. “Functional John Ellipsoids.” Journal
of Functional Analysis. Elsevier, 2022. https://doi.org/10.1016/j.jfa.2022.109441.
ieee: G. Ivanov and M. Naszódi, “Functional John ellipsoids,” Journal of Functional
Analysis, vol. 282, no. 11. Elsevier, 2022.
ista: Ivanov G, Naszódi M. 2022. Functional John ellipsoids. Journal of Functional
Analysis. 282(11), 109441.
mla: Ivanov, Grigory, and Márton Naszódi. “Functional John Ellipsoids.” Journal
of Functional Analysis, vol. 282, no. 11, 109441, Elsevier, 2022, doi:10.1016/j.jfa.2022.109441.
short: G. Ivanov, M. Naszódi, Journal of Functional Analysis 282 (2022).
date_created: 2022-03-20T23:01:38Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-08-02T14:51:11Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1016/j.jfa.2022.109441
external_id:
arxiv:
- '2006.09934'
isi:
- '000781371300008'
file:
- access_level: open_access
checksum: 1cf185e264e04c87cb1ce67a00db88ab
content_type: application/pdf
creator: dernst
date_created: 2022-08-02T10:40:48Z
date_updated: 2022-08-02T10:40:48Z
file_id: '11721'
file_name: 2022_JourFunctionalAnalysis_Ivanov.pdf
file_size: 734482
relation: main_file
success: 1
file_date_updated: 2022-08-02T10:40:48Z
has_accepted_license: '1'
intvolume: ' 282'
isi: 1
issue: '11'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: Journal of Functional Analysis
publication_identifier:
eissn:
- 1096-0783
issn:
- 0022-1236
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Functional John ellipsoids
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: 282
year: '2022'
...
---
_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.
date_created: 2023-01-12T12:02:28Z
date_published: 2022-11-14T00:00:00Z
date_updated: 2023-08-04T08:51:08Z
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: '11593'
abstract:
- lang: eng
text: 'A drawing of a graph on a surface is independently even if every pair of
nonadjacent edges in the drawing crosses an even number of times. The Z2 -genus
of a graph G is the minimum g such that G has an independently even drawing on
the orientable surface of genus g. An unpublished result by Robertson and Seymour
implies that for every t, every graph of sufficiently large genus contains as
a minor a projective t×t grid or one of the following so-called t -Kuratowski
graphs: K3,t, or t copies of K5 or K3,3 sharing at most two common vertices. We
show that the Z2-genus of graphs in these families is unbounded in t; in fact,
equal to their genus. Together, this implies that the genus of a graph is bounded
from above by a function of its Z2-genus, solving a problem posed by Schaefer
and Štefankovič, and giving an approximate version of the Hanani–Tutte theorem
on orientable surfaces. We also obtain an analogous result for Euler genus and
Euler Z2-genus of graphs.'
acknowledgement: "We thank Zdeněk Dvořák, Xavier Goaoc, and Pavel Paták for helpful
discussions. We also thank Bojan Mohar, Paul Seymour, Gelasio Salazar, Jim Geelen,
and John Maharry for information about their unpublished results related to Conjecture
3.1. Finally we thank the reviewers for corrections and suggestions for improving
the presentation.\r\nSupported by Austrian Science Fund (FWF): M2281-N35. Supported
by project 19-04113Y of the Czech Science Foundation (GAČR), by the Czech-French
collaboration project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM), and by Charles University
project UNCE/SCI/004."
article_processing_charge: No
article_type: original
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. Discrete and Computational
Geometry. 2022;68:425-447. doi:10.1007/s00454-022-00412-w
apa: Fulek, R., & Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. Discrete
and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00412-w
chicago: Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete
and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00412-w.
ieee: R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” Discrete and
Computational Geometry, vol. 68. Springer Nature, pp. 425–447, 2022.
ista: Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational
Geometry. 68, 425–447.
mla: Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete
and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 425–47, doi:10.1007/s00454-022-00412-w.
short: R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.
date_created: 2022-07-17T22:01:56Z
date_published: 2022-09-01T00:00:00Z
date_updated: 2023-08-14T12:43:52Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00412-w
external_id:
arxiv:
- '1803.05085'
isi:
- '000825014500001'
intvolume: ' 68'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.05085
month: '09'
oa: 1
oa_version: Preprint
page: 425-447
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: '186'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The Z2-Genus of Kuratowski minors
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 68
year: '2022'
...
---
_id: '11185'
abstract:
- lang: eng
text: Bundling crossings is a strategy which can enhance the readability of graph
drawings. In this paper we consider bundlings for families of pseudosegments,
i.e., simple curves such that any two have share at most one point at which they
cross. Our main result is that there is a polynomial-time algorithm to compute
an 8-approximation of the bundled crossing number of such instances (up to adding
a term depending on the facial structure). This 8-approximation also holds for
bundlings of good drawings of graphs. In the special case of circular drawings
the approximation factor is 8 (no extra term), this improves upon the 10-approximation
of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection
graph of the pseudosegments is bipartite.
acknowledgement: This work was initiated during the Workshop on Geometric Graphs in
November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian
Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during
the workshop. The first author has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Sklodowska Curie grant agreement
No 754411. The second author has been supported by the German Research Foundation
DFG Project FE 340/12-1.
article_processing_charge: No
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Stefan
full_name: Felsner, Stefan
last_name: Felsner
citation:
ama: 'Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In:
WALCOM 2022: Algorithms and Computation. Vol 13174. LNCS. Springer Nature;
2022:383-395. doi:10.1007/978-3-030-96731-4_31'
apa: 'Arroyo Guevara, A. M., & Felsner, S. (2022). Approximating the bundled
crossing number. In WALCOM 2022: Algorithms and Computation (Vol. 13174,
pp. 383–395). Jember, Indonesia: Springer Nature. https://doi.org/10.1007/978-3-030-96731-4_31'
chicago: 'Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
Crossing Number.” In WALCOM 2022: Algorithms and Computation, 13174:383–95.
LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-030-96731-4_31.'
ieee: 'A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing
number,” in WALCOM 2022: Algorithms and Computation, Jember, Indonesia,
2022, vol. 13174, pp. 383–395.'
ista: 'Arroyo Guevara AM, Felsner S. 2022. Approximating the bundled crossing number.
WALCOM 2022: Algorithms and Computation. WALCOM: Algorithms and ComputationLNCS
vol. 13174, 383–395.'
mla: 'Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
Number.” WALCOM 2022: Algorithms and Computation, vol. 13174, Springer
Nature, 2022, pp. 383–95, doi:10.1007/978-3-030-96731-4_31.'
short: 'A.M. Arroyo Guevara, S. Felsner, in:, WALCOM 2022: Algorithms and Computation,
Springer Nature, 2022, pp. 383–395.'
conference:
end_date: 2022-03-26
location: Jember, Indonesia
name: 'WALCOM: Algorithms and Computation'
start_date: 2022-03-24
date_created: 2022-04-17T22:01:47Z
date_published: 2022-03-16T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '16'
department:
- _id: UlWa
doi: 10.1007/978-3-030-96731-4_31
ec_funded: 1
external_id:
arxiv:
- '2109.14892'
intvolume: ' 13174'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.14892'
month: '03'
oa: 1
oa_version: Preprint
page: 383-395
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 'WALCOM 2022: Algorithms and Computation'
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030967307'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '13969'
relation: later_version
status: public
scopus_import: '1'
series_title: LNCS
status: public
title: Approximating the bundled crossing number
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13174
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.
date_created: 2023-10-01T22:01:14Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2023-10-03T08:04:03Z
day: '01'
department:
- _id: UlWa
doi: 10.24033/ast.1188
intvolume: ' 438'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 438
year: '2022'
...
---
_id: '11435'
abstract:
- lang: eng
text: 'We introduce a new variant of quantitative Helly-type theorems: the minimal
homothetic distance of the intersection of a family of convex sets to the intersection
of a subfamily of a fixed size. As an application, we establish the following
quantitative Helly-type result for the diameter. If $K$ is the intersection of
finitely many convex bodies in $\mathbb{R}^d$, then one can select $2d$ of these
bodies whose intersection is of diameter at most $(2d)^3{diam}(K)$. The best previously
known estimate, due to Brazitikos [Bull. Hellenic Math. Soc., 62 (2018), pp. 19--25],
is $c d^{11/2}$. Moreover, we confirm that the multiplicative factor $c d^{1/2}$
conjectured by Bárány, Katchalski, and Pach [Proc. Amer. Math. Soc., 86 (1982),
pp. 109--114] cannot be improved. The bounds above follow from our key result
that concerns sparse approximation of a convex polytope by the convex hull of
a well-chosen subset of its vertices: Assume that $Q \subset {\mathbb R}^d$ is
a polytope whose centroid is the origin. Then there exist at most 2d vertices
of $Q$ whose convex hull $Q^{\prime \prime}$ satisfies $Q \subset - 8d^3 Q^{\prime
\prime}.$'
acknowledgement: "G.I. acknowledges the financial support from the Ministry of Educational
and Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926.
M.N. was supported by the National Research, Development and Innovation Fund (NRDI)
grants K119670 and\r\nKKP-133864 as well as the Bolyai Scholarship of the Hungarian
Academy of Sciences and the New National Excellence Programme and the TKP2020-NKA-06
program provided by the NRDI."
article_processing_charge: No
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Marton
full_name: Naszodi, Marton
last_name: Naszodi
citation:
ama: 'Ivanov G, Naszodi M. A quantitative Helly-type theorem: Containment in a homothet.
SIAM Journal on Discrete Mathematics. 2022;36(2):951-957. doi:10.1137/21M1403308'
apa: 'Ivanov, G., & Naszodi, M. (2022). A quantitative Helly-type theorem: Containment
in a homothet. SIAM Journal on Discrete Mathematics. Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/21M1403308'
chicago: 'Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem:
Containment in a Homothet.” SIAM Journal on Discrete Mathematics. Society
for Industrial and Applied Mathematics, 2022. https://doi.org/10.1137/21M1403308.'
ieee: 'G. Ivanov and M. Naszodi, “A quantitative Helly-type theorem: Containment
in a homothet,” SIAM Journal on Discrete Mathematics, vol. 36, no. 2. Society
for Industrial and Applied Mathematics, pp. 951–957, 2022.'
ista: 'Ivanov G, Naszodi M. 2022. A quantitative Helly-type theorem: Containment
in a homothet. SIAM Journal on Discrete Mathematics. 36(2), 951–957.'
mla: 'Ivanov, Grigory, and Marton Naszodi. “A Quantitative Helly-Type Theorem: Containment
in a Homothet.” SIAM Journal on Discrete Mathematics, vol. 36, no. 2, Society
for Industrial and Applied Mathematics, 2022, pp. 951–57, doi:10.1137/21M1403308.'
short: G. Ivanov, M. Naszodi, SIAM Journal on Discrete Mathematics 36 (2022) 951–957.
date_created: 2022-06-05T22:01:50Z
date_published: 2022-04-11T00:00:00Z
date_updated: 2023-10-18T06:58:03Z
day: '11'
department:
- _id: UlWa
doi: 10.1137/21M1403308
external_id:
arxiv:
- '2103.04122'
isi:
- '000793158200002'
intvolume: ' 36'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2103.04122'
month: '04'
oa: 1
oa_version: Preprint
page: 951-957
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
issn:
- 0895-4801
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'A quantitative Helly-type theorem: Containment in a homothet'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2022'
...
---
_id: '9296'
abstract:
- lang: eng
text: ' matching is compatible to two or more labeled point sets of size n with
labels {1,…,n} if its straight-line drawing on each of these point sets is
crossing-free. We study the maximum number of edges in a matching compatible to
two or more labeled point sets in general position in the plane. We show that
for any two labeled convex sets of n points there exists a compatible matching
with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct
compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use
probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges.
Finally, we show that Θ(logn) copies of any set of n points are necessary and
sufficient for the existence of a labeling such that any compatible matching consists
only of a single edge.'
acknowledgement: 'A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- 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: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
In: 15th International Conference on Algorithms and Computation. Vol 12635.
Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18'
apa: 'Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International
Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon,
Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18'
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” In 15th International Conference on Algorithms and Computation,
12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.
ieee: O. Aichholzer et al., “On compatible matchings,” in 15th International
Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635,
pp. 221–233.
ista: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference
on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol.
12635, 221–233.'
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International
Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021,
pp. 221–33, doi:10.1007/978-3-030-68211-8_18.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and
Computation, Springer Nature, 2021, pp. 221–233.
conference:
end_date: 2021-03-02
location: Yangon, Myanmar
name: 'WALCOM: Algorithms and Computation'
start_date: 2021-02-28
date_created: 2021-03-28T22:01:41Z
date_published: 2021-02-16T00:00:00Z
date_updated: 2023-02-21T16:33:44Z
day: '16'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.1007/978-3-030-68211-8_18
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
intvolume: ' 12635'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.03928
month: '02'
oa: 1
oa_version: Preprint
page: 221-233
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: 15th International Conference on Algorithms and Computation
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030682101'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11938'
relation: later_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 12635
year: '2021'
...
---
_id: '9037'
abstract:
- lang: eng
text: "We continue our study of ‘no‐dimension’ analogues of basic theorems in combinatorial
and convex geometry in Banach spaces. We generalize some results of the paper
(Adiprasito, Bárány and Mustafa, ‘Theorems of Carathéodory, Helly, and Tverberg
without dimension’, Proceedings of the Thirtieth Annual ACM‐SIAM Symposium on
Discrete Algorithms (Society for Industrial and Applied Mathematics, San Diego,
California, 2019) 2350–2360) and prove no‐dimension versions of the colored Tverberg
theorem, the selection lemma and the weak \U0001D700 ‐net theorem in Banach spaces
of type \U0001D45D>1 . To prove these results, we use the original ideas of Adiprasito,
Bárány and Mustafa for the Euclidean case, our no‐dimension version of the Radon
theorem and slightly modified version of the celebrated Maurey lemma."
acknowledgement: "I wish to thank Imre Bárány for bringing the problem to my attention.
I am grateful to Marton Naszódi and Igor Tsiutsiurupa for useful remarks and help
with the text.\r\nThe author acknowledges the financial support from the Ministry
of Educational and Science of the Russian Federation in the framework of MegaGrant
no 075‐15‐2019‐1926."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
citation:
ama: Ivanov G. No-dimension Tverberg’s theorem and its corollaries in Banach spaces
of type p. Bulletin of the London Mathematical Society. 2021;53(2):631-641.
doi:10.1112/blms.12449
apa: Ivanov, G. (2021). No-dimension Tverberg’s theorem and its corollaries in Banach
spaces of type p. Bulletin of the London Mathematical Society. London Mathematical
Society. https://doi.org/10.1112/blms.12449
chicago: Ivanov, Grigory. “No-Dimension Tverberg’s Theorem and Its Corollaries in
Banach Spaces of Type P.” Bulletin of the London Mathematical Society.
London Mathematical Society, 2021. https://doi.org/10.1112/blms.12449.
ieee: G. Ivanov, “No-dimension Tverberg’s theorem and its corollaries in Banach
spaces of type p,” Bulletin of the London Mathematical Society, vol. 53,
no. 2. London Mathematical Society, pp. 631–641, 2021.
ista: Ivanov G. 2021. No-dimension Tverberg’s theorem and its corollaries in Banach
spaces of type p. Bulletin of the London Mathematical Society. 53(2), 631–641.
mla: Ivanov, Grigory. “No-Dimension Tverberg’s Theorem and Its Corollaries in Banach
Spaces of Type P.” Bulletin of the London Mathematical Society, vol. 53,
no. 2, London Mathematical Society, 2021, pp. 631–41, doi:10.1112/blms.12449.
short: G. Ivanov, Bulletin of the London Mathematical Society 53 (2021) 631–641.
date_created: 2021-01-24T23:01:08Z
date_published: 2021-04-01T00:00:00Z
date_updated: 2023-08-07T13:35:20Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1112/blms.12449
external_id:
arxiv:
- '1912.08561'
isi:
- '000607265100001'
file:
- access_level: open_access
checksum: e6ceaa6470d835eb4c211cbdd38fdfd1
content_type: application/pdf
creator: kschuh
date_created: 2021-08-06T09:59:45Z
date_updated: 2021-08-06T09:59:45Z
file_id: '9796'
file_name: 2021_BLMS_Ivanov.pdf
file_size: 194550
relation: main_file
success: 1
file_date_updated: 2021-08-06T09:59:45Z
has_accepted_license: '1'
intvolume: ' 53'
isi: 1
issue: '2'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 631-641
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- '14692120'
issn:
- '00246093'
publication_status: published
publisher: London Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: No-dimension Tverberg's theorem and its corollaries in Banach spaces of type
p
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 53
year: '2021'
...
---
_id: '9098'
abstract:
- lang: eng
text: "We study properties of the volume of projections of the n-dimensional\r\ncross-polytope
$\\crosp^n = \\{ x \\in \\R^n \\mid |x_1| + \\dots + |x_n| \\leqslant 1\\}.$ We
prove that the projection of $\\crosp^n$ onto a k-dimensional coordinate subspace
has the maximum possible volume for k=2 and for k=3.\r\nWe obtain the exact lower
bound on the volume of such a projection onto a two-dimensional plane. Also, we
show that there exist local maxima which are not global ones for the volume of
a projection of $\\crosp^n$ onto a k-dimensional subspace for any n>k⩾2."
acknowledgement: Research was supported by the Russian Foundation for Basic Research,
project 18-01-00036A (Theorems 1.5 and 5.3) and by the Ministry of Education and
Science of the Russian Federation in the framework of MegaGrant no 075-15-2019-1926
(Theorems 1.2 and 7.3).
article_number: '112312'
article_processing_charge: No
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
citation:
ama: Ivanov G. On the volume of projections of the cross-polytope. Discrete Mathematics.
2021;344(5). doi:10.1016/j.disc.2021.112312
apa: Ivanov, G. (2021). On the volume of projections of the cross-polytope. Discrete
Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2021.112312
chicago: Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.”
Discrete Mathematics. Elsevier, 2021. https://doi.org/10.1016/j.disc.2021.112312.
ieee: G. Ivanov, “On the volume of projections of the cross-polytope,” Discrete
Mathematics, vol. 344, no. 5. Elsevier, 2021.
ista: Ivanov G. 2021. On the volume of projections of the cross-polytope. Discrete
Mathematics. 344(5), 112312.
mla: Ivanov, Grigory. “On the Volume of Projections of the Cross-Polytope.” Discrete
Mathematics, vol. 344, no. 5, 112312, Elsevier, 2021, doi:10.1016/j.disc.2021.112312.
short: G. Ivanov, Discrete Mathematics 344 (2021).
date_created: 2021-02-07T23:01:12Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2023-08-07T13:40:37Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.disc.2021.112312
external_id:
arxiv:
- '1808.09165'
isi:
- '000633365200001'
intvolume: ' 344'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1808.09165
month: '05'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the volume of projections of the cross-polytope
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 344
year: '2021'
...
---
_id: '9295'
abstract:
- lang: eng
text: "Hill's Conjecture states that the crossing number cr(\U0001D43E\U0001D45B)
\ of the complete graph \U0001D43E\U0001D45B in the plane (equivalently, the
sphere) is 14⌊\U0001D45B2⌋⌊\U0001D45B−12⌋⌊\U0001D45B−22⌋⌊\U0001D45B−32⌋=\U0001D45B4/64+\U0001D442(\U0001D45B3)
. Moon proved that the expected number of crossings in a spherical drawing in
which the points are randomly distributed and joined by geodesics is precisely
\ \U0001D45B4/64+\U0001D442(\U0001D45B3) , thus matching asymptotically the conjectured
value of cr(\U0001D43E\U0001D45B) . Let cr\U0001D443(\U0001D43A) denote the
crossing number of a graph \U0001D43A in the projective plane. Recently, Elkies
proved that the expected number of crossings in a naturally defined random projective
plane drawing of \U0001D43E\U0001D45B is (\U0001D45B4/8\U0001D70B2)+\U0001D442(\U0001D45B3)
. In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked
if lim\U0001D45B→∞ cr\U0001D443(\U0001D43E\U0001D45B)/\U0001D45B4=1/8\U0001D70B2
. We construct drawings of \U0001D43E\U0001D45B in the projective plane that
disprove this."
acknowledgement: "We thank two reviewers for their corrections and suggestions on
the original version of this\r\npaper. This project has received funding from NSERC
Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation
programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg,
Austria."
article_processing_charge: No
article_type: original
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Dan
full_name: Mcquillan, Dan
last_name: Mcquillan
- first_name: R. Bruce
full_name: Richter, R. Bruce
last_name: Richter
- first_name: Gelasio
full_name: Salazar, Gelasio
last_name: Salazar
- first_name: Matthew
full_name: Sullivan, Matthew
last_name: Sullivan
citation:
ama: Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings
of complete graphs in the projective plane. Journal of Graph Theory. 2021;97(3):426-440.
doi:10.1002/jgt.22665
apa: Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., & Sullivan,
M. (2021). Drawings of complete graphs in the projective plane. Journal of
Graph Theory. Wiley. https://doi.org/10.1002/jgt.22665
chicago: Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar,
and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” Journal
of Graph Theory. Wiley, 2021. https://doi.org/10.1002/jgt.22665.
ieee: A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan,
“Drawings of complete graphs in the projective plane,” Journal of Graph Theory,
vol. 97, no. 3. Wiley, pp. 426–440, 2021.
ista: Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings
of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440.
mla: Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective
Plane.” Journal of Graph Theory, vol. 97, no. 3, Wiley, 2021, pp. 426–40,
doi:10.1002/jgt.22665.
short: A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan,
Journal of Graph Theory 97 (2021) 426–440.
date_created: 2021-03-28T22:01:41Z
date_published: 2021-03-23T00:00:00Z
date_updated: 2023-08-07T14:26:15Z
day: '23'
department:
- _id: UlWa
doi: 10.1002/jgt.22665
ec_funded: 1
external_id:
arxiv:
- '2002.02287'
isi:
- '000631693200001'
intvolume: ' 97'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2002.02287
month: '03'
oa: 1
oa_version: Preprint
page: 426-440
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Journal of Graph Theory
publication_identifier:
eissn:
- 1097-0118
issn:
- 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Drawings of complete graphs in the projective plane
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 97
year: '2021'
...
---
_id: '9468'
abstract:
- lang: eng
text: "Motivated by the successful application of geometry to proving the Harary--Hill
conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical”
drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit
sphere $\\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no
three on a great circle---and the edges of $G$ are shortest-arcs in $\\mathbb{S}^2$
connecting pairs of vertices. Such a drawing has three properties: (1) every edge
$e$ is contained in a simple closed curve $\\gamma_e$ such that the only vertices
in $\\gamma_e$ are the ends of $e$; (2) if $e\\ne f$, then $\\gamma_e\\cap\\gamma_f$
has precisely two crossings; and (3) if $e\\ne f$, then $e$ intersects $\\gamma_f$
at most once, in either a crossing or an end of $e$. We use properties (1)--(3)
to define a pseudospherical drawing of $G$. Our main result is that for the complete
graph, properties (1)--(3) are equivalent to the same three properties but with
“precisely two crossings” in (2) replaced by “at most two crossings.” The proof
requires a result in the geometric transversal theory of arrangements of pseudocircles.
This is proved using the surprising result that the absence of special arcs (coherent
spirals) in an arrangement of simple closed curves characterizes the fact that
any two curves in the arrangement have at most two crossings. Our studies provide
the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension
to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to
an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles
crossing twice.\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: R. Bruce
full_name: Richter, R. Bruce
last_name: Richter
- first_name: Matthew
full_name: Sunohara, Matthew
last_name: Sunohara
citation:
ama: Arroyo Guevara AM, Richter RB, Sunohara M. Extending drawings of complete graphs
into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics.
2021;35(2):1050-1076. doi:10.1137/20M1313234
apa: Arroyo Guevara, A. M., Richter, R. B., & Sunohara, M. (2021). Extending
drawings of complete graphs into arrangements of pseudocircles. SIAM Journal
on Discrete Mathematics. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20M1313234
chicago: Arroyo Guevara, Alan M, R. Bruce Richter, and Matthew Sunohara. “Extending
Drawings of Complete Graphs into Arrangements of Pseudocircles.” SIAM Journal
on Discrete Mathematics. Society for Industrial and Applied Mathematics, 2021.
https://doi.org/10.1137/20M1313234.
ieee: A. M. Arroyo Guevara, R. B. Richter, and M. Sunohara, “Extending drawings
of complete graphs into arrangements of pseudocircles,” SIAM Journal on Discrete
Mathematics, vol. 35, no. 2. Society for Industrial and Applied Mathematics,
pp. 1050–1076, 2021.
ista: Arroyo Guevara AM, Richter RB, Sunohara M. 2021. Extending drawings of complete
graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics.
35(2), 1050–1076.
mla: Arroyo Guevara, Alan M., et al. “Extending Drawings of Complete Graphs into
Arrangements of Pseudocircles.” SIAM Journal on Discrete Mathematics, vol.
35, no. 2, Society for Industrial and Applied Mathematics, 2021, pp. 1050–76,
doi:10.1137/20M1313234.
short: A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete
Mathematics 35 (2021) 1050–1076.
date_created: 2021-06-06T22:01:30Z
date_published: 2021-05-20T00:00:00Z
date_updated: 2023-08-08T13:58:12Z
day: '20'
department:
- _id: UlWa
doi: 10.1137/20M1313234
ec_funded: 1
external_id:
arxiv:
- '2001.06053'
isi:
- '000674142200022'
intvolume: ' 35'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2001.06053
month: '05'
oa: 1
oa_version: Preprint
page: 1050-1076
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
issn:
- '08954801'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending drawings of complete graphs into arrangements of pseudocircles
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 35
year: '2021'
...
---
_id: '9548'
abstract:
- lang: eng
text: 'We extend the notion of the minimal volume ellipsoid containing a convex
body in Rd to the setting of logarithmically concave functions. We consider a
vast class of logarithmically concave functions whose superlevel sets are concentric
ellipsoids. For a fixed function from this class, we consider the set of all its
“affine” positions. For any log-concave function f on Rd, we consider functions
belonging to this set of “affine” positions, and find the one with the minimal
integral under the condition that it is pointwise greater than or equal to f.
We study the properties of existence and uniqueness of the solution to this problem.
For any s∈[0,+∞), we consider the construction dual to the recently defined John
s-function (Ivanov and Naszódi in Functional John ellipsoids. arXiv preprint:
arXiv:2006.09934, 2020). We prove that such a construction determines a unique
function and call it the Löwner s-function of f. We study the Löwner s-functions
as s tends to zero and to infinity. Finally, extending the notion of the outer
volume ratio, we define the outer integral ratio of a log-concave function and
give an asymptotically tight bound on it.'
acknowledgement: The authors acknowledge the support of the grant of the Russian Government
N 075-15-2019-1926.
article_processing_charge: No
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Igor
full_name: Tsiutsiurupa, Igor
last_name: Tsiutsiurupa
citation:
ama: Ivanov G, Tsiutsiurupa I. Functional Löwner ellipsoids. Journal of Geometric
Analysis. 2021;31:11493-11528. doi:10.1007/s12220-021-00691-4
apa: Ivanov, G., & Tsiutsiurupa, I. (2021). Functional Löwner ellipsoids. Journal
of Geometric Analysis. Springer. https://doi.org/10.1007/s12220-021-00691-4
chicago: Ivanov, Grigory, and Igor Tsiutsiurupa. “Functional Löwner Ellipsoids.”
Journal of Geometric Analysis. Springer, 2021. https://doi.org/10.1007/s12220-021-00691-4.
ieee: G. Ivanov and I. Tsiutsiurupa, “Functional Löwner ellipsoids,” Journal
of Geometric Analysis, vol. 31. Springer, pp. 11493–11528, 2021.
ista: Ivanov G, Tsiutsiurupa I. 2021. Functional Löwner ellipsoids. Journal of Geometric
Analysis. 31, 11493–11528.
mla: Ivanov, Grigory, and Igor Tsiutsiurupa. “Functional Löwner Ellipsoids.” Journal
of Geometric Analysis, vol. 31, Springer, 2021, pp. 11493–528, doi:10.1007/s12220-021-00691-4.
short: G. Ivanov, I. Tsiutsiurupa, Journal of Geometric Analysis 31 (2021) 11493–11528.
date_created: 2021-06-13T22:01:32Z
date_published: 2021-05-31T00:00:00Z
date_updated: 2023-08-08T14:04:49Z
day: '31'
department:
- _id: UlWa
doi: 10.1007/s12220-021-00691-4
external_id:
arxiv:
- '2008.09543'
isi:
- '000656507500001'
intvolume: ' 31'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2008.09543
month: '05'
oa: 1
oa_version: Preprint
page: 11493-11528
publication: Journal of Geometric Analysis
publication_identifier:
eissn:
- 1559-002X
issn:
- 1050-6926
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Functional Löwner ellipsoids
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 31
year: '2021'
...
---
_id: '10181'
abstract:
- lang: eng
text: In this article we study some geometric properties of proximally smooth sets.
First, we introduce a modification of the metric projection and prove its existence.
Then we provide an algorithm for constructing a rectifiable curve between two
sufficiently close points of a proximally smooth set in a uniformly convex and
uniformly smooth Banach space, with the moduli of smoothness and convexity of
power type. Our algorithm returns a reasonably short curve between two sufficiently
close points of a proximally smooth set, is iterative and uses our modification
of the metric projection. We estimate the length of the constructed curve and
its deviation from the segment with the same endpoints. These estimates coincide
up to a constant factor with those for the geodesics in a proximally smooth set
in a Hilbert space.
acknowledgement: Theorem 2 was obtained at Steklov Mathematical Institute RAS and
supported by Russian Science Foundation, grant N 19-11-00087.
article_processing_charge: No
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Mariana S.
full_name: Lopushanski, Mariana S.
last_name: Lopushanski
citation:
ama: Ivanov G, Lopushanski MS. Rectifiable curves in proximally smooth sets. Set-Valued
and Variational Analysis. 2021. doi:10.1007/s11228-021-00612-1
apa: Ivanov, G., & Lopushanski, M. S. (2021). Rectifiable curves in proximally
smooth sets. Set-Valued and Variational Analysis. Springer Nature. https://doi.org/10.1007/s11228-021-00612-1
chicago: Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally
Smooth Sets.” Set-Valued and Variational Analysis. Springer Nature, 2021.
https://doi.org/10.1007/s11228-021-00612-1.
ieee: G. Ivanov and M. S. Lopushanski, “Rectifiable curves in proximally smooth
sets,” Set-Valued and Variational Analysis. Springer Nature, 2021.
ista: Ivanov G, Lopushanski MS. 2021. Rectifiable curves in proximally smooth sets.
Set-Valued and Variational Analysis.
mla: Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally
Smooth Sets.” Set-Valued and Variational Analysis, Springer Nature, 2021,
doi:10.1007/s11228-021-00612-1.
short: G. Ivanov, M.S. Lopushanski, Set-Valued and Variational Analysis (2021).
date_created: 2021-10-24T22:01:35Z
date_published: 2021-10-09T00:00:00Z
date_updated: 2023-08-14T08:11:38Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/s11228-021-00612-1
external_id:
arxiv:
- '2012.10691'
isi:
- '000705774800001'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.10691
month: '10'
oa: 1
oa_version: Published Version
publication: Set-Valued and Variational Analysis
publication_identifier:
eissn:
- 1877-0541
issn:
- 0927-6947
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Rectifiable curves in proximally smooth sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_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
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- 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.
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-30T00:00:00Z
date_updated: 2023-08-14T11:43:55Z
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: '8183'
relation: earlier_version
status: public
- id: '9308'
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: '10856'
abstract:
- lang: eng
text: "We study the properties of the maximal volume k-dimensional sections of the
n-dimensional cube [−1, 1]n. We obtain a first order necessary condition for a
k-dimensional subspace to be a local maximizer of the volume of such sections,
which we formulate in a geometric way. We estimate the length of the projection
of a vector of the standard basis of Rn onto a k-dimensional subspace that maximizes
the volume of the intersection. We \x1Cnd the optimal upper bound on the volume
of a planar section of the cube [−1, 1]n , n ≥ 2."
acknowledgement: "The authors acknowledge the support of the grant of the Russian
Government N 075-15-\r\n2019-1926. G.I.was supported also by the SwissNational Science
Foundation grant 200021-179133. The authors are very grateful to the anonymous reviewer
for valuable remarks."
article_processing_charge: No
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
- first_name: Igor
full_name: Tsiutsiurupa, Igor
last_name: Tsiutsiurupa
citation:
ama: Ivanov G, Tsiutsiurupa I. On the volume of sections of the cube. Analysis
and Geometry in Metric Spaces. 2021;9(1):1-18. doi:10.1515/agms-2020-0103
apa: Ivanov, G., & Tsiutsiurupa, I. (2021). On the volume of sections of the
cube. Analysis and Geometry in Metric Spaces. De Gruyter. https://doi.org/10.1515/agms-2020-0103
chicago: Ivanov, Grigory, and Igor Tsiutsiurupa. “On the Volume of Sections of the
Cube.” Analysis and Geometry in Metric Spaces. De Gruyter, 2021. https://doi.org/10.1515/agms-2020-0103.
ieee: G. Ivanov and I. Tsiutsiurupa, “On the volume of sections of the cube,” Analysis
and Geometry in Metric Spaces, vol. 9, no. 1. De Gruyter, pp. 1–18, 2021.
ista: Ivanov G, Tsiutsiurupa I. 2021. On the volume of sections of the cube. Analysis
and Geometry in Metric Spaces. 9(1), 1–18.
mla: Ivanov, Grigory, and Igor Tsiutsiurupa. “On the Volume of Sections of the Cube.”
Analysis and Geometry in Metric Spaces, vol. 9, no. 1, De Gruyter, 2021,
pp. 1–18, doi:10.1515/agms-2020-0103.
short: G. Ivanov, I. Tsiutsiurupa, Analysis and Geometry in Metric Spaces 9 (2021)
1–18.
date_created: 2022-03-18T09:25:14Z
date_published: 2021-01-29T00:00:00Z
date_updated: 2023-08-17T07:07:58Z
day: '29'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1515/agms-2020-0103
external_id:
arxiv:
- '2004.02674'
isi:
- '000734286800001'
file:
- access_level: open_access
checksum: 7e615ac8489f5eae580b6517debfdc53
content_type: application/pdf
creator: dernst
date_created: 2022-03-18T09:31:59Z
date_updated: 2022-03-18T09:31:59Z
file_id: '10857'
file_name: 2021_AnalysisMetricSpaces_Ivanov.pdf
file_size: 789801
relation: main_file
success: 1
file_date_updated: 2022-03-18T09:31:59Z
has_accepted_license: '1'
intvolume: ' 9'
isi: 1
issue: '1'
keyword:
- Applied Mathematics
- Geometry and Topology
- Analysis
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 1-18
publication: Analysis and Geometry in Metric Spaces
publication_identifier:
issn:
- 2299-3274
publication_status: published
publisher: De Gruyter
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the volume of sections of the cube
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: 9
year: '2021'
...
---
_id: '10860'
abstract:
- lang: eng
text: A tight frame is the orthogonal projection of some orthonormal basis of Rn
onto Rk. We show that a set of vectors is a tight frame if and only if the set
of all cross products of these vectors is a tight frame. We reformulate a range
of problems on the volume of projections (or sections) of regular polytopes in
terms of tight frames and write a first-order necessary condition for local extrema
of these problems. As applications, we prove new results for the problem of maximization
of the volume of zonotopes.
acknowledgement: The author was supported by the Swiss National Science Foundation
grant 200021_179133. The author acknowledges the financial support from the Ministry
of Education and Science of the Russian Federation in the framework of MegaGrant
no. 075-15-2019-1926.
article_processing_charge: No
article_type: original
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
citation:
ama: Ivanov G. Tight frames and related geometric problems. Canadian Mathematical
Bulletin. 2021;64(4):942-963. doi:10.4153/s000843952000096x
apa: Ivanov, G. (2021). Tight frames and related geometric problems. Canadian
Mathematical Bulletin. Canadian Mathematical Society. https://doi.org/10.4153/s000843952000096x
chicago: Ivanov, Grigory. “Tight Frames and Related Geometric Problems.” Canadian
Mathematical Bulletin. Canadian Mathematical Society, 2021. https://doi.org/10.4153/s000843952000096x.
ieee: G. Ivanov, “Tight frames and related geometric problems,” Canadian Mathematical
Bulletin, vol. 64, no. 4. Canadian Mathematical Society, pp. 942–963, 2021.
ista: Ivanov G. 2021. Tight frames and related geometric problems. Canadian Mathematical
Bulletin. 64(4), 942–963.
mla: Ivanov, Grigory. “Tight Frames and Related Geometric Problems.” Canadian
Mathematical Bulletin, vol. 64, no. 4, Canadian Mathematical Society, 2021,
pp. 942–63, doi:10.4153/s000843952000096x.
short: G. Ivanov, Canadian Mathematical Bulletin 64 (2021) 942–963.
date_created: 2022-03-18T09:55:59Z
date_published: 2021-12-18T00:00:00Z
date_updated: 2023-09-05T12:43:09Z
day: '18'
department:
- _id: UlWa
doi: 10.4153/s000843952000096x
external_id:
arxiv:
- '1804.10055'
isi:
- '000730165300021'
intvolume: ' 64'
isi: 1
issue: '4'
keyword:
- General Mathematics
- Tight frame
- Grassmannian
- zonotope
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1804.10055
month: '12'
oa: 1
oa_version: Preprint
page: 942-963
publication: Canadian Mathematical Bulletin
publication_identifier:
eissn:
- 1496-4287
issn:
- 0008-4395
publication_status: published
publisher: Canadian Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Tight frames and related geometric problems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 64
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: 2021-01-12T08:15:38Z
day: '01'
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: '7991'
abstract:
- lang: eng
text: 'We define and study a discrete process that generalizes the convex-layer
decomposition of a planar point set. Our process, which we call homotopic curve
shortening (HCS), starts with a closed curve (which might self-intersect) in the
presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where
each step consists of (1) taking shortcuts around the obstacles, and (2) reducing
the curve to its shortest homotopic equivalent. We find experimentally that, if
the initial curve is held fixed and P is chosen to be either a very fine regular
grid or a uniformly random point set, then HCS behaves at the limit like the affine
curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes
the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017),
which applied only to convex curves, and which was studied only for regular grids.
We prove that HCS satisfies some properties analogous to those of ACSF: HCS is
invariant under affine transformations, preserves convexity, and does not increase
the total absolute curvature. Furthermore, the number of self-intersections of
a curve, or intersections between two curves (appropriately defined), does not
increase. Finally, if the initial curve is simple, then the number of inflection
points (appropriately defined) does not increase.'
alternative_title:
- LIPIcs
article_number: 12:1 - 12:15
article_processing_charge: No
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- first_name: Gabriel
full_name: Nivasch, Gabriel
last_name: Nivasch
citation:
ama: 'Avvakumov S, Nivasch G. Homotopic curve shortening and the affine curve-shortening
flow. In: 36th International Symposium on Computational Geometry. Vol 164.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.12'
apa: 'Avvakumov, S., & Nivasch, G. (2020). Homotopic curve shortening and the
affine curve-shortening flow. 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.12'
chicago: Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and
the Affine Curve-Shortening Flow.” 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.12.
ieee: S. Avvakumov and G. Nivasch, “Homotopic curve shortening and the affine curve-shortening
flow,” in 36th International Symposium on Computational Geometry, Zürich,
Switzerland, 2020, vol. 164.
ista: 'Avvakumov S, Nivasch G. 2020. Homotopic curve shortening and the affine curve-shortening
flow. 36th International Symposium on Computational Geometry. SoCG: Symposium
on Computational Geometry, LIPIcs, vol. 164, 12:1-12:15.'
mla: Avvakumov, Sergey, and Gabriel Nivasch. “Homotopic Curve Shortening and the
Affine Curve-Shortening Flow.” 36th International Symposium on Computational
Geometry, vol. 164, 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020, doi:10.4230/LIPIcs.SoCG.2020.12.
short: S. Avvakumov, G. Nivasch, 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
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2021-01-12T08:16:23Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.12
external_id:
arxiv:
- '1909.00263'
file:
- access_level: open_access
checksum: 6872df6549142f709fb6354a1b2f2c06
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T11:13:49Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8007'
file_name: 2020_LIPIcsSoCG_Avvakumov.pdf
file_size: 575896
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '06'
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
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771436'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Homotopic curve shortening and the affine curve-shortening flow
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_id: '7989'
abstract:
- lang: eng
text: 'We prove general topological Radon-type theorems for sets in ℝ^d, smooth
real manifolds or finite dimensional simplicial complexes. Combined with a recent
result of Holmsen and Lee, it gives fractional Helly theorem, and consequently
the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X
be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex.
Then if F is a finite, intersection-closed family of sets in X such that the ith
reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every
non-negative integer i less or equal to k, then the Radon number of F is bounded
in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1
if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X
is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent
result of the author and Kalai, we manage to prove the following optimal bound
on fractional Helly number for families of open sets in a surface: Let F be a
finite family of open sets in a surface S such that the intersection of any subfamily
of F is either empty, or path-connected. Then the fractional Helly number of F
is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about
an existence of a (p,q)-theorem for open subsets of a surface.'
alternative_title:
- LIPIcs
article_number: 61:1-61:13
article_processing_charge: No
author:
- first_name: Zuzana
full_name: Patakova, Zuzana
id: 48B57058-F248-11E8-B48F-1D18A9856A87
last_name: Patakova
orcid: 0000-0002-3975-1683
citation:
ama: 'Patakova Z. Bounding radon number via Betti numbers. In: 36th International
Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61'
apa: 'Patakova, Z. (2020). Bounding radon number via Betti numbers. 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.61'
chicago: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 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.61.
ieee: Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International
Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.
ista: 'Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International
Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry,
LIPIcs, vol. 164, 61:1-61:13.'
mla: Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 36th International
Symposium on Computational Geometry, vol. 164, 61:1-61:13, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61.
short: Z. Patakova, 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
date_created: 2020-06-22T09:14:18Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2021-01-12T08:16:22Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.61
external_id:
arxiv:
- '1908.01677'
file:
- access_level: open_access
checksum: d0996ca5f6eb32ce955ce782b4f2afbe
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T06:56:23Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8005'
file_name: 2020_LIPIcsSoCG_Patakova_61.pdf
file_size: 645421
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:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Bounding radon number via Betti 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: 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
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
date_created: 2020-06-22T09:14:20Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2021-01-12T08:16:23Z
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:
- '18688969'
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: '7994'
abstract:
- lang: eng
text: In the recent study of crossing numbers, drawings of graphs that can be extended
to an arrangement of pseudolines (pseudolinear drawings) have played an important
role as they are a natural combinatorial extension of rectilinear (or straight-line)
drawings. A characterization of the pseudolinear drawings of K_n was found recently.
We extend this characterization to all graphs, by describing the set of minimal
forbidden subdrawings for pseudolinear drawings. Our characterization also leads
to a polynomial-time algorithm to recognize pseudolinear drawings and construct
the pseudolines when it is possible.
alternative_title:
- LIPIcs
article_number: 9:1 - 9:14
article_processing_charge: No
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Julien
full_name: Bensmail, Julien
last_name: Bensmail
- first_name: R.
full_name: Bruce Richter, R.
last_name: Bruce Richter
citation:
ama: 'Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs
to arrangements of pseudolines. In: 36th International Symposium on Computational
Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
doi:10.4230/LIPIcs.SoCG.2020.9'
apa: 'Arroyo Guevara, A. M., Bensmail, J., & Bruce Richter, R. (2020). Extending
drawings of graphs to arrangements of pseudolines. 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.9'
chicago: Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending
Drawings of Graphs to Arrangements of Pseudolines.” 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.9.
ieee: A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings
of graphs to arrangements of pseudolines,” in 36th International Symposium
on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.
ista: 'Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings
of graphs to arrangements of pseudolines. 36th International Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14.'
mla: Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements
of Pseudolines.” 36th International Symposium on Computational Geometry,
vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.9.
short: A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, 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
date_created: 2020-06-22T09:14:21Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-02-23T13:22:12Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.9
ec_funded: 1
external_id:
arxiv:
- '1804.09317'
file:
- access_level: open_access
checksum: 93571b76cf97d5b7c8aabaeaa694dd7e
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T11:06:23Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8006'
file_name: 2020_LIPIcsSoCG_Arroyo.pdf
file_size: 592661
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
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771436'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending drawings of graphs to arrangements of pseudolines
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: '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
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
date_created: 2020-06-22T09:14:19Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-08-04T08:51:07Z
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:
- '18688969'
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: '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
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: 2023-08-04T08:51:07Z
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: '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
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
- 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: 2023-08-14T11:43:54Z
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: '8183'
relation: earlier_version
status: public
- id: '10220'
relation: later_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: '6563'
abstract:
- lang: eng
text: "This paper presents two algorithms. The first decides the existence of a
pointed homotopy between given simplicial maps \U0001D453,\U0001D454:\U0001D44B→\U0001D44C,
and the second computes the group [\U0001D6F4\U0001D44B,\U0001D44C]∗ of pointed
homotopy classes of maps from a suspension; in both cases, the target Y is assumed
simply connected. More generally, these algorithms work relative to \U0001D434⊆\U0001D44B."
article_processing_charge: No
article_type: original
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Lukas
full_name: Vokřínek, Lukas
last_name: Vokřínek
citation:
ama: Filakovský M, Vokřínek L. Are two given maps homotopic? An algorithmic viewpoint.
Foundations of Computational Mathematics. 2020;20:311-330. doi:10.1007/s10208-019-09419-x
apa: Filakovský, M., & Vokřínek, L. (2020). Are two given maps homotopic? An
algorithmic viewpoint. Foundations of Computational Mathematics. Springer
Nature. https://doi.org/10.1007/s10208-019-09419-x
chicago: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An
Algorithmic Viewpoint.” Foundations of Computational Mathematics. Springer
Nature, 2020. https://doi.org/10.1007/s10208-019-09419-x.
ieee: M. Filakovský and L. Vokřínek, “Are two given maps homotopic? An algorithmic
viewpoint,” Foundations of Computational Mathematics, vol. 20. Springer
Nature, pp. 311–330, 2020.
ista: Filakovský M, Vokřínek L. 2020. Are two given maps homotopic? An algorithmic
viewpoint. Foundations of Computational Mathematics. 20, 311–330.
mla: Filakovský, Marek, and Lukas Vokřínek. “Are Two given Maps Homotopic? An Algorithmic
Viewpoint.” Foundations of Computational Mathematics, vol. 20, Springer
Nature, 2020, pp. 311–30, doi:10.1007/s10208-019-09419-x.
short: M. Filakovský, L. Vokřínek, Foundations of Computational Mathematics 20 (2020)
311–330.
date_created: 2019-06-16T21:59:14Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2023-08-17T13:50:44Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s10208-019-09419-x
external_id:
arxiv:
- '1312.2337'
isi:
- '000522437400004'
intvolume: ' 20'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1312.2337
month: '04'
oa: 1
oa_version: Preprint
page: 311-330
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P31312
name: Algorithms for Embeddings and Homotopy Theory
publication: Foundations of Computational Mathematics
publication_identifier:
eissn:
- '16153383'
issn:
- '16153375'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Are two given maps homotopic? An algorithmic viewpoint
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 20
year: '2020'
...
---
_id: '7960'
abstract:
- lang: eng
text: Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection
of sets from A has at most b path-connected components, which all are open, then
fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k.
These results also extend to two-dimensional compact surfaces.
acknowledgement: "We are very grateful to Pavel Paták for many helpful discussions
and remarks. We also thank the referees for helpful comments, which greatly improved
the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK
was also partially supported by NSF grant DMS1300120. The research stay of ZP at
IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement
of internationalization in the field of research and development at Charles University,
through the support of quality projects MSCA-IF."
article_processing_charge: No
article_type: original
author:
- first_name: Gil
full_name: Kalai, Gil
last_name: Kalai
- first_name: Zuzana
full_name: Patakova, Zuzana
id: 48B57058-F248-11E8-B48F-1D18A9856A87
last_name: Patakova
orcid: 0000-0002-3975-1683
citation:
ama: Kalai G, Patakova Z. Intersection patterns of planar sets. Discrete and
Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z
apa: Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets.
Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z
chicago: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.”
Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z.
ieee: G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete
and Computational Geometry, vol. 64. Springer Nature, pp. 304–323, 2020.
ista: Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete
and Computational Geometry. 64, 304–323.
mla: Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete
and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.
short: G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.
date_created: 2020-06-14T22:00:50Z
date_published: 2020-09-01T00:00:00Z
date_updated: 2023-08-21T08:26:34Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-020-00205-z
external_id:
arxiv:
- '1907.00885'
isi:
- '000537329400001'
intvolume: ' 64'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1907.00885
month: '09'
oa: 1
oa_version: Preprint
page: 304-323
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- '14320444'
issn:
- '01795376'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Intersection patterns of planar sets
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 64
year: '2020'
...
---
_id: '8732'
abstract:
- lang: eng
text: 'A simple drawing D(G) of a graph G is one where each pair of edges share
at most one point: either a common endpoint or a proper crossing. An edge e in
the complement of G can be inserted into D(G) if there exists a simple drawing
of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing
is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement
of lines (pseudolines), then any edge in the complement of G can be inserted.
In contrast, we show that it is NP -complete to decide whether one edge can
be inserted into a simple drawing. This remains true even if we assume that the
drawing is pseudocircular, that is, the edges can be extended to an arrangement
of pseudocircles. On the positive side, we show that, given an arrangement of
pseudocircles A and a pseudosegment σ , it can be decided in polynomial time
whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is
again an arrangement of pseudocircles.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Fabian
full_name: Klute, Fabian
last_name: Klute
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
- first_name: Tilo
full_name: Wiedera, Tilo
last_name: Wiedera
citation:
ama: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
Inserting one edge into a simple drawing is hard. In: Graph-Theoretic Concepts
in Computer Science. Vol 12301. Springer Nature; 2020:325-338. doi:10.1007/978-3-030-60440-0_26'
apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B.,
& Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In
Graph-Theoretic Concepts in Computer Science (Vol. 12301, pp. 325–338).
Leeds, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-60440-0_26'
chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit
Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.”
In Graph-Theoretic Concepts in Computer Science, 12301:325–38. Springer
Nature, 2020. https://doi.org/10.1007/978-3-030-60440-0_26.
ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and
T. Wiedera, “Inserting one edge into a simple drawing is hard,” in Graph-Theoretic
Concepts in Computer Science, Leeds, United Kingdom, 2020, vol. 12301, pp.
325–338.
ista: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts
in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science,
LNCS, vol. 12301, 325–338.'
mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is
Hard.” Graph-Theoretic Concepts in Computer Science, vol. 12301, Springer
Nature, 2020, pp. 325–38, doi:10.1007/978-3-030-60440-0_26.
short: A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera,
in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp.
325–338.
conference:
end_date: 2020-06-26
location: Leeds, United Kingdom
name: 'WG: Workshop on Graph-Theoretic Concepts in Computer Science'
start_date: 2020-06-24
date_created: 2020-11-06T08:45:03Z
date_published: 2020-10-09T00:00:00Z
date_updated: 2023-09-05T15:09:16Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/978-3-030-60440-0_26
ec_funded: 1
intvolume: ' 12301'
language:
- iso: eng
month: '10'
oa_version: None
page: 325-338
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Graph-Theoretic Concepts in Computer Science
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030604394'
- '9783030604400'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inserting one edge into a simple drawing is hard
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12301
year: '2020'
...
---
_id: '7944'
abstract:
- lang: eng
text: "This thesis considers two examples of reconfiguration problems: flipping
edges in edge-labelled triangulations of planar point sets and swapping labelled
tokens placed on vertices of a graph. In both cases the studied structures – all
the triangulations of a given point set or all token placements on a given graph
– can be thought of as vertices of the so-called reconfiguration graph, in which
two vertices are adjacent if the corresponding structures differ by a single elementary
operation – by a flip of a diagonal in a triangulation or by a swap of tokens
on adjacent vertices, respectively. We study the reconfiguration of one instance
of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor
triangulations of point sets in which each edge has a unique label and a flip
transfers the label from the removed edge to the new edge, we prove a polynomial-time
testable condition, called the Orbit Theorem, that characterizes when two triangulations
of the same point set lie in the same connected component of the reconfiguration
graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot.
We additionally provide a polynomial time algorithm that computes a reconfiguring
flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties
of a certain high-dimensional cell complex that has the usual reconfiguration
graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph,
we make partial progress on the problem of finding shortest reconfiguration sequences.
We disprove the so-called Happy Leaf Conjecture and demonstrate the importance
of swapping tokens that are already placed at the correct vertices. We also prove
that a generalization of the problem to weighted coloured token swapping is NP-hard
on trees but solvable in polynomial time on paths and stars."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
citation:
ama: Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944
apa: Masárová, Z. (2020). Reconfiguration problems. Institute of Science
and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944
chicago: Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and
Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944.
ieee: Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology
Austria, 2020.
ista: Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology
Austria.
mla: Masárová, Zuzana. Reconfiguration Problems. Institute of Science and
Technology Austria, 2020, doi:10.15479/AT:ISTA:7944.
short: Z. Masárová, Reconfiguration Problems, Institute of Science and Technology
Austria, 2020.
date_created: 2020-06-08T00:49:46Z
date_published: 2020-06-09T00:00:00Z
date_updated: 2023-09-07T13:17:37Z
day: '09'
ddc:
- '516'
- '514'
degree_awarded: PhD
department:
- _id: HeEd
- _id: UlWa
doi: 10.15479/AT:ISTA:7944
file:
- access_level: open_access
checksum: df688bc5a82b50baee0b99d25fc7b7f0
content_type: application/pdf
creator: zmasarov
date_created: 2020-06-08T00:34:00Z
date_updated: 2020-07-14T12:48:05Z
file_id: '7945'
file_name: THESIS_Zuzka_Masarova.pdf
file_size: 13661779
relation: main_file
- access_level: closed
checksum: 45341a35b8f5529c74010b7af43ac188
content_type: application/zip
creator: zmasarov
date_created: 2020-06-08T00:35:30Z
date_updated: 2020-07-14T12:48:05Z
file_id: '7946'
file_name: THESIS_Zuzka_Masarova_SOURCE_FILES.zip
file_size: 32184006
relation: source_file
file_date_updated: 2020-07-14T12:48:05Z
has_accepted_license: '1'
keyword:
- reconfiguration
- reconfiguration graph
- triangulations
- flip
- constrained triangulations
- shellability
- piecewise-linear balls
- token swapping
- trees
- coloured weighted token swapping
language:
- iso: eng
license: https://creativecommons.org/licenses/by-sa/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: '160'
publication_identifier:
isbn:
- 978-3-99078-005-3
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '7950'
relation: part_of_dissertation
status: public
- id: '5986'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
title: Reconfiguration problems
tmp:
image: /images/cc_by_sa.png
legal_code_url: https://creativecommons.org/licenses/by-sa/4.0/legalcode
name: Creative Commons Attribution-ShareAlike 4.0 International Public License (CC
BY-SA 4.0)
short: CC BY-SA (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_id: '8032'
abstract:
- lang: eng
text: "Algorithms in computational 3-manifold topology typically take a triangulation
as an input and return topological information about the underlying 3-manifold.
However, extracting the desired information from a triangulation (e.g., evaluating
an invariant) is often computationally very expensive. In recent years this complexity
barrier has been successfully tackled in some cases by importing ideas from the
theory of parameterized algorithms into the realm of 3-manifolds. Various computationally
hard problems were shown to be efficiently solvable for input triangulations that
are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial
parameter in the above context: we consider the treewidth of a compact, orientable
3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation
thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito
on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered
triangulations, we establish quantitative relations between the treewidth and
classical topological invariants of a 3-manifold. In particular, among other results,
we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold
is always within a constant factor of its Heegaard genus."
acknowledged_ssus:
- _id: E-Lib
- _id: CampIT
alternative_title:
- ISTA Thesis
article_processing_charge: No
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
citation:
ama: Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020.
doi:10.15479/AT:ISTA:8032
apa: Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032
chicago: Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.”
Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032.
ieee: K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute
of Science and Technology Austria, 2020.
ista: Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds.
Institute of Science and Technology Austria.
mla: Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032.
short: K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute
of Science and Technology Austria, 2020.
date_created: 2020-06-26T10:00:36Z
date_published: 2020-06-26T00:00:00Z
date_updated: 2023-09-07T13:18:27Z
day: '26'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:8032
file:
- access_level: open_access
checksum: bd8be6e4f1addc863dfcc0fad29ee9c3
content_type: application/pdf
creator: khuszar
date_created: 2020-06-26T10:03:58Z
date_updated: 2020-07-14T12:48:08Z
file_id: '8034'
file_name: Kristof_Huszar-Thesis.pdf
file_size: 2637562
relation: main_file
- access_level: closed
checksum: d5f8456202b32f4a77552ef47a2837d1
content_type: application/x-zip-compressed
creator: khuszar
date_created: 2020-06-26T10:10:06Z
date_updated: 2020-07-14T12:48:08Z
file_id: '8035'
file_name: Kristof_Huszar-Thesis-source.zip
file_size: 7163491
relation: source_file
file_date_updated: 2020-07-14T12:48:08Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: xviii+120
publication_identifier:
isbn:
- 978-3-99078-006-0
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6556'
relation: dissertation_contains
status: public
- id: '7093'
relation: dissertation_contains
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Jonathan
full_name: Spreer, Jonathan
last_name: Spreer
title: Combinatorial width parameters for 3-dimensional 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: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_id: '8156'
abstract:
- lang: eng
text: 'We present solutions to several problems originating from geometry and discrete
mathematics: existence of equipartitions, maps without Tverberg multiple points,
and inscribing quadrilaterals. Equivariant obstruction theory is the natural topological
approach to these type of questions. However, for the specific problems we consider
it had yielded only partial or no results. We get our results by complementing
equivariant obstruction theory with other techniques from topology and geometry.'
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Sergey
full_name: Avvakumov, Sergey
id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
last_name: Avvakumov
citation:
ama: Avvakumov S. Topological methods in geometry and discrete mathematics. 2020.
doi:10.15479/AT:ISTA:8156
apa: Avvakumov, S. (2020). Topological methods in geometry and discrete mathematics.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8156
chicago: Avvakumov, Sergey. “Topological Methods in Geometry and Discrete Mathematics.”
Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8156.
ieee: S. Avvakumov, “Topological methods in geometry and discrete mathematics,”
Institute of Science and Technology Austria, 2020.
ista: Avvakumov S. 2020. Topological methods in geometry and discrete mathematics.
Institute of Science and Technology Austria.
mla: Avvakumov, Sergey. Topological Methods in Geometry and Discrete Mathematics.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8156.
short: S. Avvakumov, Topological Methods in Geometry and Discrete Mathematics, Institute
of Science and Technology Austria, 2020.
date_created: 2020-07-23T09:51:29Z
date_published: 2020-07-24T00:00:00Z
date_updated: 2023-12-18T10:51:01Z
day: '24'
ddc:
- '514'
degree_awarded: PhD
department:
- _id: UlWa
doi: 10.15479/AT:ISTA:8156
file:
- access_level: closed
content_type: application/zip
creator: savvakum
date_created: 2020-07-27T12:44:51Z
date_updated: 2020-07-27T12:44:51Z
file_id: '8178'
file_name: source.zip
file_size: 1061740
relation: source_file
- access_level: open_access
content_type: application/pdf
creator: savvakum
date_created: 2020-07-27T12:46:53Z
date_updated: 2020-07-27T12:46:53Z
file_id: '8179'
file_name: thesis_pdfa.pdf
file_size: 1336501
relation: main_file
success: 1
file_date_updated: 2020-07-27T12:46:53Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '119'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '8182'
relation: part_of_dissertation
status: public
- id: '8183'
relation: part_of_dissertation
status: public
- id: '8185'
relation: part_of_dissertation
status: public
- id: '8184'
relation: part_of_dissertation
status: public
- id: '6355'
relation: part_of_dissertation
status: public
- id: '75'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
title: Topological methods in geometry and discrete mathematics
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...