Многогранник порядка - 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 x\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 x\leq z}$).

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

• Для каждого ${\displaystyle x\in S}$, ${\displaystyle 0\leq f(x)\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 (f(x),f(y))}$ в Декартова плоскость. В этом примере многогранник порядка состоит из всех точек в ${\displaystyle (x,y)}$-самолет с ${\displaystyle 0\leq x\leq y\leq 1}$. Это равнобедренный прямоугольный треугольник с вершинами в точках (0,0), (0,1) и (1,1).

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

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

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

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

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

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

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

Многогранник порядка линейный порядок это особый вид симплекс называется заказать симплекс или же орто-схема. Каждая точка единичный куб чьи координаты все различные, лежит в единственной из этих ортосхем, симплексе порядка для линейного порядка его координат. конгруэнтный друг к другу и (для заказов на ${\displaystyle n}$ элементы) есть ${\displaystyle n!}$ различных линейных порядков, объем симплекса каждого порядка ${\displaystyle 1/n!}$.^[2][3] В более общем смысле, порядковый многогранник может быть разбит на порядковые симплексы каноническим способом, с одним симплексом для каждого. линейное расширение соответствующего частично упорядоченного множества.^[2]Следовательно, объем любого многогранника порядка равен ${\displaystyle 1/n!}$ умноженное на количество линейных расширений соответствующего частично упорядоченного множества.^[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 \min(p(x),q(x))}$, а функция ${\displaystyle p\vee q}$ что отображает ${\displaystyle x}$ к ${\displaystyle \max(p(x),q(x))}$ обе также принадлежат многограннику порядка. ${\displaystyle \wedge }$ и ${\displaystyle \vee }$ придадим порядковому многограннику структуру непрерывного распределительная решетка, в которую вложена конечная дистрибутивная решетка из теоремы Биркгофа, т. е. каждый порядковый многогранник является распределительный многогранник. Дистрибутивные многогранники со всеми координатами вершин, равными 0 или 1, являются в точности многогранниками порядка.^[6]

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

1. Грётшель, Мартин; Юнгер, Михаэль; Райнельт, Герхард (1985), "Грани многогранника линейного упорядочения", Математическое программирование, 33 (1): 43–60, Дои:10.1007 / BF01582010, МИСТЕР  0809748
2. Стэнли, Ричард П. (1986), "Два многогранника посета", Дискретная и вычислительная геометрия, 1 (1): 9–23, Дои:10.1007 / BF02187680, МИСТЕР  0824105
3. Стэнли, Ричард (2011), Перечислительная комбинаторика, Том 1, второе издание, версия от 15 июля 2011 г. (PDF), стр. 571–572, 645
4. Брайтвелл, Грэм; Винклер, Питер (1991), "Подсчет линейных расширений", Заказ, 8 (3): 225–242, Дои:10.1007 / BF00383444, МИСТЕР  1154926
5. Биркофф, Гарретт (1937), «Кольца множеств», Математический журнал герцога, 3 (3): 443–454, Дои:10.1215 / S0012-7094-37-00334-X
6. Фельснер, Стефан; Кнауэр, Коля (2011), "Распределительные решетки, многогранники и обобщенные потоки", Европейский журнал комбинаторики, 32 (1): 45–59, Дои:10.1016 / j.ejc.2010.07.011, МИСТЕР  2727459. См., В частности, замечание 11, с. 53.