2026-08-10T23:54:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23227 2025-10-02T12:43:38Z ddc:004 open_access

Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers Streltsova, Elizaveta Wagner, Uli Levels in arrangements k-sets k-facets convex polytopes f-vector h-vector g-vector Dehn-Sommerville relations Radon partitions Gale duality g-matrix 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elizaveta Streltsova and Uli Wagner 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.75 urn:nbn:de:0030-drops-232276 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.75 eng https://creativecommons.org/licenses/by/4.0/legalcode