1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Moishe Kohan Jul 15 '16 at 4:32
  • $\begingroup$ @studiosus But that's the whole point -- I believe the statement to be true as it is. Do you think it's false? $\endgroup$ – 6005 Jul 15 '16 at 4:38
  • 1
    $\begingroup$ Yes, you are right. $\endgroup$ – Moishe Kohan Jul 15 '16 at 14:46
0
+100
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – 6005 Jul 22 '16 at 1:30
  • $\begingroup$ @6005 first prove that for 3 noncollinear points a generic projection sends them to noncollinear points. Now if you like, use Baire category theorem. Or if you know some algebraic geometry use the fact that a finite intersection of Zariski open and dense sets us again Zariski open and dense. $\endgroup$ – Moishe Kohan Jul 22 '16 at 20:30
  • $\begingroup$ I am not sure what a "generic projection" means, even after googling. $\endgroup$ – 6005 Jul 23 '16 at 1:36
  • $\begingroup$ @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$. $\endgroup$ – Moishe Kohan Jul 23 '16 at 4:15
  • $\begingroup$ By the Baire category theorem, this union is nowhere dense in $Gr_2(E^n)$. Therefore, there exists a projection as required. $\endgroup$ – Moishe Kohan Jul 23 '16 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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