Bipartite rigidity

Kalai, Gil; Nevo, Eran; Novik, Isabella

doi:10.1090/tran/6512

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