The Eigenspace

Bibliography

5 Miscellaneous

Theorem 6.5.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

\begin{align*}\indi{A}(i)\define \begin{cases}1&i\in A\\ 0&i\nin A\end{cases}\end{align*}

Observe that $\indi{A}\cd \indi{B}=\abs{A\cap B}$ so the hypothesis is equivalent to

  1. (1)

    $\indi{A}\cd \indi{A}\congruent{1}{2}$

  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
\begin{align*}0=\sums{}{A\in\cali{F}}c_{A}\indi{A}\end{align*}

Using (2) we have for each $B\in\F$

\begin{align*}0=\parens{\sums{}{A\in\cali{F}}c_A\indi{A}}\cd\indi{B}=\parens{\sums{}{A\in\cali{F}}c_A(\indi{A}\cd\indi{B})}=c_{B}\indi{B}\cd\indi{B}=c_{B}\end{align*}

showing that

\begin{align*}\abs{\F}\leq \dim_{\bb{F}_2}(\bb{F}_{2}^{n})=n\end{align*}

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

\begin{align*}\indi{A}(k)\define \begin{cases}1&k\in A\\ 0&K\nin A\end{cases}\end{align*}

Observe that $\indi{A}\cd \indi{B}=\abs{A\cap B}$ so the hypothesis is equivalent to

  1. (1)

    $\indi{A}\cd \indi{A}\congruent{1}{2}$

  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)
\begin{align*}\det(X)\equiv\det(I_{k})\congruent{1}{2}\end{align*}

in particular $\det(X)\neq 0$. We conclude

\begin{align*}\abs{\cali{F}}=k=\text{rank}(X)\leq \text{rank}(M)\leq n\end{align*}

$\square$

Theorem 6.5.2 (Odd Oddtown).label Let $\cali{F}\suf\cali{P}([n])$ be a family such that for all $A\neq B\in\cali{F}$

  1. (a)

    $\abs{A}\congruent{0}{2}$

  2. (b)

    $\abs{A\cap B}\congruent{1}{2}$

then
  1. (1)

    $\abs{\F}\leq n+1$

  2. (2)

    $\abs{\F}\leq n$

Proof. Using the same set up as Oddtown Theorem 6.5.1 over $\bb{F}_{2}$ we have the hypothesis is equivalent to

  1. (1)

    $\indi{A}\cd \indi{A}\congruent{0}{2}$

  2. (2)

    $\indi{A}\cd\indi{B}\congruent{1}{2}$

We now define a new family $\cali{F}'\suf\cali{P}([n+1])$ by
\begin{align*}\F'\define \curl{A'=A\cup \curl{n+1}:A\in\F}\end{align*}

$\square$

Direct References

The Eigenspace

Bibliography

Direct References