Maximal k-Intersecting Families of Subsets and Boolean Functions
- Authors: Zuev Y.A.1
-
Affiliations:
- Bauman Moscow State Technical University, Vtoraya Baumanskaya ul. 5
- Issue: Vol 12, No 4 (2018)
- Pages: 797-802
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213137
- DOI: https://doi.org/10.1134/S1990478918040191
- ID: 213137
Cite item
Abstract
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 maximalk-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 fork > 2.
About the authors
Yu. A. Zuev
Bauman Moscow State Technical University, Vtoraya Baumanskaya ul. 5
Author for correspondence.
Email: 79851965730@yandex.ru
Russian Federation, str. 1, Moscow, 105005
Supplementary files
