Вложение конечного графа в евклидово пространство

[arseniiv]

Элементарно вложить граф с $n$ вершинами в $n$-мерное евклидово пространство, чтобы его автоморфизмы были автоморфизмами пространства, оставляющими образ графа на месте (каждую вершину перевести в вектор заданного базиса, каждое ребро в отрезок). Однако если мы выкинем из полученной фигуры все отрезки, мы потеряем всю информацию о графе, группа симметрий станет $S_n$. Можно ли вложить граф получше — найти в некотором пространстве такое множество $n$ точек, что группа его симметрий будет изоморфна группе автоморфизмов графа, а точки при этом будут соответствовать вершинам?

Тут наверно тоже всё легко, но я не подумал ещё.

[mihaild]

Для каждой вершины $i$ запишем вектор расстояний по графу от нее до всех остальных $(d_{i,1}, d_{i,2}, \ldots, d_{i, n})$. Теперь отправляем вершину $i$ в вектор $(\sqrt{d_{i, 1}}, \ldots, \sqrt{d_{i, n}})$. Тогда по скалярным произведениям однозначно восстанавливаются ребра - и, соответственно, автоморфизмы графа это в точности изометрии, оставляющие $S$ на месте.

[arseniiv]

Спасибо, прекрасно!

[mihaild]

arseniiv, зря аплодируете, я вас, кажется, обманул. По крайней мере доказать, что мой способ работает, я не могу.
Но можно так: ребра - это базисные вектора (попарно ортогональные), вектор вершины - сумма векторов инцидентных ей ребер. Тогда вершины ортогональны тогда и только тогда, когда они не смежны.

[Geen]

mihaild в сообщении #1354743 писал(а):

Теперь отправляем вершину $i$ в вектор

А зачем корни брать здесь?

И ведь размерность $n$...

[mihaild]

Меньшую размерность не просили:) И скажем полный граф на $n$ вершинах меньше чем в $\mathbb{R}^{n - 1}$ вложить не получится.
Корни брать затем что я писал одно, думал про другое, а надо было третье...

[arseniiv]

mihaild в сообщении #1355313 писал(а):

По крайней мере доказать, что мой способ работает, я не могу.

Хм, я тогда сначала в одну сторону не понял (что любой автоморфизм реализуется), а потом как будто понял. Про необязательность корней тоже увидел.

Подумаю когда посплю с выписыванием над новым и над старым тоже, чтобы удостовериться.