Том 25, номер 4, 2018 г., Стр. 15-26

УДК 519.71
Зуев Ю. А.
Максимальные $k$-неразделенные семейства подмножеств и булевы функции

Аннотация:
Семейство подмножеств $n$-элементного множества называется $k$-неразделённым, если пересечение любых $k$ подмножеств семейства непусто. Семейство называется максимальным $k$-неразделённым, если к нему невозможно добавить ни одного подмножества, не нарушив условия $k$-неразделённости. Во взаимно однозначном соответствии с каждым семейством подмножеств находится булева функция, единичные наборы которой являются характеристическими векторами подмножеств. Показано, что семейство подмножеств будет максимальным $2$-неразделённым тогда и только тогда, когда соответствующая ему булева функция является монотонной самодвойственной. Представлена асимптотика для числа таких семейств. Указан также ряд свойств булевых функций, соответствующих $k$-неразделённым семействам, при $k > 2$.
Библиогр. 9.

Ключевые слова: $k$-неразделённое семейство подмножеств, монотонная самодвойственная булева функция, слой булева куба.

DOI: 10.17377/daio.2018.25.602

Зуев Юрий Анатольевич ¹
1. Московский гос. технический университет им. Н. Э. Баумана,
2-я Бауманская ул., 5, стр. 1, 105005 Москва, Россия
е-mail: 79851965730@yandex.ru

Статья поступила 11 декабря 2017 г.
Исправленный вариант — 16 марта 2018 г.

Литература

[1] Зуев Ю. А. Современная дискретная математика: от перечислительной комбинаторики до
криптографии XXI века. М.: Либроком, 2018.

[2] Коршунов А. Д. Число $k$-неразделённых семейств подмножеств $n$-элементного множества ($k$-неразделённых булевых функций). Ч. 1. Случай чётных $n$ и $k = 2$ // Дискрет. анализ и исслед. операций. Сер. 1. 2003. Т. 10, № 4. С. 31–69.

[3] Коршунов А. Д. Число $k$-неразделённых семейств подмножеств $n$-элементного множества ($k$-неразделённых булевых функций). Ч. 2. Случай нечётных $n$ и $k = 2$ // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, № 1. С. 12–70.

[4] Коршунов А. Д. Число $k$-неразделённых семейств подмножеств $n$-элементного множества ($k$-неразделённых булевых функций). Ч. 3. Случай $k > 2$ и произвольных $n$ // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, № 3. С. 60–73.

[5] Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991.

[6] Сапоженко А. А. О числе антицепей в многослойных ранжированных множествах // Дискрет. математика 1989. Т. 1, вып. 2. С. 110–128.

[7] Erdös P., Kleitman D. J. Extremal problems among subsets of a set // Discrete Math. 1974. Vol. 8. P. 281–294.

[8] Erdös P., Ko C., Rado R. Intersection theorems for systems of finite sets // Q. J. Math. 1961. Vol. 12. P. 313–320.

[9] Kleitman D. J. On Dedekind’s problem: The number of monotone Boolean functions // Proc. Amer. Math. Soc. 1969. Vol. 21, No. 3. P. 677–682.