Jtdylktuy

Given $2^{n-1}$ subsets of a set with $n$ elements with the property that any three have nonempty intersection, prove that the intersection of all the sets is nonempty.

My attempt:
Let $|X|=n$ and $S subset mathcal{P}(X)$ be the above mentioned set. If the intersection of all the sets in $S$ is nonempty and contains W.L.O.G $a in X$, then the set of all subsets of $X$ containing $a$ satisfy the requirement.

The claim clearly holds for $n=1$ and $n=2$. (See Hagen von Eitzen's comment below. With a different interpretation of the problem statement, the claim is false for $n=1$ and $n=2$.) In what follows, we assume that $ngeq 3$.

Let $S$ be a set with $n$ elements and $mathcal{F}$ a family of subsets of $S$ with the required properties. That is, $mathcal{F}$ satisfies the condition that $|mathcal{F}|=2^{n-1}$ and that any three (not necessarily distinct) sets in $mathcal{F}$ have a nonempty intersection.

Consider the vector space $V:=mathbb{F}_2^S$ with basis $big{e_s,|,sin Sbig}$ over the field $mathbb{F}_2$ with $2$ elements. We identify each subset $Xsubseteq S$ with the vector $$e_X:=sum_{sin X},e_s,.$$
In particular, $e_{{s}}=e_s$ for all $sin S$, and $e_emptyset=0$. Equip $V$ with the nondegenerate inner product $langle_,_rangle$ defined by
$$leftlangle e_X,e_Yrightrangle :=|Xcap Y|$$
for every $X,Ysubseteq S$ (here, $|Xcap Y|$ is considered modulo $2$).

We claim that $W:=mathbb{F}_2^Ssetminus big{e_X,big|,Xinmathcal{F}big}$ is a vector subspace of $V$. That is, $W$ is closed under addition and scalar multiplication. Clearly, $W$ is closed under scalar multiplication since $0=e_emptysetin W$ and $mathbb{F}_2={0,1}$. We are left with closure under addition.

For a subset $X$ of $S$, write $X^complement$ for $Ssetminus X$. It can be easily seen that, for each $Xsubseteq S$, either $Xinmathcal{F}$ or $X^complement in mathcal{F}$, but not both.

Suppose $A$ and $B$ are subsets of $S$ such that $e_Ain W$ and $e_Bin W$. Then, $A^complementinmathcal{F}$ and $B^complement inmathcal{F}$. Now, $e_A+e_B=e_{Atriangle B}$, where $triangle$ is the symmetric difference. Because $$(Atriangle B)cap A^complement cap B^complement=emptyset,,$$ $Atriangle B$ cannot be in $mathcal{F}$. Thus, $e_{Atriangle B}in W$.

Consequently, $W$ is indeed a subspace of $V$ with dimension $n-1$, i.e., with codimension $1$. There exists a unique linear functional $varphi:Vto mathbb{F}_2$ with kernel $W$. Hence, $varphi=langle e_T,_rangle$ for some nonempty $Tsubseteq S$ (this is because $langle_,_rangle$ is a nondegenerate symmetric bilinear form on $V$). It remains to show that $T$ is a singleton.

If $T$ contains at least three pairwise distinct elements, say $a$, $b$, and $c$, then take $A:={a}$, $B:={b}$, and $C:={a,b,c}$. Since $e_A$, $e_B$, and $e_C$ are not in $ker(varphi)$, $A$, $B$, and $C$ must be in $mathcal{F}$, but $Acap Bcap C=emptyset$. This is a contradiction, so $|T|leq 2$.

If $|T|=2$, say, $T={a,b}$, then we take $cin Ssetminus T$ (noting that $|S|=ngeq 3>|T|$), and set $A:={a}$, $B:={b}$, and $C:={a,c}$ and apply the same argument as before to arrive at a contradiction. Ergo, $T$ is a singleton: $T={t}$ for some $tin S$. This proves that every set in $mathcal{F}$ contains $t$.