4
$\begingroup$

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?

$\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$ Commented Feb 16, 2017 at 19:19

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\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$
    – karpasi
    Commented 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
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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