0
$\begingroup$

First some definitions:

A polyhedron $P$ is integral if all its extreme points are integers.

Let $P_I$ be the set of integer points in $P$.

We want to prove that $P$ is integral if and only if $P = conv(P_I)$, where $conv(P_I)$ is the convex hull of $P_I$. i.e. We want to prove that $P$ is integral iff it is equal to its integer hull.

I can prove one of the directions.

(<-)

If $P = conv(P_I)$, then for any extreme point $x$ in $P$, $x$ is in $P_I$. Therefore, $x$ is an integer. Therefore, $P$ is integral since all its extreme points are integral.

I can't prove the other direction though.

I feel like I have to use the fact that any point in a pointed polyhedron can be written as the sum of the convex combination of its extreme points and conic combination of its extreme rays, but am not sure how to.

We also just learned about totally unimodular matrices. But I don't think those can be used here.

I would greatly appreciate some help.

Thanks

$\endgroup$
1
  • $\begingroup$ If the polyhedron $P$ is the convex hull of its extreme points (as you pointed it out) then an integral polyhedron is the convex hull of some (and hence all) integer points contained in $P$. $\endgroup$
    – Levent
    Mar 13, 2018 at 22:39

2 Answers 2

1
$\begingroup$

Assume that $P\neq conv(P_I)$, pick a point in $P \backslash conv(P_I)$ and use that to contradict integrality of $P$.

$\endgroup$
1
$\begingroup$

A counterexample: consider the unbounded polyhedron in $2$ dimensions, defined by, $$P = \left\{ (x,y) \in\mathbb{R^2} \, \colon \, x = \frac{1}{2} \right\}$$ i.e., a line.

$P_I$ is empty (no integral point in $P$), so $\operatorname{conv}(P_I)$ is empty too, therefore $P \neq \operatorname{conv}(P_I)$.

However, according to your definition, $P$ is "integral" because it has no extreme points, so that "all its extreme points are integral" holds (vacuously).

$\endgroup$
1
  • $\begingroup$ Hi, welcome on the MathSE! This site supports Latex, type in $5\cdot 5$ and you will get $5\cdot 5$. $\endgroup$
    – peterh
    May 29, 2018 at 17:50

You must log in to answer this question.

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