Семинары: О. Р. Мусин, Минимальные сферические представления графов

СЕМИНАРЫ


Дискретная и вычислительная геометрия 20 декабря 2016 г. 13:45, г. Москва, ИППИ РАН, Большой Каретный переулок, 19, ауд. 307

Минимальные сферические представления графов О. Р. Мусин^ab ^a Department of Mathematics, University of Texas at Brownsville ^b Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва
Аннотация: Всякий граф $G$ может быть вложен в евклидово пространство как множество с двумя расстояниями. Минимальная размерность такого представления явно вычисляется через собственные значения $G$. В докладе мы обсудим сферические (т.е. вложения в сферу) и $J$-сферические (вложение в единичную сферу с минимальным расстоянием $\sqrt{2}$) представления $G$. Будут приведены явные формулы для минимальных размерностей таких вложений через кратность корней многочленов, задаваемых определителем Кэли–Менгера. Мы также покажем, что теорема В. Куперберга позволяет найти минимальные размерности представлений для соединения графов.