Combinatorics: Orit Raz (HUJI)

Mon, 16/12/201910:00-12:00
C-400, CS building

Combinatorics Seminar HUJI

When: Monday Dec 16, 10:00-11:45
Where: C-400, CS building

Speaker: Orit Raz (HUJI)

Title: Dense graphs have rigid parts


While the problem of determining whether a given embedding of a graph $G$ in $\R^2$ is {\it infinitesimally rigid} is well understood, specifying whether a given embedding of $G$ is {\it rigid} or not is still a hard task that usually requires ad hoc arguments. In the talk I will tell about a recent result with Jozsef Solymosi asserting that {\it every} embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least $C_0n^{3/2}(\log n)^{\beta}$ edges, for some absolute constants $C_0>0$ and $\beta\ge 1$), which satisfies some very mild general position requirements (no three vertices of $G$ are embedded to a common line), must have a subframework of size at least three which is rigid.

For the proof we use a connection between the notion of graph rigidity and configurations of lines in $\R^3$, which I will introduce. This connection allows us to use properties of line configurations established in Guth and Katz~\cite{GK2}.
(In fact, our proof requires an extended version of Guth and Katz result; the extension we need was proved by J\'anos Koll\’ar.)

We do not know whether our assumption on the number of edges is tight. I will introduce an example that shows that requiring  $\Omega(n\log n)$ edges is necessary.