# Extremal Combinatorics VI: The Frankl-Wilson Theorem

Rick Wilson

The Frankl-Wilson theorem is a remarkable theorem with many amazing applications. It has several proofs, all based on linear algebra methods (also referred to as dimension arguments). The original proof is based on a careful study of incidence matrices for families of sets. Another proof by Alon, Babai and Suzuki applies the “polynomial method”. I will describe here one variant of the theorem that we will use in connection with the Borsuk Conjecture (It follows a paper by A. Nilli).  I will post separately about more general versions, the origin of the result, and various applications. One application about the maximum volume of spherical sets not containing a pair of orthogonal vectors is presented in the next post.

Let $n=4p$ and suppose that $p$ is an odd prime.

Theorem: Let $\cal F$ be a subset of $\{-1,1\}^n$ with the property that no two vectors in $\cal F$ are orthogonal. Then $|{\cal F}| \le 4({{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}})$.

We will prove a slightly modified version which easily implies the Theorem as we stated it before:

Let $\cal G$ be the set of vectors ($x_1,x_2,\dots,x_n$) in $\{-1,1\}^n$ such that $x_1=1$ and the number of ‘1’ coordinates is even.  Let $\cal F$ be a subset of $\cal G$ with the property that no two vectors in $\cal F$ are orthogonal. Then $|{\cal F}| \le {{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}}$.

### Proof:

Claim 1: Let $x,y\in {\cal G}$. If $=0(mod~p)$ then $=0$. Continue reading