1
$\begingroup$

Let $n>1$ be an integer and let $[n]=\{1,\ldots,n\}$. An intersecting family on $[n]$ is a set $E\subseteq {\cal P}([n])$ such that for all $a,b\in E$ we have $a\cap b\neq\emptyset$. It is easy to see that an intersecting family on $[n]$ can have size $2^{n-1}$: fix $j\in[n]$ and let $E = \{s\subseteq [n]:j\in s\}$.

Question 1. If $E$ is an intersecting family on $[n]$ with $|E| = 2^{n-1}$, is there necessarily $j\in [n]$ such that $E = \{s\subseteq [n]:j\in s\}$?

Question 2. If $T\subseteq {\cal P}([n])$ has the property that $|T| > 2^{n-1}$, does this imply that $T$ is not intersecting?

$\endgroup$
1
  • 4
    $\begingroup$ For question 2 consider the 2^(n-1) pairs T, n - T. (This probably helps with question 1.) Gerhard "It's Like Figure And Ground" Paseman, 2019.04.22. $\endgroup$ – Gerhard Paseman Apr 22 '19 at 15:52
3
$\begingroup$

For $n > 2$ the answer to question 1 is no. If $n$ is odd take $E$ to be all subsets of size greater than $n/2$, and if $n$ is even take all subsets of size greater than $n/2$ along with all sets of size $n/2$ that exclude a certain element.

$\endgroup$
1
  • $\begingroup$ For even $n$ just arbitrarily pick one or the other member from each pair of disjoint subsets of size $\frac{n}2.$ $\endgroup$ – Aaron Meyerowitz Apr 23 '19 at 8:29
2
$\begingroup$

Give each element an integer weight with the entire set having weight $2k+1.$ Take all sets with total weight at least $k+1.$ Your case was one weight equal to $1$ and the rest $0$.

Take the $7$ lines of a Fano Plane and anything containing one of them. That can't be achieved by a weight function.

An intersecting family of smaller size can be enlarged to one of size $2^{n-1}.$

Also, given an intersecting family of size $2^{n-1}$ one can take any inclusion minimal member and replace it by its complement. This kind of switching can take you from any one to any other. The Fano plane example arises in this way for starting with all sets with $4$ or more of $7$ elements and then switching seven of the minimal sets.

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