Intersection of members in a separating union-closed family of sets

Question

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

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.

Answer 1

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.