A proof of the lower bound conjecture for convex polytopes
David W. Barnette · Pacific Journal of Mathematics · 1973
A d polytope is defined to be a cZ-dimensional set that is the convex hull of a finite number of points.A d-polytope is said to be simplicial if each facet is a simplex.Dually, a d-polytope is simple if each vertex has valence d.It has been conjectured that the following inequalities hold for any simplicial d-polytope p.(2) f d -1 ^(d-l)fo-(d Here, /* is the number of ^-dimensional faces of P.This conjecture is known as the Lower Bound Conjecture, hereafter to be abbreviated LBC.The LBC has been known to be true for d ^ 3 for quite some time.In 1969, D. Walkup proved the LBC for d = 4 and 5.In 1970, the author proved (2) for all simplicial d-polytopes.In this paper (1) is proved for all simplicial d-polytopes.1* Definitions and preliminary results* If v is a vertex of a d-polytope P then the antistar of v in P, denoted ast(v, P), is the set of all ά-faces of P that miss v, 0 <Ξ k ^ d -1.If H is a hyperplane that separates v from the other vertices of P, then P Π H is called the vertex figure of v.If P is simplicial, then the vertex figure of v will be a simplicial (d -1)-polytope and each &-face of the vertex figure is the intersection of H with a (k + l)-face of P.Let X be a collection of facets of a simple d-polytope P. We say that X is a strong set of facets provided that given any two facets ^7 and ^n in X there is a sequence ^7, , ^ of facets in X such that ^ Π ^7+i is a subfacet of P for all 1 ^ £ <^ w -1.A vertex v of X is said to be an exterior vertex of X provided that v belongs to exactly one facet in X.The graph of a polytope is the graph formed by its vertices and edges.A graph is said to be n-connected provided that between any two vertices there are n independent paths (that is, paths that meet only at their endpoints).A theorem of Balinski [1] states that the graph of a d-polytope is ^-connected.The following also follows from Balinski's work.LEMMA 1.The set of vertices of any facet of a d-polytope does not separate the graph of the polytope.