2

The claim is given in page 5 of this: http://wiki-math.univ-mlv.fr/gemecod/lib/exe/fetch.php/barany_lecture_1.pdf. It states that if a finite subset of points in general position $S$ of $R^d$ is partitioned into $r$ pairwise disjoint subsets $S_1, \ldots S_r$, then if the intersection of all affine subspaces $aff S_i$ is empty, we have that $|S| \leq (r-1)(d+1)$.

The proof (or at least a "counting argument") is given in the document, but I don't really understand it; how can $r(d+1) - |X| \geq r(d+1) - (r-1)(d+1)$? What is $|X|$?

aellab
  • 845
  • The claim is part of the proof of Theorem 6 on page 4. The Theorem's statement says that $X$ is "a subset of $\Bbb{R}^d$ with $\lvert X \rvert = (r-1)(d+1)+1$"... – A.P. Jan 11 '18 at 01:01
  • @A.P. I thought that was the case, but if $|X| = (r-1)(d+1) + 1$ then $r(d+1) - |X|$ is precisely $d$, so the inequality is strictly false... – aellab Jan 11 '18 at 01:02
  • Reading more closely it's clear that $X$ is a typo here, since $\sum_{i=1}^r (d+1 - \lvert S_i \rvert) = r(d+1) - \lvert S \rvert$, since by hypothesis the $S_i$ form a partition of $S$. – A.P. Jan 11 '18 at 01:05
  • And since $|S|$ is at worst case equal to $r(d+1)$ that also doesn't help :-/. Probably the fact that the intersection is empty is used somehow, though I don't understand how. – aellab Jan 11 '18 at 01:07

1 Answers1

1

I agree that this argument could be written better. Here's how I understand it:

First of all, observe that every (non-empty) affine subset $A$ of $\Bbb{R}^d$ can be written as the intersection of at most $d - \operatorname{dim}(A)$ hyperplanes in general position. We can do this by choosing one hyperplane at a time so that $\operatorname{dim}\left(H_{k+1} \cap \bigcap_{j=1}^k H_j\right) < \operatorname{dim}\left(\bigcap_{j=1}^k H_j\right)$ (see this).

Therefore each $\operatorname{aff}S_i$ can be written as the intersection of exactly $n_i$ hyperplanes in general position and, up to a slight rotation of some of them, we can consider a collection of hyperplanes in general position $\{H_1,\dotsc,H_{n_1+\dotsc+n_r}\}$ such that $$ \operatorname{aff}S_i = \bigcap_{j=1}^{n_i} H_{j+n_{i-1}} $$ where we set $n_0 = 0$. It follows that $$ \bigcap_{i=1}^r \operatorname{aff}S_i = \bigcap_{i=1}^r \bigcap_{j=1}^{n_i} H_{j+n_{i-1}} = \bigcap_{j=1}^{n_1+\dotsc+n_r} H_j. $$ Since this intersection is empty by hypothesis, the choice of hyperplanes in general position implies that $n_1+\dotsc+n_r \geq d+1$.

On the other hand, as mentioned in that argument, if the points of $S_i$ (which are at most $d+1$ by hypothesis) are in general position we know that $\operatorname{dim}\left(\operatorname{aff}(S_i)\right) = \lvert S_i \rvert - 1$, i.e. $n_i = d+1 - \lvert S_i \rvert$. Hence we just proved that $$ d+1 \leq \sum_{i=1}^r n_i = \sum_{i=1}^r \left(d+1 - \lvert S_i \rvert\right) = r(d+1) - \lvert S \rvert. $$

Finally, rearranging gives $\lvert S \rvert \leq (r-1)(d+1)$.

A.P.
  • 9,728
  • Thanks for your answer. Can you elaborate on the comment that "at most $d$ pairwise non-parallel hyperplanes" have a non-empty intersection? Couldn't it be possible that the intersection is empty if e.g. one of the hyperplanes is parallel to the intersection of two other hyperplanes (such as when three 2D planes are laid in a "triangle" formation in $R^3$)? – aellab Jan 11 '18 at 03:05
  • Sorry, I was a bit too hasty in trying to avoid talking about hyperplanes in general position. I hope now it's clear. – A.P. Jan 11 '18 at 12:39