Порядок включения

В математической области теории порядка порядок включения — это частичный порядок , который возникает как отношение подмножества -включения в некоторой коллекции объектов. Проще говоря, каждое частично упорядоченное множество P = ( X ,妻) является ( изоморфным ) порядком включения (точно так же, как каждая группа изоморфна группе перестановок – см. теорему Кэли ). Чтобы убедиться в этом, сопоставьте каждому элементу x из X множество

$X_{\leq (x)}=\{y\in X\mid y\leq x\};$

тогда транзитивность ≤ гарантирует, что для всех a и b в X мы имеем

$X_{\leq (a)}\subseteq X_{\leq (b)}{\text{ precisely when }}a\leq b.$

Могут быть наборы $S$ мощности ​ меньше $|X|$ такой, что P изоморфен порядку включения на S . Размер наименьшего возможного S называется 2- P. мерным размером

Несколько важных классов ЧУМ возникают как порядки включения для некоторых естественных коллекций, таких как булева решетка Q ^н , который представляет собой совокупность всех 2 ^н подмножества набора из n -элементов, порядки с интервальным содержанием , которые в точности являются порядками размерности порядка не более двух, и порядки с размерностью n , которые представляют собой порядки содержания для наборов из n -блоков, закрепленных в начале координат . Другие порядки сдерживания, которые интересны сами по себе, включают в себя круговые порядки , возникающие из-за дисков на плоскости, и угловые порядки .

См. также

• Теорема Биркгофа о представлении
• Граф пересечений
• Интервальный порядок

Ссылки

• Фишберн, ПК; Троттер, WT (1998). «Геометрические приказы о сдерживании: обзор». Заказ . 15 (2): 167–182. дои : 10.1023/А:1006110326269 . S2CID   14411154 .
• Санторо Н., Сидни Дж. Б., Сидни С. Дж. и Уррутия Дж. (1989). «Геометрическое сдерживание и частичные порядки». SIAM Journal по дискретной математике . 2 (2): 245–254. CiteSeerX   10.1.1.65.1927 . дои : 10.1137/0402021 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )