6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I'm perhaps not very smart, but how do we know that the union of any ${k \choose r} $ distinct $r$-sets will be different from the union of all the $r$-sets ? $\endgroup$
    – Panurge
    Mar 5, 2016 at 14:40
  • $\begingroup$ You are right, I was claiming too much. $\endgroup$ Mar 5, 2016 at 16:43
  • $\begingroup$ Thanks for the reply. I was surprised how I found it difficult to prove an apparently so meager result. It is the reason why I would be happy to know a simpler proof than the mine. $\endgroup$
    – Panurge
    Mar 5, 2016 at 16:53
  • $\begingroup$ Thinking about this some more, it seems that your Ramsey-like conditions ensure that at least $k+2$ sets (not just two) have at least $k$ elements, and this cannot be improved. Would a proof of this stronger statement perhaps be easier? $\endgroup$ Mar 6, 2016 at 9:15
  • $\begingroup$ Interesting. Feel free to develop this idea. I will look at it, but I'm now busy with something else. $\endgroup$
    – Panurge
    Mar 6, 2016 at 9:28

4 Answers 4

3
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ Great ! I was sure that my proof was too complicated. By the way, the expression "total number of elements" is perhaps somewhat misleading, but I understand your meaning (you count multiplicities). Thank you very much ! $\endgroup$
    – Panurge
    Mar 7, 2016 at 8:27
  • $\begingroup$ I explained it in other way, hopefully not misleading. $\endgroup$ Mar 7, 2016 at 15:06
1
$\begingroup$

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...

$\endgroup$
2
  • $\begingroup$ Your Helly-like lemma is interesting. $\endgroup$ Mar 6, 2016 at 17:20
  • 1
    $\begingroup$ In fact, this lemma is trivial and too weak : under the hypotheses, each element of the union is in at least s+1-l sets. Otherwise, there is an element $x$ that is in at most s-l sets. Choose l sets that don't contain $x$. The union of these l sets is not the union of all sets, contradiction. $\endgroup$
    – Panurge
    Mar 9, 2016 at 14:51
0
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Please, do not use answer boxes for running discussion or commentary. $\endgroup$
    – Todd Trimble
    Mar 7, 2016 at 18:14
  • $\begingroup$ Sorry. Would it be better to make this answer box an edit of the opening question box ? $\endgroup$
    – Panurge
    Mar 7, 2016 at 18:24
  • 2
    $\begingroup$ Well, I think it might be better (in terms of keeping to site norms), but it gets a little tricky, because at some point the question might become over-bloated. A point to keep in mind is that StackExchange sites are not designed for running discussions; they are question-answer sites. One possibility however is to open a chat room if there are people interested, or else refer to a blog if you have one. (Or the func1 polymath project itself might be a natural place for further discussion.) $\endgroup$
    – Todd Trimble
    Mar 7, 2016 at 18:46
  • $\begingroup$ Dear @Panurge would you please contact me by e-mail or Facebook or whatever? $\endgroup$ Aug 7, 2016 at 6:34
  • $\begingroup$ @Fedor Petrov Well, I would be happy to comply,but how can I do that ? I have no Facebook account (and I will not) and I don't know your e-mail address. $\endgroup$
    – Panurge
    Aug 11, 2016 at 14:55
-1
$\begingroup$

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$.

$\endgroup$
1
  • 3
    $\begingroup$ Two families, but why two distinct unions? $\endgroup$ Mar 6, 2016 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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