How many collections of subsets of {1,2,...,n} are closed under the superset operation? - MathOverflow

How many collections of subsets of {1,2,...,n} are closed under the superset operation?

2010-10-11T22:55:18Z

Say that I have the set $[n] = \{1,2,...,n\}$ and a collection $\mathcal{C} = \{ S_1, S_2, ..., S_k \}$ of subsets of $[n]$. Say that $\mathcal{C}$ is valid if it is closed under the superset operation; i.e., if $(S \in \mathcal{C} \wedge S \subseteq S' \subseteq [n]) \implies S' \in \mathcal{C}$. How many valid collections $\mathcal{C}$ are there, as a function of $n$?

Without the requirement to be closed under superset, the question is easier. There are $2^n$ subsets of $[n]$, and so there are $2^{2^n}$ ways to choose which of them belong to the collection. But not all collections are valid; for instance, if $n=2$, the valid collections are

$\mathcal{C} = \{ \emptyset, \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,

$\mathcal{C} = \{ \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,

$\mathcal{C} = \{ \{ 1 \}, \{ 1,2 \} \}$,

$\mathcal{C} = \{ \{ 2 \}, \{ 1,2 \} \}$,

$\mathcal{C} = \{ \{ 1,2 \} \}$, and

$\mathcal{C} = \{ \}$.

So rather than the answer being $2^{2^2} = 16$, there are only 6 valid collections.

Thank you in advance.

Answer by Aaron Meyerowitz for How many collections of subsets of {1,2,...,n} are closed under the superset operation?

2010-10-11T23:35:17Z

Such a set is uniquely determined by its minimal members which form an antichain. The first few values and some links are A000372 in the OEIS

Answer by Gil Kalai for How many collections of subsets of {1,2,...,n} are closed under the superset operation?

2011-07-17T14:10:25Z

This is a famous problem known as the "Dedekind Problem", and it was posed by Dedekind in 1897. The Wikipedea article has some information. There have been remarkable progress on understanding the asymptotic value of M(n) the number of antichains of sets from {1,2,...,n}. (This paper of Kleitman gives some of the history, and this paper by Kahn gives an updated history.) While $2^{{n}\choose {n/2}}$ is an obvious lower bound there is a beatiful 1966 proof by Hansel for the upperbound $3^{{n}\choose {n/2}}$.

Kleitman & Markowsky (1975). gave the asymptotic behavior of $\log M(n)$. They showed that $log M(n)$ behave asumptotically like ${{n} \choose {n/2}}$. The paper by Kahn that we already mentioned gives a simpler entropy based proof.

Amazingly, the asymptotic behavior of M(n) itself was discovered as well. in 1981, Korshunov , using an extremely complicated approach, gave asymptotics for M(n) itself. Simpler, though still difficult, arguments for Korshunov's and some related results were later given by Sapozhenko. (See eg this book.) Sapozhenko's method turned out to be very important, e.g., in the result by Galvin and Kahn on the threshold behavior of the d-dimensional hard core model.