%% Paper on perfect 1-factorisations and atomic squares by Ian M Wanless
%% A 16 page paper in plain TeX.

\input epsf

\magnification 1200
\baselineskip=14pt
\nopagenumbers

\hsize=6.5 true in  
\vsize=8.65 true in  
%% Note that the catalogue of Latin squares towards the end
%% of the paper does not fit inside an hsize of 6.0in. Also
%% the editor informs me that a vsize of 9in is too much
%% so I've trimmed it a little. 8.5in gets bad breaks.

\voffset=2\baselineskip % To compensate for headline
\font\sm =cmr8
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 
        {\smcp the electronic journal of combinatorics 6 (1999),
        \#R9\hfill\folio} \else\hfill \fi} 

\font\bigger=cmr10 scaled\magstep2

\newcount\secno
\def\section#1.#2\par{\global\advance\secno by1 \secmark#1
        \bigbreak\bigskip\noindent{\bf\S\number\secno. #2}\par\medskip}
\def\secmark#1{\xdef#1{\the\secno}    \save{#1}}
\secno=0

\newcount\thrmno
\def\thrm#1.#2\par{\global\advance\thrmno by1 \thrmmark#1
        \medbreak\medskip\noindent
        {\bf Theorem \number\thrmno.}{\sl #2}\par\medskip}
\thrmno=0
\def\thrmmark#1{\xdef#1{\the\thrmno}    \save{#1}}
\def\thcall#1{Theorem~\number#1}
\def\numon#1{\number#1}

\newcount\lemno
\def\lem#1.#2\par{\global\advance\lemno by1 \lemmark#1
        \medbreak\medskip\noindent
        {\bf Lemma \number\lemno.}{\sl #2}\par\medskip}
\lemno=0
\def\lemmark#1{\xdef#1{\the\lemno}   \save{#1}}
\def\lemc#1{Lemma~\number#1}

\newcount\eqnno
\eqnno=0
\def\eqmark#1{\global\advance\eqnno by 1 \xdef#1{\the\eqnno} \save{#1}}
\def\eqcall#1{(\number#1)}
\def\ref#1{\eqmark#1 \eqno(\number\eqnno)}

\def\prf{\noindent {\bf Proof:} }
\def\endpf{\hfill$\odot$\rightskip=0pt\medbreak}

\newcount\biblno 
\biblno=0 
\def\bibl#1{\global\advance\biblno by1 \xdef#1{\the\biblno} \save{#1}} 
\def\bibcl#1{[\number#1]}
\def\bibit#1{\bibl{#1}\item{\bibcl{#1}}}

\newcount\tabnum
\newbox\tablabel
\tabnum=0
\def\Tab#1#2{\par  \global\advance\tabnum by 1 
        \xdef#1{\the\tabnum}
        \save{#1}
        \global\setbox\tablabel=
                \vbox{\narrower\narrower\noindent Table #1: #2\par}
        \ifdim\ht\tablabel>\the\baselineskip \copy\tablabel\par 
                \else \centerline{Table #1: #2} 
        \fi
}

%%\input perfact.ref
%%\newwrite\reffile
\def\save#1{}  %% disabled
%%\def\save#1{\write\reffile{\noexpand\def\noexpand#1{#1}}}
%%\openout\reffile=perfact.ref
%%The references are now hardwired, like so:

\def \Sintro {1}
\def \Ssimpres {2}
\def \lmperfpH {1}
\def \lmninf {2}
\def \lmconjs {3}
\def \lmprimes {4}
\def \lmnotmostpan {5}
\def \efourconjs {1}
\def \lmevens {6}
\def \Scompgr {3}
\def \lmrosacon {7}
\def \lmmoreprimes {8}
\def \ealtphsq {2}
\def \lmtwiceprime {9}
\def \Satom {4}
\def \lmatom {10}
\def \lmsplitatom {11}
\def \STD {5}
\def \Ssmallord {6}
\def \eninfseven {3}
\def \eninfnine {4}
\def \Sothninf {7}
\def \tbNtwo {1}
\def \SRef {8}
\def \BAdCRC {1}
\def \BAdMd {2}
\def \BAnd {3}
\def \BBrwr {4}
\def \BDeKeo {5}
\def \BDeKet {6}
\def \BGbMd {7}
\def \BHnrcth {8}
\def \BHtRd {9}
\def \BBdm {10}
\def \BNrtn {11}
\def \BSadet {12}
\def \BStein {13}
\def \BWall {14}

\def\self{involutory}
\def\ninf{$N_\infty$ square}
\def\ntwo{$N_2$ square}
\def\pH{pan-Hamiltonian}
\def\rowinv#1{R^{-1}(#1)}
\def\transp#1{#1^T}
\def\cycgrp{{\cal C}}
\def\pfact{{\cal F}}
\def\onef{{\cal F}}
\def\numcg#1{\nu(#1)}
\def\mod#1{\ ({\rm mod}\ #1)}
\def\frac#1#2{{\textstyle{#1\over#2}}}
\def\half{\frac12}
\def\train#1{{\cal T}(#1)}
\def\qd{\quad}

\centerline{\bigger Perfect factorisations of bipartite graphs and}
\smallskip 
\centerline{\bigger Latin squares without proper subrectangles}

\bigskip

\centerline{
\vbox{\halign{#&#\hfill&#\cr
&I.~M.~Wanless&\cr &Department of Mathematics and Statistics&\cr
&University of Melbourne&\cr &Parkville Vic 3052 Australia&\cr
\noalign{\hrule height5pt width0pt}\cr
&ianw@ms.unimelb.edu.au&\cr}} }

\medskip

\centerline{Submitted: November 16, 1998;\quad Accepted January 22, 1999.}
\centerline{AMS Classifications: 05B15, 05C70.}

\line{\hrulefill}

A Latin square is \pH\ if every pair of rows forms a single
cycle. Such squares are related to perfect 1-factorisations of the
complete bipartite graph. A square is atomic if every conjugate is
\pH. These squares are indivisible in a strong sense -- they have no
proper subrectangles.  We give some existence results and a catalogue
for small orders.
In the process we identify all the perfect 1-factorisations of
$K_{n,n}$ for $n\leq9$, and count the Latin squares of order $9$
without proper subsquares.

\line{\hrulefill}


\section\Sintro. Introduction

For $k\leq n$, a $k\times n$ {\it Latin rectangle\/} is a $k\times n$
matrix of entries chosen from some set of symbols of cardinality $n$,
such that no symbol is duplicated within any row or any column.
Typically we assume that the symbol set is $\{1,2,\dots,n\}$.  We use
$L(k,n)$ for the set of $k\times n$ Latin rectangles.  Elements of
$L(n,n)$ are called {\it Latin squares\/} of order $n$. The symbol in
row $r$, column $c$ of a Latin rectangle $R$ is denoted by $R_{rc}$. A
Latin square $S$ is {\it idempotent\/} if $S_{ii}=i$ for each $i$.

If the symbol set of a Latin rectangle $R$ is $\{1,2,\dots,n\}$ then
each row $r$ is the image of some permutation $\sigma_r$
of that set. That is, $R_{ri}=\sigma_r(i)$. Moreover,
each pair of rows $(r,s)$ defines a permutation 
by $\sigma_{r,s}=\sigma_r\sigma_s^{-1}$.
Naturally $\sigma_{r,s}=\sigma_{s,r}^{-1}$. Any of these permutations
may be written as a product of disjoint cycles in the standard way.
If this product consists of a single factor we call the permutation
a {\it full cycle permutation\/}.

A {\it subrectangle} of a Latin rectangle is a submatrix (not
necessarily consisting of adjacent entries) which is itself a Latin
rectangle. If it happens to be a Latin square it is called a {\it
subsquare}.  An $a\times b$ subrectangle of a $k\times n$ Latin
rectangle is {\it proper\/} provided we have the strict inequalities
$1<a<k$ and $1<b<n$.  A Latin square without subsquares of order 2 is
said to be $N_2$ and a Latin square without proper subsquares is $N_\infty$.
Latin squares with no proper subrectangles will be of central interest
in this paper.

There are some important equivalence relations for Latin squares.  Two
squares are {\it isotopic\/} if one can be obtained from the other by
rearranging the rows, rearranging the columns and renaming the
symbols.  The set of all squares isotopic to a given square forms an
{\it isotopy class\/}.  The second operation is {\it conjugacy\/}.
Here instead of permuting within the sets of rows, columns and
symbols, we permute the sets themselves.  For example, starting with a
square $S$, we might interchange rows with columns to get $\transp S$,
the transpose of $S$.  Alternatively, we could interchange the roles
of columns and symbols to get a square $\rowinv S$, which we call
the {\it row inverse\/} of $S$.  Note that $\rowinv{S}$ can be
obtained from $S$ by replacing $\sigma_r$ by $\sigma_r^{-1}$ in each
row $r$.  If it happens that $S=\rowinv{S}$ then clearly each
$\sigma_r$ must be an involution and we say that $S$ is {\it \self\/}.
The operations of transposition and row inverse generate a
conjugacy class consisting of 6 conjugates $\{S, \transp{S},
\rowinv{S}, \transp{(\rowinv{S})}, \rowinv{\transp{S}},
\transp{(\rowinv{\transp{S}})}\}$. The closure of an isotopy 
class under conjugacy yields a {\it main class}.


Two edges of a graph are {\it independent\/} if they do not share a
common vertex.  A set of pairwise independent edges which covers the
vertices of a graph is called a {\it 1-factor\/} (also known as a {\it
perfect matching\/}).  A partitioning of the edges of a graph into
1-factors is a {\it 1-factorisation\/}.  A 1-factorisation is {\it
perfect\/} if the union of any two of its 1-factors is a single
(Hamiltonian) cycle. For a full discussion of 1-factorisations see
\bibcl\BWall, and for a short summary of known results consult
\bibcl\BAdCRC.

There is a close relationship between Latin rectangles and
1-factorisations in regular bipartite graphs, in which each row of a
rectangle corresponds to a 1-factor. For each $R\in L(k,n)$ we can
form $G(R)$, a $k$-regular subgraph of $K_{n,n}$ in which the vertex
sets correspond to the columns and the symbols, and an edge indicates
that the symbol is used in the column. The Latin property of $R$ means
that the edges corresponding to the (column, symbol) pairs within a
row are a 1-factor, and the 1-factors corresponding to different rows
are disjoint.  Hence $R$ prescribes a 1-factorisation of $G(R)$ in a
natural way.  In this paper we investigate the case where the
1-factorisation happens to be perfect. An alternative way to view our
results in terms of transversal designs will be discussed briefly in
\S\STD.

If $R$ is a $2\times a$ subrectangle of some Latin square $L$, and $R$
is minimal in that it contains no $2\times b$ subrectangle for $b<a$,
then we say that $R$ is a row cycle of length $a$. Column cycles and
symbol cycles are defined similarly, and the operations of conjugacy
on $L$ interchange these objects. Note that there is a natural 1:1
length-preserving correspondence between row cycles involving rows
$r,s$ and cycles in $\sigma_{r,s}$.  We are interested in the case
where all row cycles are as long as possible:

\proclaim Definition. A Latin rectangle $R\in L(k,n)$ is \pH\ if every
row cycle of $R$ has length $n$. Equivalently, $R$ is \pH\ if
$\sigma_{r,s}$ is a full cycle permutation for each pair of rows $r,s$
in $R$.

The name \pH\ comes from \bibcl\BHtRd, where it is used to describe a
Latin square in which each symbol cycle is Hamiltonian.  We prefer to
base our definition on row cycles because it then makes sense for Latin
rectangles which are not squares. Our definition is clearly related to
that of \bibcl\BHtRd\ by conjugacy.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section\Ssimpres. Basic properties

We examine a few simple properties of \pH\ squares. Firstly, from the
discussion in the introduction we have:

\lem\lmperfpH. There is a \pH\ square of order $n$ if and only if 
$K_{n,n}$ has a perfect 1-factorisation.

In fact the concepts of \pH\ squares and bipartite perfect
1-factorisations are so closely linked that in what follows we will
sometimes consider them synonymous.  Our second result provides further
motivation for our study.

\lem\lmninf. A Latin square is \pH\ if and only if it contains no proper 
subrectangles.  In particular every \pH\ square is $N_\infty$.

\prf  If $L\in L(n,n)$ is not \pH\ then it contains a row cycle of length
less than $n$ and this row cycle immediately gives a proper
subrectangle. Conversely, suppose $L$ contains a proper subrectangle
$R$.  Then $R$ has at least two rows so it contains at least one row
cycle $C$.  For $R$ to be proper, $C$ must have length less than
$n$. But $C$ is a row cycle of $L$, so $L$ is not \pH. \endpf

\lemc\lmninf\ gives a good reason to be interested in \pH\ Latin squares,
but also shows that constructing them is likely to be difficult. Note
that at this stage the existence question for \ninf s is not
completely resolved. Heinrich \bibcl\BHnrcth\ gave a construction
for $n=pq\neq6$ where $p$ and $q$ are prime, which was later
generalised in \bibcl\BAdMd\ to all orders except those of the form
$2^a3^b$. Only a few sporadic orders from the remaining case have
since been settled. Some small order examples have been discovered by
computer searches.  Perfect 1-factorisations have also been successfully
employed and offer greater hope of producing infinite classes of
examples.

\lem\lmconjs. If $L$ is a \pH\ square then so is any square isotopic to 
$L$, and so is $\rowinv{L}$.

\prf Isotopies preserve the lengths of row cycles and hence also the 
\pH\ property. 
The implication that $\rowinv{L}$ is \pH\ follows from the observation
that the inverse of a full cycle permutation is also a full cycle
permutation.\endpf

Note that the operations discussed in \lemc\lmconjs\ correspond to the
natural notion of isomorphism for perfect 1-factorisations. Suppose
that from a Latin square $L$ we construct a complete bipartite graph
$G$ with vertex sets $U$ and $V$, and a 1-factorisation of $G$ with
1-factors $F$. Then an isotopy of $L$ corresponds to a
relabelling/reordering of the sets $U,\ V$ and $F$. Also, taking the
row inverse of ${L}$ corresponds to switching the sets $U$ and $V$.
For a formal definition of isomorphism between 1-factorisations, and
some invariants with which to distinguish non-isomorphic
factorisations, see Chapter 11 of \bibcl\BWall. One of the ideas there
is that of a train, which we now define for factorisations of complete
bipartite graphs.

Suppose we have $G$, a copy of $K_{n,n}$ in which the vertex sets are
$U$ and $V$.  We define $\train\onef$, the {\it train\/} of a 
1-factorisation $\onef$ of $G$, to be a directed graph (with loops) on
the triples in $U\times V\times\onef$. Each of the $n^2(n-1)$ vertices
has outdegree 1. The edge from $[u,v,f]$ goes to $[u',v',f']$ where $f$
contains the edges $uv'$ and $u'v$ and $f'$ contains the edge $uv$. It
should be clear that two isomorphic factorisations of $G$ must have
isomorphic trains.

It is worth pointing out that although the factorisations
corresponding to $L$ and $\rowinv{L}$ are isomorphic, the squares $L$
and $\rowinv{L}$ may or may not be isotopic. Examples of both types
will be given in \S\Ssmallord.

A particularly simple Latin square on the set $\{1,2,\dots,n\}$ is
the Cayley table $\cycgrp_n$ of the cyclic group of order $n$.
Here $\cycgrp=\cycgrp_n$ is defined by $\cycgrp_{ij}\equiv i+j-1\mod{n}$. 
By symmetry all row cycles in $\cycgrp_n$ have length dividing $n$.
If $n$ happens to be prime the row cycles must be of length $n$, so
$\cycgrp_n$ will be a \pH\ Latin square. Hence

\lem\lmprimes. Perfect 1-factorisations of $K_{p,p}$ exist for
all prime $p$.  

In the next section we strengthen \lemc\lmprimes, by constructing
non-isomorphic perfect 1-factorisations of $K_{p,p}$ from a perfect
1-factorisation of $K_{p+1}$.

For any Latin square $L$, define $\numcg{L}$ to be the number of
conjugates of $L$ which are \pH. Note that $\numcg{\cdot}$ is a main
class invariant as a consequence of \lemc\lmconjs, so we can sensibly
write $\numcg{M}$ for a main class $M$.  An interesting property of
$\cycgrp_n$ is that it is isotopic to all of its conjugates (Theorem
4.2.2 of \bibcl\BDeKeo). So by
\lemc\lmconjs, $\numcg{\cycgrp_p}=6$ for
prime $p$. In other words, every square in the main class of
$\cycgrp_p$ is \pH.  In general this is not true of main classes
containing \pH\ squares. As we shall see in \S\Ssmallord\ below, all
Latin squares $L$ of order at most 9 (other than those isotopic to
$\cycgrp_p$ for some prime $p$) have $\numcg L$ either 0 or 2. Note
that $\numcg{L}\in\{0,2,4,6\}$ by
\lemc\lmconjs. All of these values are achievable.
In \S\Satom\ we will look at squares for which $\numcg{\cdot}=6$. 
To find a square for which $\numcg{\cdot}=4$ it is useful to consider
possible symmetries of the square:

\lem\lmnotmostpan. Suppose $L$ is a \pH\ square. If $L$ is
isotopic to $\rowinv{L}$ then $\numcg{L}\in\{2,6\}$. Alternatively, if
$L$ is isotopic to $\transp{L}$ then $\numcg{L}\in\{4,6\}$.

\prf We write $A\sim B$ if both $A$ and $B$ are \pH, or neither is.
Let the conjugates of $L$ be $L_1=L$, $L_2=\transp{L}$,
$L_3=\rowinv{L}$, $L_4=\transp{(\rowinv{L})}$,
$L_5=\rowinv{\transp{L}}$, $L_6=\transp{(\rowinv{\transp{L}})}$.  Note
that $L_1$ is \pH\ by assumption.  We make use of
\lemc\lmconjs, starting with the observation that
$L_1\sim L_3$, $L_2\sim L_5$ and $L_4\sim L_6$.  If $L_1$ and $L_3$
are isotopic then $L_2\sim L_4$ and $L_5\sim L_6$ because they are
also isotopic pairs.  But then $L_2\sim L_4\sim L_5\sim L_6$, from
which the first assertion of the lemma follows. A similar argument
works if $L_1\sim L_2$. In this case $L_3\sim L_5$ and $L_4\sim L_6$,
so that $L_1\sim L_2\sim L_3\sim L_5$ and at least four conjugates are
\pH.\endpf

As an application of \lemc\lmnotmostpan, we will meet \pH\ squares in
the next section which are derived from perfect 1-factorisations of
complete graphs. These squares are \self, so they always have
$\numcg{\cdot}\in\{2,6\}$.  The other part of \lemc\lmnotmostpan\ is
more promising for finding examples of squares for which
$\numcg{\cdot}=4$. Indeed such a square is given in
\eqcall\efourconjs. This square is symmetric about its main diagonal
so it is sufficient to note that it is \pH\ but that the symbols 1 and
11 form three separate symbol cycles.
$$\pmatrix{
 1& 2& 3& 4& 5& 6& 7& 8& 9&10&11 \cr
 2& 3& 4& 5& 6& 7& 8& 9&10&11& 1 \cr
 3& 4& 5& 6&11& 8& 1&10& 7& 9& 2 \cr
 4& 5& 6& 7& 9& 2&11& 1& 8& 3&10 \cr
 5& 6&11& 9& 4& 1&10& 7& 3& 2& 8 \cr
 6& 7& 8& 2& 1&10& 3&11& 5& 4& 9 \cr
 7& 8& 1&11&10& 3& 9& 4& 2& 6& 5 \cr
 8& 9&10& 1& 7&11& 4& 2& 6& 5& 3 \cr
 9&10& 7& 8& 3& 5& 2& 6&11& 1& 4 \cr
10&11& 9& 3& 2& 4& 6& 5& 1& 8& 7 \cr
11& 1& 2&10& 8& 9& 5& 3& 4& 7& 6 \cr
}\ref\efourconjs$$

In \lemc\lmprimes\ we saw an existence result for \pH\ Latin squares
of some orders.  Now we look at some orders for which these squares do
not exist.

\lem\lmevens. If $R\in L(k,n)$ is \pH\ then either $n$ is odd or $k\leq2$.

\prf Suppose $n$ is even and that $r,s$ are two rows of $R$.
By definition, $\sigma_{r,s}$ is a full cycle permutation on an even
number of symbols. In particular $\sigma_{r,s}$ is an odd permutation,
so $\sigma_r$ and $\sigma_s$ must be of different parities. As this is
true for any pair of rows in $R$, we see that there cannot be more
than 2 rows.\endpf

\proclaim Corollary.  Up to isomorphism, $\cycgrp_2$ is the only 
\pH\ Latin square of even order.

Gibbons and Mendelsohn \bibcl\BGbMd\ attempted to find a \pH\ square
of order 12, because they knew such a square would be $N_\infty$ (see
\lemc\lmninf). \lemc\lmevens\ explains why their search failed, and
also rules out using \pH\ squares to completely settle the remaining
existence questions for \ninf s. The best we can hope for is to find
examples for the orders which are powers of three.  This has been
achieved \bibcl\BDeKet\ for sporadic orders including $3^a$ for
$a\leq5$, by the techniques discussed in the next section.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section\Scompgr. Factorisations of complete graphs

In this section we examine connections between perfect 1-factorisations 
of complete graphs and those in complete bipartite graphs.

In \bibcl{\BDeKet, pg116} a construction is provided
for an \ninf\ of order n, given a perfect 1-factorisation of the
complete graph $K_{n+1}$ (which can only be found if $n$ is odd). This
construction, also given in \bibcl\BWall\ and mentioned in
\bibcl{\BAdMd}, is attributed to ``A. Rosa and others''. 
The construction we give is related by conjugacy.

Suppose we have a factorisation $\pfact$ of $K_{n+1}$ consisting of
1-factors $F_1,F_2,\dots, F_n$. Let the vertices of the $K_{n+1}$ be
$v_1,v_2,\dots,v_{n+1}$ and rename the 1-factors if necessary so that
$F_i$ contains the edge $v_iv_{n+1}$. We construct a Latin square
$S(\pfact)$ in which row $i$ is determined from $F_i$ as follows. The
row permutation $\sigma_i$ is the product of $\half(n-1)$ disjoint
2-cycles, where there is a 2-cycle $(ab)$ corresponding to each edge
$v_av_b\in F_i\setminus\{v_iv_{n+1}\}$. Since the factors
$\{F_i\}$ are pairwise disjoint by definition, $S(\pfact)$ is a Latin
square. Also, by construction $S(\pfact)$ is involutory and idempotent.
Finally, note that the row cycles involving rows $i$ and $j$
of $S(\pfact)$ correspond in a natural way to cycles in $F_i\cup
F_j$. In particular if $\pfact$ happens to be a perfect 1-factorisation
then $S(\pfact)$ is \pH. We have:

\lem\lmrosacon. The map $\pfact\rightarrow S(\pfact)$ is a bijection
between 1-factorisations of $K_{n+1}$ (with fixed vertex labels
$v_1,v_2,\dots,v_{n+1}$) and idempotent \self\ squares in $L(n,n)$.
It maps perfect 1-factorisations to \pH\ squares.

\prf It suffices to show the construction of $S(\pfact)$ is `reversible'.
So suppose that $L$ is an idempotent \self\ square of order $n$. Then
in $L$, each row permutation $\sigma_i$ is an involution.  Since $L$
is idempotent each $\sigma_i$ fixes $i$ and it follows that $\sigma_i$
cannot fix any $j\neq i$ without breaching the Latin property of
$L$. Hence each $\sigma_i$ must be a product of $\half(n-1)$ disjoint
2-cycles. It is a simple matter now to construct the factorisation of
$K_{n+1}$ for which $L$ is the image, by using edges corresponding to
these 2-cycles.\endpf

\proclaim Corollary. If $K_{n+1}$ has a perfect 1-factorisation, then
so does $K_{n,n}$.

The converse of this last result is not true. Note that $K_3$ does not
even have a 1-factor. However $K_{2,2}$ has a perfect 1-factorisation
(cf. the corollary to \lemc\lmevens). It may well be that this
(somewhat trivial) case is the only exception. This would follow, if
the following widely believed conjecture were proved.

\proclaim Conjecture. $K_{n}$ has a perfect 1-factorisation for all 
even positive integers $n$.

If there is a counterexample, then by \bibcl{\BWall,~p.127} it has
$n>50$. Note that Wallis chooses to exclude the trivial case
$n=2$. However we see no reason to do this given that the edge in
$K_2$ is a 1-factorisation and (vacuously) any two 1-factors in this
factorisation form a Hamiltonian cycle.

Given  the preceding comments, plus the Corollary to
\lemc\lmrosacon, it seems reasonable to suggest that:

\proclaim Conjecture. $K_{n,n}$ has a perfect 1-factorisation for $n=2$ 
and all odd positive integers $n$.

Again, any counterexample must have $n>50$. We look next at some of
the constructions which justify this claim.

Suppose $n$ is odd. We define a 1-factorisation $E_{n+1}$ of
$K_{n+1}$. There is one special vertex labelled $\infty$, the other
vertices are labelled with the congruence classes of integers modulo $n$.
For $i=1,2,\dots,n$, define factor $f_i$ to consist of the edges
$(i-1)(i+1)$, $(i-2)(i+2),\dots,(i-\lfloor\half n\rfloor)(i+\lfloor\half
n\rfloor)$ together with $i\infty$. Whenever $n$ is prime the
resulting 1-factorisation $E_{n+1}$ is perfect \bibcl\BWall. Hence by
employing the corollary to \lemc\lmrosacon\ we have an alternate proof
of \lemc\lmprimes. In fact we can squeeze out a stronger result.

\lem\lmmoreprimes. Non-isomorphic perfect 1-factorisations of $K_{p,p}$ 
exist for all prime $p\geq7$.

\prf The construction which is
the basis for \lemc\lmrosacon\ is not robust in the following
sense. Given two isomorphic perfect 1-factorisations $F_1$ and $F_2$
of $K_{n+1}$ it is possible that the perfect 1-factorisations of
$K_{n,n}$ given by $S(F_1)$ and $S(F_2)$ will not be isomorphic. This
is the case only because of the special role played by the vertex
labelled $v_{n+1}$ in the map $\pfact\rightarrow S(\pfact)$.  In
$E_{n+1}$ there are (up to symmetry) just two choices for $v_{n+1}$:
either $v_{n+1}=\infty$ or without loss of generality $v_{n+1}=1$. To
prove the lemma we show that these two choices give non-isomorphic
results.  To do this it is sufficient to show that they produce
non-isomorphic trains, as defined in \S\Ssimpres. For the remainder of
this proof all calculations will be performed modulo $n$.

In the first instance let $v_i=i$ for $i=1,\dots,n$ and put
$v_{n+1}=\infty$.  It is easy to see that the resulting \pH\ square
$S$ is defined by $S_{ij}\equiv2i-j$, and hence is isotopic to
$\cycgrp_n$. Let $h=2^{-1}\equiv\half(n+1)$.  For any vertex $[u,v,f]$
of $\train S$ there is an edge to $[u,v,f]$ from
$[hu-hv+f,-hu+hv+f,h^2u+h^2v+hf]$.  It follows that $\train S$ is
1-regular, since we know every vertex has outdegree 1.

Now suppose that we had swapped the labels on $v_{n+1}$ and $v_1$
before calculating a \pH\ square $S'$. The definition of $S'$ is easy 
enough:
$$S'_{ij}\equiv\cases{i&if $i=j$,\cr
1&if $i\equiv2j-1$,\cr
\half\big(i+1+(i-1)n\big)&if $j=1$,\cr
i-j+1&otherwise.\cr}\ref\ealtphsq$$
We claim that in $\train{S'}$ the vertex $[2,3,1]$ has indegree at
least 2, assuming $n\geq7$.  In fact the edges from both $[n,2,2]$ and
$[\half(n+1),\half(n+3),\half(n+5)]$ terminate at $[2,3,1]$ in this
case. Hence the trains $\train S$ and $\train{S'}$ cannot be
isomorphic, and we have two essentially different squares as claimed.
\endpf

Apart from $E_{p+1}$ for prime $p$, there is only one infinite family
of perfect 1-factorisations of complete graphs known.  For prime $p$ the
idea is to consider $K_{2p}$ as the union of two graphs: $K_{p,p}$ and
a double copy of $K_p$. A 1-factorisation is then built up from
1-factorisations of the two parts.  For exact details the interested
reader should consult \bibcl\BAdCRC\ or \bibcl\BWall. We mention the
result for two reasons. Firstly, the method demonstrates further
connections between perfect 1-factorisations of complete bipartite
graphs and complete graphs. Secondly of course, it gives the following
existence result, via the corollary to \lemc\lmrosacon. 

\lem\lmtwiceprime. If $p$ is prime then $K_{2p-1,2p-1}$ has a 
perfect 1-factorisation.

In this section we have looked for perfect 1-factorisations of
$K_{n,n}$ which are derived from perfect 1-factorisations of
$K_{n+1}$. As a footnote we observe that in general there are plenty
of perfect 1-factorisations of $K_{n,n}$ which do not correspond in
any obvious way to a perfect 1-factorisation of $K_{n+1}$. We shall
see in \S\Ssmallord\ that up to isomorphism there are 37 perfect
1-factorisations of $K_{9,9}$ and only one of $K_{10}$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section\Satom. Atomic squares

In his review \bibcl\BStein\ of \bibcl\BHnrcth, Stein discusses Latin
squares with an indivisibility property stronger than $N_\infty$. In
our language, Stein's squares are those $S$ for which neither $S$ nor
$\transp{S}$ has a proper subrectangle. Perhaps a more natural concept
is obtained by not favouring rows and columns over symbols.  Hence,

\proclaim Definition. A Latin square is {\it atomic\/} if none of its 
conjugates has a proper subrectangle.

The example \eqcall\efourconjs\ confirms that the atomic squares are a
strict subset of Stein's squares.  Of course we use the name `atomic'
here in the classical sense, meaning `indivisible'.  We have the
following characterisation.

\lem\lmatom. A Latin square $L$ is atomic if and only if $\numcg{L}=6$.
To test whether $L$ is atomic it suffices to establish that
$L$, $\transp{L}$ and $\transp{(\rowinv{L})}$ are \pH. 

\prf By \lemc\lmconjs\ the three listed conjugates are \pH\ if and only 
if all six conjugates of $L$ are \pH. The remainder of the lemma is a
straightforward application of \lemc\lmninf.\endpf

Stein's main question in \bibcl\BStein\ is one of existence. 
We are now in a position to partly
answer his query. Firstly, when $p$ is prime we know by
\lemc\lmatom\ that $\cycgrp_p$ is atomic since $\numcg{\cycgrp_p}=6$.
This much was alluded to by Stein \bibcl\BStein. However, by combining
\lemc\lmatom\ with \lemc\lmevens\ we also know
that atomic squares of even composite order do not exist.

So far the only examples of atomic squares we have seen are the family
of $\cycgrp_p$ for $p$ prime. To show that the class is broader, we
now display a second infinite(?)\ family, although this family also
consists only of prime orders.

\lem\lmsplitatom. Let $p\geq11$ be a prime. 
If 2 is a primitive root modulo $p$ then there exists an atomic square
of order $p$ outside the main class of $\cycgrp_p$.

\prf We show that the non-isomorphic
1-factorisations exhibited in \lemc\lmmoreprimes\ both lead to atomic
squares.  The first of these 1-factorisations gave a square isotopic to
$\cycgrp_p$, so we need only examine the second. By
\lemc\lmnotmostpan\ it suffices to show that the transpose of the
square $S'$ defined by setting $n=p$ in \eqcall\ealtphsq\ is \pH. Let
$M$ be the Latin square in which $M_{ij}\equiv i-j+1\mod p$, so that
$S'$ is nearly a copy of $M$.  We need to show that any two columns
$a$ and $b$ of $S'$ consist of a single column cycle; something we
know is true in $M$ because $M$ is isotopic to $\cycgrp_p$. We split
into two cases.

\proclaim Case 1. $1<a<b$

Consider 2-regular bipartite graphs with vertices $r_1,\dots,r_p$ and
$s_1,\dots,s_p$ corresponding to the rows and symbols
respectively. When such a graph is made from the entries in columns
$a$ and $b$ of $M$, let the graph be called $G$ and when the columns
$a$ and $b$ of $S'$ are used, let the graph be $G'$.  Then $G'$ is
obtained from $G$ by removing four edges $r_as_1$, $r_{2a-1}s_a$,
$r_bs_1$ and $r_{2b-1}s_b$, and replacing them with $r_as_a$,
$r_{2a-1}s_1$, $r_bs_b$ and $r_{2b-1}s_1$.  As already noted, $G$ must
be a single cycle. Orient it so that as we traverse it clockwise we
encounter in order $r_a$, $s_1$ then $r_b$. We next establish the
order in which the crucial edges $r_{2a-1}s_a$ and $r_{2b-1}s_b$ will
be encountered as we traverse $G$ clockwise from $r_b$. By the
symmetry inherent in $M$ we know that the clockwise distance from
$r_i$ to $s_{i}$ around $G$ cannot depend on $i$.  It follows that on
our transversal we cannot encounter $r_b$, $s_b$, $s_a$, $r_a$ in that
order, so we must reach the edge $r_{2a-1}s_a$ before
$r_{2b-1}s_b$. Similarly the orientation of the edge $r_as_1$
determines that we must reach $r_{2a-1}$ before $s_a$ and the
orientation of the edge $r_bs_1$ determines that we must reach $s_b$
before $r_{2b-1}$. In short, we must have the situation depicted in
Figure~1(a). It is then clear (see Figure~1(b)) that $G'$ is also a
single cycle.

\midinsert%Exported~at~40%%%
\centerline{\epsffile{forigcyc.eps}\hfil\epsffile{fnewcyc.eps}}
\medskip
\centerline{$\!\!\!\!\!$Figure~1(a): $G$ in case 1\hfil
$\;\;\;\;\;\;$ Figure~1(b): $G'$ in case 1}
\endinsert


\proclaim Case 2. $1=a<b$

This time we let $G$ be the graph formed by the union of the first
column of $S'$ with column $b$ of $M$, while $G'$ comes from columns 1
and $b$ of $S'$. Note that $G'$ can be obtained from $G$ by deleting
the edges $r_bs_1$ and $r_{2b-1}s_b$ and replacing them with $r_bs_b$
and $r_{2b-1}s_1$.

Consider a function $f$ from the symbol set to itself which maps
$S'_{i1}$ to $S'_{ib}$ for each $i$. Then $f(x)\equiv2x-b\mod p$. Let
$f^m$ be $f$ composed with itself $m$ times, so that
$f^m(x)\equiv2^mx-(2^m-1)b$.  We look for fixed points of $f^m$. Note
that $f^m(x)=x$ if and only if $(2^m-1)(x-b)\equiv0\mod p$. Here is
where we use the assumption that 2 is primitive modulo $p$ and hence
$2^m-1\equiv0\mod p$ only if $p-1|m$. Translating this knowledge, we
see that our graph $G$ consists of precisely two cycles, one of which
is a digon on the vertices $r_{2b-1}$ and $s_b$.  It is then obvious
(Figure~2) that the surgery performed to create $G'$ from $G$ cannot
fail to create a single cycle.
\endpf

\midinsert%Exported~at~45%%%
\centerline{\epsffile{forigdigon.eps}\hfil\epsffile{fnewdigon.eps}}
\medskip
\centerline{$\!\!$Figure~2(a): $G$ in case 2\hfil 
$\>\>\>\>$Figure~2(b): $G'$ in case 2}
\endinsert

With regard to this last result, it is of interest to note that in the
cases when 2 is not a primitive root modulo $p$, the graph $G$ in
Figure~2(a) consists of at least 3 cycles and hence $G'$ cannot be a
single cycle. It follows that our construction never gives an atomic
square in such a case. However it does give a square which is nearly
atomic.  All row cycles are Hamiltonian and only column
cycles involving the first column fail to be Hamiltonian (a similar
statement holds for the symbol cycles).

We can use \lemc\lmatom\ to screen our catalogue in
\S\Ssmallord\ for atomic squares. The conclusion is that there are no
atomic squares of order below 11 except those arising from groups of
prime order. Note that \lemc\lmsplitatom\ allows us to construct an
atomic square of order 11 different from $\cycgrp_{11}$.

Finally we note that atomic squares of composite orders do exist. For
example, it is possible to create an atomic square of order 27 by
applying the process described in \S\Scompgr\ to the perfect
1-factorisation of $K_{28}$ described in \bibcl\BAnd. It would be of
some interest to find an atomic square of an order which is not a
prime power. No such square is known to the author.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section\STD. Transversal designs

A number of our results can be neatly expressed in terms of
transversal designs (thanks to the referee for making this
observation).  A transversal design $TD(n,k)$ is a set of $nk$ points
partitioned into $k$ groups of $n$ elements each, together with a set
of blocks.  Each block must contain exactly one point from each group
and any two points from different groups must occur in exactly one
block. It is well known that Latin squares can be formed from a
$TD(n,3)$.  Simply choose a correspondence from the three groups, in
some order, to the rows, columns and symbols; then each of the $n^2$
blocks designates a symbol to be placed in a particular row and
column. Any two squares derived in this manner from the same
transversal design will be in the same main class.  More generally, a
$TD(n,k)$ is really just a set of $k-2$ mutually orthogonal Latin
squares by another name \bibcl\BBrwr.

Suppose we are given $T$, a $TD(n,3)$ with groups $G_1, G_2$ and
$G_3$.  For each point $p\in G_1$ there is a 1-factor between $G_2$
and $G_3$ given by the restriction to $G_2\cup G_3$ of all the blocks
containing $p$.  Similarly, if two points $p_1, p_2\in G_1$ are
chosen, then they induce a 2-factor on $G_2\cup G_3$. If this 2-factor
is always a Hamiltonian cycle regardless of the choice of $p_1, p_2$
then $T$ corresponds to a \pH\ Latin square (provided $G_1$ is chosen
to represent the rows). We might say that $T$ is \pH\ with respect to
$G_1$.  Of course, if $T$ is \pH\ with respect to all of its groups then
$T$ corresponds to an atomic square. In this case we say that $T$ is
an atomic transversal design (ATD).

Translating earlier results into the new terminology we find that an
$ATD(n,3)$ cannot exist if $n>2$ is even (\lemc\lmevens), but that
there is an $ATD(p,3)$ for all prime $p$ (\lemc\lmprimes). Indeed we
can construct non-isomorphic $ATD(p,3)$ for many primes $p$
(\lemc\lmsplitatom). We also know that an $ATD(27,3)$ exists but, as
we will discover in the next section, an $ATD(9,3)$ does not.

One bonus from choosing the transversal design formulation is that it
allows an immediate generalisation. We can define a $TD(n,k)$ to be an
$ATD(n,k)$ if its projection onto any 3 of its groups yields an
$ATD(n,3)$. However, the only such designs known at this stage for
$k>3$ arise from the Desarguesian projective planes of prime order
$p$. Such planes yield an $ATD(p,p+1)$ in which every restriction to 3
groups is atomic because it is isomorphic to $\cycgrp_p$. Hence we
have a generalisation of \lemc\lmprimes.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section\Ssmallord. Small orders

For $n\in\{2,3,5\}$ the catalogue of Latin squares in \bibcl\BDeKeo\
shows that there is a single main class of \ninf\ of order $n$, namely
that of $\cycgrp_n$. According to Norton \bibcl\BNrtn\
(notwithstanding the later correction by Sade \bibcl\BSadet) there are
precisely two main classes of \ntwo s of order 7. Both turn out to be
$N_\infty$ and to contain \pH\ squares. An example from the main class
other than that of $\cycgrp_7$ is: $$A_7=\pmatrix{ 1&2&3&4&5&6&7\cr
2&3&4&5&6&7&1\cr 3&4&5&6&7&1&2\cr 4&6&7&2&1&3&5\cr 5&7&2&1&3&4&6\cr
6&5&1&7&4&2&3\cr 7&1&6&3&2&5&4\cr}.\ref\eninfseven$$ 
We note that $\numcg{A_7}=2$ and that $A_7$ is isotopic to $\rowinv{A_7}$.

There are 37 main classes $M$ containing \pH\ Latin squares of
order 9. In each case $\numcg{M}=2$. Two examples are:
$$A_9=\pmatrix{1&2&3&4&5&6&7&8&9\cr2&4&1&5&7&9&8&6&3\cr
3&8&9&2&4&5&6&1&7\cr4&9&2&3&1&8&5&7&6\cr
5&3&8&1&6&7&9&4&2\cr6&5&7&8&9&4&2&3&1\cr
7&1&5&6&8&2&3&9&4\cr8&7&6&9&3&1&4&2&5\cr
9&6&4&7&2&3&1&5&8\cr}, 
\qd
B_9=\pmatrix{1&2&3&4&5&6&7&8&9\cr2&4&1&9&3&8&6&5&7\cr3&1&7&6&8&9&5&4
        &2\cr4&3&5&7&1&2&8&9&6\cr5&8&2&1&9&7&4&6&3\cr6&9&4&8&7&5&3
        &2&1\cr7&6&8&5&2&3&9&1&4\cr8&7&9&2&6&4&1&3&5\cr9&5&6&3&4&1&2&7&8\cr}
.\ref\eninfnine$$

\def\D{\cdot}

We intend to give an entire catalogue, but the above format is
impractically bulky.  Instead, we describe a Latin square using a
single line of text. We do this by first reducing the square (that is,
putting its first row and column in natural order). Then since the
first row and column are known, we omit them. For the other rows, we
write the remaining entries out in order from left to right, but
without spaces. We process the rows from top to bottom, placing a dot
between rows. The first part of the list looks like this:
$$\eqalignno{\offinterlineskip
41579863\D89245617\D92318576\D38167942\D57894231\D15682394\D76931425\D
64723158,&\cr 
41963857\D82147965\D17629538\D94832671\D58794213\D65281394\D79315426\D
36578142,&\cr
41689537\D52197846\D86712395\D64873912\D17935428\D39248651\D95361274\D
78524163,&\cr 
41785936\D52947168\D85372691\D67891423\D19523847\D38169254\D96214375\D
74638512,&\cr 
41768935\D17924658\D98235176\D64879321\D79513842\D86392514\D35641297\D
52187463,&\cr 
51689347\D19578624\D62817935\D97124863\D85743291\D36295418\D74932156\D
48361572,&\cr 
41679358\D17824695\D56291837\D38947162\D85712943\D69583421\D94135276\D
72368514,&\cr 
46587193\D14962578\D65329817\D87134962\D58793241\D39218456\D91675324\D
72841635,&\cr 
41975836\D78629451\D92813675\D39764218\D54198327\D15382964\D67241593\D
86537142,&\cr 
41835697\D62987541\D97368215\D74129863\D89513472\D15642938\D56791324\D
38274156.&\cr 
}$$

The lines above represent ten \pH\ Latin squares (one per line) in the
condensed format described. Each of these ten squares is isotopic to
its row inverse.  In the other 27 main classes (listed below) there is
no such symmetry. Note that $A_9$, $B_9$ in \eqcall\eninfnine\ are
respectively the first square in the list above and the first square
in the list below.

$$\eqalignno{
41938657\D17689542\D35712896\D82197463\D94875321\D68523914\D79264135\D
56341278,&\cr
51679438\D75124896\D12895367\D68937142\D34582971\D96248513\D49713625\D
87361254,&\cr
41598376\D52879614\D97613258\D16947823\D39285147\D85362491\D64721935\D
78134562,&\cr
41895673\D69148257\D17389562\D84723196\D92574831\D35612948\D76931425\D
58267314,&\cr
41795638\D69271845\D17328956\D74983162\D82539417\D95864321\D56147293\D
38612574,&\cr
41567938\D95748216\D17395862\D64829173\D82973451\D38214695\D79631524\D
56182347,&\cr
51648973\D98167254\D62789531\D19274368\D74923815\D35812496\D46395127\D
87531642,&\cr
46379158\D18924567\D82795613\D69187432\D71238945\D35841296\D94562371\D
57613824,&\cr
46879135\D14792568\D85627913\D78963421\D39214857\D61538294\D92145376\D
57381642,&\cr
48569173\D19842567\D56971832\D67123948\D95387421\D34618295\D71294356\D
82735614,&\cr
51649837\D46875912\D62937158\D79182364\D87314295\D35298641\D94761523\D
18523476,&\cr
51897364\D76948152\D62719835\D38271496\D19534278\D84625913\D97362541\D
45183627,&\cr
41695837\D59781264\D38529671\D87364912\D94172358\D12843596\D65917423\D
76238145,&\cr
41567893\D54872961\D76985312\D68391274\D92138457\D15249638\D39714526\D
87623145,&\cr
41983675\D95271468\D17825936\D89362147\D34597821\D58649213\D76134592\D
62718354,&\cr
41763895\D69218457\D17829563\D76984321\D94572138\D82395614\D35641972\D
58137246,&\cr
51384697\D48697521\D62738915\D37921846\D89513472\D16249358\D94175263\D
75862134,&\cr
41637895\D17948652\D68571923\D92863174\D54189237\D39215468\D76392541\D
85724316,&\cr
51789364\D86912547\D62831975\D37248691\D78395412\D19524836\D94167253\D
45673128,&\cr
47935168\D18692574\D62319857\D84273916\D59847231\D91568423\D76124395\D
35781642,&\cr
51748936\D85697142\D62931857\D49163278\D38275491\D14829365\D97514623\D
76382514,&\cr
41739865\D78691524\D52978136\D86342971\D39517248\D15864392\D94123657\D
67285413,&\cr
41739658\D84961572\D37815926\D69348217\D92173845\D15682394\D56297431\D
78524163,&\cr
48963175\D17689542\D59712368\D86274913\D34897251\D62531894\D91345627\D
75128436,&\cr
41583976\D86914257\D39725618\D64897123\D97248531\D15362894\D72139465\D
58671342,&\cr
45967138\D16728594\D59613827\D97281643\D34879215\D68194352\D72345961\D
81532476,&\cr
47639158\D14768592\D68971325\D39124867\D85397241\D56812934\D91245673\D
72583416.&\cr
}$$

\medskip

We close this section by comparing our theoretical results from
earlier sections with the data from orders up to 9. Firstly, we expect
from \lemc\lmrosacon\ to be able to construct \pH\ squares of order
$n$ from any perfect 1-factorisation of $K_{n+1}$. Indeed,
\lemc\lmmoreprimes\ shows that we may be able to construct more than
one main class starting from a given 1-factorisation. However, all
squares constructed in this way will have the symmetry that the square
is isotopic to its row inverse. For $n=7$, \lemc\lmmoreprimes\
predicts (at least) two distinct squares, and the squares constructed
there are easily seen to be isotopic to $\cycgrp_7$ and the square
$A_7$ given in \eqcall\eninfseven.

For $n=9$, \lemc\lmtwiceprime\ predicts at least one main class of
\pH\ square derived from a perfect 1-factorisation of $K_{10}$. In fact
there is only one such 1-factorisation \bibcl\BWall\ and unlike the
$n=7$ case, it produces a single main class. A representative of this
class is $A_9$ as given in \eqcall\eninfnine.  


\section\Sothninf. Other \ninf s of order 9.

We saw in \S\Ssmallord\ that all main classes of \ninf s of odd order
less than 9 contain a \pH\ square. In contrast, a minority of main
classes of \ninf s of order~9 have this property.  We show this by
looking at the subsquare structure of all \ntwo s of order 9, using a
catalogue of the 1707 main classes of such square \bibcl\BBdm. (The
lists in \S\Ssmallord\ were also prepared from this catalogue.)  Since
a Latin square cannot have a proper subsquare of more than half its
order and there are no
\ntwo s of order~4, we conclude that \ntwo s of order~9 cannot have
proper subsquares except of order~3. The breakdown of the 1707 main
classes according to the number of order~3 subsquares appears in
Table~\tbNtwo.  For each main class the number of reduced squares in
that class was calculated, and these totals are also given. (A Latin
square of order $n$ is {\it reduced\/} if the entries in its first row
and column are in the natural order $1,2,3,\dots,n$.  The total number
of squares is a factor of $n!(n-1)!$ larger than the number of reduced
squares.)

\midinsert \newdimen\digitwidth \setbox0=\hbox{\rm0} \digitwidth=\wd0
\catcode`@=\active \def@{\kern\digitwidth} \centerline{
\vbox{\offinterlineskip \hrule 
\halign{&\vrule#&\strut
        \qd\hfil#\hfil\qd&\vrule#&
        \qd\hfil#\hfil\qd&\vrule#&
        \qd\hfil#\hfil\qd&\vrule#\cr
height2pt&\omit&&&&&\cr
&Order 3 subsquares&&Main classes&&Reduced squares&\cr
height2pt&\omit&&&&&\cr
\noalign{\hrule height0.8pt}
height2pt&\omit&&&&&\cr
&@0&&1589&&28854493920&\cr
&@1&&@@46&&@@550851840&\cr
&@2&&@@@1&&@@@@9797760&\cr
&@3&&@@15&&@@123016320&\cr
&@4&&@@@3&&@@@@8164800&\cr
&@6&&@@@5&&@@@18779040&\cr
&@9&&@@24&&@@@33653760&\cr
&10&&@@@9&&@@@46267200&\cr
&12&&@@11&&@@@14152320&\cr
&18&&@@@3&&@@@@@453600&\cr
&36&&@@@1&&@@@@@@@@840&\cr
height2pt&\omit&&&&&\cr
\noalign{\hrule height0.8pt}
height2pt&\omit&&&&&\cr
&Total&&1707&&29659631400&\cr
height2pt&\omit&&&&&\cr
}\hrule}}
\Tab\tbNtwo{Subsquares of \ntwo s of order $9$.}
\endinsert

In particular we note that there are 1589 main classes of \ninf s of
order 9, yet only 37 of these contain \pH\ squares. In terms of
reduced squares, there are 28854493920 \ninf s and `only' 426746880
which are \pH\ (or have a conjugate which is \pH).

\section\SRef. References

\bibit{\BAdCRC} L.~D.~Andersen, Factorizations of graphs, 
{\it The CRC handbook of combinatorial designs\/} (Eds: C.~J.~Colbourn and
J.~H.~Dinitz), CRC Press, Boca Raton, FL, 1996, 653--667.

\bibit{\BAdMd} L.~D.~Andersen and E.~Mendelsohn, A direct construction
for Latin squares without proper subsquares, {\it Ann.\ Discrete
Math.\/} {\bf15}  (1982) 27--53.

\bibit{\BAnd} B.~A.~Anderson, A class of starter induced one-factorisations, 
{\it Lecture notes in math.\/} {\bf406} (1974) 180--185.

\bibit{\BBrwr} A.~E.~Brouwer, Block designs, {\it Handbook of 
combinatorics\/} (Eds: R.~L.~Graham, M.~Gr\"otschel and L.~Lov\'asz),
Elsevier, Amsterdam, 1995,  693--745.

\bibit{\BDeKeo} J.~D\'enes and A.~D.~Keedwell, {\it Latin squares and
their applications\/}, Akad\'emiai Kiad\'o, Budapest, 1974.

\bibit{\BDeKet} J.~D\'enes and A.~D.~Keedwell, {\it Latin squares: New
developments in the theory and applications\/}, Annals Discrete Math.\
{\bf46}, North-Holland, Amsterdam, 1991.

\bibit{\BGbMd} P.~B.~Gibbons and E.~Mendelsohn, The existence of a
subsquare free Latin square of side 12, {\it SIAM J.\ Algebraic Discrete
Methods\/} {\bf8} (1987) 93--99.

\bibit{\BHnrcth} K.~Heinrich, Latin squares with no proper subsquares,
{\it J.\ Comb.\ Th.\ Ser.\ A\/} {\bf29} (1980) 346--353.

\bibit{\BHtRd} A.~J.~W.~Hilton and C.~A.~Rodger, Hamiltonian double
Latin squares, preprint.

\bibit{\BBdm} B.~D.~McKay, private communication.

\bibit{\BNrtn} H.~W.~Norton, The $7\times7$ squares, {\it Ann.
Eugenics\/} {\bf9} (1939) 269--307. 

\bibit{\BSadet} A.~Sade, An omission in Norton's list of $7\times7$
squares, {\it Ann.\ Math.\ Statist.\/} {\bf22} (1951) 306--307.

\bibit{\BStein} S.~Stein, MR~82b05032, {\it Mathematical reviews\/} 
(1982) 486.

\bibit{\BWall} W.~D.~Wallis, {\it One-factorizations}, Kluwer Academic, 
Dordrecht, Netherlands, 1997.

\end