Jump to content

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

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

В математике , особенно в теории порядка ,порядок интервалов для набора интервалов на реальной линии— это частичный порядок, соответствующий их отношению старшинства слева направо: один интервал I 1 считается меньшим, чем другой I 2 , если I 1 находится полностью левее I 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) свободные частично упорядоченные множества, последовательности восхождения и шаблоны, избегающие перестановок», Журнал комбинаторной теории , серия 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), Интервальные порядки и интервальные графы: исследование частично упорядоченных множеств , Джон Уайли
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c865041383d5c6ff11cd056b9daa95c9__1695567360
URL1:https://arc.ask3.ru/arc/aa/c8/c9/c865041383d5c6ff11cd056b9daa95c9.html
Заголовок, (Title) документа по адресу, URL1:
Interval order - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)