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

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

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

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

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

линейных расширений P y так, что для каждого x и y в P t x предшествует y в P тогда и только тогда, когда он предшествует во всех линейных расширениях, если такой существует . То есть,

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

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

Реализаторы

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

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

,

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

Можно показать, что любое непустое семейство R линейных расширений является реализатором конечного частично упорядоченного множества P тогда и только тогда, когда для каждой пары ( x , y ) из P y x < _i критической для некоторого порядка< _я в 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 любой реализатор должен содержать линейный порядок, который начинается со всех aj _, кроме ai _bi (в некотором порядке), затем включает в себя ai _и заканчивается всеми _затем оставшимися bj _, . Это так, потому что если бы существовал реализатор, который не включал такой порядок, то при пересечении приказов этого реализатора 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, может быть реализован путем обращения одного из двух линейных расширений. Следовательно, графы сравнимости частичных порядков размерности два представляют собой в точности графы перестановок , графы, которые сами по себе являются графами сравнимости и дополняют графы сравнимости.

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

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

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

Наборы инцидентностей графов

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

Для полного графа с n вершинами порядковая размерность ЧУИ инцидентности равна $\Theta (\log \log n)$ ( Хоштен и Моррис 1999 ). Отсюда следует, что все простые n -вершинные графы имеют ЧУ инцидентности с порядковой размерностью. $O(\log \log n)$ .

k -мерный и 2-мерный

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

См. также

Интервальное измерение

Ссылки

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