Boris Bukh, Carnegie Mellon University

Abstract

The Oddtown problem is the perhaps the simplest application of the linear algebra method to extremal combinatorics. Motivated by the desire to better understand the method, we examine the generalization to composite moduli.

A family of subsets of $[n]$ is $ell$-Oddtown if the size of each set is divisible by $ell$, but no intersection is divisible by $ell$. How large can $ell$-Oddtown be? We explain the history of the problem, present the best known bound due to Szegedy, and our improvement to it.

Joint work with Ting-Wei Chao and Zeyu Zheng