2
$\begingroup$

If I'm not wrong, it is easy to prove the following statement:

If $n \leq 4$ is a natural number, if $\mathcal{F}$ is a union-closed family of non-empty sets, if the universe of $\mathcal{F}$ (i.e. the union of all members of $\mathcal{F}$) has exactly $n$ elements, if $\mathcal{F}$ is separating (i.e. for any two distinct elements $x, y$ in the universe of $\mathcal{F}$, there is a member of $\mathcal{F}$ that contains exactly one of $x, y$), then $\mathcal{F}$ has at least $n$ members and if it has exactly $n$ members, these members have a common element.

Is there a more general statement (for $n \geq 5$) in the literature ? Thanks in advance for the answers.

$\endgroup$
1
  • 1
    $\begingroup$ I proved a similar statement, and then later found a slightly more general version in a paper of LoFaro (1994 Union closed sets conjecture, improved bounds) which may be of interest. Given $F$ separating on a finite base set $\bigcup F$ of $n\gt 0$ elements, if $F$ has $4n-2$ sets or fewer then one of its elements appears in at least half the members of $F$. Gerhard "This Wasn't The Only Time" Paseman, 2016.05.18. $\endgroup$ Commented May 18, 2016 at 22:25

1 Answer 1

7
$\begingroup$

The same statement in fact holds for all $n$.

Theorem. Let $\mathcal{F}$ be a separating, union-closed family of non-empty sets on the ground set $[n]$. Then $|\mathcal{F}| \geq n$, and if $|\mathcal{F}|=n$, then there exists some $i \in [n]$ such that $i \in F$ for all $F \in \mathcal{F}$.

Proof. Rename elements of $[n]$ so that if $i<j$, then $j$ occurs in at least as many sets as $i$ does. Since $\mathcal{F}$ is separating, this implies that if $i<j$, there exists a set $F_{i,j} \in \mathcal{F}$ such that $i \notin F_{i,j}$ and $j \in F_{i,j}$. For all $i \in [n-1]$, define $F_i=\bigcup_{j=i+1}^n F_{i,j}$. Note that all $F_i$ belong to $\mathcal{F}$, since $\mathcal{F}$ is union-closed. Furthermore, if $k<\ell$, then $F_k \neq F_\ell$ since $\ell \in F_k$ but $\ell \notin F_\ell$. Together with the set $[n]$, this gives at least $n$ sets in $\mathcal{F}$. Moreover, if $|\mathcal{F}|=n$, then $\mathcal{F}=\{F_1, \dots, F_{n-1}\} \cup \{[n]\}$, and all these sets contain the element $n$.

$\endgroup$

You must log in to answer this question.

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