2
$\begingroup$

Let $\mathcal{F}$ be a family of subsets of an $n$-element set $X$. A family is intersecting iff any two of its sets have a non-empty intersection.

How can I prove that if $\mathcal{F}$ is an intersecting family, then $|\mathcal{F}|\leq 2^{n-1}$? How can I show that there is an intersecting family $\mathcal{F}'$ containing $\mathcal{F}$ such that $|\mathcal{F}'| = 2^{n−1}$.

What I've tried: Let $(Y,Z)$ be any partition of $X$. Then at most one of $Y$ and $Z$ can contain an element of $\mathcal{F}$ . If neither of them does, then both $Y$ and $Z$ are blocking sets. So, if we let $\mathcal{F}'$ consist of all sets containing a member of $\mathcal{F}$ together with one of each complementary pair of blocking sets, then $\mathcal{F}'$ contains one of each complementary pair of sets. Furthermore, since $\mathcal{F}$ is intersecting, then any two sets which contain members of $\mathcal{F}$ must intersect; a set containing a member of $\mathcal{F}$ intersects each blocking set; and, if we choose the larger of each pair of blocking sets, then any two of the chosen blocking sets intersect. So we have an intersecting family containing $\mathcal{F}$. But why $|\mathcal{F}'|=2^{n-1}$?

$\endgroup$
7
  • $\begingroup$ What are your thoughts? What have you tried? Where are you stuck? You need to provide context for your question. Otherwise it just looks like you want somebody to do your homework for you; that's not what this site is for. If you add some appropriate context, we will be happy to help. $\endgroup$
    – Om3ga
    Jan 7 at 11:19
  • 2
    $\begingroup$ @Om3ga You are completely right. I've just added my thought. Thank you. $\endgroup$
    – M.Ramana
    Jan 7 at 11:26
  • 3
    $\begingroup$ Think about pairs of sets which are complements to each other. $\endgroup$
    – Ege Erdil
    Jan 7 at 11:34
  • 1
    $\begingroup$ Thanks for your edit. You meant to say at most one of $Y$ and $Z$ can be an element of $\mathcal{F}$. It looks like the only insight you're missing is (why) $X$ has $2^n$ subsets. $\endgroup$
    – J.G.
    Jan 7 at 11:38
  • 2
    $\begingroup$ @hardmath that last comment is not quite right. given an intersecting family $F$, let $G$ be an intersecting family of maximal possible size containing $F$. if $G$ does not have size $2^{n-1}$, then there exists some $A\subseteq X$ such that $A\notin G$ and $A^c\notin G$. by maximality of $G$, neither $G\cup\{A\}$ nor $G\cup\{A^c\}$ is intersecting, so there exist $C,D\in G$ such that $A\cap C=A^c\cap D=\varnothing$. but then $C\cap D=\varnothing$, contradicting that $G$ is intersecting $\endgroup$ Jan 8 at 19:54

1 Answer 1

2
$\begingroup$

HINT: Write as $V$ the $n$-element set. Then there are $2^n$ subsets of $V$, and furthermore those $2^n$ subsets of $V$ can be partitioned into $2^{n-1}$ pairs $\{S,\bar{S}\}$, where $\bar{S}$ is the complement of $S$. If $\cal{F}$ is intersecting however, then for each $S \in \cal{F}$, its complement $\bar{S}$ in $V$ is not in $\cal{F}$, equivalently, only one of $S$, $\bar{S}$ can be in $\cal{F}$.

$\endgroup$
5
  • $\begingroup$ Thank you very much for the hint. I have a question: how can I define $\mathcal{F}'$ then? Can I define $\mathcal{F}'$ this way: $\mathcal{F}'=\{ S\; |\; \{ S,\bar{S}\}\; \text{is a partition of}\; V$? Then $\mathcal{F}'$ is not intersecting itself. $\endgroup$
    – M.Ramana
    Jan 9 at 10:35
  • $\begingroup$ You mean we need to choose just either $S$ or $\bar{S}$ for which $\{ S,\bar{S}\}$ is a partition of $V$, then since $\mathcal{F}$ is not intersecting, so $\mathcal{F}'$ contains $\mathcal{F}$? $\endgroup$
    – M.Ramana
    Jan 9 at 10:41
  • $\begingroup$ Only one of $S$, $\bar{S}$ can be in $\cal{F}$. So only half of the $2^n$ subsets of $V$ can be in $\cal{F}$. $\endgroup$
    – Mike
    Jan 9 at 12:59
  • 1
    $\begingroup$ I got it. Thanks a lot. $\endgroup$
    – M.Ramana
    Jan 9 at 13:04
  • $\begingroup$ Sorry. I understood that $|\mathcal{F}|\leq 2^{n-1}$. But what is $\mathcal{F}'$ containing $\mathcal{F}$? I've taken $\mathcal{F}'$ a family including only one of $S,\bar{S}$ for which $\{ S,\bar{S}\}$ is a partition of $V$ but is $\mathcal{F}'$ intersecting? $\endgroup$
    – M.Ramana
    Jan 12 at 15:46

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.