Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers
Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 75.
Download
Conference Paper
| Published
| English
Scopus indexed
Corresponding author has ISTA affiliation
Department
Series Title
LIPIcs
Abstract
A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.
Moreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level).
To prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.
Publishing Year
Date Published
2025-06-20
Proceedings Title
41st International Symposium on Computational Geometry
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume
332
Article Number
75
Conference
SoCG: Symposium on Computational Geometry
Conference Location
Kanazawa, Japan
Conference Date
2025-06-23 – 2025-06-27
ISBN
eISSN
IST-REx-ID
Cite this
Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In: 41st International Symposium on Computational Geometry. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SoCG.2025.75
Streltsova, E., & Wagner, U. (2025). Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In 41st International Symposium on Computational Geometry (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2025.75
Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” In 41st International Symposium on Computational Geometry, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SoCG.2025.75.
E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers,” in 41st International Symposium on Computational Geometry, Kanazawa, Japan, 2025, vol. 332.
Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 75.
Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” 41st International Symposium on Computational Geometry, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SoCG.2025.75.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2025_LIPIcs.SoCG_Streltsova.pdf
952.81 KB
Access Level

Date Uploaded
2025-07-14
MD5 Checksum
a8f7feb1aa3b896e31195841a989d622
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2504.07752