Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Bipartite rigidity


Authors: Gil Kalai, Eran Nevo and Isabella Novik
Journal: Trans. Amer. Math. Soc. 368 (2016), 5515-5545
MSC (2010): Primary 05C10, 13F55, 52C25, 05E45; Secondary 57Q35
DOI: https://doi.org/10.1090/tran/6512
Published electronically: November 16, 2015
MathSciNet review: 3458389
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We develop a bipartite rigidity theory for bipartite graphs parallel to the classical rigidity theory for general graphs, and define for two positive integers $ k,l$ the notions of $ (k,l)$-rigid and $ (k,l)$-stress free bipartite graphs. This theory coincides with the study of Babson-Novik's balanced shifting restricted to graphs. We establish bipartite analogs of the cone, contraction, deletion, and gluing lemmas, and apply these results to derive a bipartite analog of the rigidity criterion for planar graphs. Our result asserts that for a planar bipartite graph $ G$ its balanced shifting, $ G^b$, does not contain $ K_{3,3}$; equivalently, planar bipartite graphs are generically $ (2,2)$-stress free. We also discuss potential applications of this theory to Jockusch's cubical lower bound conjecture and to upper bound conjectures for embedded simplicial complexes.


References [Enhancements On Off] (What's this?)

  • [1] L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279-289. MR 511410 (80i:57004a), https://doi.org/10.2307/1998867
  • [2] L. Asimow and B. Roth, The rigidity of graphs. II, J. Math. Anal. Appl. 68 (1979), no. 1, 171-190. MR 531431 (80i:57004b), https://doi.org/10.1016/0022-247X(79)90108-2
  • [3] Eric K. Babson and Clara S. Chan, Counting faces of cubical spheres modulo two, Combinatorics and applications (Tianjin, 1996), Discrete Math. 212 (2000), no. 3, 169-183. MR 1748648 (2000m:05011), https://doi.org/10.1016/S0012-365X(99)00285-X
  • [4] Eric Babson and Isabella Novik, Face numbers and nongeneric initial ideals, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 25, 23 pp. (electronic). MR 2195431 (2007c:05202)
  • [5] Eric Babson, Isabella Novik, and Rekha Thomas, Reverse lexicographic and lexicographic shifting, J. Algebraic Combin. 23 (2006), no. 2, 107-123. MR 2223682 (2007a:13026), https://doi.org/10.1007/s10801-006-6919-3
  • [6] G. Blind and R. Blind, Gaps in the numbers of vertices of cubical polytopes. I, Discrete Comput. Geom. 11 (1994), no. 3, 351-356. MR 1271640 (95b:52014), https://doi.org/10.1007/BF02574013
  • [7] J. L. Bryant, Approximating embeddings of polyhedra in codimension three, Trans. Amer. Math. Soc. 170 (1972), 85-95. MR 0307245 (46 #6365)
  • [8] M. Chudnovsky, G. Kalai, E. Nevo, I. Novik, and P. Seymour, Bipartite minors, J. Combin. Theory Ser. B, to appear, DOI 10.1016/j.jctb.2015.08.001.
  • [9] Robert Connelly, A counterexample to the rigidity conjecture for polyhedra, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 333-338. MR 0488071 (58 #7642)
  • [10] Robert Connelly, Rigidity, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 223-271. MR 1242981 (94j:52041)
  • [11] A. Flores, Über $ n$-dimensionale komplexe die im $ \mathbb{R}^{2n+1}$ absolut selbstverschlungen sind, Ergeb. Math. Kolloq., 6:4-7, 1933/4.
  • [12] Michael H. Freedman, Vyacheslav S. Krushkal, and Peter Teichner, van Kampen's embedding obstruction is incomplete for $ 2$-complexes in $ {\bf R}^4$, Math. Res. Lett. 1 (1994), no. 2, 167-176. MR 1266755 (95c:57005), https://doi.org/10.4310/MRL.1994.v1.n2.a4
  • [13] Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Lecture Notes in Math., Vol. 438, Springer, Berlin, 1975, pp. 225-239. MR 0400239 (53 #4074)
  • [14] Jacob Eli Goodman and Hironori Onishi, Even triangulations of $ S^{3}$ and the coloring of graphs, Trans. Amer. Math. Soc. 246 (1978), 501-510. MR 515556 (80a:05092), https://doi.org/10.2307/1997991
  • [15] Branko Grünbaum, Higher-dimensional analogs of the four-color problem and some inequalities for simplicial complexes, J. Combinatorial Theory 8 (1970), 147-153. MR 0252274 (40 #5495)
  • [16] William Jockusch, The lower and upper bound problems for cubical polytopes, Discrete Comput. Geom. 9 (1993), no. 2, 159-163. MR 1194033 (93j:52016), https://doi.org/10.1007/BF02189315
  • [17] Michael Joswig, Projectivities in simplicial complexes and colorings of simple polytopes, Math. Z. 240 (2002), no. 2, 243-259. MR 1900311 (2003f:05047), https://doi.org/10.1007/s002090100381
  • [18] Gil Kalai, Characterization of $ f$-vectors of families of convex sets in $ {\bf R}^d$. I. Necessity of Eckhoff's conditions, Israel J. Math. 48 (1984), no. 2-3, 175-195. MR 770700 (86c:52003), https://doi.org/10.1007/BF02761163
  • [19] Gil Kalai, Hyperconnectivity of graphs, Graphs Combin. 1 (1985), no. 1, 65-79. MR 796184 (87c:05081), https://doi.org/10.1007/BF02582930
  • [20] Gil Kalai, Rigidity and the lower bound theorem. I, Invent. Math. 88 (1987), no. 1, 125-151. MR 877009 (88b:52014), https://doi.org/10.1007/BF01405094
  • [21] Gil Kalai, The diameter of graphs of convex polytopes and $ f$-vector theory, Applied geometry and discrete mathematics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, Amer. Math. Soc., Providence, RI, 1991, pp. 387-411. MR 1116365 (92h:52010), https://doi.org/10.1016/0899-8256(91)90037-F
  • [22] Gil Kalai, Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999) Adv. Stud. Pure Math., vol. 33, Math. Soc. Japan, Tokyo, 2002, pp. 121-163. MR 1890098 (2003e:52024)
  • [23] Victor Klee, A combinatorial analogue of Poincaré's duality theorem, Canad. J. Math. 16 (1964), 517-531. MR 0189039 (32 #6466)
  • [24] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331-340. MR 0269535 (42 #4430)
  • [25] Carl W. Lee, Generalized stress and motions, Polytopes: abstract, convex and computational (Scarborough, ON, 1993), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 440, Kluwer Acad. Publ., Dordrecht, 1994, pp. 249-271. MR 1322066 (96c:52039)
  • [26] W. Mader, Homomorphiesätze für Graphen, Math. Ann. 178 (1968), 154-168 (German). MR 0229550 (37 #5124)
  • [27] P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559-570. MR 0278183 (43 #3914)
  • [28] James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006 (85m:55001)
  • [29] E. Nevo,
    Algebraic Shifting and $ f$-Vector Theory,
    PhD thesis, Hebrew University, Jerusalem, 2007.
  • [30] Eran Nevo, Higher minors and Van Kampen's obstruction, Math. Scand. 101 (2007), no. 2, 161-176. MR 2379282 (2009d:55032)
  • [31] Eran Nevo, On embeddability and stresses of graphs, Combinatorica 27 (2007), no. 4, 465-472. MR 2359827 (2008k:05059), https://doi.org/10.1007/s00493-007-2168-x
  • [32] I. Pak,
    Lectures on discrete and polyhedral geometry,
    Book, in preparation, available at http://www.math.ucla.edu/$ \sim $pak/book.htm.
  • [33] Neil Robertson, Paul Seymour, and Robin Thomas, Sachs' linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), no. 2, 185-227. MR 1339849 (96m:05072), https://doi.org/10.1006/jctb.1995.1032
  • [34] Horst Sachs, On a spatial analogue of Kuratowski's theorem on planar graphs--an open problem, Graph theory (Łagów, 1981) Lecture Notes in Math., vol. 1018, Springer, Berlin, 1983, pp. 230-241. MR 730653 (85b:05077), https://doi.org/10.1007/BFb0071633
  • [35] Arnold Shapiro, Obstructions to the imbedding of a complex in a euclidean space. I. The first obstruction, Ann. of Math. (2) 66 (1957), 256-269. MR 0089410 (19,671a)
  • [36] Amit Singer and Mihai Cucuringu, Uniqueness of low-rank matrix completion by rigidity theory, SIAM J. Matrix Anal. Appl. 31 (2009/10), no. 4, 1621-1641. MR 2595541 (2011b:15062), https://doi.org/10.1137/090750688
  • [37] Mikhail Skopenkov, Embedding products of graphs into Euclidean spaces, Fund. Math. 179 (2003), no. 3, 191-198. MR 2029321 (2004m:57050), https://doi.org/10.4064/fm179-3-1
  • [38] Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139-157. MR 526314 (81c:05012), https://doi.org/10.2307/1998915
  • [39] Richard P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), no. 3, 236-238. MR 563925 (81f:52014), https://doi.org/10.1016/0001-8708(80)90050-X
  • [40] E. R. van Kampen, Komplexe in euklidischen Räumen, Abh. Math. Sem. Univ. Hamburg 9 (1933), no. 1, 72-78 (German). MR 3069580, https://doi.org/10.1007/BF02940628
  • [41] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), no. 1, 570-590 (German). MR 1513158, https://doi.org/10.1007/BF01594196
  • [42] Uli Wagner, Minors in random and expanding hypergraphs, Computational geometry (SCG'11), ACM, New York, 2011, pp. 351-360. MR 2919626, https://doi.org/10.1145/1998196.1998256
  • [43] Walter Whiteley, Cones, infinity and $ 1$-story buildings, Structural Topology 8 (1983), 53-70. With a French translation. MR 721956 (85h:51032)
  • [44] Walter Whiteley, A matroid on hypergraphs, with applications in scene analysis and geometry, Discrete Comput. Geom. 4 (1989), no. 1, 75-95. MR 964145 (89k:05027), https://doi.org/10.1007/BF02187716
  • [45] Walter Whiteley, La division de sommet dans les charpentes isostatiques, Structural Topology 16 (1990), 23-30. Dual French-English text. MR 1102001 (92c:52037)
  • [46] Walter Whiteley, Some matroids from discrete applied geometry, Matroid theory (Seattle, WA, 1995) Contemp. Math., vol. 197, Amer. Math. Soc., Providence, RI, 1996, pp. 171-311. MR 1411692 (97h:05040), https://doi.org/10.1090/conm/197/02540
  • [47] Wu Wen-tsün, A theory of imbedding, immersion, and isotopy of polytopes in a euclidean space, Science Press, Peking, 1965. MR 0215305 (35 #6146)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C10, 13F55, 52C25, 05E45, 57Q35

Retrieve articles in all journals with MSC (2010): 05C10, 13F55, 52C25, 05E45, 57Q35


Additional Information

Gil Kalai
Affiliation: Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem 91904, Israel – and – Department of Computer Science and Department of Mathematics, Yale University, New Haven, Connecticut 06511
Email: kalai@math.huji.ac.il

Eran Nevo
Affiliation: Department of Mathematics, Ben Gurion University of the Negev, Be’er Sheva 84105, Israel – and – Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem 91904, Israel
Email: nevoe@math.bgu.ac.il, nevo@math.huji.ac.il

Isabella Novik
Affiliation: Department of Mathematics, Box 354350, University of Washington, Seattle, Washington 98195-4350
Email: novik@math.washington.edu

DOI: https://doi.org/10.1090/tran/6512
Received by editor(s): December 20, 2013
Received by editor(s) in revised form: July 3, 2014, and July 10, 2014
Published electronically: November 16, 2015
Additional Notes: The research of the first author was partially supported by ERC advanced grant 320924, ISF grant 768/12, and NSF grant DMS-1300120, of the second author by Marie Curie grant IRG-270923 and ISF grant 805/11, and of the third author by NSF grant DMS-1069298. The first author also acknowledges the Simons Institute for the Theory of Computing.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society