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

All the point sets in this post are in general position. A set of points in $R^d$ is in general position if every $k+1$ points are affinely independent for $k \le d$. If the set contains at least $d+1$ points it is enough to demand that every $d+1$ points in the set affinely span $R^d$.

In the plane a set of three or more points is in general position if NO TRIPLE OF POINTS IS COLLINEAR.

We say that a set of points is in convex position if they all lie on he boundary of their convex hull. e.g. in the plane they are the vertices of a convex $n$-gon.

We say that a set of points is in cyclic position if their convex hull is a cyclic polytope and they all lie on the boundary of their convex hull.

In the paper that Erdos and Szekeres invented Ramsey theory; they proved that any set of $ES(n)$ points in the plane contains a subset of n in convex position. They gave decent bounds on $ES(n)$. Their lower bound is conjectured to be the truth, $ES(n)=2^{n-2}+1$. There are many extensions and generalizations (yet the upper bound after 75 years is $\frac{1}{2}$ their original upper bound, no asymptotic improvement in all these years).

There are two higher dimensional versions of this result: There are functions $ES_d(n)$ and $C_d(n)$ such that among any set of $ES_d(n)$ points in $R^d$ there is a subset of n in convex position, and among any $C_d(n)$ points there are n in cyclic position.

$ES_k(n)\leq ES_d(n)$ whenever $k\geq d$ is easy to see, and there is some interesting lower bounds on $ES_d(n)$.

Here is the question: are there decent bounds on C_d(n)? Where the function C_d(n) is the smallest number such that "among any C_d(n) points in general position there are n in cyclic position". And being in cyclic position means having the combinatorial type of the cyclic polytope. I'm more interested in the upper bound, anything that does not use Ramsey theorem is of interest. References anyone?

share|improve this question
    
I assume the function $C_d(n)$ is the smallest number such that "among any C_d(n) points there are n in cyclic position." –  Matthew Kahle Aug 6 '11 at 1:00
    
Does cyclic position mean having the combinatorial type of the cyclic polytope? –  Matthew Kahle Aug 6 '11 at 1:04
3  
A related MO question is mathoverflow.net/questions/67762/… . Indeed it would be nice to find upper bounds for C_d(n) which dont use Ramsey's theorem. The 2-dimensional case suggest this might be possible. (Also it would be interesting to find lower bounds.) –  Gil Kalai Aug 6 '11 at 8:56
add comment

3 Answers 3

Andrew Suk gives new bounds for general d and a pretty good bound for d=3

http://arxiv.org/abs/1305.5934

share|improve this answer
add comment

I know that Morris and Soltan's survey article covers some higher-dimensional cases, but I don't remember if they have any bounds of the kind you're asking for.

http://www.ams.org/journals/bull/2000-37-04/S0273-0979-00-00877-6/home.html

share|improve this answer
1  
This is a great survey, but they don't give better bounds. –  Alfredo Hubard Aug 6 '11 at 13:52
add comment

Something like this is in Grünbaum's Convex Polytopes, 2nd edition, Exercise 7.3.6, p. 126. But Grünbaum states it for neighborly polytopes, not more strongly for cyclic polytopes.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.