Размер заказа - Order dimension

Частичный порядок размерности 4 (показан как Диаграмма Хассе ) и четыре полных порядка, которые образуют реализатор для этого частичного порядка.

В математика, то измерение из частично заказанный набор (poset) - наименьшее количество общее количество заказов то пересечение из которых порождает частичный порядок. размер заказа или Размерность Душника – Миллера частичного заказа.Душник и Миллер (1941) размерность первого изученного заказа; для более подробного рассмотрения этого вопроса, чем здесь, см. Троттер (1992).

Формальное определение

Размер посета п наименьшее целое число т для которого существует семья

{ displaystyle { mathcal {R}} = (<_ {1}, dots, <_ {t})}

из линейные расширения из п так что для каждого Икс и у в п, Икс предшествует у в п тогда и только тогда, когда он предшествует у во всех линейных продолжениях. То есть,

{ displaystyle P = bigcap { mathcal {R}} = bigcap _ {i = 1} ^ {t} <_ {i}.}

Альтернативное определение размерности заказа - это минимальное количество общее количество заказов такой, что п встраивает к произведению этих общих заказов на покомпонентное упорядочивание, в котором ${ displaystyle x leq y}$ если и только если ${ Displaystyle х_ {я} leq y_ {я}}$ для всех я (Хирагути 1955 г., Милнер и Пузе, 1990 ).

Реализаторы

Семья ${ displaystyle { mathcal {R}} = (<_ {1}, dots, <_ {t})}$ линейных порядков на Икс называется реализатор посета п = (Икс, <_п) если

{ Displaystyle <_ {P} = bigcap { mathcal {R}}}

,

то есть для любого Икс и у в Икс,Икс <_п у именно когда Икс <₁ у, Икс <₂ у, ..., и Икс <_т уТаким образом, эквивалентное определение размерности ч.у. п "наименее мощность реализатора п."

Можно показать, что любое непустое семейство р линейных расширений является реализатором конечного частично упорядоченного множества п тогда и только тогда, когда для каждого критическая пара (Икс,у) из п, у <_я Икс для какого-то порядка <_я в р.

Пример

Позволять п - натуральное число, и пусть п быть частичным порядком на элементах а_я и б_я (для 1 ≤ я ≤ п) в котором а_я ≤ б_j в любое время я ≠ j, но никакие другие пары не сопоставимы. Особенно, а_я и б_я несравнимы в п; п можно рассматривать как ориентированную форму граф короны. На рисунке показан заказ этого типа для п = 4.

Затем для каждого я, любой реализатор должен содержать линейный порядок, начинающийся со всех а_j Кроме а_я (в некотором порядке), затем включает б_я, тогда а_я, и заканчивается всеми оставшимися б_j. Это потому, что, если бы существовал реализатор, который не включал такой приказ, то пересечение приказов этого реализатора имело бы а_я предшествующий б_я, что противоречило бы несравнимости а_я и б_я в п. И наоборот, любое семейство линейных порядков, которое включает по одному порядку этого типа для каждого я имеет п как его пересечение. Таким образом, п точно имеет размер п. Фактически, п известен как стандартный пример позиции измерения п, и обычно обозначается S_п.

Второй размер заказа

Частичные заказы с размерностью два можно охарактеризовать как частичные заказы, график сопоставимости это дополнять графа сопоставимости другого частичного порядка (Бейкер, Фишберн и Робертс, 1971 г. ). То есть, п является частичным порядком с размерностью два тогда и только тогда, когда существует частичный порядок Q на одном и том же наборе элементов, так что каждая пара Икс, у различных элементов сопоставимо ровно в одном из этих двух частичных порядков. Если п реализуется двумя линейными расширениями, то частичный порядок Q дополняет п может быть реализован путем обращения одного из двух линейных удлинений. Следовательно, графики сопоставимости частичных порядков размерности два - это в точности графы перестановок, графики, которые одновременно являются графиками сопоставимости и дополняют графики сопоставимости.

Частичные заказы размерности два включают последовательно-параллельные частичные порядки (Вальдес, Тарджан и Лоулер 1982 ). Это как раз те частичные заказы, Диаграммы Хассе имеют рисунки доминирования, который можно получить, используя позиции в двух перестановках реализатора в качестве декартовых координат.

Вычислительная сложность

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

Постановки заболеваемости на графах

В заболеваемость посет любой неориентированный граф грамм имеет вершины и ребра грамм как его элементы; в этой позе, Икс ≤ у если либо Икс = у или же Икс это вершина, у это край, и Икс конечная точка у. Определенные виды графов можно охарактеризовать порядковыми измерениями их наборов инцидентности: граф - это граф путей тогда и только тогда, когда размерность порядка его частичного множества инцидентности не превосходит двух, и в соответствии с Теорема Шнайдера это планарный граф тогда и только тогда, когда размерность его чугуна инцидентности не превосходит трех (Шнайдер 1989 ).

Для получения полного графика на п вершин, порядковая размерность ЧУМ инцидентности равна ${ Displaystyle Theta ( журнал журнал п)}$ (Хоштен и Моррис 1999 ). Отсюда следует, что все просто п-вершинные графы имеют позы инцидентности с размерностью порядка ${ Displaystyle О ( журнал журнал п)}$ .

k-размерный и 2-х мерный

Обобщением размерности является понятие k-размер (написано ${ displaystyle { textrm {dim}} _ {k}}$ ) - минимальное количество цепи длины не более k в чей продукт может быть встроен частичный порядок. В частности, двумерный порядок можно рассматривать как размер наименьшего набора, так что порядок встраивается в порядок включения на этом наборе.

Смотрите также

Размер интервала