Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.