4
$\begingroup$

Suppose you have an equidimensional $n$-dimensional simplicial complex $\Delta \subseteq \mathbb Q^n$; i.e., $\Delta$ is the union of finitely many $n$-simplices that intersect only along proper faces. (I really do mean to use the same $n$.) By an $n$-simplex, I mean the convex hull of $n+1$ affinely independent points in $\mathbb Q^n$. In this setup, a boundary facet is any $(n-1)$-simplex that is a facet of exactly one of the $n$-simplices that make up $\Delta$. Each boundary facet lies on a unique hyperplane, and the $n$-simplex to which it belongs lies entirely on one halfspace.

I'm having trouble proving the geometrically reasonable (maybe even obvious!) claim that the intersection of these halfspaces is contained in $\Delta$.

Question: Is it true that the intersection of these halfspaces is contained in $\Delta$? If so, can you point me to a reference? I couldn't find a proof of this in Ziegler's Lectures on Polytopes.

One thing that is throwing me off is that the claim isn't true if $\Delta$ isn't of full dimension. For instance, consider the situation in this picture: counterexample picture. Here the intersection of the boundary facets isn't even bounded.

I'm not a discrete mathematician, so thanks for bearing with me.

$\endgroup$
3
  • $\begingroup$ For a complex $\Delta$ let $\mathcal{H}(\Delta)$ be the family of the halfspaces as defined in the question. Consider a halfspace $H\in \Delta$. Then $\{H'\cap H : H'\in\mathcal{H}(\Delta)\}$ contains $\mathcal{H}(\Delta\cap H)$. $\endgroup$
    – Boris Bukh
    Jul 24, 2011 at 18:03
  • $\begingroup$ @Boris: can you expand on $H \in \Delta$? I don't quite get what you mean. $\endgroup$ Jul 24, 2011 at 19:41
  • $\begingroup$ Intersection of a boundary halfspace with the complex only reduces the set of halfspaces determined by the complex (of course, you might need to retriangulate any simplex that is intersected by hyperplane). Thus if we start taking the intersection of one halfspace at a time, we will end up with a subset of $\Delta$. $\endgroup$
    – Boris Bukh
    Jul 24, 2011 at 20:35

1 Answer 1

3
$\begingroup$

I'll risk a proof, assuming that by "the intersection of these halfspaces" you mean "the intersection of all the halfspaces of all the boundary facets."

Let point $x$ be in this intersection, and assume for the purposes of contradiction that $x$ is exterior to $\Delta$. Form an arrangement of hyperplanes $\cal{A}$ by all the hyperplanes determined by $x$ and all the ridges ($(n{-}2)$-dimensional facets, e.g., edges of tetrahedra) of $\Delta$. Find some point $z$ that is inside $\Delta$ but does not lie on $\cal A$. Such a $z$ exists because $\Delta$ cannot lie entirely within a hyperplane of $\cal{A}$. Now aim a ray $r$ from $x$ to $z$, and let $y$ be the first point on this ray that coincides with a point of $\Delta$. This $y$ must lie in the relative interior of some facet of some simplex $\sigma$ of $\Delta$, for if instead it lay on a ridge, then $y$, and therefore $z$, would lie on $\cal{A}$. The halfspace of this facet must be oriented so that it includes $\sigma$ and excludes $x$. So $x$ is afterall not inside the intersection of all the boundary halfspaces.

Of course it is possible that the intersection of the halfspaces is the empty set, but I assume you would treat that as contained in $\Delta$.

$\endgroup$
1
  • $\begingroup$ That is what I meant. Thanks! You've saved me many future headaches from trying to prove this with epsilon balls. :) $\endgroup$ Jul 24, 2011 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.