A union-closed family $\cal{F} \subseteq \cal{P}([n])$ is a family such that for every $A,B \in \cal{F}$, $A \cup B \in \cal{F}$. Are there any reasonable approximations as to how many such families (of subsets of $[n]$) there are? Or more generally, suppose we take each set $A \subseteq [n]$ to our family $\cal{F}$ with probability $p$ for some $0<p<1$, what is the probability that $\cal{F}$ is union-closed?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Following 2,4,14,122 gives oeis.org/A102897 . It is clear that the sequence satisfies $a_{n+1} \leq a_n^2$ and that this can be refined with higher order terms. Gerhard "Might Find The Terms Later" Paseman, 2017.02.16. $\endgroup$– Gerhard PasemanCommented Feb 16, 2017 at 19:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
A dual order ideal $I$ (that is, if $F\in I$ and $G\supset F$ then $G\in I$) of the lattice $B_n$ of all subsets of $[n]$ is union-closed. The number of them is $2^{\binom{n}{\lfloor n/2\rfloor}(1+o(1))}$. See http://www.ams.org/journals/tran/1975-213-00/S0002-9947-1975-0382107-0/home.html for a somewhat stronger result. This gives a lower bound on the number of union-closed families that I suspect is not far from the truth.
answered Feb 16, 2017 at 14:57
-
$\begingroup$ Thanks for the answer. I knew about the Dedekind numbers already, this is where I got the idea to ask the same for union-closed families, which as you say include all monotone increasing families (dual order ideals). Maybe a way to prove a similar upper bound would be to say that for a given antichain $C$, there are not so many union-closed families whose set of minimal elements is exactly $C$. Especially if $|C|$ is close to ${n \choose n/2}$, which is true for most antichains. $\endgroup$– karpasiCommented Feb 16, 2017 at 16:36
-
$\begingroup$ For each antichain $C$ there is exactly one union-closed family (aka Upset) whose collection of minimal elements is $C.$ $\endgroup$ Commented Feb 16, 2017 at 17:01
-
$\begingroup$ @AaronMeyerowitz I disagree. For example, in a 3-element set, the antichain $C=\{\{a,b\},\{c\}\}$ is the collection of minimal elements of the union-closed family $\{\{a,b\},\{c\},\{a,b,c\}\}$, and also of the larger union-closed families obtained by throwing in $\{a,c\}$ or $\{b,c\}$ or both. $\endgroup$ Commented Feb 16, 2017 at 17:30
-
$\begingroup$ @Andreas Yes you are right. An Upset (closed under supersets) is union-closed but but not vice-versa (as I had incorrectly claimed). And each antichain (of course) determines a unique upset. $\endgroup$ Commented Feb 16, 2017 at 21:05
$\begingroup$
$\endgroup$
So it seems like, as expected, the number is $2^{(1+o(1)){n \choose n/2}}$. Unfortunately, the paper proving it is in russian, by V.B. Alekseev:
http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=915&option_lang=eng
I haven't found any proofs written in english for this.