---
_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: '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
arxiv: 1
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: '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
arxiv: 1
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
license: https://creativecommons.org/licenses/by/4.0/
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: '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.
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: '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
arxiv: 1
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
arxiv: 1
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: '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
arxiv: 1
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
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
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
arxiv: 1
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
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: 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: '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
arxiv: 1
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: '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
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: 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
arxiv: 1
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
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. 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
arxiv: 1
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: '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: '7807'
abstract:
- lang: eng
text: "In a straight-line embedded triangulation of a point set P in the plane,
removing an inner edge and—provided the resulting quadrilateral is convex—adding
the other diagonal is called an edge flip. The (edge) flip graph has all triangulations
as vertices, and a pair of triangulations is adjacent if they can be obtained
from each other by an edge flip. The goal of this paper is to contribute to a
better understanding of the flip graph, with an emphasis on its connectivity.\r\nFor
sets in general position, it is known that every triangulation allows at least
edge flips (a tight bound) which gives the minimum degree of any flip graph for
n points. We show that for every point set P in general position, the flip graph
is at least -vertex connected. Somewhat more strongly, we show that the vertex
connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum
number of flippable edges in any triangulation of P, provided P is large enough.
Finally, we exhibit some of the geometry of the flip graph by showing that the
flip graph can be covered by 1-skeletons of polytopes of dimension (products of
associahedra).\r\nA corresponding result ((n – 3)-vertex connectedness) can be
shown for the bistellar flip graph of partial triangulations, i.e. the set of
all triangulations of subsets of P which contain all extreme points of P. This
will be treated separately in a second part."
article_processing_charge: No
arxiv: 1
author:
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: 'Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane
(Part I: Edge flips). In: Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. Vol 2020-January. SIAM; 2020:2823-2841. doi:10.1137/1.9781611975994.172'
apa: 'Wagner, U., & Welzl, E. (2020). Connectivity of triangulation flip graphs
in the plane (Part I: Edge flips). In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms (Vol. 2020–January, pp. 2823–2841). Salt Lake City,
UT, United States: SIAM. https://doi.org/10.1137/1.9781611975994.172'
chicago: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs
in the Plane (Part I: Edge Flips).” In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, 2020–January:2823–41. SIAM, 2020. https://doi.org/10.1137/1.9781611975994.172.'
ieee: 'U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the
plane (Part I: Edge flips),” in Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, Salt Lake City, UT, United States, 2020, vol. 2020–January,
pp. 2823–2841.'
ista: 'Wagner U, Welzl E. 2020. Connectivity of triangulation flip graphs in the
plane (Part I: Edge flips). Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms. SODA: Symposium on Discrete Algorithms vol. 2020–January, 2823–2841.'
mla: 'Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in
the Plane (Part I: Edge Flips).” Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, vol. 2020–January, SIAM, 2020, pp. 2823–41, doi:10.1137/1.9781611975994.172.'
short: U. Wagner, E. Welzl, in:, Proceedings of the Annual ACM-SIAM Symposium on
Discrete Algorithms, SIAM, 2020, pp. 2823–2841.
conference:
end_date: 2020-01-08
location: Salt Lake City, UT, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2020-01-05
date_created: 2020-05-10T22:00:48Z
date_published: 2020-01-01T00:00:00Z
date_updated: 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: '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: '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
arxiv: 1
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: '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
arxiv: 1
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'
...