Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:) - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:10:45Z http://mathoverflow.net/feeds/question/10039 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10039/characterizing-faces-of-3-dimensional-polyhedra-related-to-victor-eberhards-th Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:) Ali Dino Jumani 2009-12-29T16:00:12Z 2011-02-08T18:21:51Z <p><strong>Originally asked by <a href="http://mathoverflow.net/users/2866/ali-dino-jumani" rel="nofollow">Ali Dino Jumani</a>; EXTENSIVELY EDITED by David Speyer</strong>. The previous version was a bit confused, but Steven Sivek and Graham, in the comments, figured out what was going on.</p> <hr> <p>G. C. Shephard, in his paper "<a href="http://www.jstor.org/pss/3612678" rel="nofollow">Twenty Problems on Convex Polyhedra: Part I</a>", associates to a three dimensional polyhedron the sequence $(p_3, p_4, p_5, p_6, \ldots)$, with $p_k$ being the number of facets that are $k$-gons. He poses the problem of characterizing all sequences of integers which arise in this way.</p> <p>Are there any developments and references on this problem?</p> <p>the original question as appeared in Shephard's paper "Given any finite sequence (f3, f4, ...., fm) of non-negative integers, find a necessary and sufficient condition for it to be assocoated with some convex polyhedron". Following Grunbaum's Convex Polytope 2e notation, section 13.3 under Eberhard's Therorem heading, f3 is triangle renamed as p3 and f4 as p4 is square and fm as pk is n-gon. A convex polyhedron containing these faces satisfies the Eberhard's criterion. Revisions and corrections are highly appreciated, Thanks.</p> http://mathoverflow.net/questions/10039/characterizing-faces-of-3-dimensional-polyhedra-related-to-victor-eberhards-th/24340#24340 Answer by Gil Kalai for Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:) Gil Kalai 2010-05-12T06:53:25Z 2011-02-08T18:21:51Z <h2>Eberhard Theorem</h2> <p>Consider a simple 3-polytope P, (so every vertex has 3 neighbors). If $p_k$ is the number of faces of P which are k-gonal, Euler's theorem implies that </p> <p>$$(*) ~~\sum_{k \ge 3} (6-k)p_k=12.$$ </p> <p>Note that 6-gonal faces do not contribute to the LHS. </p> <p>One way to think about it is that polygonal faces with 7 and more sides contribute "negative curvature", small faces namely triangles quadrangles and pentagons, contribute positive "curvature" and hexagons are "flat".</p> <p>Eberhard's theorem asserts that if you have a sequence of numbers $p_k, k \ne 6$ such that $\sum_{k \ge 3} (6-k)p_k=12$ then you can find a simple 3-polytope with $p_k$ k-gonal faces. (But you have no control on $p_6$). </p> <h2>Extensions of Eberhard theorem</h2> <p>There are various results extending Eberhard's theorem in various directions. Chapter 13 in Grunbaum's book "<a href="http://books.google.co.il/books?id=ISHO86XJ1CsC&amp;printsec=frontcover&amp;dq=grunbaum%27s+convex+polytopes&amp;source=bl&amp;ots=S7T41O6hvF&amp;sig=wRkbvA0TtPVeRuiRFHo6FjVQv1I&amp;hl=iw&amp;ei=QkrqS7LzCaOiOLaTsPMK&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=1&amp;ved=0CAgQ6AEwAA#v=onepage&amp;q=grunbaum%27s%2520convex%2520polytopes&amp;f=false" rel="nofollow">Convex Polytopes</a>" and especially the supplemantary material at the end of the chapter in the new 2nd edition is a good source. Another general source is <a href="http://www.ma.huji.ac.il/~kalai/ch19.pdf" rel="nofollow">my chapter</a> from the "Handbook of Discrete and Computational geometry" on garphs and skeleta of polytops. </p> <p>A relatively recent paper on the subject is by Stanislav Jendrol "<a href="http://pdf.dml.cz/bitstream/handle/10338.dmlcz/136327/MathSlov_33-1983-2_7.pdf" rel="nofollow">On the face vectors of trivalent convex polyhedra</a>". Another paper by Jendrol which deals with general 3-polytopes from the same year is "On face vectors and vertex vectors of convex polyhedra" Discrete Math 118 (1993)119-144. There are analogs of Eberhard theorem for 4-regular planar graphs, for toroidal graphs and in other directions.</p> <p>A far as I know, there is no good answer known for the question posed by Shephard of characterizing all sequences $(p_3,p_4,\dots)$, and no such characterization is known even for the simple case. </p> <h2>High dimensions</h2> <p>In higher dimensions and even in four dimensions there are various different ways to extend these problems, these problems become very difficult and very little is known. </p> <h3>2-dimensional faces</h3> <p>You can ask again about the numbers of k-gonal 2-dimensional faces. While the formula above implies that in dimension 3 and more $p_3+p_4+p_5>0$ it is known that in dimensions 5 and more $p_3+p_4>0$. </p> <h3>Types of facets</h3> <p>Perhaps an even more natural extension is to consider the type of facets a given d-simensional polytope have. You can ask for a simple 4 polytope (a 4-polytope whose graph is 4-regular) what are the number of facets $p_Q$ isomorphic to a given 3-polytope Q. This gives you a vector indexed by combinatorial types of simple 3-polytopes, but I am not aware of any Eberhard type theorem and I do not know even which 3-polytopes should be considered as the analogs of the hexagons in the above formula. Dually stated and extented to triangulations of 3-spheres the question is to associate to a triangulated 3-simensional sphere (or just simplicial 3-polytope) the list of links of vertices (with multiplicities) it has. A related MO question is <a href="http://mathoverflow.net/questions/10503/simplicial-and-cubical-decompositions-of-low-valence" rel="nofollow">this one</a>.</p> <h3>Type of facets according to their number of their facets</h3> <p>Rather than classifying the facets according to their full combinatorial type we can classify them according to their own number of facets. Here, for dimension greater than 4 there is no analog for (*). It is possible that under wide circumstences the numbers of facets with k facets can be prescribed, but I am not aware of results in this direction.</p> <h3>Type of facets according to their f-vectors</h3> <p>Precscribing the entire vector of face numbers of the individual facets, may well be the most interesting extension from 3 to higher dimensions.</p> <p>There are some reasons to jump from dimension 3 directly to dimension 5. The nature of the problem is different in even and odd dimensions. Let me try to elaborate on that.</p> <p>Suppose you have a simple 5-polytope P and denote by $p_{a,b}$ the number of facets F so that $f_3(F)=a$ and $f_2(F)=b$. (For a polytope or some other cell complex X, $f_i(X)$ denotes the number of $i$-dimensional faces of $X$.) Dually, we can consider a triangulation $K$ of the 4-simensional sphere $S^4$ and let $p_{a,b}$ be the number of vertices whose <strong>link</strong> has $a$ vertices and $b$ edges.</p> <p>Now the Dehn-Sommervill relations imply that </p> <p>$$(**) \sum p_{a,b} (b-6a+30) = 60 .$$</p> <p>So now we can consider 4 dimensional facets as "small" if b-6a+30 is negative, as "large" if $b-6a+30$ is positive, and as neutral if $b=6a-30$. An analog of Eberhard theorem will say that you can prescribe the types of small and large facets and realize the polytope (or the triangulated sphere) by allowing to add many "neutral" facets. </p> <h3>Facets and non facets</h3> <p>A related question that was studied in several papers is: for which d-polytopes P there is a (d+1) polytopes Q such that all faces of Q are isomorphic to P. Such polytopes P are called "facets". An intriguing open problem is if the icosahedron is a facet. <strong>Update:</strong> Karim Adiprasito and Guenter Ziegler have just shown that the answer is no. (For all other regular polytopes P it is known that P is a facet only if there is a regular (d+1)-polytope all whose facets are isomorphic to P.</p> <h3>Cubical complexes</h3> <p>Simple polytopes are dual to simplicial polytopes, and there is some special interest in these problems for cubical complexes (or their duals). Indeed there is an analog of Eberhard's theorem for 3-polytopes with all vertex degrees 4. There should be an analog for (**) and this may be related to interesting questions about curvature of cubical complexes. </p> <h3>Stacked polytopes</h3> <p>A stack polytope is a polytope obtained by gluing simplices along facets. (They are related to Appolonian circle packing.) Stacked polytopes are simplicial. I do not know if there is an analog of Eberhard's theorem when we consider only simple 3-polytope which are dual to stacked 3-polytopes. This is also interesting for other dimensions. All facets of stacked 5 polytopes are stacked and their number of edges is four times the number of vertices minus 10. Therefore, for a dual-to-stacked 5 polytope formula (**) reduces to $$\sum p_{a,b}(10-a)=30.$$ (Here, $b=4a-10$ so we can omit the subscript $b$.) So in this case, the distinction is between facets with $a&lt;10$, those with $a>10$ and those with $a=10$. Again we can look for some analogs for Eberhard's theorem, which in this case, might be easier.</p>