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

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

Многогранник порядка частичного порядка следует отличать от многогранника линейного порядка , многогранника, определенного из числа $n$ как выпуклая оболочка индикаторных векторов множеств ребер $n$-вершинные транзитивные турниры .

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

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

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

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

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

Вершины и фасеты

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

Фасеты : порядкового многогранника бывают трех типов

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

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

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

и

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

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

Сплошная решетка

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

Если две функции $p$ и $q$ оба принадлежат порядковому многограннику частично упорядоченного множества. $(S,\leq )$, то функция $p\wedge q$ это отображает $x$ к $\min(p(x),q(x))$,и функция $p\vee q$ это отображает $x$ к $\max(p(x),q(x))$ оба также принадлежат порядковому многограннику.Две операции $\wedge$ и $\vee$ придать порядковому многограннику структуру непрерывной дистрибутивной решетки , в которую вложена конечная дистрибутивная решетка теоремы Биркгофа.То есть каждый порядковый многогранник является дистрибутивным многогранником . Дистрибутивные многогранники, у которых все координаты вершин равны 0 или 1, являются в точности многогранниками порядка.