2023/08/09 by Noga Alon, Alon, Noga, Colin Defant +5
Computer Science · Engineering · #52A40 (Secondary) #52C10 (Primary) 51M16 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2308.05208
openalex publication_date 2023/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an n-element set C⊆ℝd and a (sufficiently generic) k-element multiset V⊆ℝd, we can order the points in C by ranking each point c∈ C according to the sum of the distances from c to the points of V. Let Ψk(C) denote the set of orderings of C that can be obtained in this manner as V varies, and let ψmaxd,k(n) be the maximum of |Ψk(C)| as C ranges over all n-element subsets of ℝd. We prove that ψmaxd,k(n)=Θd,k(n2dk) when d ≥ 2 and that ψmax1,k(n)=Θk(n4\lceil k/2\rceil -1). As a step toward proving this result, we establish a bound on the number of sign patterns determined by a collection of functions that are sums of radicals of nonnegative polynomials; this can be understood as an analogue of a classical theorem of Warren. We also prove several results about the set Ψ(C)=\bigcupk≥ 1Ψk(C); this includes an exact description of Ψ(C) when d=1 and when C is the set of vertices of a vertex-transitive polytope.