2013/12/01 by Gil Kalai, Eran Nevo, Kalai, Gil +3 · 5 citations
Engineering · Biochemistry, Genetics and Molecular Biology · #Structural Analysis and Optimization #Advanced Materials and Mechanics #Cellular Mechanics and Interactions
paper · pdf · doi:10.48550/arxiv.1312.0209
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, Gb, does not contain K3,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.