Title: Extremal and probabilistic aspects of graph rigidity
Combinatorial rigidity theory addresses questions such as: given a structure defined by geometric constraints, what can be inferred about its geometric behaviour based solely on its underlying combinatorial data? Such structures are often modelled as assemblies of rigid rods connected by rotational joints, in which case the underlying combinatorial data is a graph. A typical question in this context is: given such a framework in generic position in R^d, is it rigid? That is, does every continuous motion of the vertices (joints) that preserves the lengths of all edges (rods) necessarily preserve the distances between all pairs of vertices?
In this talk, I will present new sufficient conditions for the rigidity of a framework in R^d based on the notion of rigid partitions - partitions of the underlying graph that satisfy certain connectivity properties. I will outline several broadly applicable conditions for the existence of such partitions and discuss a few applications, including results on the rigidity of (pseudo)random graphs.
Expanding on these results, I will next discuss new minimum degree conditions for d-rigidity; specifically, we will see that for d = O(sqrt(n)), if an n-vertex graph has a minimum degree of delta(G) \ge (n + d)/2 - 1, then it is d-rigid, and this is optimal. Moreover, for d = O(n / log^2 n), satisfying this degree condition guarantees floor(d/2)-rigidity, which is optimal up to a constant factor of 2. As a byproduct of our arguments, we also derive, in the corresponding minimum degree regime, a sharp lower bound on the pseudoachromatic number of a graph - the maximum size of a vertex partition such that there is an edge between any two distinct parts - in terms of its minimum degree.
The talk is based on joint work with Michael Krivelevich and Alan Lew.