# Bounds on number of linear top-$k$ orderings of lattice point sets

Given a set of $n$ lattice points $A = \{a_i\} \subset {\mathbb Z}^d$ I call a $k$-tuple $(a_{i_1},\ldots,a_{i_k})$ from $A$ a (linear) top-$k$ ordering if there is a vector $c$ such that

$$c\cdot a_{i_i} > c\cdot a_{i_2} > \ldots > c \cdot a_{i_k}$$

and $c \cdot a_{i_k} > c \cdot a$ for all other $a \in A$. For dense $A$ (i.e. the volume of the convex hull of $A$ is no more than $Cn$ for some fixed constant $C$), I can show that for fixed $d$, the number of top-$k$ orderings is $O(k^{2d(d-1)/(d+1)} n^{(d-1)/(d+1)})$, using a general theorem of Andrews that states that a polytope with lattice point vertices and volume $V$ has $O(V^{(d-1)/(d+1)})$ vertices. However I think it's extremely optimistic to think that such a general argument would give tight bounds. So my question is whether my bound on top-$k$ orderings for dense $A$ is tight; even an answer for dimension 2 would be helpful, where my current bound is $O(k^{4/3} n^{1/3})$.

-
add comment