Suppose we have a town with a set of residents $X$, where $|X| = n$ (suppose $n$ even for simplicity here). The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq X$. The eventown problem is interested in the maximum number of clubs $m$ that can be formed with these specific rules:
- All clubs are distinct.
- A club must have an even number of members. $\forall i, |C_i|$ is even.
- Any pair of two clubs shares an even number of members: $\forall i \neq j, |C_i \cap C_j|$ is even.
It is easy to show that the largest number of clubs possible is $m=2^{n/2}$. An easy construction to attain this bound goes as follow : Take any partition of $X$ into sets of size 2, $B_1,\ldots,B_{n/2}$, and consider the family $\mathcal{F}=\{\bigcup_{i\in S}B_i \ :\ S\subseteq [n/2] \}$
For any partition, this matches the required bound, and all these possibilities are pairwise isomorphic.
Is the solution unique up to isomorphism, or are there some other constructions?
Best Answer
The proof of eventown tells us that at equality, the set of clubs can be represented in $ \mathbb{F}_2^n$, as a linear subspace $F$ of dimension $n/2$ (and $ F = F^\perp$). We will use this context.
Here is a counterexample when $n = 8$.
Let the clubs be spanned by
$$\begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ \end{pmatrix}$$
Check that
However, there isn't a pairing that we can do with the first coordinate.
Here is a counterexample when $n = 7$ (so not quite what is asked).
Let the clubs be spanned by
$$\begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ \end{pmatrix}$$
Check that
However, there isn't a pairing that we can do with the first coordinate.