Google Answers Logo
View Question
Q: Integral Boundary Points of Convex Polyhedra ( Answered,   0 Comments )
Subject: Integral Boundary Points of Convex Polyhedra
Category: Reference, Education and News > Education
Asked by: truman-ga
List Price: $8.00
Posted: 05 Nov 2002 08:50 PST
Expires: 05 Dec 2002 08:50 PST
Question ID: 99387
Is there a proof for HOFFMAN and KRUSKAL's theorems dealing with
old manual typewriter back in 1956?  In the last 46 years someone must
have rewritten these proofs using TeX and eliminating all the obsolute
Subject: Re: Integral Boundary Points of Convex Polyhedra
Answered By: rbnn-ga on 05 Nov 2002 09:34 PST
Thank you for the question. 

I know how you feel here - for my dissertation I sometimes had to read
old articles and the typesetting was definitely off-putting. Sometimes
there would be 400-page monographs on some geometrical concept with
maybe one diagram, all on a typewriter.

Oddly enough, if you look at some of my math answers on here, (e.g.
clicking "rbnn") you will see that in some ways we have come full
circle - trying to type matrices and nested subscripts into the text
form on google answers doesn't yield very legible results either!

Fortunately, I have found a nicely formatted paper that proves the
Hoffman/Kruskal theorem on integral points of convex polyhedra; in
fact it proves a generalization of it. The paper is:

"Integral Solutions of Linear Complementarity Problems", by William
Cunningham and James Geelen. Mathematics of Operations Research, 23
(1998), 61-68.

This paper is in online-postscript format here: . It

If you are unable to read postscript on your computer and unable to
get to a copy of Mathematics of Operations Research, you will have to
download a postscript viewer, which is not necessarily trivial.
Instead you may want to try and print out the paper at any postscript
printer. Let me know if you have trouble viewing the postscript,
however, and I can point you to some sites to download viewers from (I
will need to know your platform).

In any case, Theorem 5 is the theorem you want (on page 3).

As always, if you have any questions, please use the "Request
Clarification" button before rating this answer.

Search Strategy
Various permutations on Hoffman, Kruskal, integral, convex, boundary
points yielded various hits, and I read through the links. To get the
citation I examined the URL of the hit on the postscript: , then went to to get the list of publications
of the author, which contained citation information for the online

Request for Answer Clarification by truman-ga on 05 Nov 2002 10:20 PST
Wow, thanks a bunch.  I hope it's not OVERLY general what's proven in
the 1998 paper.  I haven't been able to view it yet.  I'm running OS
10.2.1, but I think a number of the Macs and PCs at the U are hooked
up to Postscipt printers.  Any advice about both viewing the document
here at home and printing it out (from either a Mac or a PC) would be
very helpful.  (It is safe to assume no experience on my part with:
PCs and .ps files)



Clarification of Answer by rbnn-ga on 05 Nov 2002 11:12 PST
Although there are various postscript viewers for PCs out there, I
personally find them a bit hard to install (I use ghostview, which is
excellent, but again, I would not necessarily recommend it if you are
not familiar with PCs too much).

Fortunately, I was able to find a pdf version of the paper here:

Most, or at least some, computers in your department should have PDF
available on them already, so that if you are lucky, you can view the
paper just by going to that URL.

If you are unlucky though, you will have to install a PDF viewer. A
PDF viewer can be found here: . It tends to be
quite easy to install, and it's quite a useful thing to have.

Regarding your question about generality: No, I do not think you will
find that the theorem statement is overly general. (It's not one of
those category-theoretic statements where you don't quite know what is
being said).

To find this PDF paper, I re-searched on the title and authors of the
original paper, and "pdf" .

By the way, pdf, especially for TeX converted stuff, sometimes does
not look as good as .ps on the screen; it should print OK though.

Clarification of Answer by rbnn-ga on 06 Nov 2002 11:50 PST
Please advise whether the Cunningham paper is clear enough. If not, I
may be able to find a clearer paper or prove the theorem myself. (I
may not be though)
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy