Порядок интервалов - Википедия - Interval order

Частичный порядок на множестве {а, б, c, d, е, ж} проиллюстрировано его Диаграмма Хассе (слева) и набор интервалов, который его представляет (справа).

В ${ Displaystyle (2 + 2)}$ poset (черная диаграмма Хассе) не может быть частью интервального порядка: если а полностью прав б, и d перекрывается с обоими а и б, и c полностью прав d, тогда c должен быть полностью прав б (светло-серый край).

В математика, особенно теория порядка, то интервальный порядок для набора интервалов на реальной прямой частичный заказ соответствующие их отношению приоритета слева направо - один интервал, я₁, считаясь меньшим, чем другой, я₂, если я₁ полностью слева от я₂. Более формально посеть ${ Displaystyle Р = (Х, Leq)}$ является интервальным порядком тогда и только тогда, когда существует биекция из ${ displaystyle X}$ к набору реальных интервалов, поэтому ${ displaystyle x_ {i} mapsto ( ell _ {i}, r_ {i})}$, что для любого ${ displaystyle x_ {i}, x_ {j} in X}$ у нас есть${ displaystyle x_ {i}$ в ${ displaystyle P}$ когда именно ${ displaystyle r_ {i} < ell _ {j}}$Такие позы могут быть эквивалентно охарактеризованы как те, у которых нет индуцированного подмножества. изоморфный к паре двухэлементных цепи, другими словами, как ${ Displaystyle (2 + 2)}$-бесплатные посец.^[1]

Подкласс интервальных порядков, полученный ограничением интервалов до интервалов единичной длины, поэтому все они имеют вид ${ displaystyle ( ell _ {i}, ell _ {i} +1)}$, именно полупорядки.

В дополнять из график сопоставимости интервального порядка (${ displaystyle X}$, ≤) - это интервальный график ${ displaystyle (X, cap)}$.

Не следует путать интервальные приказы с интервалами сдерживания, которые являются приказы о включении на отрезках вещественной прямой (эквивалентно порядки измерение ≤ 2).

Порядок интервалов и размер

Нерешенная проблема в математике: Какова сложность определения размерности интервального порядка? (больше нерешенных задач по математике)

Важным параметром частичных заказов является размер заказа: размер частичного порядка ${ displaystyle P}$ наименьшее количество линейные порядки чье пересечение ${ displaystyle P}$. Для интервальных заказов размер может быть сколь угодно большим. И хотя проблема определения размерности общих частичных порядков известна как NP-жесткий, определение размерности интервального порядка остается проблемой неизвестной вычислительная сложность.^[2]

Связанный параметр измерение интервала, который определяется аналогично, но в терминах интервальных порядков вместо линейных. Таким образом, размерность интервала частично упорядоченного множества ${ Displaystyle Р = (Х, Leq)}$ наименее целое число ${ displaystyle k}$ для которых существуют интервальные заказы ${ Displaystyle prevq _ {1}, ldots, prevq _ {k}}$ на ${ displaystyle X}$ с ${ displaystyle x leq y}$ когда именно ${ Displaystyle х prevq _ {1} у, ldots,}$ и ${ Displaystyle х prevq _ {k} y}$. Размерность интервала заказа никогда не превышает размерность его порядка,^[3].

Комбинаторика

Помимо того, что они изоморфны ${ Displaystyle (2 + 2)}$-свободные посеты, немаркированные интервальные заказы на ${ Displaystyle [п]}$ также находятся в биекции с подмножеством без фиксированной точки инволюции на заказанных наборах с мощность ${ displaystyle 2n}$.^[4] Это инволюции без так называемых вложений слева или справа, где для любой инволюции${ displaystyle f}$ на ${ displaystyle [2n]}$, левое вложение исан ${ Displaystyle я в [2n]}$ такой, что ${ Displaystyle я <я + 1 <е (я + 1) <е (я)}$ а правильное вложение - это ${ Displaystyle я в [2n]}$ такой, что${ Displaystyle е (я) <е (я + 1) <я <я + 1}$.

Такие инволюции, согласно полудлине, имеют обычная производящая функция ^[5]

${ displaystyle F (t) = sum _ {n geq 0} prod _ {i = 1} ^ {n} (1- (1-t) ^ {i}).}$

Коэффициент ${ Displaystyle т ^ {п}}$ в расширении ${ Displaystyle F (т)}$ дает количество немаркированных интервальных порядков размера ${ displaystyle n}$. Последовательность этих чисел (последовательность 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), Интервальные порядки и интервальные графики: исследование частично упорядоченных множеств, Джон Вили