2
$\begingroup$

Let $\mathcal{C}$ be a collection of subsets of $[n]$ with the property that if $A, B \in \mathcal{C},$ then $A \cap B \neq \varnothing .$ (For example, $\mathcal{C}=\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$ has this property.) What is the largest that $\mathcal{C}$ can be? Hint: You will have to prove both that the number you get is possible and that no larger number is possible.

$\endgroup$
  • 2
    $\begingroup$ So what is the largest number you have managed to show is possible? Can you always do $2^{n-1}$ for example? What is your conjecture for the largest number possible? $\endgroup$ – almagest Jan 21 at 10:59
  • $\begingroup$ @almagest I am not able to prove that $2^{n-1}$ is upper bound for cardinality? I do this for $n=4$. $\endgroup$ – maths student Jan 21 at 11:05
  • 1
    $\begingroup$ Can you clarify what you mean by '[n]'? $\endgroup$ – Doug Spoonwood Jan 21 at 11:11
  • $\begingroup$ n is number of element original set can have? Say for given example we have 3 elements {1,2,3} then we have total $2^3$ possible subset out of which $2^{3-1}$ satisfy given condition. $\endgroup$ – maths student Jan 21 at 11:13
3
$\begingroup$

Hint1:

If a collection $\mathcal D\subseteq\wp([n])$ contains more than $2^{n-1}$ elements then for some $A\in\mathcal D$ we have $A^{\complement}\in\mathcal D$.

So such a collection is not a proper candidate for $\mathcal C$.

Then finding a collection $\mathcal C$ (as described) that contains $2^{n-1}$ elements is enough to prove that such a collection has $2^{n-1}$ elements.

Hint2.

In the case where $n=2k+1$ is odd have a look at the subsets that have a cardinality $\geq k+1$.

Can two of them have disjoint intersection? And how many are there?

$\endgroup$
2
$\begingroup$

The power-set of $[n]$, denoted $\wp(n)$ has cardinality $2^n$, and for each $k \in [n]$, the subset of $\wp(n)$ $$\uparrow\{k\} = \{A\subseteq[n]:k\in A\}$$ is such that $\mid\uparrow\{k\}\mid=2^{n-1}$ (can you tell why?).
It is also the case that $k \in A$, for all $A \in \uparrow\{k\}$, and so can always have $\mid\mathcal C\mid=2^{n-1}$.

Now, suppose you have $\mid\mathcal C\mid>2^{n-1}$. Can you see that there are always $A,B \in \mathcal C$ with $A \cap B = \varnothing$?
Notice that there will be $A \in \wp(n)$ such that both $A$ and $[n]\setminus A$ belong to $\mathcal C$.

$\endgroup$

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.