There are $(d+1)f$ points (denote the set of all points as $S$) in $\mathbb{R}^d$, that can be divide into $d+1$ disjoint sets $F_1,...,F_{d+1}$, each set of size $f$. If we have $$ \mathcal{H}(F_i)\bigcap \mathcal{H}(S-F_i)=\emptyset $$ for all $1\leq i\leq d+1$. How can we show the following: $$ \mathcal{H}(S)-\bigcup_{i=1}^{d+1}\mathcal{H}(S-F_i)\subseteq \operatorname{conv}(v_1,...,v_{d+1}) $$ where $v_i\in F_i$, $1\leq i\leq d+1$

  • 1
    $\begingroup$ What does $\mathcal H(\cdot)$ denote? $\endgroup$ – Ilya Bogdanov Oct 25 '15 at 19:27
  • 2
    $\begingroup$ The question seems to make sense if $\mathcal{H}(X)$ is the convex hull of $X$. This isn't quite redundant with $conv(v_1,...,v_{d+1})$. $\endgroup$ – Douglas Zare Oct 25 '15 at 20:53
  • $\begingroup$ Yes, $\mathcal{H}(\cdot)$ denotes taking the convex hull. $\endgroup$ – xzl Oct 26 '15 at 5:21

$\def\conv{\mathop{\rm conv}}\let\emp\varnothing$This is the answer if @Douglas Zare is correct, so that $\conv(\cdot)$ means the same as $\mathcal H(\{\cdot\})$.

We omit the condition that $|F_i|$ are the same, thus considering any disjoint finite sets $F_i$ with $S=\bigcup_i F_i$. Notice that we may keep only those points of $F_i$ which are the vertices of $T=\conv S$; this just makes the claim sharper. Due to the compactness reason, we may assume that the vertices of the dual polyhedron of $\conv $ are in general position; thus every $d$ vectors connecting a vertex of $\conv S$ with other vertices are independent.

If $|F_i|=1$ for every $i$, the claim is trivial. So assume that $|F_1|>1$. In this case, since $F_1$ is separated from $F_j$ with $j>1$, there exists an edge $uv$ of $T$ with $u,v\in F_1$. This edge belongs to some $(d-2)$-dimensional face $P$ of $T$ which is a part of a $(d-1)$-dimensional face $Q$.

Now rotate the hyperplane spanned by $Q$ around the affine subspace defined by $P$. Let $w$ be the first vertex we meet. Then the hyperplane $\alpha$ spanned by $P$ and $w$ separates some vertex of $Q$ from the rest vertices of $T$. Then $\alpha$ contains the vertices of at most $d-1$ of the $F_i$ (since it contains two vertices from $F_1$), so the whole simplex it cuts out of $T$ is contained in some $\conv (S-F_i)$. Now we may remove this vertex and proceed by induction.

  • $\begingroup$ Thank you for the answer. However, I am not quite follow... Why is the claim sharper when only considering vertices of $T$? Since $conv(v_1,...,v_{d+1})$ could be smaller without this condition. Besides, where did you use the condition that $\mathcal{H}(F_i)\bigcap \mathcal{H}(S-F_i)=\emptyset$? $\endgroup$ – xzl Oct 26 '15 at 5:24
  • $\begingroup$ 1) The claim is sharper, since $\mathop{\rm conv}(S-F_i)$ becomes smaller in this case. 2) The condition of non-intersection was used in the middle: all vertices of $\mathop{\rm conv} S$ belonging to $F_i$ form a connected (by edges) set, so there exists an edge with the vertices of the same color. In turn, this condition is needed to establish that the simplex to be cut is not polychromatic. $\endgroup$ – Ilya Bogdanov Oct 26 '15 at 5:57

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.