Bipartite rigidity
HTML articles powered by AMS MathViewer
- by Gil Kalai, Eran Nevo and Isabella Novik PDF
- Trans. Amer. Math. Soc. 368 (2016), 5515-5545 Request permission
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
- L. Asimow and B. Roth, The rigidity of graphs, Trans. Amer. Math. Soc. 245 (1978), 279–289. MR 511410, DOI 10.1090/S0002-9947-1978-0511410-9
- L. Asimow and B. Roth, The rigidity of graphs. II, J. Math. Anal. Appl. 68 (1979), no. 1, 171–190. MR 531431, DOI 10.1016/0022-247X(79)90108-2
- Eric K. Babson and Clara S. Chan, Counting faces of cubical spheres modulo two, Discrete Math. 212 (2000), no. 3, 169–183. Combinatorics and applications (Tianjin, 1996). MR 1748648, DOI 10.1016/S0012-365X(99)00285-X
- Eric Babson and Isabella Novik, Face numbers and nongeneric initial ideals, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 25, 23. MR 2195431
- Eric Babson, Isabella Novik, and Rekha Thomas, Reverse lexicographic and lexicographic shifting, J. Algebraic Combin. 23 (2006), no. 2, 107–123. MR 2223682, DOI 10.1007/s10801-006-6919-3
- 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, DOI 10.1007/BF02574013
- J. L. Bryant, Approximating embeddings of polyhedra in codimension three, Trans. Amer. Math. Soc. 170 (1972), 85–95. MR 307245, DOI 10.1090/S0002-9947-1972-0307245-7
- 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.
- Robert Connelly, A counterexample to the rigidity conjecture for polyhedra, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 333–338. MR 488071, DOI 10.1007/BF02684342
- Robert Connelly, Rigidity, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 223–271. MR 1242981
- A. Flores, Über $n$-dimensionale komplexe die im $\mathbb {R}^{2n+1}$ absolut selbstverschlungen sind, Ergeb. Math. Kolloq., 6:4–7, 1933/4.
- Michael H. Freedman, Vyacheslav S. Krushkal, and Peter Teichner, van Kampen’s embedding obstruction is incomplete for $2$-complexes in $\textbf {R}^4$, Math. Res. Lett. 1 (1994), no. 2, 167–176. MR 1266755, DOI 10.4310/MRL.1994.v1.n2.a4
- 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
- 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, DOI 10.1090/S0002-9947-1978-0515556-0
- 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 252274, DOI 10.1016/S0021-9800(70)80071-0
- William Jockusch, The lower and upper bound problems for cubical polytopes, Discrete Comput. Geom. 9 (1993), no. 2, 159–163. MR 1194033, DOI 10.1007/BF02189315
- Michael Joswig, Projectivities in simplicial complexes and colorings of simple polytopes, Math. Z. 240 (2002), no. 2, 243–259. MR 1900311, DOI 10.1007/s002090100381
- Gil Kalai, Characterization of $f$-vectors of families of convex sets in $\textbf {R}^d$. I. Necessity of Eckhoff’s conditions, Israel J. Math. 48 (1984), no. 2-3, 175–195. MR 770700, DOI 10.1007/BF02761163
- Gil Kalai, Hyperconnectivity of graphs, Graphs Combin. 1 (1985), no. 1, 65–79. MR 796184, DOI 10.1007/BF02582930
- Gil Kalai, Rigidity and the lower bound theorem. I, Invent. Math. 88 (1987), no. 1, 125–151. MR 877009, DOI 10.1007/BF01405094
- 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, DOI 10.1016/0899-8256(91)90037-F
- 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, DOI 10.2969/aspm/03310121
- Victor Klee, A combinatorial analogue of Poincaré’s duality theorem, Canadian J. Math. 16 (1964), 517–531. MR 189039, DOI 10.4153/CJM-1964-053-0
- G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI 10.1007/BF01534980
- 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
- W. Mader, Homomorphiesätze für Graphen, Math. Ann. 178 (1968), 154–168 (German). MR 229550, DOI 10.1007/BF01350657
- P. McMullen, The numbers of faces of simplicial polytopes, Israel J. Math. 9 (1971), 559–570. MR 278183, DOI 10.1007/BF02771471
- James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
- E. Nevo, Algebraic Shifting and $f$-Vector Theory, PhD thesis, Hebrew University, Jerusalem, 2007.
- Eran Nevo, Higher minors and Van Kampen’s obstruction, Math. Scand. 101 (2007), no. 2, 161–176. MR 2379282, DOI 10.7146/math.scand.a-15037
- Eran Nevo, On embeddability and stresses of graphs, Combinatorica 27 (2007), no. 4, 465–472. MR 2359827, DOI 10.1007/s00493-007-2168-x
- I. Pak, Lectures on discrete and polyhedral geometry, Book, in preparation, available at http://www.math.ucla.edu/$\sim$pak/book.htm.
- Neil Robertson, Paul Seymour, and Robin Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), no. 2, 185–227. MR 1339849, DOI 10.1006/jctb.1995.1032
- 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, DOI 10.1007/BFb0071633
- 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 89410, DOI 10.2307/1969998
- 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, DOI 10.1137/090750688
- Mikhail Skopenkov, Embedding products of graphs into Euclidean spaces, Fund. Math. 179 (2003), no. 3, 191–198. MR 2029321, DOI 10.4064/fm179-3-1
- Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139–157. MR 526314, DOI 10.1090/S0002-9947-1979-0526314-6
- Richard P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), no. 3, 236–238. MR 563925, DOI 10.1016/0001-8708(80)90050-X
- E. R. van Kampen, Komplexe in euklidischen Räumen, Abh. Math. Sem. Univ. Hamburg 9 (1933), no. 1, 72–78 (German). MR 3069580, DOI 10.1007/BF02940628
- K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), no. 1, 570–590 (German). MR 1513158, DOI 10.1007/BF01594196
- Uli Wagner, Minors in random and expanding hypergraphs, Computational geometry (SCG’11), ACM, New York, 2011, pp. 351–360. MR 2919626, DOI 10.1145/1998196.1998256
- Walter Whiteley, Cones, infinity and $1$-story buildings, Structural Topology 8 (1983), 53–70. With a French translation. MR 721956
- Walter Whiteley, A matroid on hypergraphs, with applications in scene analysis and geometry, Discrete Comput. Geom. 4 (1989), no. 1, 75–95. MR 964145, DOI 10.1007/BF02187716
- Walter Whiteley, La division de sommet dans les charpentes isostatiques, Structural Topology 16 (1990), 23–30. Dual French-English text. MR 1102001
- 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, DOI 10.1090/conm/197/02540
- Wu Wen-tsün, A theory of imbedding, immersion, and isotopy of polytopes in a euclidean space, Science Press, Peking, 1965. MR 0215305
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
- MR Author ID: 195990
- 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
- MR Author ID: 762118
- 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
- MR Author ID: 645524
- Email: novik@math.washington.edu
- 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.
- © Copyright 2015 American Mathematical Society
- 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
- MathSciNet review: 3458389