Tony Huynh gave a nice answer to a question I asked here :


[Number of members of a separating union-closed family whose universe has given cardinality](https://mathoverflow.net/questions/239194/number-of-members-of-a-separating-union-closed-family-whose-universe-has-given-c)


The answer shows in fact that if $\mathcal{F}$ is a finite union-closed family of finite sets, if $n$ denotes he cardinality of the universe $U(\mathcal{F})$ of $\mathcal{F}$ (union of all members of $\mathcal{F}$)


(1) there is always an element contained in at least $n$ members of $\mathcal{F}$;


(2) generally, if a union-closed and separating family has only a finite number of members, then these members are finite.


I think that (1) can be strengthened in the following manner :


(3) Let $\mathcal{F}$ be a finite union-closed and separating family of (finite) sets, let $n$ denote the cardinality of $U(\mathcal{F})$. For any $r \in \{1, \ldots , n \}$, there are $r$ members of $\mathcal{F}$ whose intersection has cardinality at least $n-r+1$.


In order to allow checking of my statements, I sketch a proof.


In first instance, don't assume finiteness and don't assume that $\mathcal{F}$ is separating. For $x$ and $y$ in $U(\mathcal{F})$, define "$x$ pursues $y$" (in $\mathcal{F}$) as meaning "each member of $\mathcal{F}$ containing $y$ contains $x$". For an element $x$ of $U(\mathcal{F})$ and a subset $S$ of $U(\mathcal{F})$, define "$x$ pursues $S$" (in $\mathcal{F}$) as meaning "each member of $\mathcal{F}$ containing $S$ contains $x$. The relation "pursues" between elements of $U(\mathcal{F})$ is transitive. $\mathcal{F}$ is separating if and only if two distinct elements of $U(\mathcal{F})$ never pursue eachother.


Lemma 1. Let be $\mathcal{F}$ a family of sets, pairwise union-closed. Let $x, a\_{1}, \ldots , a\_{k}$ be elements of $U(\mathcal{F})$ , with $k \geq 1$. If $x$ pursues $\{ a\_{1}, \ldots , a\_{k} \}$ (in $\mathcal{F}$), then $x$ pursues at least one of the elements $a\_{1}, \ldots , a\_{k}$.


Lemma 2. Let be $\mathcal{F}$ a family of sets, pairwise union-closed and separating. Let $S$ be a finite subset of $U(\mathcal{F})$, with $\vert S \vert \geq 2$. There is at least an element $x$ of $S$ such that $x$ doesn't pursue $S \setminus \{x \}$.


(In view of lemma 1, the thesis means that there is at least an element $x$ of $S$ that pursues no element of $S \setminus \{x \}$. If there was no such $x$, it would lead to a loop contradicting the fact that $\mathcal{F}$ is separable.)


Lemma 3. Let $\mathcal{F}$ be a finite union-closed and separating family of (finite) sets, let $n$ denote the cardinality of the universe $U(\mathcal{F})$ of $\mathcal{F}$ (union of all members of $\mathcal{F}$). For any $r \in \{1, \ldots , n \}$, there are $r$ members of $\mathcal{F}$ whose intersection has cardinality at least $n-r+1$.


Sketch of the proof. Induction on $r$. By induction hypothesis, there exist $r-1$ members $X\_{1}, \ldots , X\_{r-1}$ whose intersection contains a set $Y = \{{y\_1}, \ldots , {y\_s} \}$ of cardinality $s = n-r+2$. Assume (falsely) that for every $i \in \{1, \ldots , s\}$, $X{\_1}, \ldots , X{r\_1}$ are the only members of $\mathcal{F}$ containing $Y \setminus \{y\_{i} \}$. Then for every $i \in \{1, \ldots , s\}$, $y\_{i}$ pursues $Y \setminus \{y\_{i} \}$, which contradicts lemma 2.


I presume that Lemma 3 is already in the literature. Could anybody give a reference ? Thanks in advance.



Intersection of members in a separating union-closed family of sets
Statement (3) is easier to prove directly by induction on $n=|U(\mathcal{F})|$.


The base case $n=1$ is trivial.


To make the induction step for $n>1$, let $x\in U(\mathcal{F})$ be an element that belongs to at least $n$ sets from $\mathcal{F}$, such element exists by (1). Consider two cases:


* if $r=n$, take any $n$ sets from $\mathcal{F}$ containing $x$;
* if $r<n$, then construct a new family $\mathcal{F}'$ by taking all sets from $\mathcal{F}$ containing $x$ and remove $x$ from each of them. Since $U(\mathcal{F})\in \mathcal{F}$, we have $U(\mathcal{F}')=U(\mathcal{F})\setminus\{x\}$ and thus $|U(\mathcal{F}')|=n-1$. By induction, there exists a collection of $r$ sets from $\mathcal{F}'$ whose intersection has cardinality at least $n-r$. Add $x$ to each member of this collection to get a collection of sets from $\mathcal{F}$ whose intersection has cardinality at least $n+1-r$, as required.


