Размер заказа

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

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

Формальное определение [ править ]

Размерностью ч.у. P является наименьшее целое число t, для которого существует семейство

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

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

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

Альтернативное определение размерности порядка - это минимальное количество общих заказов, такое что P встраивается в их продукт с покомпонентным упорядочением, то есть тогда и только тогда, когда для всех i ( Hiraguti 1955 , Milner & Pouzet 1990 ).${\ displaystyle x \ leq y}$${\ Displaystyle х_ {я} \ leq y_ {я}}$

Реализаторы [ править ]

Семейство линейных порядков на X называется реализатором ч.у.набора P = ( X , < _P ), если ${\ displaystyle {\ mathcal {R}} = (<_ {1}, \ dots, <_ {t})}$

${\ Displaystyle <_ {P} = \ bigcap {\ mathcal {R}}}$,

это означает, что для любых x и y в X , x < _P y именно тогда, когда x < ₁ y , x < ₂ y , ... и x < _t y . Таким образом, эквивалентное определение размерности ч.у.м. P - это «наименьшая мощность реализатора P ».

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

Пример [ править ]

Пусть n будет положительным целым числом, и пусть P будет частичным порядком на элементах a _i и b _i (для 1 ≤ i ≤ n ), в котором a _i ≤ b _j всякий раз, когда i ≠ j , но никакие другие пары не сопоставимы. В частности, a _i и b _i несравнимы в P ; P можно рассматривать как ориентированную форму графа короны . На рисунке показан порядок этого типа для n = 4.

Затем для каждого i любой реализатор должен содержать линейный порядок, который начинается со всех a _j, кроме a _i (в некотором порядке), затем включает b _i , затем a _i и заканчивается всеми оставшимися b _j . Это так, потому что, если бы существовал реализатор, который не включал такой порядок, то пересечение заказов этого реализатора имело бы a _i, предшествующее b _i , что противоречило бы несравнимости a _i и b _i в P. И наоборот, любое семейство линейных порядков, которое включает по одному порядку этого типа для каждого i, имеет P в качестве пересечения. Таким образом, P имеет размерность ровно n . Фактически, P известен как стандартный пример ч.у. размерности n и обычно обозначается S _n .

Второй размер заказа [ править ]

Частичные порядки с размерностью второго порядка можно охарактеризовать как частичные порядки, граф сопоставимости которых является дополнением к графу сопоставимости другого частичного порядка ( Baker, Fishburn & Roberts, 1971 ). То есть P является частичным порядком с размерностью два тогда и только тогда, когда существует частичный порядок Q на одном и том же наборе элементов, такой, что каждая пара x , y различных элементов сравнима ровно в одном из этих двух частичных порядков. Если P реализуется двумя линейными расширениями, то частичный порядок Q, дополнительный к Pможет быть реализован путем обращения одного из двух линейных удлинений. Следовательно, графы сопоставимости частичных порядков размерности два - это в точности графы перестановок , графы, которые сами по себе являются графами сопоставимости и дополняют графы сопоставимости.

Частичные порядки размерности два включают последовательно-параллельные частичные порядки ( Valdes, Tarjan & Lawler, 1982 ). Это как раз те частичные порядки, диаграммы Хассе которых имеют рисунки доминирования , которые могут быть получены путем использования позиций в двух перестановках реализатора в качестве декартовых координат.

Вычислительная сложность [ править ]

За полиномиальное время можно определить, имеет ли данное конечное частично упорядоченное множество размерность порядка не больше двух, например, путем проверки, является ли граф сопоставимости частичного порядка графом перестановок. Тем не менее, для любого к  ^ 3, это NP-полной , чтобы проверить , является ли размер порядка не превосходит к ( Yannakakis 1 982 ).

Положения диаграмм заболеваемости [ править ]

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

Для полного графа с n вершинами размерность порядка расположения инцидентности равна ( Hoşten & Morris 1999 ). Отсюда следует, что все простые графы с n вершинами имеют множества инцидентности с порядковой размерностью .${\ Displaystyle \ Theta (\ журнал \ журнал п)}$${\ Displaystyle О (\ журнал \ журнал п)}$

k -мерность и 2-мерность [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

• Бейкер, К.А.; Fishburn, P .; Робертс, Ф. С. (1971), «Частичные порядки измерения 2», Сети , 2 (1): 11–28, DOI : 10.1002 / net.3230020103.
• Душник, Бен; Миллер, EW (1941), "Частично упорядоченные множества", Американский журнал математики , 63 (3): 600-610, DOI : 10,2307 / 2371374 , ЛВП : 10338.dmlcz / 100377 , JSTOR  2371374.
• Хирагути, Тосио (1955), «Об измерении заказов» (PDF) , Научные отчеты Университета Канадзавы , 4 (1): 1–20, MR  0077500.
• Хоштен, Серкан; Моррис, Вальтер Д., младший (1999), "Размерность порядка полного графа", дискретная математика , 201 (1-3): 133-139, DOI : 10.1016 / S0012-365X (98) 00315-X , MR  1687882.
• Милнер, ЕС; Pouzet, М. (1990), "Замечание о размерности посета", заказ , 7 (1): 101-102, DOI : 10.1007 / BF00383178 , МР  1086132 , S2CID  123485792.
• Шнайдера, W. (1989), "планарные графы и размеры посетом" Order , 5 (4): 323-343, DOI : 10.1007 / BF00353652 , S2CID  122785359.
• Троттер, Уильям Т. (1992), Комбинаторика и частично упорядоченные множества: теория размерностей , Серия Джонса Хопкинса в математических науках, Издательство Университета Джона Хопкинса, ISBN 978-0-8018-4425-6.
• Вальдес, Якобо; Тарджан, Роберт Э .; Лоулер, Евгений Л. (1982), "Признание серии параллельных орграфы", SIAM журнал по вычислениям , 11 (2): 298-313, DOI : 10,1137 / 0211023.
• Yannakakis, Михалис (1982), "Сложность проблемы размерности частичного порядка", SIAM журнал на алгебраических и дискретных методов , 3 (3): 351-358, DOI : 10,1137 / 0603036.