Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 109 / 1

Associate to each set $A_i\subseteq [n]$ its characteristic vector of a set $v_i\in {\mathbb{F}}_2^n$. The hypotheses sayIf ${\sum }_i{c}_i{v}_i=0$, taking the dot product with $v_j$ gives $c_j=0$. Thus the vectors are linearly independent, so $m\le \dim {\mathbb{F}}_2^n=n$. Equality is attained by the $n$ singleton sets.

Again let $v_i\in {\mathbb{F}}_2^n$ be the characteristic vectors. They all lie in the even-weight subspacewhich has dimension $n-1$. Their Gram matrix isbecause its diagonal entries are zero and its off-diagonal entries are one. If $Gx=0$ and $s={\sum }_i{x}_i$, then $x=s1$. ConsequentlySince $G=V{V}^T$ for a matrix whose rows lie in $E$, its rank is at most $n-1$. If $n$ is even, an even $m$ cannot reach $n$, while an odd $m$ is at most $n-1$; hence $m\le n-1$. If $n$ is odd, the same calculation gives $m\le n$.

Both bounds are sharp. For odd $n$, take $A_i=[n]\setminus \{i\}$ for $1\le i\le n$: each set has even size and two distinct sets meet in the odd number $n-2$. For even $n$, apply the same construction to $[n-1]$ and regard the resulting $n-1$ sets as subsets of $[n]$.

Let $k=k_1+\cdots +k_s$ be an integer partition. Partition $[2k]$ into blocks $X_j$ of sizes $2k_j$. For every $x\in X_j$, includeThere are $2k=n$ sets. Each has odd size; two sets from the same block meet in $2k_j-2$ points, and sets from different blocks are disjoint. Thus every pairwise intersection has even size.

The partition can be recovered from the bipartite incidence graph between the sets and ground points. A block with $k_j\ge 2$ gives one connected component containing $2k_j$ set-vertices and $2k_j$ point-vertices, while a block with $k_j=1$ gives two isolated edges. Therefore isomorphic families yield the same multiset $(k_1,\dots ,k_s)$. Distinct integer partitions give non-isomorphic families, so there are at least $p(k)$ of them.