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 and suppose that is a prime.
Theorem: Let be a subset of with the property that no two vectors in are orthogonal. Then .
We will prove a slightly modified version which easily implies the Theorem as we stated it before:
Let be the set of vectors () in such that and the number of ‘1’ coordinates is even. Let be a subset of with the property that no two vectors in are orthogonal. Then .
The ad-hoc trick:
Claim 1: Let . If then . Continue reading