Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 7 / 4 / iv

A Steiner system $S(5,6,12)$ consists of 12 points and a collection of six-element blocks such that every five-element subset lies in exactly one block. The blocks are often called hexads. Necessarily their number is $\left(\genfrac{}{}{0ex}{}{12}{5}\right)/\left(\genfrac{}{}{0ex}{}{6}{5}\right)=132$. We give the synthematic construction of the small Witt design explicitly and prove this defining property.

Write $X=\{1,\dots ,6\}$ and $Y=\{T_1,\dots ,T_6\}$. For an unordered pair $P=\{T_i,T_j\}\subset Y$, let $S(P)$ denote the unique syntheme shared by its two synthematic totals. A duad $D\subset X$ belongs to three synthemes. The corresponding three pairs $P$ partition $Y$: every synthematic total contains $D$ in exactly one of its synthemes, and each syntheme lies in exactly two synthematic totals. Thus the incidence $D\in S(P)$ gives a perfect matching of the six synthematic totals for each duad.

To describe the blocks with three points in each half, take an unordered partition $X=A\bigsqcup A^c$ into triples. A syntheme is cross if each of its three duads joins $A$ to $A^c$. Form a graph on $Y$ by declaring $P$ an edge exactly when $S(P)$ is cross. This graph is the union of two disjoint triangles. Indeed a synthematic total partitions the nine cross duads; every syntheme has either one or three cross duads, so if $k$ of its five synthemes are cross, then $3k+(5-k)=9$, giving $k=2$. Each vertex therefore has degree two. The stronger assertion about its components follows directly for $A=\{1,2,3\}$, when the two triangles areany other triple partition is obtained by relabelling $X$, which also permutes the synthematic totals. Denote the two components by $B,B^c$.

The complete block collection is given by the following three rules:

There are $2+15\cdot 3\cdot 2+10\cdot 4=132$ distinct blocks. The first two rules have different intersection sizes with $X$ from the third; within the third, a block determines its triple $A$ and its component. We next verify the Steiner system property, rather than relying solely on this count.

We need one further consequence of the triangle construction. The three synthemes attached to the three pairs within $B$ are pairwise disjoint, since any two belong to their common synthematic total, and together they are all nine cross duads of the complete bipartite graph between $A$ and $A^c$. Thus $B$ determines the unordered partition $A\bigsqcup A^c$ uniquely: it is the bipartition of this connected graph. There are 10 such partitions, each giving two different components, hence 20 different triples in $Y$. Since $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$, each triple in $Y$ corresponds to exactly one triple partition of $X$. The same reasoning applies to $B^c$.

Let $F$ be any five-point set and put $r=|F\cap X|$. If $r=5$, only $X$ can contain it; if $r=0$, only $Y$ can contain it, because no other block has five points in either half.

If $r=4$, set $D=X\setminus F$ and write $F\cap Y=\{T\}$. The three pairs attached to $D$ partition $Y$, so exactly one contains $T$; its block $(X\setminus D)\cup P$ is the unique block through $F$. If $r=1$, put $P=Y\setminus F$ and write $F\cap X=\{x\}$. The three duads of $S(P)$ partition $X$, so exactly one contains $x$; this gives the unique block $D\cup (Y\setminus P)$.

If $r=3$, write $A=F\cap X$ and $P=F\cap Y$. A syntheme has either one or three duads crossing $A\bigsqcup A^c$. In the one-cross case, $S(P)$ has exactly one duad $D$ internal to $A^c$, and the unique block is $(X\setminus D)\cup P$. No block with three points in each half is possible, since $P$ is then not an edge of either triangle. In the three-cross case, $P$ is an edge of exactly one triangle $B$, giving the unique block $A\cup B$; no duad of $S(P)$ is internal to $A^c$, so a block with four points in $X$ is impossible.

Finally let $r=2$, write $D=F\cap X$ and $B=F\cap Y$, and use the uniquely associated partition $X=A\bigsqcup A^c$ just proved. If $D$ crosses this partition, the three synthemes belonging to the pairs inside $B$ contain each cross duad exactly once. Thus the matching of $Y$ attached to $D$ has exactly one pair internal to $B$. It has exactly one pair $P$ internal to $B^c$ as well, since a matching must leave equal numbers of vertices in the two halves for cross pairs. The unique block containing $F$ is then $D\cup (Y\setminus P)$; $D$ is not contained in either $A$ or $A^c$, so no block of the third rule applies. If $D$ is internal to $A$ or $A^c$, none of its attached pairs lies inside $B$ or $B^c$, since the synthemes attached to these internal pairs are cross. Thus the second rule gives no block. The third rule gives exactly one, namely $A\cup B$ or $A^c\cup B$, according to which part contains $D$.

All possibilities have now been exhausted, provingThis is the small Witt design; the construction uses only duads, synthemes, their synthematic totals, and the induced action on those synthematic totals.