# Every embedding of a dense graph has a rigid subset - Jozsef Solymosi (University of British Columbia)

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 three which is rigid.

We do not know whether our assumption on the number of edges being $\Omega(n^{3/2}\log n)$ is tight, and we provide a construction that shows that requiring $\Omega(n\log n)$ edges is necessary.

Joint work with Orit Raz.

### About Maths Colloquium

The Mathematics Colloquium is directed at students and academics working in the fields of pure and applied mathematics, and statistics.

We aim to present expository lectures that appeal to our wide audience.

Information for speakers

#### Information for speakers

Maths colloquia are usually held on Mondays, from 2pm to 3pm, in various locations at St Lucia.

Presentations are 50 minutes, plus five minutes for questions and discussion.

Available facilities include:

- computer
- data projector
- chalkboard or whiteboard

To avoid technical difficulties on the day, please contact us in advance of your presentation to discuss your requirements.