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

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]$.