How many collections of subsets of {1,2,...,n} are closed under the superset operation? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:08:19Z http://mathoverflow.net/feeds/question/41839 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper How many collections of subsets of {1,2,...,n} are closed under the superset operation? Dave Doty 2010-10-11T22:55:18Z 2011-07-17T17:08:19Z <p>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 <em>valid</em> 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$?</p> <p>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</p> <p>$\mathcal{C} = \{ \emptyset, \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 1 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 2 \}, \{ 1,2 \} \}$,</p> <p>$\mathcal{C} = \{ \{ 1,2 \} \}$, and</p> <p>$\mathcal{C} = \{ \}$.</p> <p>So rather than the answer being $2^{2^2} = 16$, there are only 6 valid collections.</p> <p>Thank you in advance.</p> http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper/41845#41845 Answer by Aaron Meyerowitz for How many collections of subsets of {1,2,...,n} are closed under the superset operation? Aaron Meyerowitz 2010-10-11T23:35:17Z 2010-10-11T23:35:17Z <p>Such a set is uniquely determined by its minimal members which form an <em>antichain</em>. The first few values and some links are <a href="http://www.research.att.com/~njas/sequences/A000372" rel="nofollow">A000372</a> in the OEIS</p> http://mathoverflow.net/questions/41839/how-many-collections-of-subsets-of-1-2-n-are-closed-under-the-superset-oper/70551#70551 Answer by Gil Kalai for How many collections of subsets of {1,2,...,n} are closed under the superset operation? Gil Kalai 2011-07-17T14:10:25Z 2011-07-17T17:08:19Z <p>This is a famous problem known as the "Dedekind Problem", and it was posed by Dedekind in 1897. The <a href="http://en.wikipedia.org/wiki/Dedekind_number" rel="nofollow">Wikipedea article</a> 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 <a href="http://www.ams.org/journals/proc/1969-021-03/S0002-9939-1969-0241334-6/S0002-9939-1969-0241334-6.pdf" rel="nofollow">paper of Kleitman</a> gives some of the history, and <a href="http://www.google.co.il/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CBYQFjAA&amp;url=http%253A%252F%252Fciteseerx.ist.psu.edu%252Fviewdoc%252Fdownload%253Fdoi%253D10.1.1.103.1883%2526rep%253Drep1%2526type%253Dpdf&amp;rct=j&amp;q=dedekind%2520problem%2520kahn&amp;ei=TOsiTtTFOMma-waiuoyrAw&amp;usg=AFQjCNF6ORU-UmN92pZRFwMHss1iSyAJgQ" rel="nofollow">this paper by Kahn</a> 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}}$.</p> <p>Kleitman &amp; Markowsky (1975). gave the asymptotic behavior of $\log M(n)$. They showed that $log M(n)$ behave asumptotically like ${{n} \choose {n/2}}$. <a href="http://www.google.co.il/url?sa=t&amp;source=web&amp;cd=1&amp;ved=0CBYQFjAA&amp;url=http%253A%252F%252Fciteseerx.ist.psu.edu%252Fviewdoc%252Fdownload%253Fdoi%253D10.1.1.103.1883%2526rep%253Drep1%2526type%253Dpdf&amp;rct=j&amp;q=dedekind%2520problem%2520kahn&amp;ei=TOsiTtTFOMma-waiuoyrAw&amp;usg=AFQjCNF6ORU-UmN92pZRFwMHss1iSyAJgQ" rel="nofollow">The paper by Kahn</a> that we already mentioned gives a simpler entropy based proof.</p> <p>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 <a href="http://www.amazon.co.uk/Dedekinds-functionals-Dedekinda-granichnykh-funktsionalov/dp/5922111175" rel="nofollow">this book</a>.) Sapozhenko's method turned out to be very important, e.g., in the result by <a href="http://www.nd.edu/~dgalvin1/pdf/phasetransition.pdf" rel="nofollow">Galvin and Kahn</a> on the threshold behavior of the d-dimensional hard core model. </p>