Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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