Порядок интервалов - Interval order - Wikipedia
В математика, особенно теория порядка, то интервальный порядок для набора интервалов на реальной прямой частичный заказ соответствующие их отношению приоритета слева направо - один интервал, я1, считаясь меньшим, чем другой, я2, если я1 полностью слева от я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) свободные позы, последовательности восхождения и паттерн, избегающий перестановок», Журнал комбинаторной теории, Серия А, 117 (7): 884–909, arXiv:0806.0666, Дои:10.1016 / j.jcta.2009.12.007, МИСТЕР 2652101.
- Фельснер, С. (1992), Интервальные заказы: комбинаторная структура и алгоритмы (PDF), Кандидат наук. диссертация, Технический университет Берлина.
- Felsner, S .; Habib, M .; Меринг, Р. Х. (1994), «О взаимодействии между измерением интервала и измерением» (PDF), Журнал SIAM по дискретной математике, 7 (1): 32–40, Дои:10.1137 / S089548019121885X, МИСТЕР 1259007.
- Фишберн, Питер С. (1970), «Непереходное безразличие с неравными интервалами безразличия», Журнал математической психологии, 7 (1): 144–149, Дои:10.1016/0022-2496(70)90062-3, МИСТЕР 0253942.
- Загир, Дон (2001), «Инварианты Васильева и странное тождество, связанное с эта-функцией Дедекинда», Топология, 40 (5): 945–960, Дои:10.1016 / с0040-9383 (00) 00005-7, МИСТЕР 1860536.
дальнейшее чтение
- Фишберн, Питер (1985), Интервальные порядки и интервальные графики: исследование частично упорядоченных множеств, Джон Вили