Illustrated by Fano plane $\Pi_2$ of 7 “points” and 7 “lines” (diagram again; get properties from class, including):

– Each line has 3 points
– Any 2 points on a unique line

That makes it a 2-(7,3,1) design. In general:

Definition 1.1 (p.1) A $t$-design with parameters $(v,k,\lambda)$, a.k.a. a $t$-$(v,k,\lambda)$ design, is a pair ${\mathfrak D} = (X,{\mathfrak B})$ where

@ $X$ is a set of $v$ “points”
@ $\mathfrak B$ is a collection of $k$-element “blocks”, each a subset of $X$
@ any $t$ points contained in exactly $\lambda$ blocks.

E.g. $\Pi_2$ is also a 1-(7,3,3) design, and Petersen is 1-(10,2,3).
Trivial example: any collection of $b$ blocks is a 0-$(v,k,b)$ design. Is $\Pi_2$ a 3-design?

Even more trivial: If $v \lt k$ or $k \lt t$ then $\lambda=0$ (and if $v \lt t$ then $\lambda$ is undefined); we don’t care about such examples, nor indeed the example where $\lambda=0$ because $\mathfrak B$ is empty.

We do care very much about the special case

$\lambda = 1$ (as with $\Pi_2$);

that’s a Steiner system (a.k.a. $S(t,k,v)$).

[Further examples: the $S(2,3,81)$ of the game “Set”; after Prop. 1.4 and its Corollaries: the S(3,4,8) obtained by adding a point to $\Pi_2$ etc. – more on this later in the term]

Aim: describe all designs, up to equivalence.

That’s asking too much!

But it can be done, with interesting results, for many particular cases, some of which will appear shortly. E.g. 2-(7,3,1) is unique.

Constructing $t$-designs gets harder as $t$ increases, with one exception …

Only slightly less trivial: the set of all $v \choose k$ subsets is a trivial design: the symmetric group $S_v$ acts transitively on $t$-element subsets, so each is contained in the same number (namely $v-t \choose k-t$). That’s a complete block design; we’re interested in incomplete ones. The $t$-design condition says that the set of blocks is “balanced” among all elements, pairs, …, $t$-subsets. This is sometimes called a

BIBD: balanced incomplete block design.

Warning: depends on ordering of $X$ and $\mathfrak B$; also, some authors use a definition with rows and columns switched, resulting in transpose of our matrix. To do it more canonically, we may think of the associated linear transformation between $F^X$ and $F^{\mathfrak B}$ where $F$ is the ground field (and $F^X,F^{\mathfrak B}$ are the vectors spaces of maps from $X,\mathfrak B$ respectively to $F$); for instance a map $f: X \to F$ goes to the map ${\mathfrak B} \to F$ taking any block $B$ to $\sum_{x \in B} f(x)$.

1.11 (p.4), generalized slightly:

If it’s a $t$-$(v,k,\lambda)$ design then:

@ each block has $k$ points ⇔ each row dots with all-1’s column to $k$ ⇔ $M$ * (all-1’s column) = $k$*(all-1’s column)

@ if $t \geq 1$: each point is in $r=\lambda_1$ blocks ⇔ each column dots with all-1’s row to r ⇔ (all-1’s row) * M = r*(all-1’s row)

The fact that rows and columns are interchangeable so far suggests defining the dual ${\mathfrak D}^{\sf T}$ of a design ${\mathfrak D} = (X,{\mathfrak B})$ [see p.5, I’m changing the text’s order of exposition] so that the incidence matrix of ${\mathfrak D}^{\sf T}$ is is the transpose of the incidence matrix of $\mathfrak D$ (as the notation suggests). Morally speaking ${\mathfrak D}^{\sf T} = ({\mathfrak B},X)$. Since $X$ does not consist of subsets of $\mathfrak B$, we interpret this as $$ {\mathfrak D}^{\sf T} = (X^{\sf T}, {\mathfrak B}^{\sf T}) = ({\mathfrak B}, \{\beta_x : x \in X\}) $$ where $$ \beta_x := \{B \in {\mathfrak B}: x \in B\} $$ NB in general this might be only a “structure”, not a design. A structure $\mathfrak D$ is a design if the adjacency matrix has no repeated rows, and ${\mathfrak D}^{\sf T}$ is a design if there are no repeated columns. So, for instance, consider

1100
1100
0011
0011

($\mathfrak D$ and ${\mathfrak D}^{\sf T}$ are 1-(4,2,2) structures, both isomorphic with the regular graph-with-multiplicity @=@ @=@), and

110000
001100
000011

($\mathfrak D$ is the 1-(6,2,1) design @-@ @-@ @-@, and ${\mathfrak D}^{\sf T}$ is a 1-(3,1,2) structure; that’s a degenerate example because it“s twice the complete design — can you find a nondegenerate example?) In any case the dual of a 1-structure is a 1-structure, and — as ought to be the case with a notion of duality —

$({\mathfrak D}^{\sf T})^{\sf T}$ is canonically isomorphic with $\mathfrak D$.

OK: what if we actually have a 2-design, such as $\Pi_2$? Check that for $\Pi_2$ the dual ${\mathfrak D}^{\sf T}$ is also a 2-design, indeed with the same parameters. This isn’ always true, but it does suggest something that is. Let’s see:

@ if also $t=2$: each pair of points in $\lambda$ blocks ⇔ any two different columns have dot product $\lambda$. The dot product of a column with itself is again $r4$, so ...

1.11 iii) $M^{\sf T} M = (r-\lambda) I + \lambda J$ ($v \times v$ matrices)

where $J$ = all-1’s matrix. (Likewise if $t \geq 2$, replacing $\lambda$ by $\lambda_2$.) Note that this excludes repeated columns unless $r = \lambda$, which is (not surprisingly) impossible except in trivial cases as we soon see.

The first two properties in (1.11) can also be expressed in terms of $J$:

1.11 ii) $M J = k J$ ($v \times v$ matrices)
1.11 i) $J M = r J$ ($b \times b$ matrices) That might seem like just bookkeeping, but (iii) lets us actually do nontrivial things using linear algebra (and then (i) and (ii) will help too). We need:

Lemma 1.12 (p.4): for the identity and all-1 matrices $I,J$ of order $n$ we have $$ det(xI+yJ) = (x+ny) x^{n-1}. $$ In particular, $xI+yJ$ has rank n iff $x$ and $x+ny$ are nonzero.

[NB it's a priori a homogeneous polynomial of degree $n$; also ${\rm det}(I+yM)$ is a polynomial in $y$ of degree rank($M$), and since $J$ has rank 1 it had to be linear in $y$.]

Pf.: $xI+yJ$ symmetric ⇔ spectral theorem applies (orthonormal eigenvectors, det = product of eigenvalues). All-1’s has eigenvalue x+ny and its orth. complement has dimension $n-1$ and eigenvalue $x$, etc.

[Yes, Lemma 1.12 can also be obtained directly by row operations; but we'll soon make similar applications of the spectral theorem in settings where a more direct approach is not available.]

In our case x+ny is certainly nonzero: it’s $r+(v-1)\lambda$ and both terms are positive. What about $x=r-\lambda$? Well we saw that

(1.9) $r (k-1) = (v-1) \lambda$

so, $$ (r-\lambda) (k-1) = (v-1) \lambda - (k-1) \lambda = (v-k) \lambda $$ so as long as $k\gt 1$ (remember we must have $k\geq t$ for nontriviality) and $k \lt v$ (it’s not just the complete design $(X,\{X\})$) we have $r-\lambda \gt 0$. Hence:

Theorem 1.14 (p.5) [Fisher’s inequality] In a nonempty 2-design with $k \lt v$ we have $b \geq v$.

Proof: We have written a nondegenerate $v \times v$ matrix as a product of two matrices each of rank at most $b$. QED

What if equality holds? First of all $M$ is a square matrix, and (1.8) $bk=vr$ means that $b=v$ iff $k=r$, so (1.11) means $MJ=JM$. But then $M$ commutes with $M^{\sf T} M$ since that’s a linear combination of $I$ and $J$, so $M M^{\sf T} M = M^{\sf T} M M$, and since $M$ is invertible we conclude $M M^{\sf T} = M^{\sf T} M$, which is already known (1.11 again) to be $(r-\lambda) I + \lambda J$. But this means that every two blocks have $\lambda$ points in common! That in turn means that ${\mathfrak D}^{\sf T}$ is also a 2-design. To summarize:

Theorem 1.15 (p.5) In a 2-design with $k \leq v$, TFAE:
(a) $b=v$
(b) $r=k$
(c) any two blocks have $\lambda$ points in common
(d) any two blocks have a constant number of points in common.
[(e) ${\mathfrak D}^{\sf T}$ is a 2-design.]

Proof: a ⇔ b follows from $bk=rv$ ($b/v=r/k$). We’ve just shown that these imply c, and c ⇒ d ⇔ e are obvious. Finally for e ⇒ a, if ${\mathfrak D}^{\sf T}$ is a 2-design then it satisfies the hypotheses of Fisher’s inequality (notably the condition $k \lt; v$ becomes $r \lt; b$, which is equivalent because bk=rv), so we may apply Fisher to both $\mathfrak D$ and ${\mathfrak D}^{\sf T}$ to get $b \geq v \geq b$, whence $b=v$. QED

A 2-design satisfying these conditions is said to be square (because the incidence matrix is square; again the book warns that the literature also contains other terminology for this). You might find problem 2 on the homework easier now.

It“s harder to construct $t$-designs as $t$ increases because

Cor. 1.6 (p.3): a $t$-($v,k,\lambda$) design is automatically also an $s$-($v,k,\lambda_s$) design for each $s \leq t$, with $\lambda_s$ given by:

Prop. 1.4: If $S$ is a subset of $X$ with $s = |S| \in [0,t]$ then the number of blocks containing $S$ is $$ \lambda_s := \left( {v-s \choose t-s} \left/ {k-s \choose t-s}\right. \right) \lambda. $$ Proof: double count pairs $(B,T)$ where $B$ is a block and $S \subset T \subset X$ with $|T|=t$.

Cor. 1.7: If a $t$-($v,k,\lambda$) design exists then $$ {k-s \choose t-s} \left| {v-s \choose t-s} \lambda \right. $$ for each $s=0,1,\ldots,t-1.$

Example:

$b := \lambda_0 =$ # blocks and
$r := \lambda_1 =$ # blocks containing a given point [if $t \gt 0$...]

satisfy $$ b k = v r. $$ Likewise if $t=2$ then we have $$ r = \left({v-1 \choose 1} \left/ {k-1 \choose 1}\right.\right) \lambda = \frac{v-1}{k-1} \lambda $$ so $(v-1)\lambda = r(k-1)$ [p4, (1.9)].

Even for $\lambda=1$, infinitely many examples known with $t=2,3$ but only finitely many for $t=4,5$ (we’ll see all the \ldquo;classical\rdquo; ones) and none known with 6 or more! [Update: though thanks to Keevash, as of 2014 we know they exist.]

What does “up to equivalence” mean?

p.3 isomorphism from $(X,{\mathfrak B})$ to $(X',{\mathfrak B}')$: bijection $f: X \to X'$ that takes $\mathfrak B$ to ${\mathfrak B}'$.

Automorphism of $(X,{\mathfrak B})$ = isomorphism $(X,{\mathfrak B}) \to (X,{\mathfrak B})$; these form a group.

If $G$ is $t$-transitive, or even transitive on $t$-subsets, then $(X,{\mathfrak B})$ is automatically a $t$-design. Many $t$-designs explained this way, including $\Pi_2$ (and Petersen).

and the fact that the RHS is invertible. We showed that equality holds if the dual design ${\mathfrak D}^{\sf T}$ is also a 2-design, and noted that in that case $M$ is a square matrix. A further necessary condition (part of the project of deciding which parameters $v,k,\lambda$ are realized by a $t$-design):

Theorem 1.21 (Bruck-Ryser-Chowla; p.7) Suppose there exists a square 2-$(v,k,\lambda)$ design. Then:

i) $v$ even ⇒ $k-\lambda$ is a square [NB not “$k$ is square”; that’s a typo for “$n$ is square” where CvL define $n=k-\lambda$]
ii) $v$ odd ⇒ there exist nonzero integers $x,y,z$ such that $z^2 = (k-\lambda) x^2 + (-1)^{(v-1)/2} \lambda y^2.$

Proof of (i): Recall that $\det(xI+yJ) = (x+yn) x^{n-1}$ [Lemma 1.12]. If $xI+yJ = M^{\sf T} M$ for a square matrix $M$ then $$ \det(xI+yJ) = \det M^{\sf T} \det M = \det M \det M = (\det M)^2 $$ and since $M$ is an integer matrix $\det(M)$ is an integer. So, a necessary condition is that $\det(xI+yJ)$ be a square. Now in our case $n = v$, and $x + yn = r - \lambda + v\lambda = r + (v-1) \lambda$, and we already saw (1.9) that $(v-1) \lambda = r(k-1)$ so it’s $rk$ which for a square design is $k^2$ (recall 1.15b). So $\det(M) = k (k-\lambda)^{(v-1)/2}$, which is an integer iff v is odd or $k-\lambda$ is a square. So if $v$ is even then $k-\lambda$ must be a square, as claimed.

As for (ii): the rows are vectors in ${\bf Z}^v$ whose Gram matrix of inner products is the invertible matrix $(r-\lambda) I + \lambda J$. So a necessary condition is that such vectors exist in ${\bf Q}^v$, which is to say that the quadratic form with Gram matrix $(r-\lambda) I + \lambda J$ be equivalent to the standard form with Gram matrix $I$. A necessary condition is square determinant, and the arithmetic theory of quadratic forms gives the additional condition (ii). The names BRC are not in alphabetical order because BR proved it in 1949 for the special case $\lambda=1$ of square Steiner systems (= projective planes of order $q=k-1$), and Chowla generalized in 1950 to arbitrary $\lambda$. That condition can in turn be checked “locally” modulo powers of primes dividing $k-\lambda$ and $\lambda$; for instance if $\lambda=1$, so $(v,k) = (q^2+q+1, q+1)$, we find that $(-1)^{(v-1)/2} = (-1)^{(q^2+q)/2}$ is 1 if $q$ is 0 or $3 \bmod 4$, and $-1$ if q is 1 or $2 \bmod 4$; in the former case the condition is automatically satisfied (let $x=0, y=z$) and in the latter we ask that $q = (y/z)^2 + (x/z)^2$, which by Fermat is equivalent to $q$ = sum of two integer squares and can be checked from the prime factorization of $q$. This condition is necessary but not sufficient ($q=10$, which may be still the only known case where BRC allows parameters that have been proved impossible).

Thm. 1.20 (p.6): let $B$ be a block of a 2-($v,k,\lambda)$ design. Then there are at least $k(r-1)^2 / ((k-1)(\lambda-1) + (r-1))$ blocks intersecting $B$ nontrivially [other than $B$ itself]; equality ⇔ every block other than $B$ meets $B$ in a constant number of points, in which case that constant is $1 + (k-1)(\lambda-1)/(r-1)$.

[Note that for a square design, $k=r$ simplifies that constant to $\lambda$ as expected. To recover Fisher, show that the lower bound of Thm. 1.20 is at least $b-1$ using (1.8) $bk=vr$ and (1.9) $r(k-1)=(v-1)\lambda$, see top of page 7.]

Happily it’s not the specific formula that we’ll use (we won’t cover chapter 7) — you certainly need not memorize that result for the exam! — but you should know the technique (called the “variance trick” by the textbook’s authors): obtain the first few “moments” $\sum 1, \sum i, \sum i^2$ (usually by some kind of double counting) to get at the mean and variance, which must be positive (in other words, apply Cauchy-Schwarz: the average of $i^2$ is at least the square of the average of $i$); since we have only a 2-design we can get only the zeroth, first, and second moment, but in other contexts one may be able to calculate an exploit higher moments too.

Proof of Thm. 1.20: For a block $B'$ other than $B$, let $i(B') = \#(B \cap B')$. Let $d \leq b-1$ be the number of $B'$ for which $i(B') \gt 0$, so the intersection is nonempty. We’ll find the sums of $1, i, i^2$ over those $B'$ to get the mean and variance. (The book lets $n_i$ be the number of solutions of $i(B)=i$, and finds the sum over $i$ of $n_i$, $i n_i$, and $(i^2-i)n_i$; that’s the same as summing $1, i, i^2-i$, and thus yields the sum of $1, i, i^2$ respectively.)

• The sum of 1 is of course $d$.
• The sum of $i$ is the number of pairs $(B',x)$ with $x$ contained in both $B$ and $B'$; there are $k$ choices of $x$, each giving $r-1$ choices of $B'$, so the sum is $k(r-1)$.
• Likewise the sum of $i^2-i$ is the number of triples $(B',x,y)$ where $x,y$ are distinct elements of both $B$ and $B'$, so their number is $(k^2-k)(\lambda-1)$.

Thus the sum of $i^2$ is the sum of $i^2-i$ plus the sum of $i$, which is $$ (k^2-k)(\lambda-1) + k(r-1) = k ((k-1)(\lambda-1) + (r-1)). $$ Now Cauchy-Schwarz says $$ \left(\sum 1\right) \left(\sum i^2\right) \geq \left(\sum i\right)^2, $$ with equality iff all i are equal. Therefore $d = sum(1) \geq \left(\sum i\right)^2 / \left(\sum i^2\right)$, which is exactly what we claimed; in the case of equality, the constant value of $i$ is $$ \frac{\sum i^2}{\sum i} = k \frac{(k-1)(\lambda-1) + (r-1)}{k (r-1)}, $$ which is exactly $1 + \frac{(k-1)(\lambda-1)}{r-1}$ as claimed. QED

Duality and polarity of a square design (1.18, 1.19 on page 6): If $\mathfrak D$ is a square design that is isomorphic with the dual design $\mathfrak D^{\sf T}$, then we can call $\mathfrak D$ self-dual, and any such isomorphism is called a duality of $\mathfrak D$; explicitly, it consists of bijections $\sigma: X \to {\mathfrak B}, \tau: {\mathfrak B} \to X$ such that $x \in B$ iff $\tau(B) \in \sigma(x)$. [NB the book uses exponential notation $B^\tau, x^\sigma$, which switches the order of composition of bijections; also there’s a typo in the first display of p.6: each $\mathfrak B$ (the collection of blocks) should be plain $B$ (a single block of $\mathfrak B$).] In terms of the incidence matrix $M$, the maps $\sigma,\tau$ switch rows and columns; alternatively, they are a permutation of the rows and columns that takes $M$ to $M^{\sf T}$. Composing two dualities $(\sigma,\tau)$ and $(\sigma',\tau')$ yields an automorphism $(\tau' \sigma, \sigma' \tau)$ of ${\mathfrak D} = (X,{\mathfrak B})$; also, a duality can be composed from either side with an automorphism of $\mathfrak D$ to yield another duality. So the dualities of a self-dual design $\mathfrak D$ extend ${\rm Aut}({\mathfrak D})$ to a bigger group containing ${\rm Aut}({\mathfrak D})$ with index 2.

A duality that’s an involution in this group, i.e. for which $\tau\sigma$ is the identity permutation of $X$ (and thus $\sigma\tau$ is the identity permutation of $\mathfrak B$), is called a polarity. In terms of $M$, there’s a polarity iff we can permute the rows (and columns) to get a symmetric matrix — this makes the $i$-th block the image under $\sigma$ of the $i$-th point for each $i$. For example, $\Pi_2$ is polar:

   1 1 0 1 0 0 0
   1 0 1 0 0 0 1
   0 1 0 0 0 1 1
   1 0 0 0 1 1 0
   0 0 0 1 1 0 1
   0 0 1 1 0 1 0
   0 1 1 0 1 0 0

Def. 2.1 (p.29): Graph: $G = (V,E)$ where $V$ is a finite set of “vertices” (singular = “vertex”) and $E$ is a collection of two-element subsets of $V$ (“edges”). Equivalently, a finite set $V$ with a relation that is symmetric and never reflexive. So we’re dealing only with undirected graphs – edge $\{v,v'\}$ is the same as $\{v',v\}$ – without loops (there’s no “$\{v,v\}$”) or multiple edges (each $\{v,v'\}$ can appear at most once). We say $v$ is adjacent to $v'$, or a neighbor of $v'$, in the graph iff $\{v,v'\}$ is an edge; the latter term suggests: the neighborhood of $v$ is the set of all vertices $v'$ adjacent to $v'$. We denote the neighborhood of $v$ by $G(v)$. Also we can say $v$ is “incident” with an edge $e$ iff $v$ one of its two vertices.

[Isomorphism and automorphism of graphs are defined as expected: isomorphism $G=(V,E) \to G'=(V',E')$ is a bijection $V \to V'$ that induces a bijection $E \to E'$; if $G=G'$ this is an automorphism, and the automorphisms of $G$ form a group.]

So a graph is at least a 0-$(n,2,\#E)$ design, and never a 2-$(n,2,\lambda)$ design except in the trivial cases of the null graph ($E = \emptyset$, $\lambda=0$) or the complete graph (in which $E$ consists of all 2-element subsets and $\lambda=1$). Graphs that are 1-$(n,2,d)$ designs are called regular of degree $d$. (In general the degree of a vertex $v$ of $G$ is the number of edges containing it; the text calls this the “valency” (p.30), which makes some sense if you think about chemistry and forget double (and triple etc.) bonds. So a graph is regular iff all vertices have the same degree.) But we already know that we don’t expect to do much with 1-designs. How to impose more structure than $t=1$ (too flabby, except for degree 1 or 2 and their complements) but less than $t=2$ (only trivial examples)?

As suggested by the Petersen graph:

Def. 2.4 (p.32) a graph $G$ that is neither null nor complete is strongly regular iff the number of common neighbors of any two vertices $v,v'$ depends only on whether $v$ and $v'$ are equal, adjacent or non-adjacent.

In the first case that number is just $\deg(v)$ so the graph must be regular. So we have two parameters: $n=\#V$ and $k={\rm degree}$. The other two cases give us two more parameters. We say $G = (V,E)$ is strongly regular with parameters $(n,k,\lambda,\mu)$ if:

There are $n$ vertices (i.e. $\#V = n$);
$G$ is regular of degree $k$;
any two adjacent vertices have $\lambda$ common neighbors; and
any two non-adjacent vertices have $\mu$ common neighbors.

[NB: i) excluding null or complete graphs relieves us from the conundrum of an ill-defined $\lambda$ or $\mu$ respectively.
ii) The book uses $\Gamma$, and you’re welcome to do so too, but $G$ is easier to type or TeX (though no easier to handwrite).
iii) I use American spellings but you won’t be penalized for using the text’s British spellings such as "neighbours" ;-) ]

Examples:

The complement $\bar G$ of a graph $G = (V,E)$ is $(V,\bar{E})$ where $\bar E$ is the set of all two-element subsets of $V$ not in $E$. (Same as the complement of a $t$-design.) $G$ is regular of degree $k$ iff $\bar G$ is regular of degree $\#V-k-1$. $G$ is strongly regular with parameters $(n,k,\lambda,\mu)$ iff $\bar G$ is strongly regular with parameters $(n, n-k-1, \bar\lambda, \bar\mu)$ with $$ \bar\lambda = n-2 + \mu - 2k, \quad \bar\mu = n + \lambda - 2k $$ (Prop. 2.7 (p.33), using Inclusion-Exclusion; sanity check: $\bar{\bar\lambda} = \lambda$ and $\bar{\bar\mu} = \mu$ — be sure to change $k$ to $n-k-1$ when doing this. As the text notes, since $\bar\lambda$ and $\bar\mu$ are nonnegative we must have $n \geq 2k-\lambda, n \geq 2k - \mu + 2$.)

(2.8) i) The “triangular graph” $T(m)$ has ${m \choose 2} = (m^2-m)/2$ vertices, indexed by 2-element subsets of an $m$-element set $S$; two are adjacent iff they have an element in common. (So the complement has two pairs adjacent if disjoint.) Parameters: $((m^2-m)/2, 2m-4, m-2, 4)$ [why?]. We must take $m \geq 4$, else the graph is complete (and also null if $m \lt 3$…).
$T(4)$ is the octahedron, complement of $3.K_2$: 12–34 13–24 14–23.
$T(5)$ is the complement of the Petersen graph, as you can check from its labeling in the introductory handout.
These examples may be misleading: for $m$ large enough, $T(m)$ has smaller degree than its complement (how large is “large enough”?). See the second picture on p.35 (Fig. 2.3) for $T(9)$, and note the convention (p.34) for drawing this graph so the picture doesn’t become an ugly clutter.
Automorphism group contains the symmetric group $S_m$, and usually equals $S_m$, though with a couple of exceptions – trivial for $m=2$, a bit more interesting for $m=4$. We’ll use this to study the structure of $S_m$ later in the course.

ii) “Square lattice graph” $L_2(m)$: vertices = $S \times S$ with $\#S = m$; two vertices are adjacent iff they have a common coordinate; parameters $(m^2, 2m-2, m-2, 2)$. Why doesn’t $S \times T$ work if $\#S \neq \#T$? Must have $m \gt 1$; $L_2(2)$ is a 4-cycle and the complement of $2.K_2$ (the only cycles that are strongly regular with our definitions are the 4- and 5-cycle); for $L_2(3)$ see Figure 2.2 (p.34); this graph is its own complement (Problem 5ii = page 45). Automorphism group? It contains (and we’ll soon easily show it equals) the wreath product $S_m\ {\rm wr}\ S_2$, with $2 m!^2$ elements.

iii) (2.9, p.34-35) for $r \gt 1$ and $m \gt 1$ the disjoint union $r.K_m$ of $r$ complete graphs of order $m$ is strongly regular with parameters $(rm, m-1, m-2, 0)$ — the only strongly regular graphs with $\mu = 0$. See page 34-35 for some further quaint terminology involving some of these graphs and their complements.

Since we use $\{1,2,...,n\}$ to index both vertices and rows/columns, it’s useful to think of the $(i,j)$ entry $a_{i,j}$ as being really the $(x,y)$ entry where $x = v_i$, $y = v_j$. This makes it canonical: $A$ is really a linear operator (self-transformation) on a vector space ${\bf R}^V$ with an orthogonal basis $\{e_x : x \in V\}$, and it takes $e_x$ to $\sum_{y \in G(x)} e_y$, that is, to the sum of $e_y$ over $y$ in the neighborhood of $x$ — morally speaking it takes $x$ to $G(y)$. For example, the degree of $x$ is the inner product of $Ae_x$ with the all-1’s vector ${\bf j}$, which (since $A$ is symmetric) is also the inner product $\langle e_x, A{\bf j}\rangle$. A graph is regular of degree $k$ iff $A{\bf j} = k {\bf j}$, i.e. iff $\bf j$ is a $k$-eigenvector of $A$. The adjacency matrix of the complementary graph $\bar G$ is $J-I-A$ (where $J$ is the all-1\rsquo;s square matrix of order $n$, as in Chapter 1).

So what does $A^2$ do? Well, $A e_x$ to the sum of $e_y$ over neighbors $y$ of $x$, so $A^2 e_x$ is the sum of $A e_y$ over those $y$. Writing $A e_y = \sum_{z \in G(y)} e_z$, we see that the $(x,z)$ entry of $A^2$ is the number of paths $(x,y,z)$ of length $2$ (note that $x=z$ is allowed). Likewise the $(x,x')$ entry of $A^3$ is the number of length-3 paths $(x,y,z,x')$ (again with repeats and backtracks allowed), etc. For that matter the $(x,y)$ entry of $A=A^1$ is the number of length-1 paths, i.e. the number of edges $\{x,y\}$; and the $(x,y)$ entry of $A^0$ is 1 if $x=y$ and 0 else, so it does behave like the number of “length-0 paths”… For an undirected graph, the length-$m$ paths from $x$ to $x'$ are in bijection with the length-$m$ paths from $x'$ to $x$ (just retrace the path backwards), so $A^m$ is symmetric, as it should be since $A$ is.

Now we know from linear algebra that we can analyze $A^k$ via the “spectrum” (i.e. eigenvalues) and eigenspaces of $A$. This is one reason why the adjacency matrix and its spectrum constitute such an important graph invariant. [Note that the spectrum really is a graph invariant: reindexing the vertices changes $A$ to a similar matrix but does not change the spectrum; equivalently, it’s just a different indexing of the coordinates for the linear operator on ${\bf R}^V$.] A further example: the diagonal entries of $A^m$ are the number of closed paths $(x_1,x_2,...,x_m)$ of length $m$ going through a given vertex $x_1$; thus the sum is the number of closed paths with no restriction on the $x_m$ (and with a choice of initial point $x_1$ and direction, e.g. each pentagon counts $10$ times). But the sum of the diagonal entries of a matrix is its trace, and the trace of $A^m$ is the sum of the $m$-th powers of its eigenvalues counted with multiplicity.

In the case of equality we say $G$ is a Moore graph of girth 5. Equivalently, a Moore graph of degree 5 s a strongly regular graph with parameters $(k^2+1, k, 0, 1)$..

For higher odd girths $g$, see Exercise 9 on page 45; but it turns out that past $g=5$ the only such graph is a $g$-cycle, as can be shown by generalizing our techniques to study the spectrum of the adjacency matrix of such a graph In PS4 you will find a similar analysis of minimal graphs of degree $d$ and girth 6. For other values of the girth, see e.g. Bollobás’s book Extremal Graph Theory.

In particular we’ll prove the simplicity of $A_n$ ($n\gt4$) and ${\rm PSL}_n(k)$ ($n\gt2$, or $n=2$ and $\#k\gt3)$, explaining how simplicity fails in small cases like $A_4$ and ${\rm PSL_2(F_3)}$, and also prove the simplicity of each $M_n$ (which will lead us to the corresponding Steiner systems); and use some of our designs and graphs to explain some other remarkable behavior like coincidences among some of these groups (listed below) and the automorphism group of $S_6$ (which, uniquely among all $S_n$, is larger than its group of inner automorphisms). We’ll temporarily leave our textbook, relying on my text and TeX notes and some other sources, except for using some of Chapter 6 (on ${\rm Aut}(S_6)$).

The isomorphisms we’ll address are as follows (listed by increasing group size):

		12		$A_4 \cong {\rm PSL_2}({\bf F}_3)$
'		24		$S_4 \cong {\rm PGL_2}({\bf F}_3)$
		60		$A_5 \cong {\rm (P)SL_2}({\bf F}_4) \cong {\rm PSL_2}({\bf F}_5)$
'		120		$S_5 \cong {\rm \Sigma L_2}({\bf F}_4) \cong {\rm PGL_2}({\bf F}_5)$
		168		${\rm (P)SL}_3({\bf F}_2) \cong {\rm PSL_2}({\bf F}_7)$
'		336		${\rm Aut}\bigl({\rm (P)SL}_3({\bf F}_2)\bigr) \cong {\rm PGL_2}({\bf F}_7)$
		360		$A_6 \cong {\rm PSL_2}({\bf F}_9)$
		20160		$A_8 \cong {\rm (P)SL_4}({\bf F}_2)$

and for $n=7$ and higher we can’t tell because we don’t know how many coincident triples of secants there are. So this technique cannot work (at least not in this form) past $q=5$.

Also, just how transitively do we expect ${\rm Aut}(\Pi)$ to act? Suppose $\Pi = {\bf P}^2({\bf F}_q)$ and consider ${\rm PGL}_3({\bf F}_q)$. This group acts 2-transitively; not 3-transitively because of collinearity, but that’s the only obstruction even up to $4$ points. Indeed for any $P_1,P_2,P_3,P_4$ no three of which are collinear, and any $Q_1,Q_2,Q_3,Q_4$ no three of which are collinear, there is an automorphism in ${\rm PGL_3}({\bf F}_q)$ taking $P_1$ to $Q_1$, $P_2$ to $Q_2$, $P_3$ to $Q_3$, and $P_4$ to $Q_4$ — and this automorphism is unique! More generally we have (whether or not $k$ is finite)::

Proposition: For any field $k$, the group ${\rm PGL}_n(k)$ acts simply transitively on ordered $(n+1)$-tuples of points in ${\bf P}^{n-1}(k)$ in general linear position.

“Simply transitively” means that for any two such $(n+1)$-tuples $(P_0,P_1,\ldots,P_n)$ and $(Q_0,Q_1,\ldots,Q_n)$ there is a unique group element taking one to the other. “General linear position” means no $3$ points on a line, no $4$ on a plane, …, no $n$ on a hyperplane. This last condition is actually sufficient: if we have $k$ points on a projective subspace of dimension $k-2$ then any $n$ points containing them are on a subspace of dimension $n-2$. Equivalently, general linear position that if we lift $P_0,P_1,\ldots,P_n$ to nonzero vectors $v_0,v_1,\ldots,v_n \in k^n$ then any $n$ of these $n+1$ vectors form a basis for $k^n$.

Proof: It is enough to prove this for one choice of $(P_0,P_1,\ldots,P_n)$. Let $P_0$ be $(1:1:1:\ldots:1)$, and for each $i=1,2,\ldots,n$ let $P_i$ be the (1-dimensional subspace of $k^n$ generated by) the $i$-th unit vector. Let $v_0,\ldots,v_n$ be nonzero vectors in $k^n$ corresponding to $Q_0,\ldots,Q_n$. General linear position $\Leftrightarrow$ any $n$ of these are linearly independent $\Leftrightarrow$ any $n$ of these form a basis. So there’s a linear map $T$ taking each $e_i$ to the corresponding $v_i$. This map is unique, so how do we get $P_0$ to go to $Q_0$? Projectively, $P_1,\ldots,P_n$ go to $Q_1,\ldots,Q_n$ iff each $e_i$ goes to $c_i v_i$ for some nonzero scalar $c_i$, and any choice of $(c_1,\ldots,c_n)$ gives a unique $T$; conversely $T$ determines $(c_1:\ldots:c_n)$ [note the colons: these are projective coordinates]. Now $v_1,\ldots,v_n$ is a basis, so $v_0 = a_1 v_1 + \ldots + a_n v_n$ for some scalars a_1,...,a_n; moreover none of them are zero because then there’d be a linear dependence among $v_0$ and the other $n-1$ vectors $v_i$. So choose $(c_1:\ldots:c_n) = (a_1:\ldots:a_n)$ and we’re done. QED

Note that it should follow that $\#({\rm PGL}_n({\bf F}_q))$ is the number of ordered $(n+1)$-tuples of points in general linear position in ${\bf P}^{n-1}({\bf F}_q)$; this can be checked directly (as we in effect did for $q=n=3$).

OK, so we expect transitivity on $n$-arcs for $n=4$ but not beyond. Yet a hyperoval in $\Pi_4$ has $6$  points. How can this be?

Let’s count: taking q=4 in the above n-arc counts, we find that the number of ordered hyperovals is $$ 21 \cdot 20 \cdot 16 \cdot 9 \cdot 2 \cdot 1 = 6! \cdot 168. $$

in particular, having chosen the first 4 points we have no choice about the last 2 except for their order. We can give explicit coordinates starting from those of our proof above for the first 4 points: each of the remaining two must have nonzero coordinates, all distinct. Scaling the first to 1, there are only two choices: $(1:a:b)$ and $(1:b:a)$, where $a,b$ are the elements of ${\bf F}_4$ other than $0$ and $1$, satisfying $$ ab = a+b = a^3 = b^3 = 1. $$

So we have the hyperoval consisting of the points

and now it’s clear that the remaining two points are switched by the automorphism of ${\bf P}^2({\bf F}_4)$ that takes each coordinate to its Galois conjugate: $0,1,a,b$ go to $0,1,b,a$ respectively.

So in fact it is reasonable to expect even for $n=4$ that every bijection of hyperovals lifts to a unique isomorphism of projective planes (provided it’s true that $\Pi_4$ is the unique order-4 projective plane up to automorphism). That is what we shall prove.

Before starting this, recall yet another way that n=4 is special. We know one way of getting hyperovals in an algebraic projective plane ${\bf P}^2(k)$ when $\#k$ is even: use a conic plus its center. If all ordered hyperovals are equivalent then any point can be the center. How can this be? Two conics can meet in at most 4 points (Bézout). But that’s just enough for center-switching to work for $\#(k)=4$. (It also works for $\#(k)=2$, but that’s not as surprising…)

OK: start with any order-4 projective plane $\Pi$ and one of its $6! \cdot 168$ ordered ovals $O = \{p_1,p_2,p_3,p_4,p_5,p_6\}$. This lets us identify $15$ of the lines: the ${6 \choose 2} = 15$ secants $s_{i,j}$. That leaves $15$ points and $6$ passant lines to account for. Each of the $15$ points is on $3$ secants and $2$ passants. This immediately tells us (check this!) that the passant lines form a hyperoval $O^*$ in the dual projective plane $\Pi^*$, whose secants are the $15$ points off $O$. How to label $O^*$? Since we’ll show that any permutation $g$ of $O$ lifts uniquely to ${\rm Aut}(\Pi)$, we have a homomorphism from the permutations of $O$ to those of $O^*$ — and that turns out to be an outer automorphism from $S_6$ to $S_6$ ! We’ll see how this happens next.

Consider one of these points $q$. It is contained in $6/2=3$ secants of $O$, and thus $5-3=2$ passant lines. Now the secants determine a partition of $O$ into three pairs. A partition of a six-element set into three pairs is called a syntheme in this context. For any $n$, the number of partitions of a $2n$-element set into $n$ pairs is $$ 1 \cdot 3 \cdot 5 \cdot 7 \cdots (2n-1) = \frac{(2n)!}{2^n n!}. $$

Recall that we found in $\Pi_4$ a hyperoval $O$ and a dual oval $O*$ permuted by $S_6$ in different ways, and showed that the resulting outer automorphism of $S_6$ is essentially unique (i.e., unique up to inner automorphism). Such 6-element sets $O,O^*$ with non-conjugate actions of $S_6$ are said to be “dual” to each other. This duality gives:

• a bijection between 15 pairs in $O$ and 15 synthemes in $O^*$;
• a bijection between 15 synthemes in $O$ and 15 pairs in $O^*$;
• a bijection between 10 even splits of $O$ and 10 even splits in $O^*$.

                  132
                66    66
             30    36    30
          12    18    18    12
        4     8    10     8     4
     1     3     5     5     3     1
  1     0     3     2     3     0     1

[See page 22 of the textbook; a reference for practically all the group theory we shall need, and much more, is Joseph J. Rotman’s An Introduction to the Theory of Groups (Springer 1995), which you can view (and download for personal use only) from hollis.harvard.edu on a Harvard computer.]

We saw(*) that if a projective plane $\Pi$ of order $n$ is extendable then either $n=2$ or $n=4$, and in both cases $\Pi$ is algebraic. For $n=2$, the extension is the Hadamard 3-(8,4,1) design. For $n=4$ it must be a 3-(22,6,1) Steiner system. We investigate this case next; it also leads us to the 4-(23,7,1) and 5-(24,8,1) systems and the Mathieu groups, via a construction that the text attributes to Lüneburg (page 22).
(*) assuming the nonexistence of a projective plane of order 10, or at any rate of an extendable one.

A 3-(22,6,1) design $\mathfrak D = {\mathfrak D}_{22}$ has ${22 \choose 3} \big/ {6 \choose 3} = 77$ blocks. Choosing a point p and identifying the derived design ${\mathfrak D}_p$ with $\Pi_4$, we see that the blocks are:
21: $p$ + line
56: hyperoval
[BTW the CvL text uses $\infty_1$ for $p$, and likewise $\infty_2,\infty_3$ for the points that extend $\mathfrak D$ further to 4-(23,7,1) and 5-(24,8,1); other sources use I,II,III.] The intersection triangle is as follows (see Table 1.1 on page 21, and ignore for now the leftward diagonals that start 759 and 253):

	    77 
	  56  21
	40  16   5
      28  12   4   1
    20   8   4   0   1
  16   4   4   0   0   1
16   0   4   0   0   0   1

In particular any two of the 56 hyperovals intersect in 0 or 2 points. It turns out that this is an equivalence relation on the 168 hyperovals (that is: if we say $O \sim O'$ if $O,O'$ are hyperovals that are equal or intersect in 0 or 2 points, then $\sim$ is an equivalence relation), with three equivalence classes. We could check this combinatorially, but what does it “mean”?

Recall that all hyperovals are equivalent under ${\rm Aut}(\Pi_4)$, and every element of ${\rm Aut}(\Pi_4)$ is either in ${\rm PGL}_3({\bf F}_4)$ or is the Galois conjugate of an element of ${\rm PGL}_3({\bf F}_4)$. So, say we have two hyperovals $O,O'$. We can get from $O$ to $O'$ by some $g_0 \in {\rm Aut}(\Pi_4)$. Then $g \in {\rm Aut}(\Pi_4)$ takes $O$ to $O'$ iff $g = g_0 h$ with $h(O)=O$, i.e. with $h$ in the stabilizer ${\rm Stab}(O)$. We have already identified ${\rm Stab}(O)$ with the group $S_6$ of permutations of $O$; and we’ve also seen that a permutation $\pi$ of $O$ comes from ${\rm PGL}_3({\bf F}_4)$ [without a Galois conjugation] iff $\pi$ is even. So, composing with an odd permutation if necessary, we can assume that $g_0 \in {\rm PGL}_3({\bf F}_4)$, and then $g \in {\rm PGL}_3({\bf F}_4)$ takes $O$ to $O'$ iff $g = g_0 h$ for some $h$ in the subgroup $A_6$ of ${\rm Stab}(O)$.

Now I claim:

   1) There exists a well-defined surjective homomorphism $\det: {\rm PGL_3}({\bf F}_4) \to {\bf F}_4^*$;

   2) $A_6$ is in the kernel ${\rm PSL_3}({\bf F}_4)$ of $\det$;

whence it follows that

   3) All $g$ taking $O$ to $O'$ have the same determinant.

Thus we can define an equivalence relation on the 168 hyperovals by defining

   $O \sim O'$ iff there exists $g \in {\rm PSL_3}({\bf F}_4)$ taking $O$ to $O'$.

This equivalence relation partitions the hyperovals into 3 equivalence classes, each of size $168/3=56$.

It turns out that this is the equivalence relation we need to extend $\Pi_4$.

Proof of (1): we know from linear algebra that there is a surjective homomorphism $\det: {\rm GL}_3({\bf F}_4) \to {\bf F}_4^*$. The point is that this homomorphism takes every scalar $3 \times 3$ matrix to 1, and thus “factors through the quotient”: for any nonzero scalar $c$ and any $3 \cdot 3$ matrix $g$ we have $\det(cg) = c^3 \det(g) = \det g$, so the determinant can be defined even when we identify $cg$ with $g$.

Proof of (2) (and thus of (3)): The kernel of $\det: A_6 \to {\bf F}_4^*$ is normal and of index 1 or 3. But $A_6$ is simple, and of order $\gt 3$ Therefore $\ker(\det)$ is all of $A_6$, as claimed.

Having partitioned the 168 orbits into three equivalence classes each of size 56, we next show that any of these equivalence classes yields a 3-(22,6,1) design. Fix any three points. We claim they’re in a unique block. If one of the three is $p$, the other two lie on a unique line and we’re done. If not, but they’re collinear, we’re still done (they can’t be on a hyperoval because no hyperoval meets a line in as many as three points). Finally, if three non-collinear points, put them at the three unit vectors, and then exactly one of the three hyperovals through them works. Indeed if $O$ is any oval then ${\rm diag}(1,1,a)$ and ${\rm diag}(1,1,b)$ takes $O$ to some hyperovals $O', O''$ in the other two equivalence classes, so exactly one of $O, O', O''$ is in the class we chose. So there exists a 3-(22,6,1) design ${\mathfrak D}_{22},$ as desired.

We next show that the three equivalence classes are the only sets $\mathfrak S$ of 56 hyperovals such that $\#(O\cap O')$ is even for all $O,O' \in {\mathfrak S}$. [This $\mathfrak S$ is a fraktur S.] To this end we prove that our two equivalence relations on hyperovals are the same: hyperovals $O,O'$ are in the same ${\rm PSL_3}({\bf F}_4)$ orbit iff $\#(O\cap O')$ is even. The forward direction follows from the fact that these hyperovals are blocks of a 3-(22,6,1) design and we already used the intersection triangle to show that the intersection always has size 0, 2, or 6. Thus the reverse direction is equivalent to the claim that given a hyperoval $O$ there are $112$ hyperovals $O'$ such that $\#(O\cap O')$ is odd. (Note that $112 = 168 - 56 = (2/3) \cdot 168$.) We prove this using another intersection triangle. While the hyperovals do not constitute a 3-(21,6,\lambda) design, they do satisfy the hypothesis that for $S \subseteq O$ the number of $O'$ such that $S \subseteq O \cap O'$ depends only on $s := \#S$. For $s \leq 4$ this follows from transitivity of the action of ${\rm PGL_3}({\bf F}_4)$ on $s$-tuples of points on general linear position; for $s \geq 4$ it follows from the fact that $O$ is the only hyperoval containing $S$. The counts $\nu_{s,s}$ are: $$ \nu_{0,0} = 168, \ \nu_{1,1} = \frac6{21} 168 = 48, \ \nu_{2,2} = \frac5{20} 48 = 12, \ \nu_{3,3} = \frac4{16} 12 = 3, \ \nu_{4,4} = \nu_{5,5} = \nu_{6,6} = 1. $$

The resulting intersection triangle is

	    168
	  120 48
	84  36  12
      57  27   9   3
    37  20   7   2   1
  22  15   5   2   0   1
10  12   3   2   0   0   1

As a “sanity check”, the total number of hyperovals should be $\sum_{j=0}^6 {6 \choose j} \nu_{6,j}$ which indeed comes to $$ 10 + 6\cdot 12 + 15 \cdot 3 + 20\cdot 2 + 1 = 10 + 72 + 45 + 40 + 1 = 168. $$

The even $j$ contribute $10 + 45 + 1 = 56$ to the sum, and the odd $j$ contribute $72 + 40 = 112$ as claimed.

This means that $\mathfrak D$ is the unique 3-(22,6,1) design up to isomorphism, and indeed for any 3-(22,6,1) design ${\mathfrak D}' = (X',{\mathfrak B}')$ and any point $p' \in X'$ we may choose an isomorphism ${\mathfrak D}' \to {\mathfrak D}_{22}$ taking $p'$ to $p$. Taking ${\mathfrak D}' = {\mathfrak D}_{22}$ we conclude that ${\rm Aut}({\mathfrak D}_{22})$ is 3-transitive on points (and thus transitive on blocks).