Sean Dewar

A beginners guide to combinatorial rigidity and flexibility in the plane

Consider a graph as bar-and-joint framework in the plane, with edges modelling rigid bars and vertices modelling fully flexible joints between bars. With this construction (now called a realisation of the graph), one can now ask the following question: does the realisation allow for any bar-length-preserving deformation that is not a rigid body motion? If it does then we say that our realisation of our graph is flexible, otherwise we say that it is rigid. Interestingly, rigidity is a generic property, in the sense that one generic realisation is rigid if and only if all are rigid. Because of this, restricting solely to generic realisations allows us to essentially remove the geometry from the question, leaving ourselves with an entirely combinatorial problem to solve. In my talk I will cover two purely combinatorial aspects of rigidity theory: determining whether a graph has a generic rigid realisation, and determining whether a graph has any flexible realisations. The talk will also cover a simplistic crash course on Matroid Theory and its applications to the topic. Time permitting, I will also speak about some of my own recent results in the area, including links between algebraic connectivity and rigidity (and in particular Ramanujan graphs), constant-time algorithms for determining rigidity for highly symmetric graphs, and flexibility conditions for braced 1-skeletons of Penrose tilings.