Вебинар "О криптоморфизме между решетками подмножеств Дэвиса, атомистическими решетками, системами замкнутых множеств при выполнении аксиомы отделимости T1"

Во вторник, 15 ноября 2022 г. в 15.30 состоится вебинар по теме "О криптоморфизме между решетками подмножеств Дэвиса, атомистическими решетками, системами замкнутых множеств при выполнении аксиомы отделимости T1".

Докладчиком выступит Дмитрий Игнатов, заведующий научно-учебной лабораторией моделей и методов вычислительной прагматики, доцент департамента анализа данных и искусственного интеллекта факультета компьютерных наук, НИУ ВШЭ, Москва. 

Аннотация: В докладе пойдет речь о семействах замкнутых множеств (известных как семейства Мура) для случая, когда все одноэлементные множества семейства замкнуты. Задача порождения таких семейств для объектно-признаковых или транзакционных данных хорошо известна в майнинге данных как поиск частых (замкнутых) множеств товаров (Frequent Itemset Mining).  В частности, нами приводится количество таких строгих (включающих пустое множество) и нестрогих семейств для 6 элементов (признаков). Мы также приводим количество таких неэквивалентных семейств Мура относительно всех перестановок базового множества вплоть до n=6. Поиск в OEIS и существующей литературе показал совпадение найденных чисел (с учетом изоморфизма семейств) с числом решеток на основе объединения множеств, полученным Д.М. Дэвисом (последовательность OEIS A235604, до n=5), и c |L_n| (без учета изоморфизма) – числом атомистических решеток на n атомах, найденным С. Мейпс (до n=6), соответственно. Нами  установлено взаимно-однозначные соответствия между этими тремя типами решеток на основе соответствий Галуа и анализа формальных понятий (Formal Concept Analysis). Кратко обсуждаются два использованных перечислительных алгоритма, а также дополнительные результаты их работы наибольший размер семейства множеств без пересечений для n=6, наша гипотеза для n=7, верхняя граница числа атомистических решеток L_n и некоторые структурные свойства L_n, основанные на теории экстремальных решеток.

Оригинальная статья, послужившая основой для рассказа
Статья профессора Дэвиса
Туториал по анализу формальных понятий

Исследуемые автором последовательности OEIS: 
https://oeis.org/A334254
https://oeis.org/A334255
https://oeis.org/A235604
https://oeis.org/A355517

Диаграмма решетки L₄