1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are right. I opened my PC with the aim to cut my extravagant proof, but you preceded me. I used many times the technique you indicate, but I am sometimes blind. $\endgroup$ – Panurge May 23 '16 at 5:13
  • $\begingroup$ I would be nice if such elementary facts were freely available on Internet... $\endgroup$ – Panurge May 23 '16 at 5:19
  • 1
    $\begingroup$ A detail : it is necessary to prove that $\mathcal{F}'$ is separating. $\endgroup$ – Panurge May 23 '16 at 15:36
  • 1
    $\begingroup$ If I'm not wrong, it is possible to ensure that $\mathcal{F}'$ is separating by choosing $x$ such that the number of members of $\mathcal{F}$ containing x is as large as possible. Then the proof given by Tony Huynh shows that an element of $U(\mathcal{F})$ other than $x$ cannot belong to every member of $\mathcal{F}$ containing $x$ and this implies that $\mathcal{F}'$ is separating. $\endgroup$ – Panurge May 23 '16 at 17:15
  • $\begingroup$ Perhaps the simplest thing to do is to note that the proof given by Tony Huynh also proves the generalization... $\endgroup$ – Panurge May 26 '16 at 19:07

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.