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 a 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}}.


The ad-hoc trick:

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