How many top-$k$ orderings can be induced by linear functionals on integer points in a square?

15 Views Asked by At

Let $X = ([1,n] \times [1,n]) \cap {\mathbb N}\times {\mathbb N}$ for positive integer $n$. For $k \leq n^2,$ a top-$k$ ordering $(x_{a_1},x_{a_2}, \ldots, x_{a_k})$ induced by a vector $c$ is a $k$-tuple of $k$ points in $X$ such that $c \cdot x_{a_1} > c \cdot x_{a_2} > \ldots > c \cdot x_{a_k} > x$ for all points $x$ not in the tuple. Asymptotically (up to a constant factor is fine), how many distinct top-$k$ orderings are possible as a function of $k$ and $n$? Or if that's too hard, what is an asymptotic upper bound? The best upper bound I currently have is $O(k^{2/3}n^{2/3})$, and it uses a pretty deep theorem about bounding the number of vertices of polytopes with integer vertices, in terms of their volumes. But it seems like there should be a more elementary way to approach this problem. Even an elementary proof of my current bound or a slightly worse bound would be appreciated.