# Sufficiently many points in $\mathbb{R}^d$ must contain $m$ points forming the vertices of a convex polytope?

Let us say that a set of points in $\mathbb{R}^d$ is minimal if it forms exactly the set of vertices of a convex polytope. Equivalently, no proper subset of the points has the same convex hull; no point is contained in the convex hull of the others.

Then there is a well-known application of Ramsey's theorem to discrete geometry that says the following:

(1) For any integer $m$, there exists an integer $n$ such that any $n$ points in $\mathbb{R}^2$, no three collinear, contains a minimal subset of $m$ points.

In this case, since it's $\mathbb{R}^2$, a minimal set is just a convex $m$-gon. You can find the proof here.

The question is simply replacing $\mathbb{R}^2$ with $\mathbb{R}^d$ above.

Prove or disprove: (2) For any integer $m$, there exists an integer $n$ such that any $n$ points in $\mathbb{R}^d$, no three collinear, contains a minimal subset of $m$ points.

The proof of (1) relies on two facts: (i) that a set of points in $\mathbb{R}^2$ is minimal if and only if every subset of 4 points in it is minimal, and (ii) that any set of five points contains a minimal subset of 4 points. (ii) fails in $\mathbb{R}^d$. So I am not sure the argument given at the cut-the-knot link extends in any obvious way. (An almost identical argument is given in Douglas B West's Introduction to Graph Theory, 2nd edition, page 382.)

I believe that the argument in the cut-the-knot link does extend to $\mathbb{R}^d$ (at least, it extends to $\mathbb{R}^3$, with some work) if in (2) the $n$ points are in general position. But we only said no three were collinear.

• At the very least you should replace the notion of collinearity in $R^d$ with something else, maybe that no $k+1$ points belong to a $k-1$-dimensional affine subspace. – Moishe Kohan Jul 15 '16 at 4:32
• @studiosus But that's the whole point -- I believe the statement to be true as it is. Do you think it's false? – 6005 Jul 15 '16 at 4:38
• Yes, you are right. – Moishe Kohan Jul 15 '16 at 14:46

This is indeed true in all dimension $d$ provided that no 3 points are collinear. See the proof sketched here: Take an $n$ point subset $X\subset R^d$ such that no 3 are collinear and project to a configuration $p(X)$ a generic 2-plane. Now apply the Erdős–Szekeres conjecture to $p(X)$, find a subset $Z=p(Y)\subset W=p(X)$ of cardinaly $m=N_2(n)$ which spans a convex $m$-gon. Then $Y$ is minimal in your sense since: If $y\in Y$ is a convex combination of $Y-\{y\}$ then the same remains true for the projection, contradicting the choice of $Z$.
• Thank you for answering! I don't exactly see what part of the page you meant to refer to but it doesn't matter, I know the Erdos-Szekeres conjecture is the theorem under "Larger Polygons". I have one question about your proof. While I believe that surely a projection $p$ exists preserving that no three points are colinear, how do we prove it exists? – 6005 Jul 22 '16 at 1:30
• @6005: Consider the Grassmannian $Gr_2(E^n)$ of 2-planes in $E^n$. It is a smooth compact manifold. Orthogonal projections to 2-planes in $E^n$ can be identified with the elements of $Gr_2(E^n)$. A projection $g\in Gr_2(E^n)$ is generic if it belongs to some open and dense subset of $Gr_2(E^n)$. You can easily check that given a set $S$ of three noncollinear points in $E^n$, the set of projections $P_S$ sending them to collinear points is closed and nowhere dense. Now, you run through all 3-element subsets $S$ of your finite set and take the union of the corresponding subsets $P_S$. – Moishe Kohan Jul 23 '16 at 4:15
• By the Baire category theorem, this union is nowhere dense in $Gr_2(E^n)$. Therefore, there exists a projection as required. – Moishe Kohan Jul 23 '16 at 4:16