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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.