Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 16 down vote accepted

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

share|improve this answer
    
It seems these are called <a href="en.wikipedia.org/wiki/Dedekind_number">Dedekind numbers</a>. Thank you! –  Dave Doty Oct 11 '10 at 23:43
2  
Sorry, the last comment did not parse the link correctly: they are called Dedekind numbers, en.wikipedia.org/wiki/Dedekind_number –  Dave Doty Oct 11 '10 at 23:44
    
Thanks again Aaron. Here is the paper that motivated this question: arxiv.org/abs/1011.3493. The relevant part is Proposition 4.3. I added an acknowledgement to you for your help. –  Dave Doty Nov 16 '10 at 7:56
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.