Literature about a property of union closed families?

Question

Trying to solve a problem, I fell on the following statement :

If $k$ and $r$ are natural numbers such that $r \leq k$, if a union closed family of sets ("union closed" means that the union of two sets from the family is always a member of the family) has at least ${k \choose r} + 1$ members with cardinality $r$, then this family has at least two members with cardinality $\geq k$.

I think I have a proof. Could anybody disprove this statement or indicate a mention of it in the literature ? Thanks in advance.

Edit: Perhaps I should say why I'm interested in this question. In a comment about a blogpost of Timothy Gowers,

https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/

Thomas Bloom noted that if F is a union-closed family with $m$ members, then Frankl's conjecture "trivially implies that, for every $k\leq \log_2 m$, there exists some $k$-set which has abundancy at least $1/2^k$." (In other words, there is a $k$-set contained in at least $m/2^k$ members of F.)

He added: "Note that the other extremal case, when $k=\log_2m$, is trivially true."

Now, if $k$ denotes the largest integer such that $2^{k} \leq m$ and if $k$ is not exactly $\log_2m$, then the "other extremal case" is not so trivial (for me, in any case), but it results (without use of Frankl's conjecture) from the statement in my question.

Edit: Perhaps it is better that I prove that the above statement implies Thomas Brown's first step towards Frankl's conjecture.

Le $m > 0$ be a natural number, let $k$ denote the largest integer such that $2^{k} \leq m$. The case where $m = 2^{k}$ being trivial, assume that $m > 2^{k}$. Let $F$ be a union-closed family of sets with $m$ members. Thomas Brown's first step is the following statement :

There are two members of $F$ whose intersection has at least $k$ elements. (Since $F$ is union-closed, it amounts to say that $F$ has at least two members with cardinality $\geq k$. Indeed, if $X$ and $Y$ are two members with cardinality $\geq k$, we can assume that $Y$ is not a subset of $X$. Then $X$ and $X \cup Y$ are two distinct members of $F$ whose intersection has cardinality $\geq k$.)

Assume it is false. (Denying hypothesis.) Thus $F$ has at least $m-1$ members with cardinality $< k$. Since $m > 2^{k}$, there are at least $2^{k}$ members of $F$ with cardinality $\leq k-1$. For each $r \leq k-1$, let $n_{r}$ denote the number of members of $F$ with cardinality $r$. Our last result expresses that $\sum_{=0}^{k-1} n_{r} \geq 2^{k}$. If for each $r$, we had $n_{r} \leq {k \choose r}$, then we would have $\sum_{r=0}^{k-1} {k \choose r} \geq 2^{k}$, i.e. $2^{k}-1 \geq 2^{k}$, which is false. Thus there is at least an $r \leq k-1$ such that the number $n_{r}$ of members of $F$ with cardinality $r$ is $> {k \choose r}$. By Petrov's theorem (i.e. the first statement in this post, which Fedor Petrov proved in an elegant manner on this thread), this implies that $F$ has a least two members with cardinality $\geq k$. So the denying hypothesis contradicts itself.

Answer 1

This is similar to your proof but without induction.

We prove that there are at least 3 such sets. For $r=k$ this is clear, so assume that $k>r$. Consider our $\binom{k}{r}+1$ $r$-sets. Call an element $v\in V$ appropriate if $v$ belongs to at most $\binom{k-1}{r-1}$ our sets. Then there exist at least $\binom{k}{r}+1-\binom{k-1}{r-1}=\binom{k-1}{r}+1$ our sets not containing $v$. Their union contains at least $k$ elements, and does not contain $v$. Now I claim that between any $k$ elements $x_1,\dots,x_k$ there exists an appropriate element $v$. Indeed, if not, then total number of pairs (our $r$-set $A$, $x_i\in A$) is at least $k(\binom{k-1}{r-1}+1)>r (\binom{k}{r}+1)$, a contradiction. So, we may find appropriate element $v$, the union $U$ of our sets not containing $v$ has cardinality at least $k$. Thus there exists appropriate $u\in U$ and the union of our sets which do not contain $u$ is a third set after $V,U$.

I wonder whether bound 3 may be further improved (for some values of $k,r$, of course for $k=r$ it can not.)

Answer 2

Here is my proof.

Lemma. Let $X_{1}, \ldots , X_{s}$ distinct sets, with nonempty union, let $l$ a natural number such that $l \leq s$ and assume that for all distinct indices $i_{1}, \ldots , i_{l}$ in $\{1, \ldots s \}$, $X_{i_{1}} \cup \ldots \cup X_{i_{l}}$ is equal to the whole union $X_{1} \cup \ldots \cup X_{s}$.

Then one can find $s+1-l$ sets among $X_{1}, \ldots , X_{s}$ that have an element in common.

Proof of the lemma. Take a natural number $m$ with the same properties as $l$, but minimal. Since the whole union $X_{1} \cup \ldots \cup X_{s}$ is nonempty by hypothesis, $m \geq 1$. By minimality of $m$, we can choose $i_{1}, \ldots , i_{m-1}$ in $\{1, \ldots s \}$ such that $X_{i_{1}} \cup \ldots \cup X_{i_{m-1}}$ is not equal to the whole union $X_{1} \cup \ldots \cup X_{s}$. Choose an element $x$ not in $X_{i_{1}} \cup \ldots \cup X_{i_{m-1}}$. Let $j$ be any index not in $\{i_{1}, \ldots , i_{m-1}\}$. Since $m$ has the same properties as $l$, $X_{i_{1}} \cup \ldots \cup X_{i_{m1}} \cup X_{j}$ is equal to the whole union $X_{1} \cup \ldots \cup X_{s}$. Thus, for every $j$ not in $\{i_{1}, \ldots , i_{m-1}\}$, $x$ is in $X_{j}$. Since there are $s+1-m \geq s+1-l$ such indices $j$, we have proved he lemma.

Statement in the opening post. If $k$ and $r$ are natural numbers such that $r \leq k$, if a union closed family of sets ("union closed" means that the union of two sets from the family is always a member of the family) has at least ${k \choose r} + 1$ members with cardinality $r$, then this family has at least two members with cardinality $\geq k$.

Proof. Induction on $r$. It is trivially true for $r=0$ (the hypothesis is impossible in this case). Let $X_{1}, \ldots , X_{s}$ distinct sets, with $s = {k \choose r} + 1$. Let $F$ denote the union-closed family generated by these sets. We have to prove that $F$ has at least two members with cardinality $\geq k$. Assume it is false (denying hypothesis). Let $V$ denote the union of the sets. Then $V$ has cardinalty at least $k+1$ (since it has more than ${k \choose r}$ subsets with cardinality $r$). In view of our denying hypothesis, $V$ is the only member of $F$ with cardinality at least $k$. The thesis is trivially true for $k=r$, thus we can assume $k\geq r+1$. The union of ${k-1 \choose r} + 1$ members of $V$ wih cardinality $r$ has cardinality at least $k$ (same reasoning as for the cardinality of $V$), thus, in view of the unicity of $V$, the union of ${k-1 \choose r} + 1$ members of $V$ wih cardinality $r$ is always equal to $V$. By the lemma, applied to the sets $X_{1}, \ldots X_{s}$, one can find

${k \choose r} + 2 - ({k-1 \choose r} + 1) = {k-1 \choose r-1} + 1$ sets $X_{i}$ whith a common element $x$. The ${k-1 \choose r-1} + 1$ sets $X_{i} \setminus \{x\}$ are of cardinality $r-1$. By induction hypothesis, the union-closed family generated by these sets has at least two members with cardinality at least $k-1$, thus the union-closed family generated by the correspondings $X_{i}$ has at least two members with cardinality at least $k$. Thus the denying hypothesis contradicts itself.

This proof seems a bit complicated to me, and I hope I made no errors...

Answer 3

So, Fedor Petrov gave an excellent proof and Thomas Brown's first step towards Frankl's conjecture is proved. In order to prove the first half of the second step, it would be sufficient to prove the following statement : if $r$ and $k'$ are two natural numbers such that $r \leq k'$, the union-closed family generated by ${k'+1 \choose r} + 1$ sets with cardinality $r$ has three members whose intersection is of cardinality at least $k'$.

The proof of this new statement seems more difficult...

(In order to prove that his new statement is sufficient for proving the first half of Thomas Brown's second step, I use the following fact : if a union-closed family has at least $k'+3$ members of cardinality a least $k'$, this family has three members whose intersection is of cardinality at least $k'$.)

Edit : I wrote "The proof of this new statement seems more difficult..." Isn't it a stupidity ? Fedor Petrov's method furnishes an element $v$ and a second family (contained in the first family) of at least ${k' \choose r}$ $r$-sets that don't contain $v$. Again, there is an element $v'$ in the union of these ${k' \choose r}$ $r$-sets and a third family (contained in the second family) of at least ${k'-1 \choose r}$ $r$-sets that don't contain $v'$ and thus contain neither $v$ nor $v'$. The union of the first family, the union of the second family and the union of the third family are three distinct members of the generated family, they have cardinality at least $k'$ and their intersection is the third family, so the cardinality of the intersection is at least $k'$. So, the first half of Thomas Brown' second step is proved.

Answer 4

A union of $\dbinom kr$ sets with cardinality $r$ has cardinality $\ge k$, and there are two of them due to there being $\ge k$ elements in $X$.