Convex Polyhedra - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T21:07:00Z http://mathoverflow.net/feeds/question/12829 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12829/convex-polyhedra Convex Polyhedra Ali Dino Jumani 2010-01-24T10:12:34Z 2010-09-02T12:09:33Z <p>Exactly what set of mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the combinatorial types) the Convex Polyhedra (starting with simple polyhedron to general).</p> http://mathoverflow.net/questions/12829/convex-polyhedra/12856#12856 Answer by David Speyer for Convex Polyhedra David Speyer 2010-01-24T17:56:39Z 2010-01-24T17:56:39Z <p>If you are looking for software, I recommend <a href="http://www.opt.tu-darmstadt.de/polymake/doku.php" rel="nofollow">POLYMAKE</a>, an open source program which can take a polyhedron specified either by inequalities or vertices and return (among many things) the $f$-vector.</p> http://mathoverflow.net/questions/12829/convex-polyhedra/25029#25029 Answer by Gil Kalai for Convex Polyhedra Gil Kalai 2010-05-17T16:06:18Z 2010-09-02T08:51:28Z <p>Dear Ali,</p> <p>Well there are various tools which are useful to the study of convex polytopes. The following list is perhaps not complete and it certainly should not be frightening. (I dont know very well various of these tools.)</p> <p><strong>1) Basic tools of linear algebra and convexity.</strong></p> <p>The notions of supporting hyperplanes, seperation theorems, Caratheodory, Helly and Radon theorem etc.</p> <p><strong>2) Combinatorics</strong></p> <p>Some of the study of convex polytopes translates geometric questions to purely combinatorial questions. So familiarity with combinatorial notions and techniques is useful. </p> <p><strong>3) Graph theory</strong> </p> <p>As Joe mentioned the study of polytopes in 3 dimensions is closely related to the study of planar graphs. There are few other connections to graph theory so it is useful to be familiar with some graph theory.</p> <p><strong>4) Gale duality</strong></p> <p>The notion of Gale duality is a linear-algebra concept which privides an important technique in the study of convex polytopes.</p> <p><strong>5) Some basic algebraic topology</strong></p> <p>Euler's theorem and its higher dimensional analogues is of central imoprtance and this theorem is closely related to algebraic topology. Another example: there is a result by Perles that the [d/2]-dimensional skeleton of a simplicial polytope determines the entire combinatorial structure. (See <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V1K-45F5SP3-M&amp;_user=626711&amp;_coverDate=09%252F30%252F1984&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1448414877&amp;_rerunOrigin=scholar.google&amp;_acct=C000032999&amp;_version=1&amp;_urlVersion=0&amp;_userid=626711&amp;md5=0d85705b265518a989a50047debcf651&amp;searchtype=a" rel="nofollow">this paper by Jerome Dancis</a>.) The proof is based on an elementary topological argument. Borsuk-Ulam theorem also has various nice applications for the study of polytopes.</p> <p><strong>6) Some functional analysis</strong></p> <p>There is a result by <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.bams/1183538130" rel="nofollow">Figiel, Lindenstrauss, and Milman</a> that a centrally symmetric convex polytope in d dimension satisfies $$log f_0(P) \cdot log f_{d-1}(P) \ge \gamma d$$ for some absolute positive constant $\gamma$. The proof is based on a certain variation of Dvoretzky theorem and I am not aware of an alternative approach.</p> <p><strong>7) Some commutative algebra</strong></p> <p>Several notions and results from commutative algebra plays a role in the study of convex polytopes and related objects. Especially important is the notion of Cohen Macaulay rings and results about these rings.</p> <p><strong>8) Toric varieties</strong></p> <p>Understanding the topology of certain verieties called "toric varieties" turned out to be quite important for the study of convex polytopes.</p> <p>All these items refer to general polytopes. There is also a (related) reach study of polytopes arising in combinatorial optimization. Here is a link to <a href="http://www.cs.uu.nl/research/techreps/repo/CS-1996/1996-27.pdf" rel="nofollow">a paper entitled "Polyhedral combinatorics an annotated bibliography"</a> by Karen Aardal and Robert Weismantel.</p> <h3>references</h3> <p>Here are some relevant references: Ziegler's book: Lectures on Convex Polytopes, and the second edition of Grunbaum's book "Convex polytopes" will give a very nice introduction to topics 1) - 4). The connection with commutative algebra and some comments and references to the connection with toric varieties (topics 7 and 8) can be found in (chapters 2 and 3 of) the second edition of Stanley's book "Combinatorics and Commutative Algebra". Relations with algebraic topology and with functional analysis can be found in various papers. This <a href="http://en.wikipedia.org/wiki/Polyhedral_combinatorics" rel="nofollow">wikipedia article</a> can also be useful.</p>