Monday, January 4, 2010

Теория частичных порядков

Изучаю последние несколько дней теорию частичных порядков [1] с ударением на следующие вопросы:
  1. Линейные расширения частичных порядков и их число для различных классов порядков.
  2. Инварианты графов сравнимости для соответствующих порядков.
Число линейных расширений данного линейного порядка является инвариантом графа сравнимости, также как и размерность Душника-Миллера.
Искал, но пока не нашел какие-либо описания такого параметра множества линейных расширений, как число линейных расширений с числом скачков (jump (setup) number) [2] или числом cтупенек (bump (stair) number) в заданном интервале. Известны задачи о нахождении перестановки с минимальным числом скачков (ступенек). Меня интересует число линейных расширений данного порядка с нулевым числом ступенек.

Кроме того, не нахожу ничего о выпуклых разбиениях симметрической группы.

1. Graham R.L. et al. Handbook of combinatorics Vol. 1.
2. Лозин В.В. E-свободные двудольные графы / Дискретный анализ и исследование операций, 2000.

No comments:

Post a Comment