2
$\begingroup$

Here is what I have understood this question as:

Every subset of [n] is contained in an intersecting family of size 2^n-1

This is my approach:

I took a set, X={1,2,3}

I list down all the subsets of X: {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3 }, {1,2,3}

Now, I take any one from the above, let us take {2,3}, and name it A

To build an Intersecting family containing A, I take any element from A, let us say, 3. I remove 3 from X and list down all the subsets of our new X: {}, {1}, {2}, {1,2}. I further add 3 to each of these sets, so I have now: {3}, {1,3}, {2,3}, {1,2,3}.

The above list forms an intersecting set containing A, and is of size 4(2^3-1).

In the same way, I can repeat the above steps for all subsets of X, and conclude the same solution.

I apologise for a naive question, but I would like to know if I am correct in this approach, and If I am, How should I approach for a mathematical proof?

$\endgroup$
1
1
$\begingroup$

Welcome to this site. Is the following all you require or have I misunderstood your question?

Let $x$ be an element of a set $X$ which has $n$ elements.

The set $X-\{x\}$ has $n-1$ elements and therefore has $2^{n-1}$ subsets. Add $x$ back into each of these subsets to give us the required family.

$\endgroup$
1
  • $\begingroup$ Thankyou for your warm welcome. Absolutely, Once again, thank you. $\endgroup$ Sep 10 '19 at 8:47
1
$\begingroup$

Your arguing about the set $X$ is correct, albeit somewhat laborious. But $X=\{1,2,3\}$ is just a special case. Now you have to extend your argument to the general setup in the question; then erase the proof concerning $X$.

You are given a nonempty subset $A\subset[n]:=\{1,2,\ldots, n\}$. Choose a number $a\in A$ and consider the family $${\cal F}:=\bigl\{X\subset[n]\bigm| a\in X\bigr\}\ .$$

$\endgroup$
1
  • $\begingroup$ Thankyou Christian, It solves my problem very efficiently $\endgroup$ Sep 10 '19 at 9:02

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.