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?)

References

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
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.
Article copyright: © Copyright 2015 American Mathematical Society