Решетки максимальных антицепей

Хоменко Анастасия, Кеелус Милена Научный руководитель: Александр Леонидович Попович Сентябрь 2023

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

Работа посвящена исследованию свойств конструкции представления конечных решеток решетками максимальных антицепей. В первых двух главах приведены необходимые определения и примеры понятий частично упорядоченного множества, решетки, антицепи и максимальной антицепи. Для нашего исследования важна теорема о том, что любая конечная решетка представима как решетка максимальных антицепей некоторого ч.у. множества. Это порождает вопросы о том, единственное ли такое представление (ответ: нет), существуют ли среди таких представлений «наиболее информативные».

В данной работе мы обнаружили прекрасное свойство решеток максимальных антицепей: если высота ч.у. множества достаточно высока (больше 1), то в нем можно выделять подмножества максимальных антицепей, в некотором смысле «близкие» друг к другу. Данные подмножества образуют интервалы в решетке, а вся решетка распадается в «склеенную сумму» (определение будет дано в работе) таких интервалов, подобно одеялу сшитому из лоскутов.

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

Среди решеток выделяют класс дистрибутивных решеток, который играет центральную роль в теории решеток (по утверждению Г. Гретцера). Нам удалось показать, что всякая конечная дистрибутивная решетка является склеенной суммой булевых решеток (т.е. решеток подмножеств множеств), причем вся информация об этой сумме может быть удобно получена из конструкции решетки максимальных антицепей подходящего ч.у. множества

Решетки часто являются инструментом визуализации качественных данных: понятий, качеств, состояний, событий. Разложение диаграммы в "одеяло из лоскутов"— в склеенную сумму — помогает лучшим образом группировать информацию, вводить классификации, строить автоматическую навигацию в больших иерархиях объектов.

Цель работы: найти алгоритм, который позволяет по данной решетке строить ч.у. множество, решётка максимальных антицепей которого изоморфна данной и имеет максимальную высоту.

Задачи: 1) Изучить базовые факты теории решеток и строго доказать их;

2) Найти алгоритм, который позволяет по данной решетке строить ч.у. множество, решётка максимальных антицепей которого изоморфна данной и имеет максимальную высоту. Доказать найденный алгоритм;

3) Изучить полученную конструкцию склеенной суммы на дистрибутивных решетках.

Методы: сбор информации, анализ, наблюдение.

Результаты:
1) Теорема 1 (общеизвестная). Максимальные антицепи образуют решетку.
2) Теорема 2 (общеизвестная). Всякая конечная решетка изоморфна решетке максимальных антицепей некоторого ч.у. множества.
3) Теорема 3. Решетка максимальных антицепей ч.у. множества высоты больше 1 раскладывается в нетривиальную склеенную сумму.
4) Теорема 4. Найденный алгоритм позволяет по решетке строить ч.у. множество максимальной высоты, решетка максимальных антицепей которого изоморфна данной.
5) Теорема 5. Всякая конечная дистрибутивная решетка раскладывается в склеенную сумму булевых, причем все параметры склейки задаются максимальными антицепями ч.у. множества элементов решетки, неразложимых в объединение.

Литература

[1] G. Birkhoff (1984) Lattice theory.
[2] G. Gr¨atzer (1982) General Lattice Theory.
[3] G. Markowsky (2001) An overview of the poset of irreducibles.
[4] M. Morvan (1996) Simplicial Elimination Schemes, Extremal Lattices and Maximal Antichain Lattices

• Цели
• Задачи
• Актуальность
• Результаты
• Применение
• Оборудование