Talk information

Date: Sunday, January 14, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Noga Alon (Princeton)
Title: Ordering candidates via vantage points

Abstract:

For a set $C$ of $n$ points in $\mathbb{R}^d$ and a set V of k points in $\mathbb{R}^d$, let $\mathrm{ord}(C,V)$ denote the order of the points $c$ of $C$ determined by the sum of their (Euclidean) distances $\sum_{v \in V} |v-c|$ from the points of $V$. What is the maximum possible number of orders $f(k,d,n)$ one can get this way for a fixed set $C$ of size $n$ in $\mathbb{R}^d$, as $V$ ranges over all sets of size $k$?

For $k=1$ this is not difficult and well known since the 70s, but even the problem of understanding the asymptotic behaviour of this maximum for the case $k=2$ and dimension $d=2$ for large $n$, raised in a recent paper of Carbonero et. al., is not easy. We settle this problem by showing that for every fixed $k$ and $d>1$, $f(k,d,n)$ grows like a polynomial of degree $2kd$ in $n$.

The main novelty in the proof is an upper bound for the number of sign patterns of functions, where each function is a linear combination of not too many square roots (or other rational fractional powers) of nonnegative multivariate real polynomials of bounded degrees, extending results of Warren and Milnor in real algebraic geometry.

Joint work with Colin Defant, Noah Kravitz and Daniel Zhu.