Skip to main content
added 53 characters in body
Source Link
Yury
  • 726
  • 3
  • 9

Here is a counterexample. ConsdierConsider vectors $v^1 = (4,4,1,1)$, $v^2 = (1,1,4,4)$, and $v^3 =(3,3,3,3)$. They form an antichain, as required. Further, $d = 3 < n =4$. However, there is no hyperplane $\{x:\alpha x = \beta\}$ with all $\alpha_i > 0$ that contains all vectors $v^i$.

Discussion. It's not hard to see that the required hyperplane exists if and only if the affine span $L$ of vectors $\{v^i\}$ is disjoint froman antichain (that is, the difference between any two distinct vectors in $L$ is not in the orthant $Q_- = \{x: x_i \leq 0 \text{ for all } i\}$). In one direction the proof is immediate: if the desiredIf all $v^i$ lie in a hyperplane $H$ exists, then$H = \{x:\alpha x = \beta\}$ (1) $L \subset H$ andwith all (2$\alpha_i > 0$) $H$ is disjoint from, then $Q_-$$L \subset H$. ThusTherefore, $L$ is disjoint fromevery distinct $Q_-$$u, v\in L$ must be incomparable. To prove the criterion inIn the other direction, consider a hyperplane strictly separating $L$ and $Q_-$ and then translate it so that it contains all points $v^i$the criterion follows from duality.

In the counterexample above, the affine span $L$ contains linepoints $\{(x,x,x,x): x\in \mathbb{R}\}$$(5/2,5/2,5/2,5/2) = \frac{(4,4,1,1)+ (1,1,4,4)}{2}$ and thus is not disjoint from $Q_-$$(3,3,3,3)$ are in $L$. But the former is less than the latter in each coordinate.

Here is a counterexample. Consdier vectors $v^1 = (4,4,1,1)$, $v^2 = (1,1,4,4)$, and $v^3 =(3,3,3,3)$. They form an antichain, as required. Further, $d = 3 < n =4$. However, there is no hyperplane $\{x:\alpha x = \beta\}$ with all $\alpha_i > 0$ that contains all vectors $v^i$.

Discussion. It's not hard to see that the required hyperplane exists if and only if the affine span $L$ of vectors $\{v^i\}$ is disjoint from the orthant $Q_- = \{x: x_i \leq 0 \text{ for all } i\}$. In one direction the proof is immediate: if the desired hyperplane $H$ exists, then (1) $L \subset H$ and (2) $H$ is disjoint from $Q_-$. Thus, $L$ is disjoint from $Q_-$. To prove the criterion in the other direction, consider a hyperplane strictly separating $L$ and $Q_-$ and then translate it so that it contains all points $v^i$.

In the counterexample above, the affine span $L$ contains line $\{(x,x,x,x): x\in \mathbb{R}\}$ and thus is not disjoint from $Q_-$.

Here is a counterexample. Consider vectors $v^1 = (4,4,1,1)$, $v^2 = (1,1,4,4)$, and $v^3 =(3,3,3,3)$. They form an antichain, as required. Further, $d = 3 < n =4$. However, there is no hyperplane $\{x:\alpha x = \beta\}$ with all $\alpha_i > 0$ that contains all vectors $v^i$.

Discussion. It's not hard to see that the required hyperplane exists if and only if the affine span $L$ of vectors $\{v^i\}$ is an antichain (that is, the difference between any two distinct vectors in $L$ is not in the orthant $Q_- = \{x: x_i \leq 0 \text{ for all } i\}$). In one direction the proof is immediate: If all $v^i$ lie in a hyperplane $H = \{x:\alpha x = \beta\}$ (with all $\alpha_i > 0$), then $L \subset H$. Therefore, every distinct $u, v\in L$ must be incomparable. In the other direction, the criterion follows from duality.

In the counterexample above, points $(5/2,5/2,5/2,5/2) = \frac{(4,4,1,1)+ (1,1,4,4)}{2}$ and $(3,3,3,3)$ are in $L$. But the former is less than the latter in each coordinate.

Source Link
Yury
  • 726
  • 3
  • 9

Here is a counterexample. Consdier vectors $v^1 = (4,4,1,1)$, $v^2 = (1,1,4,4)$, and $v^3 =(3,3,3,3)$. They form an antichain, as required. Further, $d = 3 < n =4$. However, there is no hyperplane $\{x:\alpha x = \beta\}$ with all $\alpha_i > 0$ that contains all vectors $v^i$.

Discussion. It's not hard to see that the required hyperplane exists if and only if the affine span $L$ of vectors $\{v^i\}$ is disjoint from the orthant $Q_- = \{x: x_i \leq 0 \text{ for all } i\}$. In one direction the proof is immediate: if the desired hyperplane $H$ exists, then (1) $L \subset H$ and (2) $H$ is disjoint from $Q_-$. Thus, $L$ is disjoint from $Q_-$. To prove the criterion in the other direction, consider a hyperplane strictly separating $L$ and $Q_-$ and then translate it so that it contains all points $v^i$.

In the counterexample above, the affine span $L$ contains line $\{(x,x,x,x): x\in \mathbb{R}\}$ and thus is not disjoint from $Q_-$.