Arrange points such that translates of orthants separate subsets of them

43 Views Asked by At

Is it possible to arrange $n$ distinct points $A = \{x_1, \ldots, x_n\} \subseteq \mathbb R^k$ so that every subset $B \subseteq A$ could be written as $$ (y_B + \mathbb R_{\ge 0}^k) \cap A $$ for some point $y_B \in \mathbb R^k$, i.e., $B = (y_B + \mathbb R_{\ge 0}^k) \cap A$. In some sense this means that the translates of the orthants $y_B + \mathbb R_{\ge 0}^k$ separate all subsets of $A$.

Is this possible if $k < n$?

If $k = n$ (or more generally $k \ge n$) this is possible. Let us denote the $j$-the coordinate of some point $x$ by $\pi_j(x)$, for example $\pi_2((1,2,3)) = 2$. Now let $A = \{x_1, \ldots, x_{n-1}\}$ be some such arrangement in $\mathbb R^{n-1}$. Then we can embed this into $\mathbb R^{n-1} \times\{0\} \subseteq \mathbb R^n$, hence we suppose the $n$-coordinate of the $x_i$ is zero, and also of the $2^{n-1}$ points $y_B$ for $B \subseteq A$ too. Let $x := \max_{B\subseteq A} \max_{j=1,\ldots,n-1} \pi_j(y_B)$. Set $x_n = (x,\ldots,x,-1)$. Then $x \notin y_B + \mathbb R_{\ge 0}^n$ for all $B \subseteq A$. Now consider $y_{B \cup \{x_n\}} := (\pi_1(y_B), \ldots, \pi_{n-1}(y_B), -1)$, we have $$ (y_{B\cup \{x_n\}} + \mathbb R_{\ge 0}^n) \cap (A \cup \{x_n\}) = B \cup \{x_n\}. $$ Noting that for $n = 1$ everything is trivial so we can inductively find such an arrangement of $n$ points in $\mathbb R^n$.

I somehow think it is not possible if $k < n$ (for example you cannot do it if $k = 1$). But I do not have an argument for this...

1

There are 1 best solutions below

0
On BEST ANSWER

We will call a set $A=\{x_1, \dots, x_n\}$ separable if your property holds, i.e. $\forall B \subset A, \exists\ y_B \in \mathbb{R}^k$ such that $B = (y_B + \mathbb R_{\ge 0}^k) \cap A.$

Let $\pi_j(v)$ denote the $j$th coordinate of $v$ as you suggested.

Definition: Coordinate $j$ is separating for point $x_i$ if $\pi_j(x_i) < \pi_j(x_k) \ \forall k \neq i,$ i.e. if $x_i$ has the strictly minimum $j$th-coordinate value among all points.

Claim 1: $A$ is separable $\implies$ every $x \in A$ has some separating coordinate, i.e.:

$$\forall i, \exists j \text{ such that } \pi_j(x_i) < \pi_j(x_k) \ \forall k \neq i.$$

Proof: Consider subsets of the form $B = A - \{x_i\}$. By assumption, $A$ is separable so $y_B$ exists. Now $x_i \notin B \implies x_i \notin (y_B + \mathbb R_{\ge 0}^k) \implies$ there exists some coordinate $j$ s.t. $\pi_j(x_i) < \pi_j(y_B)$. But all other $x_k \in B$, which means $\pi_j(y_B) \le \pi_j(x_k)$. Combining, we have $\pi_j(x_i) < \pi_j(x_k)$ strictly.

Corrollary: $n > k$ is impossible, because there are only $k$ coordinates and so $n$ points cannot each have its own separating coordinate. (Clearly two points cannot have the same $j$ as separating coordinate, since ties are not allowed.)


In fact, the converse of Claim 1 is also true, i.e.

Claim 2: $A$ is separable $\iff$ every $x \in A$ has some separating coordinate.

Proof: We only need to prove the $\Leftarrow$ direction, and we will do so by constructing $y_B$ explicitly. For any $B\subset A$, consider any $x_i \notin B$ and suppose it is separating in coordinate $j$. Pick $\pi_j(y_B) = \min_{k \neq i} \pi_j(x_k),$ i.e. the second-minimum value. This choice would exclude $x_i$ and no other point. We can do this for every $x_i \notin B$ because they all have different separating coordinates. Finally, in all other coordinates pick $\pi_j(y_B) = \min_{k} \pi_j(x_k),$ i.e. the minimum value so as to include all points. Thus, every point $\in B$ has all its coordinates $\ge y_B$ while every point $\notin B$ has its separating coordinate $< y_B$.

Example: For $n=k$, let $\pi_j(x_i) = -1$ if $i=j$ and $=0$ if $i \neq j$. For every $B$, simply set $\pi_j(y_B) = -1$ if $x_j \in B$ and $=0$ if $x_j \notin B$. Thus we have an explicit construction which does not rely on proof by induction.