Пятница 19.04. Виктор Лопаткин: "Двудольные графы как полиномы и полиномы как двудольные графы"
PDMI seminars
Тема: Двудольные графы как полиномы и полиномы как двудольные графы
Место: ауд. 106
Время: 19.04.2019, 16:00
Докладчик: Виктор Лопаткин
Abstract:
В докладе будут представлены следующие две конструкции:
(1) По каждому неориентированному (ориентированному) конечному двудольному графу $\Gamma = (V,U,E)$ строится полином $p(\Gamma)$, который в случае, если граф $\Gamma$ неориентируемый, то $p\in \mathbb{N}[x]$, а если $\Gamma$ -- ориентируемый, то $p(\Gamma) \in \mathbb{N}[x,y]$.
(2) По каждому полиному $p\in \mathbb{N}[x]$ строится неоринтируемый двудольный конечный граф $\Gamma(p)$, а по каждому полиному $p\in\mathbb{N}[x,y]$ строится ориентируемый конечный двудольный граф $\Gamma(p)$.
При этом, обе эти конструкции взаимно обратны друг к другу, то есть $\Gamma(p(\Gamma)) = \Gamma$. Мы далее покажем, что обычное произведение (двудольных) графов $\Gamma_1\times \Gamma_2$ соответствует произведению их полиномов, то есть $\Gamma_1 \times \Gamma_2 = \Gamma(p(\Gamma_1)\cdot p(\Gamma_2))$, а граф соответствующий сумме полиномов, скажем $p_1+p_2$, есть граф полученный ``приклеиванием'' графа $\Gamma(p_1)$ к $\Gamma(p_2)$ по определённому, но при этом простому, правилу.
Как приложение, мы обсудим делимость в полукольцах $\mathbb{N}[x]$, $\mathbb{N}[x,y]$ с помощью этих конструкций. Наконец, мы вводим на множестве двудольных графов топологию Зарисского.
Доклад по совместной работе с Андреем Гринблат.
Dmitry Itsykson
_______________________________________________
Discrete Mathematics Seminar mailing list
(Un)subscription: https://logic.pdmi.ras.ru/cgi-bin/mailman/listinfo/dmseminar
Web page: http://logic.pdmi.ras.ru/~dmseminar/