COLLOQUIUM: Every embedding of a dense graph has a rigid subset
While the problem of determining whether an embedding of a graph G in the plane is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that requires ad hoc arguments.
In this talk, we show that every embedding (not necessarily generic) of a dense enough graph which satisfies that no three vertices of G are embedded to a common line, must have a subframework of size at least six which is rigid.
Joint work with Orit Raz.
Professor Jozsef Solymosi, University of British Columbia