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
    $\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$ – Gerhard Paseman May 18 '16 at 22:25
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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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