Интервальный порядок
В математике , особенно в теории порядка ,порядок интервалов для набора интервалов на реальной линии— это частичный порядок, соответствующий их отношению старшинства слева направо: один интервал I 1 считается меньшим, чем другой I 2 , если I 1 находится полностью левее I 2 .Более формально, счетное частичное множество является интервальным порядком тогда и только тогда, когдасуществует биекция из набору реальных интервалов,так ,такой, что для любого у нас есть в именно когда .
Такие частично-множества могут быть эквивалентнохарактеризуются как те, у которых нет индуцированного подмножества изоморфного , пары двухэлементных цепей , другими словами, как -свободные позы. [1] Полностью записано, это означает, что для любых двух пар элементов и нужно иметь или .
Подкласс интервальных порядков, полученный путем ограничения интервалов единицей длины, поэтому все они имеют вид , это именно полупорядки .
Дополнение ( графа сравнимости интервального порядка , ≤)это график интервалов .
Интервальные порядки не следует путать с порядками содержания интервалов, которые представляют собой порядки включения интервалов на реальной линии (эквивалентно порядкам размерности ≤ 2).
Интервальные порядки и размерности [ править ]
В чем сложность определения размерности интервального порядка?
Важным параметром частичных заказов является размер заказа : размер частичного заказа. — наименьшее число линейных порядков, пересечение которых . Для интервальных порядков размерность может быть сколь угодно большой. И хотя проблема определения размерности общих частичных порядков, как известно, NP-трудна , определение размерности интервального порядка остаётся проблемой неизвестной вычислительной сложности . [2]
Связанным параметром является размерность интервала , которая определяется аналогично, но в терминах интервальных порядков, а не линейных порядков. Таким образом, интервальная размерность частично упорядоченного множества является наименьшим целым числом для которых существуют интервальные порядки на с именно когда и . Интервальный размер заказа никогда не превышает его размерность. [3]
Комбинаторика [ править ]
Помимо того, что он изоморфен -бесплатные посеты,немаркированные интервальные ордера на также находятся в биекциис подмножеством без фиксированной точки инволюций на упорядоченных множествах с мощностью . [4] Этоинволюции без так называемых вложений левых или правых соседей, где для любой инволюции на , левое вложениеа такой, что и правильное вложение - это такой, что .
Такие инволюции по полудлине имеют обычную производящую функцию [5]
Коэффициент в расширении дает количество немаркированных интервальных порядков размера . Последовательность этих чисел (последовательность A022493 в OEIS ) начинается
- 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, …
Примечания [ править ]
Ссылки [ править ]
- Буске-Мелу, Мирей ; Классон, Андерс; Дьюкс, Марк; Китаев, Сергей (2010), «(2+2) свободные частично упорядоченные множества, последовательности восхождения и шаблоны, избегающие перестановок», Журнал комбинаторной теории , серия A, 117 (7): 884–909, arXiv : 0806.0666 , doi : 10.1016/j .jcta.2009.12.007 , MR 2652101 , S2CID 8677150 .
- Фельснер, С. (1992), Интервальные порядки: комбинаторная структура и алгоритмы (PDF) , доктор философии. диссертация, Технический университет Берлина .
- Фельснер, С.; Хабиб, М.; Меринг, Р.Х. (1994), «О взаимодействии интервального измерения и размерности» (PDF) , SIAM Journal on Discrete Mathematics , 7 (1): 32–40, doi : 10.1137/S089548019121885X , MR 1259007 .
- Фишберн, Питер К. (1970), «Нетранзитивное безразличие с неравными интервалами безразличия», Журнал математической психологии , 7 (1): 144–149, doi : 10.1016/0022-2496(70)90062-3 , MR 0253942 .
- Загер, Дон (2001), «Инварианты Васильева и странное тождество, связанное с эта-функцией Дедекинда», Topology , 40 (5): 945–960, doi : 10.1016/s0040-9383(00)00005-7 , MR 1860536 .
Дальнейшее чтение [ править ]
- Фишберн, Питер (1985), Интервальные порядки и интервальные графы: исследование частично упорядоченных множеств , Джон Уайли