Home

Пятница 19.04. Виктор Лопаткин: "Двудольные графы как полиномы и полиномы как двудольные графы"

Пятница, 19 апреля, ауд. 106. Начало в 16:30.

Докладчик: Виктор Лопаткин.

Тема: Двудольные графы как полиномы и полиномы как двудольные графы.

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] $ с помощью этих конструкций. Наконец, мы вводим на множестве двудольных графов топологию Зарисского.

Доклад по совместной работе с Андреем Гринблат.