Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:4, 797–802
Volume 25, No 4, 2018, P. 15-26
UDC 519.71
Yu. A. Zuev
Maximal $k$-intersecting families of subsets and Boolean functions
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.
DOI: 10.17377/daio.2018.25.602
Yury A. Zuev 1
1. Bauman Moscow State Technical University,
5 Vtoraya Baumanskaya St., 105005 Moscow, Russia
e-mail: 79851965730@yandex.ru
Received 11 December 2017
Revised 16 March 2018
References
[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, No. 4, 31–69, 2003 [Russian].
[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, No. 1, 12–70, 2005 [Russian].
[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 \ge 3$ and arbitrary $n$, Diskretn. Anal. Issled. Oper., Ser. 1, 12, No. 3, 60–70, 2005 [Russian].
[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, Diskretn. Mat., 1, No. 2, 110–128, 1989 [Russian]. Translated in Discrete Math. Appl., 1, No. 2, 149–169, 1991.
[7] P. Erdös and D. J. Kleitman, Extremal problems among subsets of a set, Discrete Math., 8, 281–294, 1974.
[8] P. Erdös, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Q. J. Math., Oxf. II. Ser., 12, 313–320, 1961.
[9] D. J. Kleitman, On Dedekind’s problem: The number of monotone Boolean functions, Proc. Am. Math. Soc., 21, No. 3, 677–682, 1969.
