В математике , особенно в теории порядка , порядок интервалов для набора интервалов на действительной прямой - это частичный порядок, соответствующий их отношению приоритета слева направо - один интервал 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 , Руководство по эксплуатации 2652101 , S2CID 8677150.
- Фельснер, С. (1992), Интервальные порядки: комбинаторная структура и алгоритмы (PDF) , Ph.D. диссертация, Технический университет Берлина.
- Felsner, S .; Habib, M .; Möhring, RH (1994), "О взаимодействии между интервалом измерения и измерения" (PDF) , SIAM журнал по дискретной математике , 7 (1): 32-40, DOI : 10,1137 / S089548019121885X , MR 1259007.
- Фишберн, Питер К. (1970), "Непереходная индифферентность с интервалами неравного безразличия", Журнал математической психологии , 7 (1): 144-149, DOI : 10,1016 / 0022-2496 (70) 90062-3 , МР 0253942.
- Загира, Дон (2001), "инварианты Васильева и странная личность связаны с дедекиндовым этой-функцией", Топология , 40 (5): 945-960, DOI : 10.1016 / s0040-9383 (00) 00005-7 , MR 1860536.
дальнейшее чтение
- Фишберн, Питер (1985), интервальные порядки и интервальные графики: исследование частично упорядоченных множеств , Джон Вили