Event Details

Rigid partitions

A graph is called d-rigid if there exists a "generic" embedding of its vertex set into R^d such that every continuous motion of the vertices that preserves the lengths of all edges actually preserves the distances between all pairs of vertices. In this talk, I will present new sufficient conditions for the d-rigidity of a graph in terms of the existence of "rigid partitions" - partitions of the graph that satisfy certain connectivity properties. Following this, I will outline several broadly applicable conditions for the existence of rigid partitions and discuss a few applications, among which are new results on the rigidity of highly connected, (pseudo)random graphs, and dense graphs.

The talk is based on joint work with Michael Krivelevich and Alan Lew.