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

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

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

В математике , особенно в теории порядков , порядок интервалов для набора интервалов на действительной прямой — это частичный порядок , соответствующий их отношению старшинства слева направо: один интервал, I ₁ , считается меньшим другого, I ₂ , если I ₁ полностью левее I ₂ . Более формально, счетное частично упорядоченное множество является порядком интервалов тогда и только тогда, когда существует биекция из в набор действительных интервалов, поэтому , такой, что для любого мы имеем в точно тогда, когда . ${\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}}$

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

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

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

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

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

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

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

(еще нерешенные проблемы по математике)

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

Связанный параметр — это размерность интервала , которая определяется аналогично, но в терминах порядков интервала вместо линейных порядков. Таким образом, размерность интервала частично упорядоченного множества — это наименьшее целое число, для которого существуют порядки интервала на с точно тогда, когда и . Размерность интервала порядка никогда не превышает его размерности порядка. ^[3] ${\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}$

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

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

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

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

Примечания

1. Фишберн (1970)
2. Фелснер (1992, стр. 47)
3. Фельснер, Хабиб и Мёринг (1994).
4. Буске-Мелу и др. (2010)
5. Загир (2001)

Ссылки

• Буске-Мелу, Мирей ; Клаэссон, Андерс; Дьюкс, Марк; Китаев, Сергей (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), «Инварианты Васильева и странное тождество, связанное с эта-функцией Дедекинда», Топология , 40 (5): 945–960, doi : 10.1016/s0040-9383(00)00005-7 , MR  1860536.

Дальнейшее чтение

• Фишберн, Питер (1985), Интервальные порядки и интервальные графы: исследование частично упорядоченных множеств , Джон Уайли