Geodesic
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/}
}
TY  - JOUR
AU  - Yu. A. Zuev
TI  - Maximal $k$-intersecting families of subsets and Boolean functions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 15
EP  - 26
VL  - 25
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_4_a1/
LA  - ru
ID  - DA_2018_25_4_a1
ER  - 
%0 Journal Article
%A Yu. A. Zuev
%T Maximal $k$-intersecting families of subsets and Boolean functions
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 15-26
%V 25
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_4_a1/
%G ru
%F 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/

[1] Yu. A. Zuev, Modern Discrete Mathematics: From Enumerative Combinatorics to Cryptography of the XXI Century, Librokom, Moscow, 2018 (Russian)

[2] A. D. Korshunov, “The number of $k$-nonseparated families of subsets of an $n$-element set ($k$-nonseparated Boolean functions). I. The case of even $n$ and $k=2$”, Diskretn. Anal. Issled. Oper. Ser. 1, 10:4 (2003), 31–69 (Russian) | MR | Zbl

[3] A. D. Korshunov, “The number of $k$-nonseparated families of subsets of an $n$-element set ($k$-nonseparated Boolean functions of $n$ variables). II. The case of odd $n$ and $k=2$”, Diskretn. Anal. Issled. Oper. Ser. 1, 12:1 (2005), 12–70 (Russian) | MR | Zbl

[4] A. D. Korshunov, “The number of $k$-nonseparated families of subsets of an $n$-element set ($k$-nonseparated Boolean functions of $n$-variables). III. The case of $k\geq3$ and arbitrary $n$”, Diskretn. Anal. Issled. Oper. Ser. 1, 12:3 (2005), 60–73 (Russian) | MR | Zbl

[5] R. G. Nigmatullin, The Complexity of Boolean Functions, Nauka, Moscow, 1991 (Russian)

[6] A. A. Sapozhenko, “On the number of antichains in multilevelled ranked posets”, Discrete Math. Appl., 1:2 (1991), 149–169 | DOI | MR | Zbl

[7] Erdös P., Kleitman D. J., “Extremal problems among subsets of a set”, Discrete Math., 8 (1974), 281–294 | DOI | MR | Zbl

[8] Erdös P., Ko C., Rado R., “Intersection theorems for systems of finite sets”, Q. J. Math., 12 (1961), 313–320 | DOI | MR | Zbl

[9] Kleitman D. J., “On Dedekind's problem: The number of monotone Boolean functions”, Proc. Amer. Math. Soc., 21:3 (1969), 677–682 | MR | Zbl