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

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

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

В математика, особенно теория порядка, то интервальный порядок для набора интервалов на реальной прямой частичный заказ соответствующие их отношению приоритета слева направо - один интервал, я₁, считаясь меньшим, чем другой, я₂, если я₁ полностью слева от я₂. Более формально посеть ${\displaystyle P=(X,\leq )}$ является интервальным порядком тогда и только тогда, когда существует биекция из ${\displaystyle X}$ к набору реальных интервалов, поэтому ${\displaystyle x_{i}\mapsto (\ell _{i},r_{i})}$, что для любого ${\displaystyle x_{i},x_{j}\in X}$ у нас есть${\displaystyle x_{i}<x_{j}}$ в ${\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 P=(X,\leq )}$ наименее целое число ${\displaystyle k}$ для которых существуют интервальные заказы ${\displaystyle \preceq _{1},\ldots ,\preceq _{k}}$ на ${\displaystyle X}$ с ${\displaystyle x\leq y}$ когда именно ${\displaystyle x\preceq _{1}y,\ldots ,}$ и ${\displaystyle x\preceq _{k}y}$. Размерность интервала заказа никогда не превышает размерность его порядка,^[3].

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

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

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

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

Коэффициент ${\displaystyle t^{n}}$ в расширении ${\displaystyle F(t)}$ дает количество немаркированных интервальных порядков размера ${\displaystyle n}$. Последовательность этих чисел (последовательность A022493 в OEIS ) начинается

1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, …

Примечания

1. Фишберн (1970)
2. Фельснер (1992, п. 47)
3. Фельснер, Хабиб и Меринг (1994).
4. Bousquet-Mélou et al. (2010)
5. Загир (2001)

Рекомендации

• Буске-Мелу, Мирей; Клаэссон, Андерс; Герцоги, Марк; Китаев, Сергей (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), Интервальные порядки и интервальные графики: исследование частично упорядоченных множеств, Джон Вили