Theorem 7.6.1 (Oddtown Theorem).label Let $[n]\define \curl{1,2,...,n}$ and $\F\suf\cali{P}([n])$ be a family such that $\abs{A}\congruent{1}{2}$ for all $A\in\F$ and $\abs{A\cap B}\congruent{0}{2}$ for all $A\neq B\in \F$. Then $\abs{F}\leq n$.
Proof. For each $A\in \F$ consider the indicator associated with $A$, $\indi{A}\in \bb{F}^{n}_{2}$ defined by
Observe that $\indi{A}\cd \indi{B}=\abs{A\cap B}$ so the hypothesis is equivalent to
- (1)
$\indi{A}\cd \indi{A}\congruent{1}{2}$
- (2)
$\indi{A}\cd\indi{B}\congruent{0}{2}$
for all $A\neq B\in\F$. If there is a linear relation over $\bb{F}_{2}$ then
Using (2) we have for each $B\in\F$
showing that
We shall now provide a proof over $\Q$ or any field of characteristic $0$ (as $\Q$ embeds there). For each $A\in \F$ consider the indicator associated with $A$, $\indi{A}\in \Q^{n}$ defined by
Observe that $\indi{A}\cd \indi{B}=\abs{A\cap B}$ so the hypothesis is equivalent to
- (1)
$\indi{A}\cd \indi{A}\congruent{1}{2}$
- (2)
$\indi{A}\cd\indi{B}\congruent{0}{2}$
for all $A\neq B\in\F$. Let $m=\abs{\cali{F}}$ and write $\cali{F}=\curl{A_1,...,A_m}$. Let the matrix $M$ whose $k^{th}$ column is $\indi{A_k}$ with the canonical identification of $\indi{A}\bij (\indi{A}(\el))\in \Q^{n}$ where $\el\in[n]$ then $X\define M^{T}M$ is the matrix such that $X_{ij}=\abs{A_i\cap A_j}$. By (1) and (2)
in particular $\det(X)\neq 0$. We conclude
$\square$
Post a Comment