Интервальный порядок

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

The $(2+2)$ частичное положение (черная диаграмма Хассе) не может быть частью интервального порядка: если a находится полностью справа от b , а d перекрывается как с a , так и с b , а c полностью справа от d , то c должен быть полностью справа от b (светло-серый край).

В математике , особенно в теории порядка , порядок интервалов для набора интервалов на реальной линии — это частичный порядок , соответствующий их отношению старшинства слева направо: один интервал I ₁ считается меньшим, чем другой I ₂ , если I ₁ находится полностью левее I ₂ . Более формально, счетное частичное множество $P=(X,\leq )$является интервальным порядком тогда и только тогда, когда существует биекция из $X$набору реальных интервалов, так $x_{i}\mapsto (\ell _{i},r_{i})$, такой, что для любого $x_{i},x_{j}\in X$ у нас есть $x_{i}<x_{j}$ в $P$ именно когда $r_{i}<\ell _{j}$.

Такие частично-множества могут быть эквивалентно характеризуются как те, у которых нет индуцированного подмножества изоморфного , пары двухэлементных цепей , другими словами, как $(2+2)$-свободные позы . Полностью записано, это означает, что для любых двух пар элементов $a>b$ и $c>d$ нужно иметь $a>d$ или $c>b$.

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

Дополнение ( интервального графа сравнимости порядка $X$, ≤) это график интервалов $(X,\cap )$.

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

Интервальные порядки и размерности

Нерешенная задача по математике :

В чем сложность определения размерности интервального порядка?

(еще нерешенные задачи по математике)

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

Связанным параметром является размерность интервала , которая определяется аналогично, но в терминах интервальных порядков, а не линейных порядков. Таким образом, интервальная размерность частично упорядоченного множества $P=(X,\leq )$ является наименьшим целым числом $k$ для которых существуют интервальные порядки $\preceq _{1},\ldots ,\preceq _{k}$ на $X$ с $x\leq y$ именно когда $x\preceq _{1}y,\ldots ,$ и $x\preceq _{k}y$. Интервальный размер заказа никогда не превышает его размерность.

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

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

Такие инволюции по полудлине имеют обычную производящую функцию

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

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