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)

Request Permissions   Purchase Content 
 

 

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


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