Tell me more ×
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.
up vote 0 down vote favorite

My work with computability has led me to face the following combinatorial problem:

Let $n\geqslant 3,m\geqslant 2$, $N=\{1, \ldots, n \}$ and let $U_m\subset 2^N$ be a collection of subsets of $N$, all of them of size $m$. Assume also that $\lvert U_m \rvert \leqslant n - m$.

The question is: How can one compute an upper bound for the cardinality of the set $\mathcal{C}= \{ c \cup d \mid c,d\in U_m \wedge \lvert c \cup d \rvert = m + 1 \}$.

What i believe is that $\lvert \mathcal{C} \rvert \leqslant n - m - 1$, but i just cannot find out how to prove it.

Can anyone shed some light on this matter ?

Thanks a lot for all your comments !!!

Greetings...

share|improve this question
1  
You probably want to add the assumption that every element of $N$ appears in some member of $U_m$. Otherwise there is an easy counterexample for $n=6$,$m=2$: take $U_2 = \{\,\{ 1,2 \}\,,\,\{2,3\}\,,\,\{3,4\}\,,\,\{4,1\}\,\}$. (The idea of this counterexample would clearly generalise.) – Arthur Fischer♦ Aug 24 '12 at 7:30
Yes, you are right, without the assumption that $\bigcup U_m = N$,it is not true that $\lvert \mathcal{C} \rvert \leqslant n - m - 1$. But then with this extra hypothesis, how to prove the desired inequality ? Thanks !!! – onebengaltiger Aug 29 '12 at 6:11

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.