4
$\begingroup$

Given a point set $E=\{\alpha_j\}_{j=1}^m\subset \mathbb{N}^{n}$ ($1\leq m< \infty$).

Define the polyhedron $\mathcal{N}(E)$ to be the convex hull of the set \begin{equation*} \bigcup_{j=1}^m \left(\alpha_j + \mathbb{R}^n_{+}\right), \end{equation*} where $\mathbb{R}^n_+=\{x\in \mathbb{R}^n:x_j\geq 0, \, 1 \leq j\leq n\}$. If there are $n$ facet (the face has dimension $n-1$) $ F_1,\,F_2,\,\cdots,\,F_n $ on $\mathcal{N}(E)$ satisfying $$ \bigcap_{j=1}^n F_j\neq \emptyset. $$

How to prove that for $n\geq 3$, if the intersection of $n$ facets is nonempty, then it must be a single point?

For a general convex polytopes, this claim is not feasible. For a 4-dimensional example, see Show that each edge of the cyclic polytope $C_4(6)$ is contained in either three or four facets, and either three or four 2-faces.

I think the concepts of redundant face maybe helpful. And I can only prove the case $n=3$, in the following answer (I post it to avoid a length question) I show if three facets intersect, then they must coincide with a single point.

$\endgroup$
9
  • $\begingroup$ Is it true that $\mathcal{N}(E) = \mathbb{R}^n_{+} + \Gamma(E)$ where $\Gamma(E)$ is convex hull of $E?$ $\endgroup$
    – dsh
    Oct 8, 2023 at 11:06
  • $\begingroup$ yeah and we can assume that $E$ is finite. $\endgroup$
    – cbi
    Oct 8, 2023 at 11:07
  • $\begingroup$ Then, I guess, you can find all facets of $\mathcal{N}(E)$ from facets of $\Gamma(E)$ and $\mathbb{R}^n_{+} $ and maybe apply counterexample you provided. $\endgroup$
    – dsh
    Oct 8, 2023 at 11:09
  • $\begingroup$ It is different. That counterexample is a bounded closed polytope. $\endgroup$
    – cbi
    Oct 8, 2023 at 11:12
  • $\begingroup$ Thanks, I thought facets $\mathcal{N}(E)$ is union of some subset of facets of $\Gamma(E)$ (which is also bounded polytope) and of some subset of facets of $\mathbb{R}^n_{+}.$ $\endgroup$
    – dsh
    Oct 8, 2023 at 11:16

1 Answer 1

1
$\begingroup$

This answer is only for the case $n=3$.

Since the affine hull of a facet is a 2-dimensional plane, there exist $w_j\in \mathbb{R}^n$ ($n=3$) such that the equation of these (support) plane is $w_{j}\cdot x=1$, $j=1,2,3$, with $$\mathcal{N}(E)\subset\bigcap_{j=1}^3\{x:w_j\cdot x\geq 1\}.$$ In our framework, one can easily show that $w_j\in \mathbb{R}^{n}_+$ (in higher dimension this fact is also true). Then our claim is equivalent to the linear independence of $\{w_1,w_2,w_3\}$. If they are not linear independent, we show there is a contradiction. Firstly, we can assume that there exist $\lambda_j$, $j=1,2$ such that $$ w_3=\lambda_1 w_1+\lambda_2 w_2. $$ Let $\beta\in \cap_{j=1}^3 F_j$ is a point on $\mathcal{N}(E)$. Then $\beta\cdot w_j=1$. Thus $\lambda_1+\lambda_2=1$. Without loss of generality, we can always assume that $\lambda_1,\lambda_2$ are non-negative. (Indeed, if there is a negative, say $\lambda_1$, then we rewrite the relation of $w_j$ as $$ w_2=\frac{1}{\lambda_2}(w_3-\lambda_1 w_1)=:\mu_1 w_3+\mu_2 w_1 $$

with $\mu_j$ non-negative.)

Now we assume $\lambda_j$ are non-negative, however, since $w_3$ is the normal vector of the (proper) facet $F_3$, we can choose $\alpha\in F_3$ and $\alpha$ not belong to $F_1,F_2$, then $w_j\cdot\alpha>1$ for $j=1,2$. And $$ 1=w_3\cdot\alpha=\lambda_1 w_1\cdot \alpha+\lambda_2 w_2\cdot \alpha>\lambda_1+\lambda_2=1. $$ A contradiction.

In higher dimensions, I can also use a similar arguments but I stuck.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .