zhChinese    enEnglish
  ПМ-ПУ  » Структура » Преподаватели  » Ногин В.Д.  » Проблема

Проблема

Частично упорядоченное множество (ч.у.м.) - это множество X, на котором задан частичный порядок R\,, т.е. рефлексивное, транзитивное и антисимметричное бинарное отношение. В ч.у.м. имеется по крайней мере одна пара a,b \in X\, несравнимых элементов, для которых как соотношение (a,b) \in R\,, так и соотношение (b,a) \in R\, является ложным.

Согласно теореме Шпильрайна всякий частичный порядок, заданный на некотором множестве, всегда может быть продолжен до линейного порядка (т.е. такого, который не содержит несравнимых пар элементов) на том же самом множестве. Следует заметить, что подобное продолжение частичного порядка, как правило, неединственно.

В 1948 году американцами Душником и Миллером было предложено понятие размерности частично упорядоченного множества как минимального числа линейных продолжений, пересечение которых совпадает с исходным частичным порядком. По определению, размерность линейно упорядоченного множества равна единице. Чем больше размерность ч.у.м., тем более (в определенном смысле) это множество отличается от линейно упорядоченного множества.

Рассмотрим ч.у.м., состоящее из конечного числа элементов. Если из данного ч.у.м. удалить один какой-то элемент, то его размерность либо сохраняется, либо уменьшается ровно на единицу. Если размерность ч.у.м. равна m\, и при удалении всякого его элемента размерность уменьшается, то такое множество называют m\,-несводимым. Подобого рода множества представляют собой наиболее сложные с точки зрения теории размерности образования.

Напомним, что элемент a \in X\, данного ч.у.м. называется максимальным, если из выполнения соотношения (b,a) \in R\, при некотором b\in X\, всегда следует a=b\,.

Проблема (1990, [III, 9], [III, 14]. Определить наибольшее возможное значение f(m,n)\, числа максимальных элементов m\,-несводимого ч.у.м., состоящего из  n \ge 4\, элементов.