RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2018 Volume 25, Issue 4, Pages 15–26 (Mi da906)

Maximal $k$-intersecting families of subsets and Boolean functions

Yu. A. Zuev

Bauman Moscow State Technical University, 5 Vtoraya Baumanskaya St., 105005 Moscow, Russia

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 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.

UDC: 519.71

Received: 11.12.2017
Revised: 16.03.2018

DOI: 10.17377/daio.2018.25.602


 English version:
Journal of Applied and Industrial Mathematics, 2018, 12:4, 797–802

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024