7
$\begingroup$

Let $\mathcal{P}$ be a polyhedron in $\mathbb{R}^n$. I want to show that the face $\mathcal{F}'$ of a face $\mathcal{F}$ of $\mathcal{P}$ is still a face of $\mathcal{P}$.

There are various proofs of this fact for polytopes. For example in Ziegler's "Lectures on Polytopes" proposition $2.3$. I want to show that the same holds for polyhedra. My idea is that I can take a large enough polytope $\mathcal{V}$ that intersects both $\mathcal{F}$ and $\mathcal{F}'$ in some way. At this point I find that $\mathcal{V} \cap \mathcal{F}'$ is a face of $\mathcal{V} \cap \mathcal{P}$, since the latter is a polytope (by the so-called main theorem in Ziegeler's textbook). From this I would want to conclude that $\mathcal{F}'$ is a face of $\mathcal{P}$. Maybe this is a typical problem: if the proof is pointed out somewhere reference would be fine for me as an answer.

EDIT about definitions:

  1. A polyhedron is the intersection of a finite number of closed halfspaces. This is a convex set.

  2. A polytope is the convex hull of e finite number of points.

  3. A face $\mathcal{F}$ of a convex set $\mathcal{P}$ is any set defined by $\mathcal{F}=\mathcal{P}\cap\{ \mathbf{x}: \mathbf{a}\cdot \mathbf{x} - c = 0\},$ where $\mathbf{a}\cdot \mathbf{x} - c \ge 0$ is an inequality valid for all $\mathbf{x} \in \mathcal{P}$

$\endgroup$
3
  • 2
    $\begingroup$ This sounds like an elementary problem: could you expand your definitions of polytope, polyhedron and face so people without access to Ziegler can understand the exact question? $\endgroup$
    – HTFB
    Sep 23, 2015 at 13:07
  • $\begingroup$ I added definitions. I have always the feeling that problems in convex geometry are trivial, but than again they might be not. I have found myself a proof of this fact. I will post it, since no other proof has appeared. $\endgroup$
    – Kore-N
    Sep 24, 2015 at 18:52
  • $\begingroup$ Thanks. Other definitions of, e.g., polyhedra were certainly available. "Elementary" doesn't mean "trivial", not by a long chalk! $\endgroup$
    – HTFB
    Sep 25, 2015 at 13:48

1 Answer 1

1
$\begingroup$

Let us suppose that $\mathcal{F}$ is defined by $\mathcal{P} \cap \{ \mathbf{x}: f_1(\mathbf{x}) := \mathbf{a}\cdot \mathbf{x} - c = 0 \}$, where $f_1(\mathbf{x}) \geq 0$ is a valid inequality for $\mathcal{P}$. Let us take any face $\mathcal{F}' \subset \mathcal{F},$ given by $\mathcal{F} \cap \{ \mathbf{x}: f_2(\mathbf{x}):=\mathbf{b}\cdot \mathbf{x} - d = 0 \}$, where $f_2(x) \geq 0$ is a valid inequality for $\mathcal{F}$. From the main theorem about polyhedra we know that $\mathcal{P} = conv(\mathbf{Q}) + cone(\mathbf{V})$. Here we view matrices as sets of column vectors. Now we observe that if $f_1(\mathbf{x}) \geq 0$ is valid for $\mathcal{P}$ then $f_1(\mathbf{x}) = \mathbf{a} \cdot \mathbf{q}_i - c \geq 0$ and $\mathbf{a} \cdot \mathbf{v}_j \geq 0$. This last inequality must be valid because if there exists $j$ with $\mathbf{a} \cdot \mathbf{v}_j < 0,$ we could choose $R > 0$ big enough for $f_1(\mathbf{q_i + R \mathbf{v}_j}) < 0$ and this contradicts the fact that $f_1(\mathbf{x})$ is a valid inequality for $\mathcal{P}$. Now we can choose $\lambda$ big enough such that $\lambda f_1(\mathbf{x}) + f_2 (\mathbf{x}) \geq 0$ is valid for all $\mathbf{q}_i \not \in \mathcal{F}$. Furhter more, at the cost of augmenting again $\lambda$, we find $\lambda \mathbf{a} \cdot \mathbf{v}_j + \mathbf{b} \cdot \mathbf{v}_j \geq 0,$ for all $j$ for which $\mathbf{a} \cdot \mathbf{v}_j \neq 0$. Now we observe that $\mathcal{F}$ is a polyhedron aswell. So we find that $\mathcal{F} = conv(\mathbf{R}) + cone(\mathbf{W})$. if, for some $j,$ $\mathbf{a} \cdot \mathbf{v}_j = 0,$ we find that $\mathbf{v}_j \in cone(W)$. From this follows (because $f_2(\mathbf{x})$ is a valid inequality for $\mathcal{F}$) that $\mathbf{b} \cdot \mathbf{v}_j \geq 0$ and hence that $\lambda \mathbf{a} \cdot \mathbf{v}_j + \mathbf{b} \cdot \mathbf{v}_j \geq 0$ is immediatley respected (because it is respected by both terms). Now we can conclude the proof. Let us take $\mathbf{x} \in \mathcal{P}$. We know that $\mathbf{x} = \sum_i \mu_i \mathbf{q}_i + \sum_j \nu_j \mathbf{v}_j,$ hence $$\lambda f_1(\mathbf{x}) + f_2 (\mathbf{x}) = $$ $$ = \sum_i \mu_i \left( \lambda \mathbf{a} \cdot \mathbf{q}_i + \mathbf{b} \cdot \mathbf{q}_i- \lambda c - d \right) + \sum_j \nu_j \left( \lambda \mathbf{a} \cdot \mathbf{v}_j + \mathbf{b} \mathbf{v}_j\right). $$ From what we have seen we can conclude that the terms in the right sum are positive, and so also those in the left sum. From this follows that $\lambda f_1(\mathbf{x}) + f_2 (\mathbf{x}) \geq 0$ is an inequality valid for the whole polyhedron $\mathcal{P}$.

$\endgroup$

You must log in to answer this question.

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