3
$\begingroup$

A family of sets $\mathcal{F} \subseteq 2^{[n]}$ is called union-closed if for any two sets $A,B \in \mathcal{F}$, $A \cup B \in \mathcal{F}$. We say that $\mathcal{F} \subseteq 2^{[n]}$ is sparse if the average size of a set in $\mathcal{F}$ is less than $n/2$. $\mathbb{E}_{A \in \mathcal{F}}|A| < n/2$.

Let's denote by $f(n)$ the number of sparse union-closed families of subsets of $[n]$. Any good bounds on $f(n)$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Of course all subfamilies of $2^{[n/2-1]}$ are sparse.

For any $k$, the number of union-closed families $\mathcal F\subseteq 2^{[k]}$ is $u(k)=2^{\binom{k}{\lfloor k/2\rfloor}(1+o(1))}$ (link), where $\binom{k}{[k/2]}\in\Theta(2^k/\sqrt{k})$ (link).

Apply this with $k=n/2$ and we get some bounds:

$\log_2 u(n) \in \Theta (2^n/\sqrt{n})$,

$\log_2 f(n) \in \Omega (2^{n/2}/\sqrt{n/2})$, and $%\log_2\log_2 U_n=n-\frac12\log_2 n+O(1)$ $%\log_2\log_2 S_n\ge \frac12 n -\frac12\log_2 n+O(1)$ $$\frac12\le\lim_{n\to\infty}\frac{\log_2\log_2 f(n)}n\le \lim_{n\to\infty}\frac{\log_2\log_2 u(n)}n = 1.$$

$\endgroup$
3
  • $\begingroup$ not all subfamilies of $2^{[n/2-1]}$ are union-closed $\endgroup$ Commented Oct 31, 2020 at 13:39
  • $\begingroup$ @mathworker21 correct; so I'm substituting $[n/2-1]$ for $n$. Maybe I should write it more explicitly $\endgroup$ Commented Oct 31, 2020 at 15:17
  • $\begingroup$ @mathworker21 updated now $\endgroup$ Commented Nov 1, 2020 at 0:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .