О числе максимальных шпернеровых семейств типа (K,K+1)

Аннотация: 

В статье исследуются свойства семейств F подмножеств конечного множества S={a1,a2,...,an} попарно несравнимых по бинарному отношению включения с двумя ограничениями: а) для любо-го A∉F найдется множество A'∈F, такое, что либо A⊂A', либо A'⊂A, б) для любого A∈F  |A|∈{k,k+1}. Приводится рекурсивный алгоритм построения всех таких семейств. Существенно улучшается ранее полученная автором верхняя оценка для числа всех семейств. Устанавливается также, что каждое такое семейство F однозначно определяется некоторым своим минимальным собственным фрагментом F',F'⊂F.

Прикрепленный файлРазмер
Cтатья (стр. 49-55)361.27 кб