8
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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." $\endgroup$ Aug 6, 2011 at 1:00
  • $\begingroup$ Does cyclic position mean having the combinatorial type of the cyclic polytope? $\endgroup$ Aug 6, 2011 at 1:04
  • 3
    $\begingroup$ 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.) $\endgroup$
    – Gil Kalai
    Aug 6, 2011 at 8:56

3 Answers 3

3
$\begingroup$

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

http://arxiv.org/abs/1305.5934

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ This is a great survey, but they don't give better bounds. $\endgroup$ Aug 6, 2011 at 13:52
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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