Полином порядка

Не путать с Порядком полинома .

Полином порядка — это многочлен , изучаемый в математике, в частности в алгебраической теории графов и алгебраической комбинаторике . Полином порядка подсчитывает количество сохраняющих порядок отображений из частично упорядоченного набора в цепочку длины $n$. Эти карты, сохраняющие порядок, были впервые представлены Ричардом П. Стэнли во время изучения упорядоченных структур и перегородок в качестве доктора философии. студент Гарвардского университета в 1971 году под руководством Джан-Карло Роты .

Определение

Позволять $P$ быть конечным частично упорядоченным множеством с $p$ элементы, обозначенные $x,y\in P$, и пусть $[n]=\{1<2<\ldots <n\}$ быть цепью $n$ элементы. Карта $\phi :P\to [n]$ сохраняет порядок, если $x\leq y$ подразумевает $\phi (x)\leq \phi (y)$. Число таких карт растет полиномиально с увеличением $n$, а функция, считающая их количество, является полиномом порядка $\Omega (n)=\Omega (P,n)$.

Аналогичным образом мы можем определить полином порядка, который подсчитывает количество карт, строго сохраняющих порядок. $\phi :P\to [n]$, значение $x<y$ подразумевает $\phi (x)<\phi (y)$. Число таких отображений представляет собой полином строгого порядка $\Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)$.

Оба $\Omega (n)$ и $\Omega ^{\circ }\!(n)$ иметь степень $p$. Отображения, сохраняющие порядок, обобщают линейные расширения $P$, сохраняющие порядок биекции $\phi :P{\stackrel {\sim }{\longrightarrow }}[p]$. Действительно, ведущий коэффициент $\Omega (n)$ и $\Omega ^{\circ }\!(n)$ - количество линейных расширений, разделенное на $p!$.

Примеры

Сдача в аренду $P$ быть цепочкой ​ $p$ элементы, у нас есть

$\Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)$ и $\Omega ^{\circ }(n)={\binom {n}{p}}.$

Существует только одно линейное расширение (тождественное отображение), и оба многочлена имеют главный член. ${\tfrac {1}{p!}}n^{p}$.

Сдача в аренду $P$ быть антицепью ​ $p$ несравнимые элементы, мы имеем $\Omega (n)=\Omega ^{\circ }(n)=n^{p}$. Поскольку любая биекция $\phi :P{\stackrel {\sim }{\longrightarrow }}[p]$ (строго) сохраняет порядок, существуют $p!$ линейные расширения, и оба полинома сводятся к главному члену ${\tfrac {p!}{p!}}n^{p}=n^{p}$.

Теорема взаимности

Существует связь между картами, строго сохраняющими порядок, и картами, сохраняющими порядок:

$\Omega ^{\circ }(n)=(-1)^{|P|}\Omega (-n).$

В случае, если $P$ является цепью, это восстанавливает отрицательное биномиальное тождество . Существуют аналогичные результаты для хроматического полинома и полинома Эрхарта (см. ниже), всех частных случаев общей теоремы Стэнли о взаимности .

Связи с другими счетными полиномами

Хроматический полином

Хроматический полином $P(G,n)$подсчитывает количество правильных раскрасок конечного графа $G$ с $n$ доступные цвета. Для ациклической ориентации $\sigma$ краев $G$, существует естественный частичный порядок «нисходящих» вершин $V(G)$ подразумеваемое основными отношениями $u>v$ в любое время $u\rightarrow v$ представляет собой направленное ребро $\sigma$. (Таким образом, диаграмма Хассе ЧУМ является подграфом ориентированного графа $\sigma$.) Мы говорим $\phi :V(G)\rightarrow [n]$ совместим с $\sigma$ если $\phi$ сохраняет порядок. Тогда у нас есть

$P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),$

где $\sigma$ пробегает все ациклические ориентации G, рассматриваемые как структуры ЧУМ.

Порядковый многогранник и полином Эрхарта

Основная статья: Порядковый многогранник

Многогранник порядка связывает многогранник с частичным порядком. Для посета $P$ с $p$ элементы, порядковый многогранник $O(P)$ есть набор сохраняющих порядок отображений $f:P\to [0,1]$, где $[0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}$ — упорядоченный единичный интервал, ЧУМ-непрерывная цепочка. Более геометрически мы можем перечислить элементы $P=\{x_{1},\ldots ,x_{p}\}$и определить любое отображение $f:P\to \mathbb {R}$ с точкой $(f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}$; тогда порядковый многогранник — это множество точек $(t_{1},\ldots ,t_{p})\in [0,1]^{p}$ с $t_{i}\leq t_{j}$ если $x_{i}\leq x_{j}$.

Полином Эрхарта подсчитывает количество целочисленных точек решетки внутри расширений многогранника . В частности, рассмотрим решетку $L=\mathbb {Z} ^{n}$ и $d$-мерный многогранник $K\subset \mathbb {R} ^{d}$ с вершинами в $L$; тогда мы определяем

$L(K,n)=\#(nK\cap L),$

количество точек решетки в $nK$, расширение $K$ положительным целочисленным скаляром $n$. Эрхарт показал, что это рациональный полином степени $d$ в переменной $n$, предоставил $K$ имеет вершины в решетке.

Фактически, полином Эрхарта многогранника порядка равен полиному порядка исходного ЧУ множества (со сдвинутым аргументом):

$L(O(P),n)\ =\ \Omega (P,n{+}1).$

Это является непосредственным следствием определений, учитывая включение $(n{+}1)$-цепной посет $[n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R}$.