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


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


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.


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.