Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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})$.

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.