Алгебро-логические методы в информатике и искусственный интеллект

Four-element generating sets with block count widths at most two in partition lattices

[Четырехэлементные порождающие множества с шириной блоков не более двух в решетках разбиений]

Gábor Czédli

University of Szeged, Bolyai Institute, Szeged, Hungary

Аннотация: Разбиения конечного множества образуют так называемую решетку разбиений. Хенрик Штриец доказал, что эта решетка имеет четырехэлементное порождающее множество; его статья была продолжена дюжиной других. Две недавние статьи автора показывают, что малые порождающие множества этих решеток могут быть применены в криптографии. Количество блоков разбиения — это количество его блоков. Дано четырехэлементное множество разбиений, перечислите количество блоков его элементов в порядке возрастания. Затем вычтите первое (т. е. наименьшее) количество блоков из всех четырех, чтобы получить компоненты четырехмерного вектора. Этот вектор и его последний компонент называются типом количества блоков и шириной количества блоков данного четырехэлементного множества. Существует ровно десять типов количества блоков шириной не более двух. В данном исследовании доказывается, что для любой решетки разбиений над конечным базовым множеством, содержащим не менее восьми элементов, каждый из десяти типов количества блоков шириной не более двух является типом количества блоков четырехэлементного порождающего множества решетки разбиений; более того, дается нижняя граница числа этих порождающих множеств.

Ключевые слова: решётка эквивалентностей, четырёхэлементное порождающее множество, решётка разбиений, множество малых порождающих множеств.

УДК: 512.62

MSC: 06B99, 06C10

Поступила в редакцию: 10.10.2024
Исправленный вариант: 18.11.2024
Принята в печать: 19.11.2024

Язык публикации: английский

DOI: 10.26516/1997-7670.2025.53.141