Многогранник порядка - Order polytope

В математике порядковый многогранник конечного частично заказанный набор это выпуклый многогранник определяется из набора. Точками многогранника порядка являются точки монотонные функции из данного набора в единичный интервал, его вершины соответствуют верхние наборы частичного порядка, а его размер - количество элементов в частичном порядке. Многогранник порядка - это распределительный многогранник, что означает, что покоординатные минимумы и максимумы пар его точек остаются внутри многогранника.

Порядковый многогранник частичного порядка следует отличать от многогранник линейного порядка, многогранник, определенный из числа ${ displaystyle n}$ как выпуклый корпус из индикаторные векторы наборов ребер ${ displaystyle n}$-вертекс переходные турниры.^[1]

Определение и пример

А частично заказанный набор пара ${ Displaystyle (S, leq)}$ куда ${ displaystyle S}$ - произвольное множество и ${ displaystyle leq}$ это бинарное отношение на парах элементов ${ displaystyle S}$ это рефлексивно (для всех ${ displaystyle x in S}$, ${ displaystyle x leq x}$), антисимметричный (для всех ${ displaystyle x, y in S}$ с ${ Displaystyle х neq y}$ максимум один из ${ displaystyle x leq y}$ и ${ displaystyle y leq x}$ может быть истинным) и транзитивным (для всех ${ displaystyle x, y, z in S}$, если ${ displaystyle x leq y}$ и ${ displaystyle y leq z}$ тогда ${ Displaystyle х leq z}$).

Частично заказанный набор ${ Displaystyle (S, leq)}$ называется конечным, когда ${ displaystyle S}$ это конечный набор. В этом случае набор всех функций ${ displaystyle f}$ эта карта ${ displaystyle S}$ к действительные числа образует конечномерную векторное пространство, с точечное сложение функций как операцию векторного суммирования. Размер пространства - это просто количество элементов ${ displaystyle S}$. Многогранник порядка определяется как подмножество этого пространства, состоящее из функций ${ displaystyle f}$ со следующими двумя свойствами:^[2][3]

• Для каждого ${ displaystyle x in S}$, ${ Displaystyle 0 Leq е (х) Leq 1}$. То есть, ${ displaystyle f}$ отображает элементы ${ displaystyle S}$ к единичный интервал.
• Для каждого ${ displaystyle x, y in S}$ с ${ displaystyle x leq y}$, ${ Displaystyle f (x) leq f (y)}$. То есть, ${ displaystyle f}$ это монотонная функция

Например, для частично упорядоченного набора, состоящего из двух элементов ${ displaystyle x}$ и ${ displaystyle y}$, с ${ displaystyle x leq y}$ в частичном порядке функции ${ displaystyle f}$ от этих точек к действительным числам можно отождествить с точками ${ Displaystyle (е (х), е (у))}$ в Декартова плоскость. В этом примере многогранник порядка состоит из всех точек в ${ Displaystyle (х, у)}$-самолет с ${ Displaystyle 0 Leq Икс Leq Y Leq 1}$. Это равнобедренный прямоугольный треугольник с вершинами в точках (0,0), (0,1) и (1,1).

Вершины и грани

Вершины многогранника порядка состоят из монотонных функций из ${ displaystyle S}$ к ${ displaystyle {0,1 }}$. То есть многогранник порядка является интегральный многогранник; у него нет вершин с дробными координатами. Эти функции в точности соответствуют индикаторные функции из верхние наборы частичного заказа. Следовательно, количество вершин равно количеству верхних множеств.^[2]

В грани многогранники порядка бывают трех типов:^[2]

• Неравенства ${ Displaystyle 0 Leq F (х)}$ для каждого минимального элемента ${ displaystyle x}$ частично упорядоченного набора,
• Неравенства ${ Displaystyle е (у) leq 1}$ для каждого максимального элемента ${ displaystyle y}$ частично упорядоченного набора, и
• Неравенства ${ Displaystyle f (x) leq f (y)}$ для каждых двух различных элементов ${ displaystyle x, y}$ которые не имеют третьего отдельного элемента ${ displaystyle z}$ между ними; то есть для каждой пары ${ Displaystyle (х, у)}$ в покрывающее отношение частично заказанного набора.

Грани можно рассматривать более симметрично, вводя специальные элементы ${ displaystyle bot}$ ниже всех элементов в частичном порядке и ${ displaystyle top}$ прежде всего элементы, отображаемые ${ displaystyle f}$ равными 0 и 1 соответственно, и сохраняя только неравенства третьего типа для результирующего расширенного частично упорядоченного набора.^[2]

В более общем смысле, с таким же увеличением на ${ displaystyle bot}$ и ${ displaystyle top}$, грани всех размерностей многогранника порядка соотносятся один к одному с частными частичного порядка. Каждая грань конгруэнтна многограннику порядков соответствующего частичного порядка.^[2]

Объем и полином Эрхарта

Многогранник порядка линейный порядок это особый вид симплекс называется заказать симплекс или же орто-схема. Каждая точка единичный куб чьи координаты все различные, лежит в единственной из этих ортосхем, симплексе порядка для линейного порядка его координат. конгруэнтный друг к другу и (для заказов на ${ displaystyle n}$ элементы) есть ${ displaystyle n!}$ различных линейных порядков, объем симплекса каждого порядка ${ Displaystyle 1 / п!}$.^[2][3] В более общем смысле, порядковый многогранник может быть разбит на порядковые симплексы каноническим способом, с одним симплексом для каждого. линейное расширение соответствующего частично упорядоченного множества.^[2]Следовательно, объем любого многогранника порядка равен ${ Displaystyle 1 / п!}$ умноженное на количество линейных расширений соответствующего частично упорядоченного множества.^[2][3] Эта связь между количеством линейных расширений и объемом может быть использована для эффективного приближения количества линейных расширений любого частичного порядка (несмотря на то, что точное вычисление этого числа является # P-complete ) путем применения схема рандомизированной полиномиальной аппроксимации для объема многогранника.^[4]

В Многочлен Эрхарта многогранника порядка - это многочлен, значения которого при целых значениях ${ displaystyle x}$ дать количество целочисленных точек в копии многогранника, масштабированной с коэффициентом ${ displaystyle x}$. Для многогранника порядка многочлен Эрхарта равен (после небольшой замены переменных) порядковый полином соответствующего частично упорядоченного множества. Этот многочлен кодирует несколько частей информации о многограннике, включая его объем (старший коэффициент многочлена и количество его вершин (сумма коэффициентов).^[2][3]

Непрерывная решетка

К Теорема Биркгофа о представлении для конечного распределительные решетки, то верхние наборы любого частично упорядоченного множества образуют конечную дистрибутивную решетку, и каждая конечная дистрибутивная решетка может быть представлена ​​таким образом.^[5] Верхние множества соответствуют вершинам многогранника порядка, поэтому отображение верхних множеств в вершины обеспечивает геометрическое представление любой конечной дистрибутивной решетки. В этом представлении ребра многогранника соединяют сравнимые элементы решетки.

Если две функции ${ displaystyle p}$ и ${ displaystyle q}$ оба принадлежат порядковому многограннику частично упорядоченного множества ${ Displaystyle (S, leq)}$, то функция ${ displaystyle p wedge q}$ что отображает ${ displaystyle x}$ к ${ Displaystyle мин (п (х), д (х))}$, а функция ${ displaystyle p vee q}$ что отображает ${ displaystyle x}$ к ${ Displaystyle макс (п (х), д (х))}$ обе также принадлежат многограннику порядка. ${ displaystyle wedge}$ и ${ displaystyle vee}$ придадим порядковому многограннику структуру непрерывного распределительная решетка, в которую вложена конечная дистрибутивная решетка из теоремы Биркгофа, т. е. каждый порядковый многогранник является распределительный многогранник. Дистрибутивные многогранники со всеми координатами вершин, равными 0 или 1, являются в точности многогранниками порядка.^[6]

Рекомендации