1
$\begingroup$

This question is inspired by this one.

Let $P \subset \mathbb R_{+}^n$ be a convex polyhedron whose complement in $\mathbb R_{+}^n$ has finite volume. Let $Int(P) = P \cap \mathbb N^n$. (For motivation: they are the set of exponent vectors of integrally closed, $0$-dimensional monomial ideals in $\mathbb C[x_1,\cdots, x_n]$, but we probably don't need it here).

Question 1: Is there a nice characterization (perhaps using the corner points) of when we can find one hyperplane $H$ that separate $Int(P)$ and its complement in $\mathbb N^n$? Namely, such that $Int(P)$ is precisely the intersection of a closed half-space defined by $H$ and $\mathbb N^n$?

Question 2: More generally, we can look at the least number of hyperplanes needed to cut out $Int(P)$. Is such number studied in the literature? Any good algorithm to find it?

Some examples: for $n=2$, let $P$ be the convex hull of $\{(0,2); (1,1); (3,0)\}$. Then one can find $H : 2x+3y=5$. But for the convex hull of $\{(0,3); (1,1); (3,0)\}$, it is easy to see that one needs $2$ lines.

$\endgroup$

1 Answer 1

3
$\begingroup$

The answer to both your questions is Gomory cuts. From a non-interger extreme point $x$ of $P$ it is easy to find an hyperplane $H$ which separate $x$ from $Int(P)$. Such an hyperplane is called a Gomory cut. It can be shown that by applying this procedure a finite number of time one can describe $Int(P)$ as a finite intersection of halfspaces.

I don't have the exact references around but it seems that this document contains all the details: http://www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Eisenbrand/publications/diss.pdf

$\endgroup$
1

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.