Заказать многогранник

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

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

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

Частично упорядоченное множество — это пара , где — произвольное множество и бинарное отношение на парах его элементов , которое является рефлексивным (для всех , ), антисимметричным (для всех, у которых не более одного из и может быть истинным) и транзитивным (для все , если и то ). ${\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}$

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

• Для каждого , . То есть сопоставляет элементы с единичным интервалом . ${\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}$

Например, для частично упорядоченного множества, состоящего из двух элементов и , причем в частичном порядке, функции от этих точек к действительным числам можно отождествить с точками на декартовой плоскости . В этом примере порядковый многогранник состоит из всех точек -плоскости с . Это равнобедренный прямоугольный треугольник с вершинами (0,0), (0,1) и (1,1). ${\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}$

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

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

Фасеты порядкового многогранника бывают трех типов: [ ^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)}$

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

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

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

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

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

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

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

Если две функции и обе принадлежат порядковому многограннику частично упорядоченного множества , то функция , которая отображает в , и функция , которая отображает обе , также принадлежат порядковому многограннику. Две операции и придают порядковому многограннику структуру непрерывной дистрибутивной решетки , в которую вложена конечная дистрибутивная решетка теоремы Биркгофа. То есть каждый порядковый многогранник является дистрибутивным многогранником . Дистрибутивные многогранники, у которых все координаты вершин равны 0 или 1, являются в точности многогранниками порядка. ^[6] ${\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 }$

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

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