---
_id: '15168'
abstract:
- lang: eng
text: 'A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its
vertices with colours 1, … , k such that each edge contains a unique maximal colour.
Deciding whether an input hypergraph admits LO k-colouring with a fixed number
of colours is NP-complete (and in the special case of graphs, LO colouring coincides
with the usual graph colouring). Here, we investigate the complexity of approximating
the "linearly ordered chromatic number" of a hypergraph. We prove that the following
promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between
the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable.
We prove this result by a combination of algebraic, topological, and combinatorial
methods, building on and extending a topological approach for studying approximate
graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).'
acknowledgement: "Marek Filakovský: This research was supported by Charles University
(project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35),
and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This
research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All
data is provided in full in the results section of this paper. Jakub Opršal: This
project has received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413.
Uli Wagner: This research was supported by the Austrian Science Fund (FWF project
P31312-N35)."
alternative_title:
- LIPIcs
article_number: '34'
article_processing_charge: No
arxiv: 1
author:
- first_name: Marek
full_name: Filakovský, Marek
id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87
last_name: Filakovský
- first_name: Tamio Vesa
full_name: Nakajima, Tamio Vesa
last_name: Nakajima
- first_name: Jakub
full_name: Opršal, Jakub
id: ec596741-c539-11ec-b829-c79322a91242
last_name: Opršal
orcid: 0000-0003-1245-3456
- first_name: Gianluca
full_name: Tasinato, Gianluca
id: 0433290C-AF8F-11E9-A4C7-F729E6697425
last_name: Tasinato
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly
ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: 41st International
Symposium on Theoretical Aspects of Computer Science. Vol 289. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.STACS.2024.34'
apa: 'Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U.
(2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.
In 41st International Symposium on Theoretical Aspects of Computer Science
(Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.STACS.2024.34'
chicago: Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato,
and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform
Hypergraphs.” In 41st International Symposium on Theoretical Aspects of Computer
Science, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
https://doi.org/10.4230/LIPIcs.STACS.2024.34.
ieee: M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in 41st
International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand,
France, 2024, vol. 289.
ista: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness
of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International
Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical
Aspects of Computer Science, LIPIcs, vol. 289, 34.'
mla: Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable
3-Uniform Hypergraphs.” 41st International Symposium on Theoretical Aspects
of Computer Science, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.STACS.2024.34.
short: M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st
International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-03-14
location: Clermont-Ferrand, France
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2024-03-12
corr_author: '1'
date_created: 2024-03-24T23:00:59Z
date_published: 2024-03-01T00:00:00Z
date_updated: 2026-04-07T12:36:50Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.STACS.2024.34
ec_funded: 1
external_id:
arxiv:
- '2312.12981'
isi:
- '001300393400034'
file:
- access_level: open_access
checksum: 0524d4189fd1ed08989546511343edf3
content_type: application/pdf
creator: dernst
date_created: 2024-03-25T07:44:30Z
date_updated: 2024-03-25T07:44:30Z
file_id: '15175'
file_name: 2024_LIPICs_Filakovsky.pdf
file_size: 927290
relation: main_file
success: 1
file_date_updated: 2024-03-25T07:44:30Z
has_accepted_license: '1'
intvolume: ' 289'
isi: 1
language:
- iso: eng
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'
related_material:
record:
- id: '20339'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 289
year: '2024'
...
---
_id: '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
arxiv: 1
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: 2025-04-14T07:43:59Z
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
arxiv: 1
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.
corr_author: '1'
date_created: 2023-08-06T22:01:11Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-09-10T09:35:55Z
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: '14445'
abstract:
- lang: eng
text: "We prove the following quantitative Borsuk–Ulam-type result (an equivariant
analogue of Gromov’s Topological Overlap Theorem): Let X be a free ℤ/2-complex
of dimension d with coboundary expansion at least ηk in dimension 0 ≤ k < d. Then
for every equivariant map F: X →ℤ/2 ℝd, the fraction of d-simplices σ of X with
0 ∈ F (σ) is at least 2−d Π d−1k=0ηk.\r\n\r\nAs an application, we show that for
every sufficiently thick d-dimensional spherical building Y and every map f: Y
→ ℝ2d, we have f(σ) ∩ f(τ) ≠ ∅ for a constant fraction μd > 0 of pairs {σ, τ}
of d-simplices of Y. In particular, such complexes are non-embeddable into ℝ2d,
which proves a conjecture of Tancer and Vorwerk for sufficiently thick spherical
buildings.\r\n\r\nWe complement these results by upper bounds on the coboundary
expansion of two families of simplicial complexes; this indicates some limitations
to the bounds one can obtain by straighforward applications of the quantitative
Borsuk–Ulam theorem. Specifically, we prove\r\n\r\n• an upper bound of (d + 1)/2d
on the normalized (d − 1)-th coboundary expansion constant of complete (d + 1)-partite
d-dimensional complexes (under a mild divisibility assumption on the sizes of
the parts); and\r\n\r\n• an upper bound of (d + 1)/2d + ε on the normalized (d
− 1)-th coboundary expansion of the d-dimensional spherical building associated
with GLd+2(Fq) for any ε > 0 and sufficiently large q. This disproves, in a rather
strong sense, a conjecture of Lubotzky, Meshulam and Mozes."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Pascal
full_name: Wild, Pascal
id: 4C20D868-F248-11E8-B48F-1D18A9856A87
last_name: Wild
citation:
ama: Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers
of simplicial complexes. Israel Journal of Mathematics. 2023;256(2):675-717.
doi:10.1007/s11856-023-2521-9
apa: Wagner, U., & Wild, P. (2023). Coboundary expansion, equivariant overlap,
and crossing numbers of simplicial complexes. Israel Journal of Mathematics.
Springer Nature. https://doi.org/10.1007/s11856-023-2521-9
chicago: Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap,
and Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics.
Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2521-9.
ieee: U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing
numbers of simplicial complexes,” Israel Journal of Mathematics, vol. 256,
no. 2. Springer Nature, pp. 675–717, 2023.
ista: Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing
numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717.
mla: Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and
Crossing Numbers of Simplicial Complexes.” Israel Journal of Mathematics,
vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:10.1007/s11856-023-2521-9.
short: U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.
corr_author: '1'
date_created: 2023-10-22T22:01:14Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2024-10-09T21:07:12Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s11856-023-2521-9
external_id:
isi:
- '001081646400010'
file:
- access_level: open_access
checksum: fbb05619fe4b650f341cc730425dd9c3
content_type: application/pdf
creator: dernst
date_created: 2023-10-31T11:20:31Z
date_updated: 2023-10-31T11:20:31Z
file_id: '14475'
file_name: 2023_IsraelJourMath_Wagner.pdf
file_size: 623787
relation: main_file
success: 1
file_date_updated: 2023-10-31T11:20:31Z
has_accepted_license: '1'
intvolume: ' 256'
isi: 1
issue: '2'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 675-717
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Coboundary expansion, equivariant overlap, and crossing numbers of simplicial
complexes
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 256
year: '2023'
...
---
_id: '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
arxiv: 1
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.
corr_author: '1'
date_created: 2024-01-08T09:48:56Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2025-09-09T14:08:25Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1093/imrn/rnad210
external_id:
arxiv:
- '2212.11781'
isi:
- '001184146800001'
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'
isi: 1
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'
scopus_import: '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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2023
year: '2023'
...
---
_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
arxiv: 1
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 and 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 and 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 and 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 and 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: 2025-05-14T10:51:32Z
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 and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Topology and adjunction in promise constraint satisfaction
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 52
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
arxiv: 1
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: 2025-01-20T14:05: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: '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
arxiv: 1
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.
corr_author: '1'
date_created: 2023-07-23T22:01:14Z
date_published: 2023-07-05T00:00:00Z
date_updated: 2024-10-09T21:06:01Z
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: '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
arxiv: 1
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'
...
---
OA_place: publisher
_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
orcid: 0009-0008-0457-9730
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.
corr_author: '1'
date_created: 2023-07-31T10:20:55Z
date_published: 2023-07-31T00:00:00Z
date_updated: 2026-04-07T13:29:29Z
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
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
arxiv: 1
author:
- first_name: Grigory
full_name: Ivanov, Grigory
id: 87744F66-5C6F-11EA-AFE0-D16B3DDC885E
last_name: Ivanov
orcid: 0000-0002-5021-3982
- first_name: Seyda
full_name: Köse, Seyda
id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb
last_name: Köse
orcid: 0009-0008-0457-9730
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).
corr_author: '1'
date_created: 2023-02-26T23:01:00Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2026-04-07T13:29:28Z
day: '01'
department:
- _id: UlWa
- _id: GradSch
doi: 10.1016/j.disc.2023.113363
external_id:
arxiv:
- '2201.10892'
isi:
- '001189844500001'
intvolume: ' 346'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 346
year: '2023'
...
---
_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
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: 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: 2025-04-14T13:52:37Z
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: '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
arxiv: 1
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: '12129'
abstract:
- lang: eng
text: 'Given a finite point set P in general position in the plane, a full triangulation
of P is a maximal straight-line embedded plane graph on P. A partial triangulation
of P is a full triangulation of some subset P′ of P containing all extreme points
in P. A bistellar flip on a partial triangulation either flips an edge (called
edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as
vertex of degree 3. The bistellar flip graph has all partial triangulations as
vertices, and a pair of partial triangulations is adjacent if they can be obtained
from one another by a bistellar flip. The edge flip graph is defined with full
triangulations as vertices, and edge flips determining the adjacencies. Lawson
showed in the early seventies that these graphs are connected. The goal of this
paper is to investigate the structure of these graphs, with emphasis on their
vertex connectivity. For sets P of n points in the plane in general position,
we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar
flip graph is (n−3)-vertex connected; both results are tight. The latter bound
matches the situation for the subfamily of regular triangulations (i.e., partial
triangulations obtained by lifting the points to 3-space and projecting back the
lower convex hull), where (n−3)-vertex connectivity has been known since the late
eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky
and Balinski’s Theorem. For the edge flip-graph, we additionally show that the
vertex connectivity is at least as large as (and hence equal to) the minimum degree
(i.e., the minimum number of flippable edges in any full triangulation), provided
that n is large enough. Our methods also yield several other results: (i) The
edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products
of associahedra) and the bistellar flip graph can be covered by graphs of polytopes
of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation
is regular, if it has distance n−3 in the Hasse diagram of the partial order of
partial subdivisions from the trivial subdivision. (iii) All partial triangulations
of a point set are regular iff the partial order of partial subdivisions has height
n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations
and such that every proper subset has only regular triangulations, i.e., there
are no small certificates for the existence of non-regular triangulations.'
acknowledgement: "This is a full and revised version of [38] (on partial triangulations)
in Proceedings of the 36th Annual International Symposium on Computational Geometry
(SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings
of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis
research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt,
Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on
full triangulations. Research was supported by the Swiss National Science Foundation
within the collaborative DACH project Arrangements and Drawings as SNSF Project
200021E-171681, and by IST Austria and Berlin Free University during a sabbatical
stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco
Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger
and Valentin Stoppiello for carefully reading earlier versions and for many helpful
comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology
Zürich"
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane.
Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2
apa: Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs
in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2
chicago: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane.” Discrete & Computational Geometry. Springer Nature,
2022. https://doi.org/10.1007/s00454-022-00436-2.
ieee: U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer
Nature, pp. 1227–1284, 2022.
ista: Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the
plane. Discrete & Computational Geometry. 68(4), 1227–1284.
mla: Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the
Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer
Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.
short: U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.
corr_author: '1'
date_created: 2023-01-12T12:02:28Z
date_published: 2022-11-14T00:00:00Z
date_updated: 2025-07-10T11:54:56Z
day: '14'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00436-2
external_id:
isi:
- '000883222200003'
file:
- access_level: open_access
checksum: 307e879d09e52eddf5b225d0aaa9213a
content_type: application/pdf
creator: dernst
date_created: 2023-01-23T11:10:03Z
date_updated: 2023-01-23T11:10:03Z
file_id: '12345'
file_name: 2022_DiscreteCompGeometry_Wagner.pdf
file_size: 1747581
relation: main_file
success: 1
file_date_updated: 2023-01-23T11:10:03Z
has_accepted_license: '1'
intvolume: ' 68'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Theoretical Computer Science
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1227-1284
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '7807'
relation: earlier_version
status: public
- id: '7990'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Connectivity of triangulation flip graphs in the plane
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '14381'
abstract:
- lang: eng
text: Expander graphs (sparse but highly connected graphs) have, since their inception,
been the source of deep links between Mathematics and Computer Science as well
as applications to other areas. In recent years, a fascinating theory of high-dimensional
expanders has begun to emerge, which is still in a formative stage but has nonetheless
already lead to a number of striking results. Unlike for graphs, in higher dimensions
there is a rich array of non-equivalent notions of expansion (coboundary expansion,
cosystolic expansion, topological expansion, spectral expansion, etc.), with differents
strengths and applications. In this talk, we will survey this landscape of high-dimensional
expansion, with a focus on two main results. First, we will present Gromov’s Topological
Overlap Theorem, which asserts that coboundary expansion (a quantitative version
of vanishing mod 2 cohomology) implies topological expansion (roughly, the property
that for every map from a simplicial complex to a manifold of the same dimension,
the images of a positive fraction of the simplices have a point in common). Second,
we will outline a construction of bounded degree 2-dimensional topological expanders,
due to Kaufman, Kazhdan, and Lubotzky.
article_processing_charge: No
article_type: original
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Wagner U. High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky,
and others). Bulletin de la Societe Mathematique de France. 2022;438:281-294.
doi:10.24033/ast.1188
apa: Wagner, U. (2022). High-dimensional expanders (after Gromov, Kaufman, Kazhdan,
Lubotzky, and others). Bulletin de La Societe Mathematique de France. Societe
Mathematique de France. https://doi.org/10.24033/ast.1188
chicago: Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan,
Lubotzky, and Others).” Bulletin de La Societe Mathematique de France.
Societe Mathematique de France, 2022. https://doi.org/10.24033/ast.1188.
ieee: U. Wagner, “High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky,
and others),” Bulletin de la Societe Mathematique de France, vol. 438.
Societe Mathematique de France, pp. 281–294, 2022.
ista: Wagner U. 2022. High-dimensional expanders (after Gromov, Kaufman, Kazhdan,
Lubotzky, and others). Bulletin de la Societe Mathematique de France. 438, 281–294.
mla: Wagner, Uli. “High-Dimensional Expanders (after Gromov, Kaufman, Kazhdan, Lubotzky,
and Others).” Bulletin de La Societe Mathematique de France, vol. 438,
Societe Mathematique de France, 2022, pp. 281–94, doi:10.24033/ast.1188.
short: U. Wagner, Bulletin de La Societe Mathematique de France 438 (2022) 281–294.
corr_author: '1'
date_created: 2023-10-01T22:01:14Z
date_published: 2022-01-01T00:00:00Z
date_updated: 2025-09-10T09:55:10Z
day: '01'
department:
- _id: UlWa
doi: 10.24033/ast.1188
external_id:
isi:
- '000958364400007'
intvolume: ' 438'
isi: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 281-294
publication: Bulletin de la Societe Mathematique de France
publication_identifier:
eissn:
- 2102-622X
issn:
- 0037-9484
publication_status: published
publisher: Societe Mathematique de France
quality_controlled: '1'
scopus_import: '1'
status: public
title: High-dimensional expanders (after Gromov, Kaufman, Kazhdan, Lubotzky, and others)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 438
year: '2022'
...
---
_id: '10776'
abstract:
- lang: eng
text: 'Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior).
Given a point p in the interior of K, a hyperplane h passing through p is called
barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question
whether, for every K, there exists an interior point p through which there are
at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly
resolved affirmatively by showing that this is the case if p=p0 is the point of
maximal depth in K. However, while working on a related question, we noticed that
one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample;
this re-opens Grünbaum’s question. It follows from known results that for n≥2,
there are always at least three distinct barycentric cuts through the point p0∈K
of maximal depth. Using tools related to Morse theory we are able to improve this
bound: four distinct barycentric cuts through p0 are guaranteed if n≥3.'
acknowledgement: The work by Zuzana Patáková has been partially supported by Charles
University Research Center Program No. UNCE/SCI/022, and part of it was done during
her research stay at IST Austria. The work by Martin Tancer is supported by the
GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and
UNCE/SCI/004.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Zuzana
full_name: Patakova, Zuzana
id: 48B57058-F248-11E8-B48F-1D18A9856A87
last_name: Patakova
orcid: 0000-0002-3975-1683
- first_name: Martin
full_name: Tancer, Martin
last_name: Tancer
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. Discrete
and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7
apa: Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through
a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7
chicago: Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through
a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022.
https://doi.org/10.1007/s00454-021-00364-7.
ieee: Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex
body,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp.
1133–1154, 2022.
ista: Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body.
Discrete and Computational Geometry. 68, 1133–1154.
mla: Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” Discrete
and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.
short: Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68
(2022) 1133–1154.
date_created: 2022-02-20T23:01:35Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-02T14:38:58Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s00454-021-00364-7
external_id:
arxiv:
- '2003.13536'
isi:
- '000750681500001'
intvolume: ' 68'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2003.13536
month: '12'
oa: 1
oa_version: Preprint
page: 1133-1154
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Barycentric cuts through a convex body
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '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
arxiv: 1
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).
corr_author: '1'
date_created: 2022-03-20T23:01:38Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2024-10-09T21:01:51Z
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: '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
arxiv: 1
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: 2025-09-10T09:35:56Z
day: '16'
department:
- _id: UlWa
doi: 10.1007/978-3-030-96731-4_31
ec_funded: 1
external_id:
arxiv:
- '2109.14892'
isi:
- '001435074700031'
intvolume: ' 13174'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13174
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
arxiv: 1
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: '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
arxiv: 1
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. 2022;30(2):657-675. doi:10.1007/s11228-021-00612-1
apa: Ivanov, G., & Lopushanski, M. S. (2022). 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, 2022.
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, vol. 30, no. 2. Springer Nature,
pp. 657–675, 2022.
ista: Ivanov G, Lopushanski MS. 2022. Rectifiable curves in proximally smooth sets.
Set-Valued and Variational Analysis. 30(2), 657–675.
mla: Ivanov, Grigory, and Mariana S. Lopushanski. “Rectifiable Curves in Proximally
Smooth Sets.” Set-Valued and Variational Analysis, vol. 30, no. 2, Springer
Nature, 2022, pp. 657–75, doi:10.1007/s11228-021-00612-1.
short: G. Ivanov, M.S. Lopushanski, Set-Valued and Variational Analysis 30 (2022)
657–675.
date_created: 2021-10-24T22:01:35Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2024-05-22T09:23:37Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s11228-021-00612-1
external_id:
arxiv:
- '2012.10691'
isi:
- '000705774800001'
intvolume: ' 30'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.10691
month: '06'
oa: 1
oa_version: Published Version
page: 657-675
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 30
year: '2022'
...