Maximal $k$-intersecting families of subsets and Boolean functions
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 15-26
Voir la notice de l'article provenant de la source Math-Net.Ru
A family of subsets of an $n$-element set is $k$-intersecting if the intersection of every $k$ subsets in the family is nonempty. A family is maximal $k$-intersecting if no subset can be added to the family without violating the $k$-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets. We show that a family of subsets is maximal $2$-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established for $k>2$. Bibliogr. 9.
Keywords:
k-intersecting family of subsets, monotone selfdual Boolean function, layer of Boolean cube.
@article{DA_2018_25_4_a1,
author = {Yu. A. Zuev},
title = {Maximal $k$-intersecting families of subsets and {Boolean} functions},
journal = {Diskretnyj analiz i issledovanie operacij},
pages = {15--26},
publisher = {mathdoc},
volume = {25},
number = {4},
year = {2018},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DA_2018_25_4_a1/}
}
Yu. A. Zuev. Maximal $k$-intersecting families of subsets and Boolean functions. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 15-26. http://geodesic.mathdoc.fr/item/DA_2018_25_4_a1/