Введение

Математическая мера для частичных порядков

В математике размерность частично упорядоченного множества (посета) — это наименьшее число полных порядков, пересечение которых порождает данный частичный порядок. Это понятие также иногда называют размерностью порядка или размерностью Дюшника — Миллера частичного порядка. Размерностью порядка впервые занимались; для более детального изучения этой темы, чем представлено здесь, обратитесь к [ссылка].

Пример

Пусть n – положительное целое число, и пусть P – частичный порядок на элементах ai и bi (для 1 ≤ i ≤ n), в котором ai ≤ bj, когда i ≠ j, но никакие другие пары не сравнимы. В частности, ai и bi несравнимы в P; P можно рассматривать как ориентированную форму графа короны. На иллюстрации показан порядок этого типа для n = 4. Тогда, для каждого i, любой реализатор должен содержать линейный порядок, который начинается со всех aj, кроме ai (в некотором порядке), затем включает bi, затем ai, и заканчивается всеми оставшимися bj. Это связано с тем, что если бы существовал реализатор, не включающий такой порядок, то пересечение порядков этого реализатора имело бы ai, предшествующее bi, что противоречило бы несравнимости ai и bi в P. И наоборот, любая семья линейных порядков, которая включает один порядок этого типа для каждого i, имеет P в качестве своего пересечения. Таким образом, размерность P равна ровно n. Фактически, P известен как стандартный пример частично упорядоченного множества размерности n и обычно обозначается Sn.

Второе измерение заказа

Частичные порядки с размерностью порядка два могут быть охарактеризованы как частичные порядки, граф сопоставимости которых является дополнением к графу сопоставимости другого частичного порядка. То есть, P является частичным порядком с размерностью порядка два тогда и только тогда, когда существует частичный порядок Q на том же множестве элементов, такой что каждая пара различных элементов x и y сопоставима ровно в одном из этих двух частичных порядков. Если P реализуется двумя линейными расширениями, то частичный порядок Q, дополнительный к P, может быть реализован путем обращения одного из этих двух линейных расширений. Следовательно, графы сопоставимости частичных порядков размерности два являются точно графами перестановок – графами, которые сами по себе являются графами сопоставимости и дополнениями к графам сопоставимости. Частичные порядки размерности два включают в себя последовательно-параллельные частичные порядки. Это именно те частичные порядки, чьи диаграммы Хассе имеют доминирующие рисунки, которые можно получить, используя позиции в двух перестановках реализатора в качестве декартовых координат.

Комплексность вычислений

Можно определить за полиномиальное время, имеет ли заданное конечное частично упорядоченное множество размерность порядка не более двух, например, путем проверки, является ли граф сопоставимости этого частичного порядка графом перестановок. Однако для любого k ≥ 3 задача проверки, не превышает ли размерность порядка k, является NP-полной.

Набор графиков частоты

Для любого неориентированного графа G инцидентный частично упорядоченный набор (poset) имеет вершины и ребра G в качестве своих элементов; в этом наборе x ≤ y, если либо x = y, либо x — вершина, y — ребро, и x является концом ребра y. Определенные типы графов могут быть охарактеризованы размерностью порядка их инцидентных частично упорядоченных наборов: граф является путь-графом тогда и только тогда, когда размерность порядка его инцидентного частично упорядоченного набора не превосходит двух, и согласно теореме Шнайдера он является планарным графом тогда и только тогда, когда размерность порядка его инцидентного частично упорядоченного набора не превосходит трех. Для полного графа на n вершинах размерность порядка инцидентного частично упорядоченного набора равна . Следовательно, все простые n-вершинные графы имеют инцидентные частично упорядоченные наборы с размерностью порядка .

k-мер и 2-мер

Обобщением понятия размерности является понятие k-размерности (обозначается), которое представляет собой минимальное число цепей длины не более k, в произведение которых можно вложить данный частичный порядок. В частности, 2-размерность порядка можно интерпретировать как размер наименьшего множества, в которое порядок может быть вложен в отношение включения.