|
This article is cited in 2 scientific papers (total in 2 papers)
The number of families of subsets that are closed with respect to intersections
V. B. Alekseev
Abstract:
Let $\alpha(n)$ be the number of families of subsets of an $n$-element set having the property:
for every two subsets of the family, their intersection belongs to the family as well. In this article it is proved that $\log_2\alpha(n)\sim C_n^{[n/2]}$ as $n\to\infty$. It follows from this that the same result is also valid for some other structures, in particular for the number of all possible closure operations on an $n$-element set. These results are obtained as a corollary of the analogous result as $n\to \infty$ and $k=o(\sqrt n/\log_2^2n)$ for the number of families of subsets of an $n$-element set which satisfy the condition: if $k$ one-element extensions of a subset $A$ belong to the family, then $A$ belongs to the family as well. Since there is a correspondence between families of subsets and functions of logic algebra, these results establish also asymptotics of the logarithm for the number of functions of the logic algebra of $n$ variables with the corresponding properties.
Received: 15.11.1988
Citation:
V. B. Alekseev, “The number of families of subsets that are closed with respect to intersections”, Diskr. Mat., 1:2 (1989), 129–136
Linking options:
https://www.mathnet.ru/eng/dm915 https://www.mathnet.ru/eng/dm/v1/i2/p129
|
Statistics & downloads: |
Abstract page: | 765 | Full-text PDF : | 423 | References: | 1 | First page: | 3 |
|