The previous talk in the series is here. The next talk in the series is here.
How many subsets of {1,2,…,n} of size n/2 can you pick if the intersection of any two of them is required to have size at most αn? The answer turns out to depend heavily on whether α is less than, equal to, or greater than 1/4. The reason 1/4 is a natural boundary is that if you choose two sets of size n/2 at random then the expected size of their intersection is n/4. In this video I discuss the case where α is greater than 1/4 and the case where α is less than 1/4. The case α=1/4 will be covered in the next video.
It occurs to me now that there is an approach to the last thing I did that allows one to avoid the final calculations. One can just observe that the construction gives us k+1 unit vectors that add up to zero such that all their inner products are the same. If the inner products are all -δ, then
0 = |u1 + … + uk+1|2 = k+1 – k(k+1)δ
and it follows that δ = 1/k, as required.
This video was produced by Tim Gowers as part of his Part III course at the University of Cambridge. Printed notes for this course are available here.