1
$\begingroup$

In "Union-free Hypergraphs and Probability Theory", the first theorem states that the upper bound on $f(n)$, which is defined to be

the maximum number of distinct subsets of an $n$-element set such that all the $f(n) \choose 2$ pairwise unions are distinct

is

$f(n) \leq 1 + 2^{(n+1)/2}$

Then they state that it's "an immediate consequence of ${f(n) \choose 2} \leq 2^n$." Can someone explain this "immediate consequence?

As far as I understand hypergraphs, the only upper bound I could come up with for $f(n)$ itself is $2^n$, so ${f(n) \choose 2} \leq 2^{(n-1)}(2^{n} - 1)$.

1 Answers 1

2

There can be no more than $2^n$ pairwise distinct unions, since there are no more than $2^n$ subsets. Thus $\binom{f(n)}{2}\le 2^n$.

For brevity let $x=f(n)$. Then $\frac{x(x-1)}{2}\le 2^{n}.$ That yields $x(x-1)\le 2^{n+1}$. Since $x(x-1)$ is for our purposes an increasing function of $x$, all we need to do is to check that already when $x=1+2^{(n+1)/2}$, we have $x(x-1) \ge 2^{n+1}$. This is easy.