Summary
For an arbitrary triangulated (d-1)-manifold without boundaryC withf 0 vertices andf 1 edges, define\(\gamma (C) = f_1 - df_0 + \left( {\begin{array}{*{20}c} {d + 1} \\ 2 \\ \end{array} } \right)\). Barnette proved that γ(C)≧0. We use the rigidity theory of frameworks and, in particular, results related to Cauchy's rigidity theorem for polytopes, to give another proof for this result. We prove that ford≧4, if γ(C)=0 thenC is a triangulated sphere and is isomorphic to the boundary complex of a stacked polytope. Other results: (a) We prove a lower bound, conjectured by Björner, for the number ofk-faces of a triangulated (d-1)-manifold with specified numbers of interior vertices and boundary vertices. (b) IfC is a simply connected triangulatedd-manifold,d≧4, and γ(lk(v, C))=0 for every vertexv ofC, then γ(C)=0. (lk(v,C) is the link ofv inC.) (c) LetC be a triangulatedd-manifold,d≧3. Then Ske11(Δ d+2) can be embedded in skel1 (C) iff γ(C)>0. (Δ d is thed-dimensional simplex.) (d) IfP is a 2-simpliciald-polytope then\(f_1 (P) \geqq df_0 (P) - \left( {\begin{array}{*{20}c} {d + 1} \\ 2 \\ \end{array} } \right)\). Related problems concerning pseudomanifolds, manifolds with boundary and polyhedral manifolds are discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alexandrov, A.D.: Convex polyhedra. Moscow, 1950 (Russian); German transl., Konvexe Polyeder. Berlin: Akademie-Verlag 1958
Altshuler, A.: 3-pseudomanifolds with preassigned links. Trans. Am. Math. Soc.241, 213–237 (1978)
Altshuler, A., Perles, M.A.: Quotient polytopes of cyclic polytopes, Part I: Structure and characterization. Isr. J. Math.36, 97–125 (1980)
Altshuler, A., Steinberg, L.: Neighborly 4-polytopes with 9 vertices. J. Comb. Theory, Ser. A15, 270–287 (1973)
Asimow, L., Roth, B.: The rigidity of graphs I. Trans. Am. Math. Soc.245, 279–289 (1978)
Asimow, L., Roth, B.: The rigidity of graphs II. J. Math. Anal. Appl.68, 171–190 (1979)
Balinski, M.: On the graph structure of convex polyhedra inn-space. Pac. J. Math.11, 431–434 (1961)
Banchoff, T.F.: Tightly embedded 2-dimensional polyhedral manifolds. Am. J. Math.87, 462–472 (1975)
Barnette, D.: The minimum number of vertices of a simple polytope. Isr. J. Math.10, 121–125 (1971)
Barnette, D.: A proof of the lower bound conjecture for convex polytopes. Pac. J. Math.46, 349–354 (1973)
Barnette, D.: Graph theorems for manifolds. Isr. J. Math.16, 62–72 (1973)
Barnette, D.: Generalized combinatorial cells and facet splitting. Pac. J. Math.46, 349–354 (1973)
Barnette, D.: Polyhedral maps on 2-manifolds. In: Convexity and related combinatorial geometry. Kay, D.C., Breen, M. (eds.), pp. 7–19. New York: Marcel Dekker Inc. 1982
Barnette, D., Grünbaum, B.: On Steinitz's theorem concerning convex polytopes and on some properties of planar graphs. The many facets of graph theory. Lecture Notes in Math. vol. 110, pp. 27–40. Berlin-Heidelberg-New York: Springer 1969
Billera, L.J., Lee, C.W.: A proof of the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes. J. Comb. Theory, Ser. A31, 237–255 (1981)
Billera, L.J., Lee, C.W.: The number of faces of polytopes pairs and unbounded polyhedra. Eur. J. Comb.2, 307–322 (1981)
Björner, A.: The minimum number of faces of a simple polyhedron. Eur. J. Comb.1, 27–31 (1980)
Björner, A., Kalai, G.: An extended Euler-Poincaré formula. (Preprint)
Beineke, L.W., Pippert, R.E.: Properties and characterizations ofk-trees. Mathematica18, 141–151 (1971)
Bricard, R.: Mémoire sur la théorie de l'octa dre articulé. J. Math. Pures Appl., IX. Ser. 3, 113–138 (1897)
Brönsted, A.: An introduction to convex polytopes. Graduate text in Mathematics, vol. 90. Berlin-Heidelberg-New York: Springer 1983
Cauchy, L.: Sur les polygones et les polyèdres, Second Memoire, I. Ecole Polytechnique9 (1813), 87 (=Oeuvres complètes d'Augustin Cauchy, 2nd sér., Tome 1, 1905, pp. 26–38)
Cooper, D., Thurston, W.P.: Triangulating 3-manifolds using 5 vertex link types. Preprint
Connelly, R.: A counterexample to the rigidity conjecture for polyhedra. Publ. Math., Inst. Hautes Étud. Sci.47, 333–338 (1978)
Connelly, R.: Conjectures and open problems in rigidity. Proc. International Congress of Math., Helsinki, 1978
Connelly, R.: The rigidity of certain cabled frameworks and the second order rigidity of arbitrarily triangulated convex surfaces. Adv. Math.37, 272–299 (1980)
Dirac, G.A.: Homomorphism theorems for graphs. Math. Ann.153, 69–80 (1964)
Gluck, H.: Almost all simply connected closed surfaces are rigid. In: Geometric topology. Lecture Notes in Math., vol. 438, pp. 225–239. Berlin-Heidelberg-New York: Springer 1975
Goresky, M., MacPherson, R.: Intersection homology theory. Topology 19, 135–162 (1980)
Graver, J.: A combinatorial approach to infinitesimal rigidity. (Preprint)
Grünbaum, B.: Convex polytopes. New York: Wiley Interscience 1967
Grünbaum, B.: Polytopes, graphs and complexes. Bull. Am. Math. Soc.76, 1131–1201 (1970)
Grünbaum, B., Shephard, G.C.: Lecture on lost mathematics. Preprint Syracuse University, 1978
Harary, F., Palmer, E.M.: On acyclic simplicial complexes. Mathematika15, 115–122 (1968)
Kalai, G.: Combinatorial problems in convexity and the combinatorics of simplicial complexes. Ph.D. Thesis, Jerusalem, 1983
Kalai, G.: Weakly saturated graphs are rigid. Ann. Discrete Math.20, 189–190 (1984)
Kalai, G.: Heperconnectivity of graphs. Graphs Comb.1, 65–80 (1985)
Kalai, G.: Rigidity and the lower bound theorem II: Elementary polytopes. (Preprint)
Kalai, G.: Rigidity and the lower bound theorem III: Triangulated manifolds with “few edges”. (Preprint)
Klee, V.: A comparison of primal and dual method of linear programming Num. Math.9, 227–235 (1966)
Klee, V.: Polytope pairs and their relations to linear programming. Acta Math.113, 1–25 (1974)
Klee, V.: Ad-pseudomanifold withf 0 vertices has at least df 0-(d-1)(d+2)d-simplices. Houston J. Math.1, 81–86 (1975)
Kühnel, W., Banchoff, T.F.: The 9 vertex complex projective plane. The Math. Intell.5, issue 3, 11–22 (1983)
Kühnel, W., Lassmann, G.: The unique 3-neighborly 4-manifold with few vertices. J. Comb. Theory, Ser. A35, 173–184 (1983)
Kuiper, N.H.: Tight embeddings and maps. Submanifolds of geometric type tree inE N, The Chern Symposium. Singer, I.M. (ed.), pp. 97–145, Berlin Heidelberg New York: Springer 1980
MacPherson, R.: Intersection homology. Herman Weyl lectures. (in press) (1987)
McMullen, P.: The numbers of faces of simplicial polytopes. Isr. J. Math.9, 559–570 (1971)
McMullen, P., Shephard, G.C.: Convex polytopes and the upper bound conjecture. London Math. Soc. Lecture Notes Series, vol. 3. London/New York: Cambridge Univ. Press 1971
McMullen, P., Walkup, D.W.: A generalized lower bound conjecture for simplicial polytopes. Mathematika18, 264–273 (1971)
Ringel, G.: Map color theorem. Berlin-Heidelberg-New York: Springer 1974
Roth, B.: Rigid and flexible frameworks. Am. Math. Mon.88, 6–21 (1981)
Schenzel, P.: On the number of faces of simplicial complexes and the purity of Frobenius. Math. Z.178, 125–142 (1981)
Spanier, E.H.: Algebraic topology. New York: McGraw Hill 1966
Stanley, R.: The upper bound conjecture and Cohen-Macaulay rings. Stud. Appl. Math.54, 135–142 (1975)
Stanley, R.: The number of faces of simplicial convex polytopes. Adv. Math.35, 236–238 (1980)
Stanley, R.: The number of faces of simplicial polytopes and spheres. Discrete geometry and convexity, Goodman, J.E., Lutwak, E., Malkevitch, J., Pollack, R. (eds.), pp. 212–223. New York: Ann NY Acad Sci 1985
Stanley, R.: Interactions between commutative algebra and combinatorics. Boston: Birkhäuser 1983
Stanley, R.: Enumerative combinatorics. Vol. I, Wadsworth, Monterey, 1986
Stanley, R.: Generalizedh-vectors, intersection cohomology of toric varieties, and related results. Proc. Japan-USA workshop on commutative algebra and combinatorics (to appear)
Stoker, J.J.: Geometric problems concerning polyhedra in the large. Commun. Pure Appl. Math.21, 119–168 (1968)
Steinitz, E., Rademacher, H.: Vorlesungen über die Theorie der Polyeder. Berlin-Göttingen: Springer 1934
Tay, T.S., Whiteley, W.: Generating all isostatic frameworks. Struct. Topology11, 21–70 (1985)
Walkup, D.: The lower bound conjecture for 3-and 4-manifolds. Acta Math.125, 75–107 (1970)
Welsh, D.: Matroid theory. London: Academic Press 1976
Whiteley, W.: Cones, infinity and 1-story buildings. Struct. Topology8, 53–70 (1983)
Whiteley, W.: Infinitesimally rigid polyhedra I. Statics of Frameworks. Trans. Am. Math. Soc.285, 431–465 (1984)
Gromov, M.: Partial differential relations. Berlin Heidelberg New York: Springer 1986
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kalai, G. Rigidity and the lower bound theorem 1. Invent Math 88, 125–151 (1987). https://doi.org/10.1007/BF01405094
Issue Date:
DOI: https://doi.org/10.1007/BF01405094