Rigidity and the lower bound theorem 1
Tóm tắt
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.
Tài liệu tham khảo
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