Clubs whose intersections are multiples of six (Oddtown variant)

290 Views Asked by At

This is a question about generalizing the famous "Clubs in Oddtown" problem. The original setup is that a town has $n$ people, and $m$ clubs each consisting of a subset of the population. Each club has an odd number of members, while any two distinct clubs have an even number of members in common. Given this, you the goal is to prove $m\le n$. You can prove this using linear algebra over $\mathbb F_2$.

One might ask if the results still hold if we replace $2$ with another number $d$. That is, if we have a town with $n$ people and $m$ clubs such that the number of people in any club is not a multiple of $d$, while the number of people in common to any two clubs is a multiple of $d$, what it is the greatest possible value of $m$ in terms of $n$? When $d=p$ for any prime $p$, you can prove $m\le n$ using the same argument but with $\mathbb F_p$-linear algebra. You can also prove that $m\le n$ when $d=p^k$ is any prime power, see Generalize Oddtown.

This leads me to ask, can we also prove that $m\le n$ for all other $d$? For concreteness, I am asking about $d=6$ (I like to call this variant "Clubs in Sioux City"). That is,

Question: There is a town with $n$ people and $m$ clubs consisting of subsets of the population. Any club has a number of members which is not a multiple of $6$, while the number of members in common to any two clubs is a multiple of $6$. Can we conclude that $m\le n$?

I know that you can prove $m\le 2n$, by combining the $d=2$ and $d=3$ results (proving this result is what was asked at that question I linked before). But from playing with small cases, it does not seem like it is possible to create a setup with $m>n$, though I also cannot prove this. Does anyone know how to prove that $m\le n$, or how to construct a set of $n+1$ clubs satisfying the requirements?