[Math] Odd number of members, odd number of intersections

combinatorics

In Oddtown with $n$ citizens, $m$ clubs are formed. Every club has an odd number of members and also each two clubs have an odd number of members in common. Given that no two clubs have exactly the same members, find the largest possible value of $m$.

As mavropnevma said Here, The other three cases, "odd clubs with even pairwise intersections", "even clubs with even pairwise intersections", and "even clubs with odd pairwise intersections are discussed in Bollobas's book, The Art of Mathematics, but not this one, so I'm intrested to see it's answer.

P.S: The topic in AoPS got no answers, so I'm posting it here…..

Best Answer

This case can be reduced to the one with even clubs and even intersections.

Let's call the maximal number of clubs in the odd/odd and even/even cases $o_n$ and $e_n$, respectively. Gerry has already shown $e_{n-1}\le o_n\le e_{n+1}$. To see that in fact $o_n\le e_n$, consider the clubs as vectors in $\mathbb F_2^n$, indexed by the citizens, pick some club $c$, and form a set $S$ of clubs by adding $c$ to all clubs (including $c$ itself). The resulting vectors are even and have even intersections.

As shown in Bollobas' book, $e_n=2^{\lfloor n/2\rfloor}$. Thus the bounds in $e_{n-1}\le o_n\le e_n$ coincide for odd $n$, so for this case we have $o_n=2^{(n-1)/2}$. For even $n$, note that $S$ does not contain the componentwise complement of any of its elements, since the original clubs corresponding to an element of $S$ and its complement would also be complements of each other, and would thus have even intersection. Thus we can double the size of $S$ by adding the complements of all its elements, and all vectors will still be even and have even intersections (since $n$ is even). Thus in this case $o_n\le e_n/2=2^{n/2-1}$, so that $2^{n/2-1}$ is both a lower and upper bound. In summary, $o_n=2^{\lfloor(n-1)/2\rfloor}$ for either parity of $n$.