\documentclass[12pt]{article}
\usepackage{bm,latexsym,array,amsthm,amssymb,amsfonts,amsmath}

%% The lines between the two rows of %'s are more or less compulsory.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 
% formatted for EJC, October 13, 2004
% most recent changes by Doug, October 14, 2004
% last small edit by Jeff, Oct 20, 2004 
% final version as will appear in EJC 

\setlength{\textwidth}{6.3in}
\setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{guess}[thm]{Conjecture}
%\theoremstyle{definition}
\newtheorem{example}[thm]{Example}

\def\Z{{\mathbb Z}}
\def\qed{\hfill $\Box$ \vskip .15 in}
%\def\pf{\vskip -.125in  \noindent {\em Proof: }}
\def\rk{\noindent {\em Remark: }}
\def\pf{\noindent {\em Proof: }}
\renewcommand{\thefootnote}{\ensuremath{\fnsymbol{footnote}}}


\allowdisplaybreaks

\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
  {\footbf 12} (2005), \#R1\hfil\footrm\thepage}}
\makeatother
\pagestyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The further structure of the front page need not be exactly as below,
%% but the header must contain the names and addresses of the authors
%% as well as the submission and acceptance dates.

\title{Sequentially perfect and uniform one-factorizations\\ of the 
complete graph}

\author{
Jeffrey H. Dinitz \\[-0.8ex]
\small Mathematics and Statistics\\[-0.8ex]
\small University of Vermont, Burlington, VT, USA 05405\\[-0.8ex]
\small \texttt{Jeff.Dinitz@uvm.edu}
\and
Peter Dukes \\[-0.8ex]
\small Mathematics  and Statistics\\[-0.8ex]
\small University of Victoria, Victoria, BC, Canada V8W 3P4\\[-0.8ex]
\small \texttt{dukes@oddjob.math.uvic.ca}
\and 
Douglas R.\ Stinson\\[-0.8ex]
\small School of Computer Science\\[-0.8ex]
\small University of Waterloo, Waterloo, ON, Canada N2L 3G1\\[-0.8ex]
\small \texttt{dstinson@uwaterloo.ca}}


\date{\small 
Submitted: Aug 23, 2004; Accepted: Oct 12, 2004; Published: Jan 7, 2005\\
\small Mathematics Subject Classifications: 05C70}

\begin{document}
\maketitle

\begin{abstract}
In this paper, we consider a weakening of the definitions
of uniform and perfect one-factorizations of the complete graph.  
Basically, we want to order the $2n-1$ one-factors of a one-factorization
of the complete graph $K_{2n}$ in such a way that the 
union of any two (cyclically) consecutive one-factors is always isomorphic
to the same
two-regular graph.
This
property is termed {\em sequentially uniform};
if this two-regular graph is a Hamiltonian cycle, then
the property is termed {\em sequentially
perfect}.  We will discuss several methods for constructing 
sequentially uniform and 
sequentially
perfect one-factorizations. In particular, we 
prove for any integer $n \geq 1$ that there is a 
sequentially perfect
one-factorization of $K_{2n}$.
As well, for any odd integer $m \geq 1$, 
we prove that there is a 
sequentially uniform
one-factorization of $K_{2^t m}$ of type $(4,4,\dots,4)$ for all integers
$t \geq 2 + \lceil \log_2 m \rceil$ (where type $(4,4,\dots,4)$ denotes
a two-regular graph consisting of disjoint cycles of length four).
\end{abstract}




\section{Introduction}

A {\em one-factor} of a graph $G$ is a subset of its edges which
partitions the vertex set.  A {\em one-factorization} of a graph $G$
is a partition of its edges into one-factors.  Any one-factorization
of the complete graph $K_{2n}$ has $2n-1$ one-factors, each of which
has $n$ edges.  For a survey of one-factorizations of the complete
graph, the reader is referred to \cite{MR}, \cite{Walsurvey} or \cite{Walbook}.

A one-factorization $\{F_0,\dots,F_{2n-2} \}$ of $K_{2n}$ is {\em
sequentially uniform} if the one-factors can be ordered
$(F_0,\dots,F_{2n-2} )$ so that the graphs with edge sets $F_i \cup
F_{i+1}$ (subscripts taken modulo $2n-1$) are isomorphic for all $0
\leq i \leq 2n-2$.  Since the union of two one-factors is a 2-regular
graph which is 2-edge-colorable, it is isomorphic to a disjoint union
of even cycles.  We say the multiset $T=(k_1,\dots,k_r)$ is the {\em
type} of a sequentially uniform one-factorization if $F_i \cup
F_{i+1}$ is isomorphic to the disjoint union of cycles of lengths
$k_1, \dots, k_r$, where $k_1 + \dots + k_r = 2n$.  
When the union of every two consecutive
one-factors is a Hamiltonian cycle, the one-factorization is said to
be {\em sequentially perfect}.

The idea to consider orderings of the one-factors in a one-factorization of 
$K_{2n}$ is not entirely academic.  In fact, an ordered one-factorization of 
$K_{2n}$ is a schedule of play for a round-robin tournament 
(played in $2n-1$ rounds).
Round-robin tournaments possessing certain desired properties 
have been studied (see \cite[Chapter 5]{Walbook}, 
or \cite{finizio}); however, to our knowledge, 
round robin tournaments with this ``uniform'' property have not been considered
previously.

The definition above is a relaxation of the definition of uniform
(perfect) one-factoriz\-ation of $K_{2n}$, which requires that the union of 
{\em any} two one-factors be isomorphic (Hamiltonian, respectively).  
Much work has been
done on perfect one-factorizations of $K_{2n}$; for a survey, 
see Seah \cite{Seah}.  Perfect
one-factorizations of $K_{2n}$ are known to exist 
whenever $n$ or $2n-1$ is prime, and when $2n=16,$ $28,$ $36,$ $40,$
$50,$ $126,$ $170$, $244,$ $344$, $730$, $1332$, $1370$, $1850$,
$2198$, $3126$, $6860$, $12168,$ $16808,$ and $29792$ (see \cite{andersen}). 
Recently a few
new perfect one-factorizations have been found, the smallest of which
is in $K_{530}$ (see \cite{DD,Le,Wa}); however before this, no new perfect
one-factorization of $K_{2n}$ had been found since 1992 
(\cite{newest}). The smallest value of $2n$ for which the existence of a
perfect one-factorization of $K_{2n}$ is unknown is $2n=52$.  We will
show that sequentially perfect one-factorizations are much easier to
produce and indeed we will produce a sequentially perfect
one-factorization of $K_{2n}$ for all $n \geq 1$.

Various uniform one-factorizations have been constructed from {\em Steiner
triple systems}, \cite{MR}.  For instance, when $n=2^m$ for some
positive $m$, the so-called binary projective Steiner
triple systems provide a construction
of uniform one-factorizations of $K_{2n}$ of type $(4,4,\dots,4)$.  There
are also sporadic examples of {\em perfect} Steiner
triple systems, \cite{perSTS}, which give 
rise to uniform one-factorizations of type $(2n-4,4)$. 
When $v= 3^m$, uniform one-factorizations
$(4,6, \ldots, 6)$ exist 
(these are Steiner one-factorizations from Hall triple systems) 
and when $p$ is an odd prime there is a uniform one-factorization of 
$K_{p^s +1}$ of type $(p+1,2p, \ldots,2p)$ which arises from the elementary 
abelian 
$p$-group (see \cite{MR}).  

The remainder of this paper is organized as follows.
In Section \ref{starter.sec}, we review the classical ``starter'' construction
for one-factorizations and we show that sequentially perfect
one-factorizations of $K_{2n}$ exist for all $n$. In Section
\ref{small.sec}, we summarize existence results
obtained by computer for small orders. 
In Section \ref{quotient.sec},
we investigate the construction of sequentially uniform
one-factorizations from  so-called quotient starters 
in noncyclic abelian groups.
Here we obtain interesting number-theoretic conditions
that determine if the resulting one-factorizations can be ordered so that they
are sequentially uniform. In Section \ref{product.sec}, we present
a recursive product construction which yields 
infinite classes of sequentially uniform
one-factorizations of $K_{2^t m}$ of type $(4,4,\dots,4)$, for any
odd integer $m$.

\section{Starters}
\label{starter.sec}

We describe our main tool for finding sequentially uniform one-factorizations. 
Let $\Gamma$ be an abelian group of order $2n-1$, written additively.
A {\em starter} in $\Gamma$ is a set of $n-1$ pairs
$S=\{\{x_1,y_1\},\dots,\{x_{n-1},y_{n-1}\}\}$ such that every nonzero
element of $\Gamma$ appears as some $x_i$ or $y_i$, and also as some
difference $x_j-y_j$ or $y_j-x_j$.  Let $S^* = S \cup \{\{0,\infty\}\}$
and define $x+ \infty = \infty+x = \infty$ for all $x \in \Gamma$.
Then $\{S^*+x : x \in \Gamma\}$ forms a one-factorization of $K_{2n}$
(with vertex set $\Gamma \cup \{ \infty \}$).  

Many of the known constructions for (uniform and perfect)
one-factorizations use starters in this way.  In our first lemma we
note the connection between starter-induced one-factorizations and
sequentially uniform one-factorizations.  Clearly, the order in which the
$1$-factors are listed is essential to the type of a sequentially
uniform one-factorization.  Thus we will sometimes refer to {\em ordered
one-factorizations} in this context. Whenever we discuss 
sequentially uniform one-factorizations, we will always give
the $1$-factor ordering.

\begin{lemma}\label {lem1}
Let $S$ be a starter in $\Z_{2n-1}$ with $n \geq 1$.  Then the ordered
one-factorization of $K_{2n}$ generated by $S$, namely 
$(S^*, S^*+1,
S^*+2, \ldots, S^*+ (2n-2) )$ is sequentially uniform.
\end{lemma}

\pf For any $x \in \Z_{2n-1}$, we have $(S^* + x) \cup (S^* +(x+1)) =
x+(S^* \cup (S^* + 1))$, so all unions of two consecutive one-factors
in the given order are isomorphic.  \qed

\rk When $\gcd (k,2n-1)=1$, the ordering
$(S^*,S^*+k,S^*+2k,\dots,S^*+(2n-2)k)$ of the same one-factorization
is also sequentially uniform. Note, however, that it is not
necessarily of the same type as the ordered one-factorization $(S^*,
S^*+1, S^*+2, \ldots, S^*+ (2n-2) )$.

\medskip

The most well-known one-factorization of $K_{2n}$ (called $GK(2n)$) is
generated from the {\em patterned} starter $P= \{\{x,-x\} : x \in
\Z_{2n-1} \}$ in the cyclic group $\Z_{2n-1}$.  It is known when $2n-1$
is prime that $GK(2n)$ is a perfect one-factorization and, in
general, $GK(2n)$ is a uniform one-factorization for all $n \geq 1$.
The cycle lengths in $P^* \cup (P^*+k)$ for $k \in \Z_{2n-1} \setminus
\{0\}$ are now given.

\begin{lemma}\label{lem2}
Let $P$ be the patterned starter in $\Z_{2n-1}$ with $n \geq 1$.  Let
$k \in \Z_{2n-1} \setminus \{0\}$ with $\gcd (2n-1,k)=d$.  Then $P^* \cup
(P^*+k)$ consists of a cycle of length $1+(2n-1)/d$ and $(d-1)/2$
cycles of length $2(2n-1)/d$.
\end{lemma}

\pf The cycle through infinity is
$(\infty,0,2k,-2k,4k,-4k,\dots,-k,k)$, which has length $1+(2n-1)/d$.
All other cycles (if any) are of the form
$$(i,-i,2k+i,-2k-i,4k+i,-4k-i,\dots,-2k+i,2k-i),$$ for $1 \leq i < d$. \qed

Combining Lemmas \ref{lem1} and \ref{lem2} (with $d=1$) we have the 
following result.

\begin{thm}
\label{seqper}
For every $n\geq 1$ there exists a sequentially perfect one-factorization 
of $K_{2n}$.
\end{thm}

Contrast this with the known results for perfect one-factorizations:
the sporadic small values mentioned in the Introduction, 
and only two infinite
classes (each of density zero).



\section{Small orders}
\label{small.sec}

The one-factorizations of $K_4$ and $K_6$ are unique and in each case they are 
perfect.
Hence both are sequentially perfect (the only possible type in 
these small cases).
The one-factorization of $K_8$ obtained from the unique Steiner triple 
system of order $7$ has type $(4,4)$ while 
$GK(8)$ is a perfect one-factorization.  Hence there exist
sequentially uniform one-factorizations of $K_8$ of all possible types.

We have checked all starters in $\Z_9$ by computer and report that no
ordering of the translates of any of these starters yields a
sequentially uniform one-factorization of $K_{10}$ of type
$(4,6)$. However, there does exist a uniform one-factorization of
type $(4,6)$ (it is one-factorization \#1 in the list of all $396$ 
non-isomorphic one-factorizations of
$K_{10}$ given in \cite[p.\ 655]{andersen}).  Clearly this is also
sequentially uniform of type $(4,6)$ under any ordering of the
one-factors.  {}From Theorem \ref{seqper} there exists a sequentially
perfect one-factorization of $K_{10}$. Thus sequentially uniform
one-factorizations of $K_{10}$ exist for both possible types.

Obviously, the ordering of the one-factors can affect the type of the
$2$-factors formed from consecutive $1$-factors in an ordered
one-factorization.  Given a starter $S$ in $\Z_{2n-1}$, let $F_S(k)$
denote the ordered one-factorization $(S^*, S^*+k, S^*+2k, \ldots,
S^*+ (2n-2)k )$ of $K_{2n}$.  In the following examples we discuss 
sequentially uniform one-factorizations in $K_{12}$ and
$K_{14}$.  In $\Z_{13}$ we will give one starter which induces all
possible types of ordered one-factorizations when different orderings
are imposed on translates of that starter.

\begin{example}  \label{12}
Given the following starter in $\Z_{11}$, 
$$S=\{\{1,2\}, \{3,8\}, \{4,6\}, \{5,9\}, \{7,10\} \},$$ $F_S(1)$
is sequentially uniform of type $(6,6)$, $F_S(2)$ is sequentially
uniform of type $(4,8)$ and $F_S(3)$ is sequentially uniform of type
$(12)$.
\end{example}

By checking all starters in $\Z_{11}$, we found that no ordering of
any of the one-factoriz\-ations formed by these starters gave a
sequentially uniform one-factorization of type $(4,4,4)$.  However,
Figure \ref{444} provides a non-starter-induced ordered
one-factorization which is sequentially uniform of this type.

\begin{figure}
\caption{A sequentially uniform one-factorization of $K_{12}$ with 
type $(4,4,4)$}
\label{444}
$$
\begin{array}{c}
F_0: \{\{ 0, 1 \}, \{2, 6 \}, \{ 3, 4 \}, \{ 7, 9 \}, \{ 8, 10 \}, \{ 5, 11 \} 
\} \\
F_1: \{\{0, 2 \}, \{ 1, 6 \}, \{ 3, 9 \}, \{ 4, 7 \}, \{ 5, 10 \}, \{ 8, 11 \} 
\} \\
F_2: \{\{0, 3 \}, \{ 1, 4 \}, \{ 5, 8 \}, \{ 6, 7 \}, \{ 2, 9 \}, \{ 10, 11 \} 
\}\\
F_3: \{\{0, 4 \}, \{ 1, 3 \}, \{ 2, 8 \}, \{ 7, 10 \}, \{ 6, 11 \}, \{ 5, 9 \} 
\}\\
F_4: \{\{0, 5 \}, \{ 1, 2 \}, \{ 3, 8 \}, \{ 4, 9 \}, \{ 6, 10 \}, \{ 7, 11 \} 
\}\\
F_5: \{\{0, 8 \}, \{ 1, 7 \}, \{ 2, 11 \}, \{ 3, 5 \}, \{ 4, 6 \}, \{ 9, 10 \} 
\}\\
F_6: \{\{ 0, 6 \}, \{1, 5 \}, \{ 2, 10 \}, \{ 4, 8 \}, \{ 3, 7 \}, \{ 9, 11 \} 
\}\\
F_7: \{\{ 0, 7 \}, \{1, 10 \}, \{ 2, 5 \}, \{ 3, 6 \}, \{ 4, 11 \}, \{ 8, 9 \} 
\}\\
F_8: \{\{0, 9 \}, \{ 1, 11 \}, \{ 2, 3 \}, \{ 4, 10 \}, \{ 5, 6 \}, \{ 7, 8 \} 
\}\\
F_9: \{\{0, 11 \}, \{ 1, 9 \}, \{ 2, 4 \}, \{ 3, 10 \}, \{ 6, 8 \}, \{ 5, 7 \} 
\}\\
F_{10}: \{\{ 0, 10 \}, \{1, 8 \}, \{ 2, 7 \}, \{ 3, 11 \}, \{ 4, 5 \}, \{ 6, 9 \} 
\}
\end{array}
$$
\end{figure}

In \cite{PP} it is found that there exist exactly five nonisomorphic
perfect one-factorizations of $K_{12}$ and in \cite{C} a uniform
one-factorization of type $(6,6)$ is given.  {}From the enumeration 
in \cite{enum12}, it is known that there exist no other uniform
one-factorizations of $K_{12}$.  Hence it is noteworthy that $F_S(2)$ 
(defined in Example \ref{12})
gives a sequentially uniform one-factorization of $K_{12}$ of type
$(8,4)$ and Figure \ref{444} gives a sequentially uniform
one-factorization of type $(4,4,4)$.




\begin{example}\label{14}
  The following starter in $\Z_{13}$,
$$S= \{\{1,10\}, \{2,3\}, \{4,9\}, \{5,7\}, \{6,12\}, \{8,11\}\},$$
yields sequentially uniform one-factorizations of $K_{14}$ of all
possible types: namely $(14)$, $(10,4),$ $(8,6),$ and $(6,4,4)$.
Specifically, $F_S(3)$ is sequentially uniform of type $(6,4,4)$, $F_S(1)$
is sequentially uniform of type $(8,6)$, $F_S(2)$ is sequentially
uniform of type $(10,4)$ and $F_S(5)$ is sequentially uniform of type
$(14)$.  \end{example}

For large $n$, there are many more possible types than
there are translates, so the starter in Example \ref{14} 
is of particular interest.
In the Appendix we give examples of sequentially uniform 
one-factorizations of $K_{2n}$ of all possible types, 
for $14 \leq 2n \leq 24$.


\section{Starters in non-cyclic groups}
\label{quotient.sec}

Many uniform and perfect one-factorizations are known to be
starter-induced over a non-cyclic group; for example, see \cite{DS}.
So it is natural to also expect sequentially uniform
one-factorizations where the ordering is not cyclic.  In this section we 
give a numerical condition that determines when certain starter-induced 
one-factorizations over non-cyclic groups are sequentially uniform. 


Let $q$ be an odd prime-power (not a prime)
and write $q = 2 r t + 1$, where $t$ is
odd. In order to eliminate trivial cases, we will
assume that $t > 1$. 
Suppose $\omega$ is a generator of the multiplicative group of
$\mathbb{F}_q$ and let $Q$ be the subgroup (of order $t$) generated by
$\omega^{2r}$.  Suppose the cosets of $Q$ are $C_i = \omega^i Q$,
$i=0,\dots,2r-1$.  A starter $S$ in $\mathbb{F}_q$ is said to be an $r$-{\em
quotient starter} if, whenever $\{x,y\}, \{x',y'\} \in S$ with $x,x'
\in C_i$, it holds that $y/x=y'/x'$.  An $r$-quotient starter $S$ can be
completely described by a list of {\em quotients}
$(a_0,\dots,a_{r-1})$, such that
$$S=\{\{x,a_ix\} : (a_i-1)x \in C_i, i=0,\dots,r-1\}.$$
It is not hard to see that $S^* \cup (S^* + x)$ is isomorphic to $S^* 
\cup (S^*+y)$ whenever $x/y \in C_0 \cup C_r$.
It follows that every $1$-quotient starter yields a uniform
one-factorization.  We now show that, 
although $r$-quotient starters might not generate uniform 
one-factorizations when $r>1$, 
\cite{DS}, the resulting one-factorizations
usually can be ordered in such a way that they are sequentially uniform.

\begin{thm}
\label{ordering}
Suppose $q =p^d$ is an odd prime-power (with $p$ prime and $d >1$) 
such that $q=2rt+1$ and $t>1$ is odd. 
Let $S$ be any 
$r$-quotient starter in $\mathbb{F}_q$.  Then the one-factorization
generated by $S$ can be ordered to
be sequentially uniform if and only if the multiplicative order of $p$
modulo $t$ is equal to $d$.
\end{thm}

\pf Let $q = p^d = 2rt+1$ with $t$ odd.  $C_0$ is the multiplicative
subgroup of $\mathbb{F}_q^*$ generated by a primitive $t$th root of
$1$ in $\mathbb{F}_q$, say $\alpha$. The splitting field of $x^t - 1$
over $\mathbb{F}_p$ is $\mathbb{F}_{p^e}$, where $e$ is the smallest
positive integer such that $p^e \equiv 1 \pmod{t}$. Hence the extension field
$\mathbb{F}_p(\alpha) = \mathbb{F}_q$ if and only if the
multiplicative order of $p$ modulo $t$, which we denote by
$\mathsf{ord}_t(p)$, is equal to $d$.

Suppose that $\mathsf{ord}_t(p) = d$.  Then $\mathbb{F}_p(\alpha) =
\mathbb{F}_q$ and $1, \alpha, \dots , \alpha^{d-1}$ is a basis of
$\mathbb{F}_q$ over $\mathbb{F}_p$.  Therefore, every element $x \in
\mathbb{F}_q$ can be expressed uniquely as a $d$-tuple $(x_1 , \dots ,
x_d ) \in ( \mathbb{Z}_p)^d$, where \[x = \sum _{i=1}^{n} x_i \alpha
^{i-1}.\]

Now, consider the graph on vertex set $( \mathbb{Z}_p)^d$ in which two
vertices are adjacent if and only if they agree in $d-1$ coordinates
and their values in the remaining coordinate differ by $1$ modulo
$p$ (this is a
{\em Cayley graph} of the elementary abelian group of order
$p^d$). 
It is not hard to check that this graph has a hamiltonian cycle, say $C =
(y_1, y_2, \dots , y_{p^d}, y_1)$. The cycle $C$ provides the desired
ordering of $\mathbb{F}_q$ because the difference between any two
consecutive elements $y_i$ and $y_{i+1}$ is in $C_0 \cup C_r$
(note that one of $y_i - y_{i+1}$ and $y_{i+1}- y_i$
is a power of $\alpha$ and hence in $C_0$, while the other is in
$C_r$).

Conversely, suppose that $\mathsf{ord}_t(p) = e < d$.  Then
$\mathbb{F}_p(\alpha) = \mathbb{F}_{p^e}$ which is a strict subfield
of $\mathbb{F}_q$.  Clearly $C_0 \cup C_r \subseteq \mathbb{F}_{p^e}$.
Suppose that $y_1, y_2, \dots $ is an ordering of the elements of
$\mathbb{F}_q$ such that adjacent elements always have a difference
that is an element of $C_0 \cup C_r$.  Without loss of generality we
can take $y_1 = 0$. But then every element $y_i$ is in the subfield
$\mathbb{F}_{p^e}$, which is a
contradiction.  Hence, the desired ordering cannot exist. \qed

It is interesting to note that the proof above does not depend on the 
structure of the starter $S$.  Either all $r$-quotient starters  in 
$\mathbb{F}_q$ yield sequentially uniform one-factorizations
or they all do not do so.  

\begin{example}
Let $q=25$ so that $t=3$ and $r=4$.  We have $\mathsf{ord}_t(p)=2=d$, so 
Theorem~\ref{ordering} asserts that
any $4$-quotient starter will yield a sequentially uniform 
one-factorization.  
In particular, if we take $\mathbb{F}_{25} = \Z_5[x] / (x^2+x+2)$ then $C_0$ contains 
a basis 
$\{1,\alpha\}$ for the field, where $\alpha=x^8=3x+1$.  The field 
elements can be 
cyclically ordered \[0,1,2,3,4,3x,\dots,3x+4,x, \dots, 
x+4,4x,\dots,4x+4,2x,\dots,2x+4,0\]
so that the difference of consecutive elements is either $1$ or $\alpha$.
\end{example}

Most applications of $r$-quotient starters use values of $r$ that
are powers of two (see, for example, \cite{DS}). 
It is interesting to 
determine the conditions under which the hypotheses 
of Theorem \ref{ordering} are satisfied in this case.
This is done in Lemma \ref{num}.
%We prove the following corollary of Theorem \ref{ordering}.

\begin{lemma}
\label{num}
Suppose $q = p^d$ is an odd prime-power (with $p$ prime and $d >1$) 
such that $q=2^kt+1$ and $t>1$ is odd.
Then one of the two following conditions hold:
\begin{enumerate}
\item $\mathsf{ord}_t(p) = d$, or
\item $p = 2^j - 1$ for some integer $j$ (i.e., $p$ is a Mersenne prime) and
$d = 2$. (In this case, $\mathsf{ord}_t(p) = 1$ is less than $d$.)
\end{enumerate}
\end{lemma}

\pf Suppose that 
$p^e \equiv 1 \pmod{t}$ for some positive integer $e < d$
(note that $e | d$). Let $p^e = bt+1$ where $b$ is a positive integer.
Then
\[
2^kt + 1 = q 
= (p^e)^{d/e} 
= (bt+1)^{d/e} 
= cbt+1
\]
for some integer $c$.
Hence, $b | 2^k$, and therefore $b = 2^{\ell}$ for some
positive integer $\ell \leq k$.
So we have that $p^e = 2^{\ell} t + 1$.

Let $\rho  = p^e$ and $f = d/e$. Then we have that
\[ t = \frac{{\rho }^f - 1}{2^k} = \frac{{\rho } - 1}{2^{\ell}}.\]
Removing common factors, we obtain
\begin{equation}
\label{eq1}  {\rho }^{f-1} + {\rho }^{f-2} +\dots + \rho  + 1 = 2^{k-\ell}.
\end{equation}

Suppose that $k = \ell$. Then the right side of (\ref{eq1}) is
equal to $1$, so $f = 1$ and $d =e$. This contradicts the assumption
that $d > e$. Therefore $k > \ell$ and the right side of  (\ref{eq1}) 
is even.

Now, suppose that $f$ is odd. Then the left side of  (\ref{eq1}) 
is odd, and we have a contradiction. Therefore $f$ is even,
and $\rho  + 1$ is a factor of the left side of  (\ref{eq1}).
 This implies that $2^{k-\ell} \equiv 0 \pmod{\rho  + 1}$, and
 hence
 $\rho  = 2^j - 1$ for some integer $j \geq 2$.
 Then, after dividing (\ref{eq1}) by the factor $\rho  + 1$, we 
obtain the following equation:
\begin{equation}
\label{eq2}  {\rho }^{f-2} + {\rho }^{f-4} +\dots + {\rho }^2 + 1 = 2^{k-\ell-j}.
\end{equation}

Suppose that $j < k-\ell$. Then the right side of
(\ref{eq2}) is even and ${\rho }^2 + 1$ is a factor of the left side of
 (\ref{eq2}), so ${\rho }^2 = 2^i - 1$ for some integer $i \geq 2$.
 But $\rho  = 2^j - 1$ where $j \geq 2$, so $\rho  \equiv 3 \pmod{4}$.
 Then ${\rho }^2 \equiv 1 \pmod{4}$, which contradicts the
 fact that ${\rho }^2 = 2^i - 1$ where $i \geq 2$.
Therefore we have that $j = k-\ell$. This implies that $f=2$ and
so $d = 2e$. So $\rho  = 2^j - 1$ for some integer $j$ and
$q = {\rho }^2$.

However, it is easy to prove that the 
Diophantine equation $2^u-y^v = 1$ has no solution
in positive integers with $u,v > 1$\footnote[2]{This result is a special
case of {\em Catalan's Conjecture}, which 
states that the Diophantine equation $x^u-y^v = 1$ has no solution
in positive integers with $u,v > 1$ except for 
$3^2 - 2^3 = 1$. Catalan's Conjecture was proven correct in 2002 by
Mih\u{a}ilescu (see Mets\"{a}nkyl\"{a} \cite{met} for a recent exposition
of the proof).}.
See, for example, Cassels \cite[Corollary 2]{Cas}.
Therefore, we can conclude 
%
%But we can say a bit more by appealing to {\em Catalan's Conjecture}, which 
%states that the Diophantine equation $x^u-y^v = 1$ has no solution
%in positive integers with $u,v > 1$ except for 
%$3^2 - 2^3 = 1$. Catalan's Conjecture was proven in 2002 by
%Mih\u{a}ilescu (see Mets\"{a}nkyl\"{a} \cite{met} for a recent exposition
%of the proof). 
%
%We have that $2^j - \rho  = 1$. Hence, from the truth of  Catalan's Conjecture, it immediately follows
that $\rho $ is prime. Hence, $p=2^j-1$ is a Mersenne prime, $e=1$ and $d=2$.
In this case, we have $q = p^{2}$. %Suppose we write $q$ in the form
%$q = 2^{k}t+1$ where $t$ is odd (this can be done uniquely).
Then we have that
\[ q-1 = (p-1)(p+1) = (p-1)2^j \equiv 0 \pmod{t}.\]
But $t$ is odd, so $p \equiv 1 \pmod{t}$.
Therefore $\mathsf{ord}_t(p) = 1$. 
\qed

\begin{example}
Let $q= 961= 31^2$ so $p=31$ and $d=2$.  
Here $p = 31 = 2^5-1$ is a Mersenne prime.
We can write $q = 2^5 15 + 1$, so $t = 15$.
We see that $\mathsf{ord}_t(p)=1 < 2$, 
as asserted by Lemma \ref{num}.
\end{example}

The following corollary is an immediate consequence
of Theorem \ref{ordering} and Lemma \ref{num}.

\begin{cor}
\label{mersenne}
Suppose $q = p^d$ is an odd prime-power (with $p$ prime and $d >1$) 
such that $q=2^kt+1$ and $t>1$ is odd.
Let $S$ be any 
$2^{k-1}$-quotient starter in $\mathbb{F}_q$.  Then the one-factorization
generated by  $S$ can be ordered to
be sequentially uniform if and only if 
it is not the case that $p$ is a Mersenne prime and $d=2$.
\end{cor}



\section{Product construction}
\label{product.sec}

We now recall the usual product construction for one-factorizations, and 
apply it to determine another infinite class of sequentially uniform 
one-factorizations.

Suppose that $F$ is a one-factor on $X$ and $G$ is a one-factor on $Y$, 
where $|X| = 2n$ and $|Y| = 2m$.  Define various one-factors of $X \times 
Y$ by
\begin{eqnarray*}
F^* &=&  \big\{ \{ (x_i,y),(x'_i,y) \} : \{x_i,x'_i\} \in F, y \in Y \big\},\\ 
G^* &=& \big\{ \{ (x,y_j),(x,y'_j) \} : x \in X, \{y_j,y'_j\} \in G \big\}, \\
FG &=& \big\{ \{ (x_i,y_j),(x'_i,y'_j) \} : \{x_i,x'_i\} \in F, \{y_j,y'_j\} 
\in G \big\}. 
\end{eqnarray*}

Given one-factorizations 
$\mathcal{F} = \{ F_0, \dots , F_{2n-2} \}$ and
$\mathcal{G} = \{ G_0, \dots , G_{2m-2} \}$ of $K_{2n}$ and $K_{2m}$ on 
the points $X$ and $Y$, respectively, it is easy to see that
\begin{eqnarray*}
\mathcal{F} \mathcal{G} &=& \big\{ F_i G_j : i = 0, \dots, 2n-2 {\rm \ and\ } 
j=0, \dots, 2m-2 \big\} \\
&& \bigcup \big\{ F_i^* : i = 0, \dots, 2n-2 \big\} \bigcup \big\{ G_j^* : 
j=0, \dots, 2m-2 \big\}
\end{eqnarray*}
is a one-factorization of $X \times Y$.

The following are easy lemmas about the cycle types of pairs of 
one-factors in $\mathcal{F} \mathcal{G}$.

\begin{lemma}
\label{44-1}
For any $i \in \{0,\dots,2n-2\}$ and $j \in \{0,\dots,2m-2\}$, the 
following all have cycle type $(4,4,\dots,4)$:%\\
\begin{description}
%\indent
%{\rm (i)} 
\item{(i)} $F^*_i \cup G^*_j$, %\\
%\indent
%{\rm (ii)} 
\item{(ii)} $F_iG_j \cup F^*_i$, and%\\
%\indent
%{\rm (iii)} 
\item{(iii)} $F_iG_j \cup G^*_j$.
\end{description}
\end{lemma}

\begin{lemma}
\label{44-2}
If $(F_0, F_1, \dots , F_{2n-2})$ is sequentially uniform 
of type $(4,4,\dots,4)$, then the 
following all have cycle type $(4,4,\dots,4)$:%\\
%\indent
\begin{description}
%{\rm (i)} 
\item{(i)} $F^*_i \cup F^*_{i+1}$, and %\\
%\indent
%{\rm (ii)} 
\item{(ii)} $F_iG_j \cup F_{i+1}G_j$, %\\
\end{description}
for any $i,j$, where the subscripts $i+1$ are reduced modulo $2n-1$.
\end{lemma}

We can use the above results to give a product construction for
sequentially uniform one-factorizations of type $(4, 4, \dots , 4)$.

\begin{thm}
Suppose there exists a sequentially uniform one-factorization of $K_{2n}$ of
type $(4, 4, \dots , 4)$. Let $m \leq n$.
Then there is a sequentially uniform one-factorization of $K_{4mn}$ of
type $(4, 4, \dots , 4)$.
\end{thm}

\pf  We use all the notation above, with $(F_0, F_1, \dots , F_{2n-2})$ 
sequentially uniform 
of type $(4,4,\dots,4)$
and $\cal G$ any one-factorization of $K_{2m}$.  
The ordered one-factorization 
$$
\begin{array}{c}
\big( G^*_0,F_0 G_0, F_1 G_0, \dots, F_{2n-2} G_0, F^*_{2n-2}, \vspace{.05in} \\
G^*_1,F_1 G_1, F_2 G_1, \dots, F_0 G_1, F^*_0, \vspace{.05in} \\
G^*_2,F_2 G_2, F_3 G_2, \dots, F_1 G_2, F^*_1, \vspace{.05in} \\
\vdots  \vspace{.05in} \\
G^*_{2m-2},F_{2m-2} G_{2m-2}, \dots, F_{2m-3} G_{2m-2}, F^*_{2m-3}, \vspace{.05in} \\
F^*_{2m-2}, F^*_{2m-1}, \dots, F^*_{2n-3} \big)
\end{array}
$$
of $K_{4mn}$ is sequentially uniform of type $(4,4,\dots,4)$ by 
Lemmas~\ref{44-1} and \ref{44-2}. \qed

By applying the above product construction with $2n$ a power of $2$ --- for 
which the existence of {\em uniform} one-factorizations of type 
$(4,4,\dots,4)$ are known --- one immediately has the following corollary.

\begin{cor} 
\label{4asym}
For any odd integer $m\geq 1$, there is a sequentially uniform
one-factoriz\-ation of $K_{2^t m}$ of type $(4,4,\dots,4)$ for all integers
$t \geq 2 + \lceil \log_2 m \rceil$. 
\end{cor}

Let $t_0 = t_0(m)$ denote the smallest integer such that there is a
sequentially uniform one-factorization of $K_{2^t m}$ of type
$(4,4,\dots,4)$ for all integers $t \geq t_0$.  Corollary~\ref{4asym}
provides an explicit upper bound on $t_0(m)$; however, 
for a particular value of
$m$, we might be able to give a better bound on $t_0(m)$. 
For example, the sequentially perfect one-factorization of
$K_{4}$ %of type $(4)$ %discussed in Section  \ref{small.sec} 
shows that $t_0(1)=2$, the 
sequentially uniform one-factorization of $K_{12}$ of type $(4,4,4)$ given in
Figure \ref{444} yields $t_0(3)=2$, and the 
sequentially uniform one-factorization of $K_{20}$ of type 
$(4,4,4,4,4)$ exhibited
in the Appendix gives $t_0(5)=2$.
%For example, the sequentially uniform
%one-factorization of $K_{12}$ of type $(4,4,4)$ given in Example\ref{444}
%gives $t_0(3)=2$. 
In fact, we conjecture that $t_0(m) = 2$ for all 
odd integers $m \geq 1$. 

As a final note, we observe that the existence results
for sequentially uniform one-factorizations of $K_{2^t m}$ of type
$(4,4,\dots,4)$ provide an interesting contrast to
those for uniform one-factorizations of $K_{2^t m}$ of type
$(4,4,\dots,4)$, which exist only when $m=1$
(see Cameron \cite[Proposition 4.3]{C}).


\section*{Acknowledgements}

The authors would like to to thank Dan Archdeacon, Cameron Stewart 
and Hugh Williams for 
useful discussions and pointers to the literature.

D.\  Stinson's research is supported by the Natural Sciences and
Engineering Research Council of Canada
through the  grant NSERC-RGPIN \#203114-02.
P.\ Dukes was supported by an NSERC post-doctoral fellowship.

\begin{thebibliography}{99}
\bibitem{andersen}
L.D. Andersen. Factorizations of graphs. In 
{\em The CRC Handbook of Combinatorial Designs},
C.J.~Colbourn and J.H.~Dinitz, eds., CRC Press, 
Boca Raton, 1996, pp. 653--666.

\bibitem{C}
P.J.~Cameron. Minimal edge-colourings of complete graphs. {\em J. 
London Math. Soc.} {\bf 11} (1975) 337--346.

\bibitem{Cas}
J.W.S.~Cassels.
On the equation $a^ x-b^ y=1$.  
{\em Amer. J. Math.} {\bf 75} (1953), 159--162.




%\bibitem{handbook}
%C.J.~Colbourn and J.H.~Dinitz, eds. {\em The CRC Handbook of Combinatorial
%Designs}. CRC Press, Boca Raton, 1996.

\bibitem{DD}
J.H.~Dinitz and P. Dukes. 
Some new perfect one-factorizations of the complete graph. 
University of Vermont Mathematics Research Report
No.\ 2004-01.


\bibitem{enum12}
J.H.~Dinitz, D.K.~Garnick, and B.D.~McKay. 
There are $526,915,620$
nonisomorphic one-factorizations of $K_{12}$. 
{\em J. Combin. Des.} {\bf
2} (1994), 273--285.

\bibitem{DS}
J.H.~Dinitz and D.R.~Stinson. Some new perfect one-factorizations from 
starters in finite 
fields. {\em J. Graph Theory} {\bf 13} (1989), 405--415.

%\bibitem{prs}
%J.H.~Dinitz. Some perfect Room squares.
%{\em J. Combin. Math. Combin. Comput.} {\bf 2} (1987), 29--36.

\bibitem{finizio} N.J.~Finizio. 
Tournament designs balanced with respect to several bias categories. 
{\em Bull. Inst. Combin. Appl.}
{\bf 9} (1993), 69--95. 

\bibitem{perSTS}
M.J.~Grannell, T.S.~Griggs, and J.P.~Murphy. Some new perfect Steiner 
triple systems. {\em J. Combin. Des.} {\bf 7} (1999), 327--330.

%\bibitem{Hort} J.D.~Horton. Room designs and one-factorizations. {\em
%Aequationes Math.} {\bf 22} (1981), 56--63.

\bibitem{Le}
V. Leck. Personal communication, 2001.\\ (See
\verb+http://www.emba.uvm.edu/~dinitz/newresults.html+.)

\bibitem{MR}
E.~Mendelsohn and A.~Rosa. One-factorizations of the complete graph --- A 
survey. {\em J. Graph Theory} {\bf 9} (1985), 43--65.

\bibitem{met}
T.~Mets\"{a}nkyl\"{a}. 
Catalan's Conjecture: Another old Diophantine problem solved.
{\em Bull. Amer. Math. Soc.} {\bf 41} (2004), 43--57. 

\bibitem{PP}
A.P.~Petrenyuk and A.Ya.~Petrenyuk. Intersection of perfect 
$1$-factorizations of complete graphs (Russian).
{\em Cybernetics} {\bf 1980} 6--8, 149.

\bibitem{Seah} E.~Seah.
Perfect one-factorizations of the complete graph --- a survey.  
{\it Bull. Inst. Combin. Appl.}  {\bf 1}  (1991), 59--70. 

\bibitem{Walsurvey} W.D.~Wallis. One-factorizations of the complete
graph. In {\em Contemporary Design Theory: A Collection of Surveys},
J.H.~Dinitz and D.R.~Stinson, eds., John Wiley \& Sons, New York,
1992, pp. 593--631.

\bibitem{Walbook} W.D.~Wallis. {\em One-factorizations}. 
Kluwer Academic Publishers, Dordrecht, NL, 1997.

\bibitem{Wa} 
I.M. Wanless. Atomic Latin squares based on cyclotomic
orthomorphisms. Submitted.

\bibitem{newest}
J.Z.~Zhang. Some results on perfect $1$-factorizations of $K_{2n}$. {\em 
Dianzi Keji Daxue Xuebao} {\bf 21} (1992), 434--436.

\end{thebibliography}

\newpage

%\noindent
%{\Large{\bf Appendix}}

%\noindent

\appendix

\section*{Appendix} 

Below is a table giving all possible types for sequentially uniform 
one-factorizations of $K_{2n}$, $14 \leq 2n \leq 24$.  
Each type is realized by the ordered $1$-factorization $F_S(1)$ corresponding 
to the starter
$S=\{\{x_i,x_i+i\} : i = 1,\dots,n-1 
\}$ in $\Z_{2n-1}$.
\footnotesize
$$
\begin{array}[t]{|c|c|}
\hline 
{\rm type} & (x_1,\dots,x_{n-1}) \\
\hline 
\hline 
(14 ) & (1, 5, 8, 6, 12, 3)\\ 
\hline 
(10, 4 ) & (1, 9, 4, 6, 3, 12)\\ 
\hline 
(8, 6 ) & (1, 5, 9, 6, 3, 11)\\ 
\hline 
(6,4,4) & (7,2,9,1,6,10)\\ 
\hline
\hline 
(16 ) & (1, 4, 8, 9, 7, 14, 3)\\ 
\hline 
(12, 4 ) & (1, 4, 8, 9, 5, 12, 7)\\ 
\hline 
(10, 6 ) & (1, 7, 11, 4, 5, 12, 6)\\ 
\hline 
(8, 8 ) & (1, 3, 7, 9, 6, 8, 12)\\ 
\hline 
(8, 4, 4 ) & (2, 11, 9, 4, 5, 1, 14)\\ 
\hline 
(6, 6, 4 ) & (3, 11, 2, 6, 7, 8, 9)\\ 
\hline 
(4, 4, 4, 4 ) & (3, 6, 11, 12, 5, 7, 2)\\ 
\hline
\hline 
(18 ) & (1, 3, 7, 12, 8, 9, 4, 6)\\ 
\hline 
(14, 4 ) & (1, 3, 11, 8, 4, 10, 6, 7)\\ 
\hline 
(12, 6 ) & (1, 5, 8, 12, 9, 4, 13, 15)\\ 
\hline 
(10, 8 ) & (1, 3, 6, 11, 8, 10, 7, 4)\\ 
\hline 
(10, 4, 4 ) & (1, 13, 5, 7, 9, 4, 16, 12)\\ 
\hline 
(8, 6, 4 ) & (1, 4, 12, 5, 8, 10, 7, 3)\\ 
\hline 
(6, 6, 6 ) & (1, 6, 10, 5, 11, 15, 7, 12)\\ 
\hline 
(6, 4, 4, 4 ) & (3, 7, 12, 2, 8, 10, 11, 14)\\ 
\hline
\hline 
(20 ) & (1, 3, 6, 11, 13, 8, 10, 4, 7)\\ 
\hline 
(16, 4 ) & (1, 3, 9, 13, 10, 8, 4, 18, 16)\\ 
\hline 
(14, 6 ) & (1, 3, 9, 7, 13, 8, 10, 15, 16)\\ 
\hline 
(12, 8 ) & (1, 3, 9, 13, 6, 10, 8, 18, 14)\\ 
\hline 
(12, 4, 4 ) & (1, 5, 12, 6, 9, 17, 11, 8, 13)\\ 
\hline 
(10, 10 ) & (1, 3, 12, 9, 11, 4, 7, 17, 18)\\ 
\hline 
(10, 6, 4 ) & (1, 4, 10, 11, 7, 18, 9, 14, 8)\\ 
\hline 
(8, 8, 4 ) & (1, 3, 12, 10, 6, 7, 16, 9, 18)\\ 
\hline 
(8, 6, 6 ) & (1, 4, 5, 13, 9, 10, 11, 7, 3)\\ 
\hline 
(8, 4, 4, 4 ) & (2, 5, 11, 4, 10, 12, 13, 9, 16)\\ 
\hline 
(6, 6, 4, 4 ) & (2, 14, 8, 13, 7, 4, 18, 1, 15)\\ 
\hline 
(4, 4, 4, 4, 4 ) & (6, 16, 17, 11, 4, 8, 3, 5, 12)\\ 
\hline
\end{array}
~
\begin{array}[t]{|c|c|}
\hline
{\rm type} & (x_1,\dots,x_{n-1}) \\
\hline 
\hline 
(22 ) & (1, 3, 4, 10, 11, 13, 8, 12, 9, 17)\\ 
\hline 
(18, 4 ) & (1, 3, 4, 13, 11, 12, 8, 6, 10, 20)\\ 
\hline 
(16, 6 ) & (1, 3, 4, 10, 11, 12, 13, 9, 6, 19)\\ 
\hline 
(14, 8 ) & (1, 3, 4, 12, 9, 11, 13, 10, 6, 19)\\ 
\hline 
(14, 4, 4 ) & (1, 4, 7, 11, 12, 14, 19, 8, 9, 3)\\ 
\hline 
(12, 10 ) & (1, 3, 6, 11, 13, 10, 12, 20, 8, 4)\\ 
\hline 
(12, 6, 4 ) & (1, 3, 7, 15, 11, 8, 13, 4, 9, 17)\\ 
\hline 
(10, 8, 4 ) & (1, 3, 7, 11, 14, 6, 13, 9, 16, 8)\\ 
\hline 
(10, 6, 6 ) & (1, 3, 7, 16, 12, 8, 6, 11, 9, 15)\\ 
\hline 
(10, 4, 4, 4 ) & (1, 5, 11, 13, 19, 6, 8, 10, 16, 20)\\ 
\hline 
(8, 8, 6 ) & (1, 3, 12, 6, 13, 14, 4, 9, 7, 19)\\ 
\hline 
(8, 6, 4, 4 ) & (1, 3, 10, 16, 12, 9, 4, 6, 19, 8)\\ 
\hline 
(6, 6, 6, 4 ) & (1, 8, 6, 11, 12, 19, 13, 18, 7, 14)\\ 
\hline 
(6, 4, 4, 4, 4 ) & (1, 11, 5, 16, 9, 6, 17, 10, 19, 15)\\ 
\hline
\hline 
(24 ) & (1, 3, 4, 9, 11, 15, 12, 14, 8, 10, 18)\\ 
\hline 
(20, 4 ) & (1, 3, 4, 13, 10, 16, 12, 6, 11, 8, 21)\\ 
\hline 
(18, 6 ) & (1, 3, 4, 10, 16, 13, 8, 9, 11, 12, 18)\\ 
\hline 
(16, 8 ) & (1, 3, 4, 10, 12, 15, 11, 8, 13, 19, 9)\\ 
\hline 
(16, 4, 4 ) & (1, 3, 6, 10, 16, 11, 15, 12, 4, 8, 19)\\ 
\hline 
(14, 10 ) & (1, 3, 4, 13, 16, 8, 11, 12, 6, 9, 22)\\ 
\hline 
(14, 6, 4 ) & (1, 3, 6, 10, 12, 16, 13, 11, 21, 8, 4)\\ 
\hline 
(12, 12 ) & (1, 3, 4, 10, 12, 16, 13, 11, 6, 8, 21)\\ 
\hline 
(12, 8, 4 ) & (1, 3, 4, 13, 10, 12, 9, 14, 20, 11, 8)\\ 
\hline 
(12, 6, 6 ) & (1, 3, 4, 15, 9, 10, 11, 12, 13, 21, 6)\\ 
\hline 
(12, 4, 4, 4 ) & (1, 3, 13, 15, 4, 6, 14, 10, 8, 20, 11)\\ 
\hline 
(10, 10, 4 ) & (1, 3, 6, 15, 16, 8, 11, 12, 4, 7, 22)\\ 
\hline 
(10, 8, 6 ) & (1, 3, 4, 11, 9, 16, 12, 13, 8, 10, 18)\\ 
\hline 
(10, 6, 4, 4 ) & (1, 3, 4, 12, 15, 13, 10, 6, 9, 21, 11)\\ 
\hline 
(8, 8, 8 ) & (1, 3, 4, 11, 16, 8, 10, 12, 13, 9, 18)\\ 
\hline 
(8, 8, 4, 4 ) & (1, 3, 19, 14, 10, 7, 4, 12, 8, 6, 21)\\ 
\hline 
(8, 6, 6, 4 ) & (1, 3, 9, 13, 22, 15, 7, 10, 11, 6, 8)\\ 
\hline 
(8, 4, 4, 4, 4 ) & (1, 4, 16, 10, 13, 9, 5, 22, 17, 11, 20)\\ 
\hline 
(6, 6, 6, 6 ) & (1, 5, 6, 12, 15, 21, 10, 11, 13, 8, 3)\\ 
\hline 
(6, 6, 4, 4, 4 ) & (1, 6, 14, 7, 13, 15, 3, 12, 19, 22, 16)\\ 
\hline 
(4, 4, 4, 4, 4, 4 ) & (5, 17, 9, 11, 13, 21, 1, 22, 16, 10, 3)\\ 
\hline
\end{array}
$$

\end{document}

.