×

Maximal \(k\)-intersecting families of subsets and Boolean functions. (Russian, English) Zbl 1438.05007

Diskretn. Anal. Issled. Oper. 25, No. 4, 15-26 (2018); translation in J. Appl. Ind. Math. 12, No. 4, 797-802 (2018).
Summary: 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\).

MSC:

05A16 Asymptotic enumeration
06E30 Boolean functions
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] P. Erdös, C. Ko, and R. Rado, “Intersection Theorems for Systems of Finite Sets,” Quart. J. Math. Oxford Ser. II, 12, 313-320 (1961). · Zbl 0100.01902
[2] P. Erdös and D. J. Kleitman, “Extremal Problems among Subsets of a Set,” DiscreteMath. 8, 281-294 (1974). · Zbl 0281.04002
[3] 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), 31-69 (2003). · Zbl 1032.05006
[4] 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), 12-70 (2005). · Zbl 1077.05007
[5] 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 ≥ 3 and Arbitrary n,” Diskretn. Anal. Issled. Oper. Ser. 1, 12 3, 60-70 (2005). · Zbl 1249.05015
[6] A. A. Sapozhenko, “On the Number of Antichains inMultilevelled Ranked Posets,” Diskretn. Mat. 1 2, 110-128 (1989) [DiscreteMath. Appl. 1 (2), 149-169 (1991)].
[7] Yu. A. Zuev, Modern Discrete Mathematics: From Enumerative Combinatorics up to Cryptography of the XXI Century (Librokom,Moscow, 2018) [in Russian].
[8] R. G. Nigmatullin, The Complexity of Boolean Functions (Nauka, Moscow, 1991) [in Russian]. · Zbl 0719.68024
[9] D. J. Kleitman, “On Dedekind’s Problem: The Number of Monotone Boolean Functions,” Proc. Amer. Math. Soc. 21 (3), 677-682 (1969). · Zbl 0186.30702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.