O kwadratowej zanurzalności grafów dwudzielnych i grafów theta

Niech $G=(V,E)$ będzie spójnym grafem prostym. Zanurzeniem kwadratowym nazywamy takie odwzorowanie $\varphi: V \to H$, że dla wszystkich $x,y \in V$ spełniony jest warunek $$\|\varphi(x) - \varphi(y)\|^2=d(x,y),$$ gdzie $(H,\|\cdot\|)$ jest pewną przestrzenią Hilberta, a $d(x,y)$ to odległość grafowa. Mówimy, że graf jest klasy QE, jeśli spełnia zanurzenie kwadratowe, w przeciwnym razie jest klasy non-QE. Ponadto, graf klasy non-QE jest nazywany primary, jeśli nie zawiera izometrycznie zanurzalnego podgrafu właściwego klasy non-QE. Pokażemy, że dla każdej liczby wierzchołków większej, bądź równej 5 istnieje graf primary. Wykład oparty na wspólnej pracy z Wojciechem Młotkowskim i Michałem Wojtylakiem.