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?
Best Answer
Andrew Suk gives new bounds for general d and a pretty good bound for d=3
http://arxiv.org/abs/1305.5934