% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

\usepackage{latexsym,tikz,amsfonts}

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand\lam{\lambda}
\newcommand\lcm{\mathrm{lcm}\,}
\newcommand\vj{\mathbf{1}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand\Z{\mathbb{Z}}
\newcommand\F{\mathbb{F}}
\newcommand{\bG}{\mathbb{G}}
\newcommand{\bH}{\mathbb{H}}
\newcommand\cR{\mathcal{R}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{construction}[theorem]{Construction}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

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

% if needed include a line break (\\) at an appropriate place in the title

\title{Resolvable group divisible designs\\ with
large groups}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Peter J. Dukes\thanks{Supported by NSERC grant 312595--2010.}\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small University of Victoria\\[-0.8ex] 
\small Victoria, Canada\\
\small\tt dukes@uvic.ca\\
\and
Esther R.~Lamken\\
\small 773 Colby Street\\[-0.8ex]
\small San Francisco, U.S.A.\\
\small\tt lamken@caltech.edu\\
\and
Alan C.H. Ling\\
\small Department of Computer Science\\[-0.8ex]
\small University of Vermont\\[-0.8ex] 
\small Burlington, U.S.A.\\
\small\tt aling@emba.uvm.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{July 23, 2015}{\today}\\
\small Mathematics Subject Classifications: 05B05,05C70}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We prove that the necessary divisibility conditions are sufficient for the
existence of resolvable group divisible designs with a fixed number of
sufficiently large groups.  Our method combines an application of the Rees
product construction with a streamlined recursion based on incomplete
transversal designs.  With similar techniques, we also obtain new results on
decompositions of complete multipartite graphs into a prescribed graph.
\end{abstract}

\section{Introduction}


A \emph{group divisible design},  or GDD, is a triple $(V,\Pi,\cB)$
which satisfies the following properties.

\begin{itemize}

\item  $\Pi $ is  a partition of the set $V$ into subsets called
\emph{groups}:
 $\Pi=\{V_1,\dots,V_u\}$.
\item    $\cB$ is a collection of subsets of $V$ called \emph{blocks} such
that
a group and a block contain at most one point in common.
\item  Every pair of points from distinct groups occurs in precisely
$\lambda$ blocks;
$\lambda$ is called the \emph{index}.
\end{itemize}

The \emph{type} of a GDD is a list of its group sizes, say
$T=(g_1,g_2,\dots,g_u)$, where $|V_i|=g_i$ for $i=1,2,\dots,u$.
We usually use exponential notation to shorten the type.  In particular,
if all groups have the same size, say $|V_i|=g$ for each $i$, then the GDD
is called \emph{uniform} and its type is written $g^u$.

Consider a GDD of type $T$ and index $\lam$ and suppose the set of its block
sizes belongs to $K \subseteq \Z_{\ge 2}$.  (Blocks of size one can be
discarded without loss.)  We write this as a GDD$_{\lambda}(T,K)$ for
consistency with PBD notation(see below); it is often also denoted as a 
$(K,\lambda)$-GDD of type $T$.
We adopt two standard conventions: if $K=\{k\}$, we write `$k$' instead of
`$\{k\}$' and if
$\lambda =1$,  it can be omitted from the notation.

Group divisible designs are common generalizations of pairwise balanced
designs, balanced incomplete block designs, and transversal designs.
A \emph{pairwise balanced design}, or PBD$(v,K)$, is a GDD$(1^v,K)$.  A
\emph{balanced incomplete block design}, $(v,k,\lambda)$-BIBD,
is a GDD$_{\lambda}(1^v,k)$. A \emph{transversal design}, or TD$(k,n)$, is
a GDD$(n^k,k)$.  In this case, blocks of the GDD are transversals of the
group
partition $\Pi$.

A \emph{parallel class}  or \emph{resolution class} in a
GDD $(V,\Pi,\cB)$ is a subcollection of $\cB$ which partitions $V$. A GDD
is \emph{resolvable} if $\cB$  can be completely partitioned into
parallel classes.  A resolvable GDD is abbreviated RGDD and,
similarly, a resolvable TD is denoted RTD.

As is natural in the case of resolvable designs and transversal designs, we
restrict
our attention in this paper to the case where all blocks have a constant
size, say $k$.
Then, \cite[Lemma 1.1]{Vanst} tells us that in such an RGDD all groups have
the same size; that is, they are uniform.

For the existence of an RGDD$_{\lambda}(g^u,k)$,  it is clearly
necessary that
\begin{equation}
\label{rgdd-res}
gu \equiv 0 \pmod{k}.
\end{equation}
Also, by considering degrees at each point, another necessary condition is
\begin{equation}
\label{rgdd-local}
\lambda g(u-1) \equiv 0 \pmod{k-1}.
\end{equation}
These conditions are not sufficient in general.  For example, there does not
exist GDD$(2^6,3)$ with index $\lam=1$.
On the other hand, in \cite{CDLL}, it was shown that, given fixed $k$ and
$g$,
%\eqref{rgdd-res} and \eqref{rgdd-local}
these conditions are sufficient for $u \gg 0$.


\begin{theorem}[\cite{CDLL}]
\label{asymptotic-rgdd}
Given $g, \lambda \ge 1$ and $k \ge 2$, there exists
RGDD$_{\lambda}(g^u,k)$ for all sufficiently large $u$ satisfying
$gu \equiv 0 \pmod{k}$ and $\lambda g(u-1) \equiv 0 \pmod{k-1}.$
\end{theorem}


Here,  we take the opposite point of view,  fixing $u$
and considering large admissible $g$.  This is similar to the existence
theory
for (resolvable) transversal designs, \cite{CES}, and  GDDs of large order,
\cite{M}.
It is well known that a TD$(k,n)$ is equivalent to a set of $k-2$ mutually
orthogonal latin squares of order $n$. Therefore, from the result of Chowla,
Erd\H{o}s and Strauss in \cite{CES}, a TD$(k,n)$ exists for
sufficiently large integers $n$.  See also \cite{Handbook} for references
and further results.
Since an RTD$(k,n)$ is equivalent to a TD$(k+1,n)$, we also have the
existence of
RTD$(k,n)$ for all sufficiently large $n$.  Our work in this paper is an
extension of this result to RGDDs.

The asymptotic existence of uniform GDDs with large groups and index one is
a  recent result of Moh\'acsy, \cite{M}.
Note that the necessary divisibility conditions are a bit weaker than in the
resolvable case.

\begin{theorem}[\cite{M}]
\label{asymptotic-largegp}
Let $k$ and $u$ be positive integers, $2\leq k \leq u$.
There exists a GDD$(g^u,k)$ for all sufficiently large $g$ satisfying
%the necessary divisibility conditions
$g(u-1) \equiv 0 \pmod{k-1}$ and $g^2u(u-1) \equiv 0\pmod{k(k-1)}$.
\end{theorem}

This paper obtains a similar theorem for resolvable GDDs.
Given integers $u \ge k$, let
\begin{equation}
\label{gmin-def}
g_{\min} = \frac{k(k-1)}{\gcd(u,k) \gcd(u-1,k-1)}.
\end{equation}
Then (\ref{rgdd-res}) and (\ref{rgdd-local}) can be summarized simply as
$g_{\min} \mid g$.  We now state our main result.

\begin{theorem}
\label{main}
Given integers $u \ge k \ge 2$, there exist RGDD$(g^u,k)$ for all
sufficiently large $g \equiv 0 \pmod{g_{\min}}$.
\end{theorem}

The rest of the paper is structured as follows.  In the next section, we
cover the necessary background for our constructions, including some
slightly more general objects.  Then, in Section 3, we construct the first
general examples of RGDDs with a fixed arbitrary number of groups.  Section
4 contains the recursive argument used to complete the proof.  In Section 5,
we extend our results to graph decompositions which we call `transverse' 
graph GDDs and RGDDs. 

We conclude with a discussion of some related results and questions, including a few remarks on 
the existence problem for graph RGDDs with $g$ fixed and $u$ large.  

\section{Background}

We introduce some variant designs and prior results which are useful for our
constructions to follow.

\subsection{Holey GDDs}

A (uniform) \emph{holey group divisible design} is a quadruple
$(V,\Pi,\Xi,\cB)$, where
\begin{itemize}
\item
$V$ is a set of $v$ points;
\item
$\Pi=\{V_1,\dots,V_u\}$ is a partition of $V$ into \emph{groups} of size
$mt$ for each $i$;
\item
$\Xi=\{W_1,\dots,W_t\}$ is a partition of $V$ into \emph{holes}, where $|V_i
\cap W_j|=m$ for each $i,j$.
\item
$\cB \subseteq \binom{V}{k}$ is a set of of blocks which meet each group and
each hole in at most one point; and
\item
any two points from distinct groups and distinct holes appear together in
exactly one block.
\end{itemize}
With these parameters, the above design is abbreviated as an HGDD of type $u
\times m^t$.  To indicate the block size, we write HGDD$(u \times m^t,k)$.
It should be remarked that letting $m=1$ in the definition leads to
`modified group divisible designs', also known as `grid designs'. An HGDD is
also a special type of `double group divisible design', or DGDD; see
\cite{miaodgdd} for a definition.  Resolvability of HGDDs is defined similarly as for GDDs; see \cite{wangrhgdds} for a definition
and an existence theorem for $k=3$.

\begin{example}
The pattern of groups and holes for an HGDD of  type $5 \times 2^4$ is shown
in
Figure~\ref{hgdd-ex}.  The underlying graph is 24-regular; admissible block
sizes are $2,3$ and $4$.
\end{example}

\begin{figure}[htpb]
\begin{center}
\begin{tikzpicture}
\filldraw (0,0) circle [radius=.1];
\filldraw (0,0.5) circle [radius=.1];
\filldraw (0,1) circle [radius=.1];
\filldraw (0,1.5) circle [radius=.1];
\filldraw (0,2) circle [radius=.1];
\filldraw (0,2.5) circle [radius=.1];
\filldraw (0,3) circle [radius=.1];
\filldraw (0,3.5) circle [radius=.1];

\filldraw (1,0) circle [radius=.1];
\filldraw (1,0.5) circle [radius=.1];
\filldraw (1,1) circle [radius=.1];
\filldraw (1,1.5) circle [radius=.1];
\filldraw (1,2) circle [radius=.1];
\filldraw (1,2.5) circle [radius=.1];
\filldraw (1,3) circle [radius=.1];
\filldraw (1,3.5) circle [radius=.1];

\filldraw (2,0) circle [radius=.1];
\filldraw (2,0.5) circle [radius=.1];
\filldraw (2,1) circle [radius=.1];
\filldraw (2,1.5) circle [radius=.1];
\filldraw (2,2) circle [radius=.1];
\filldraw (2,2.5) circle [radius=.1];
\filldraw (2,3) circle [radius=.1];
\filldraw (2,3.5) circle [radius=.1];

\filldraw (3,0) circle [radius=.1];
\filldraw (3,0.5) circle [radius=.1];
\filldraw (3,1) circle [radius=.1];
\filldraw (3,1.5) circle [radius=.1];
\filldraw (3,2) circle [radius=.1];
\filldraw (3,2.5) circle [radius=.1];
\filldraw (3,3) circle [radius=.1];
\filldraw (3,3.5) circle [radius=.1];

\filldraw (4,0) circle [radius=.1];
\filldraw (4,0.5) circle [radius=.1];
\filldraw (4,1) circle [radius=.1];
\filldraw (4,1.5) circle [radius=.1];
\filldraw (4,2) circle [radius=.1];
\filldraw (4,2.5) circle [radius=.1];
\filldraw (4,3) circle [radius=.1];
\filldraw (4,3.5) circle [radius=.1];

 \draw[rounded corners=4pt] (-0.4,-0.4) rectangle (0.4,3.9);
 \draw[rounded corners=4pt] (0.6,-0.4) rectangle (1.4,3.9);
 \draw[rounded corners=4pt] (1.6,-0.4) rectangle (2.4,3.9);
 \draw[rounded corners=4pt] (2.6,-0.4) rectangle (3.4,3.9);
 \draw[rounded corners=4pt] (3.6,-0.4) rectangle (4.4,3.9);

 \draw[rounded corners=4pt] (-0.5,-0.2) rectangle (4.5,0.7);
 \draw[rounded corners=4pt] (-0.5,0.8) rectangle (4.5,1.7);
 \draw[rounded corners=4pt] (-0.5,1.8) rectangle (4.5,2.7);
 \draw[rounded corners=4pt] (-0.5,2.8) rectangle (4.5,3.7);

\node at (0,4.4) {$V_1$};
\node at (1,4.4) {$V_2$};
\node at (2,4.4) {$V_3$};
\node at (3,4.4) {$V_4$};
\node at (4,4.4) {$V_5$};

\node at (-1,3.25) {$W_1$};
\node at (-1,2.25) {$W_2$};
\node at (-1,1.25) {$W_3$};
\node at (-1,0.25) {$W_4$};

\end{tikzpicture}
\end{center}
\caption{Groups and holes for an HGDD of type $5\times 2^4$}
\label{hgdd-ex}
\end{figure}

The holes (or groups) of an HGDD can be filled to create a GDD. The proof of
the following is straightforward and omitted.

\begin{construction}
\label{fill-hgdd}
If there exists an HGDD$(u \times m^t,k)$ and a GDD$(m^t,k)$, then there
exists a GDD$((mu)^t,k)$.
\end{construction}

\subsection{Index reduction}

We point out two constructions which are used to reduce the index of a
design; they  take as
inputs  designs of index $\lam$  and produce designs of index one.


\begin{construction}
\label{inflation-hgdd}
Suppose there exists an RGDD$_\lam(g^u,k)$, and let $q \equiv 1 \pmod{\lam}$
be a large prime power.  Then there exists a resolvable HGDD$(q \times
g^u,k)$.
\end{construction}

\begin{proof}[Proof sketch]
This is a routine extension of Lemma 3.2 in \cite{DL}, which is for the case
$g = 1$.  Suppose our ingredient design is $(X,\Pi,\cA)$.  The construction
has point set $X \times \F_q$ and partitions induced by $\Pi$ and $\F_q$.
We first set up a uniform choice function from blocks in $\cA$ on each pair
of points to the (multiplicative) cosets of index $l$ in $\F_q$.  This
defines a lifting of each block in $\cA$ onto $X \times \F_q$.  From the
structure of the choice function, the lifted blocks can be developed such
that they cover two points $(x,a)$, $(y,b)$ (once) if and only if $x$ and
$y$ are in different groups of $\Pi$ and $a \neq b$.  It follows that we
have an HGDD of type $q \times g^u$.  Resolvability of this HGDD arises from
additively developing the parallel classes induced from $\cA$.
\end{proof}

\begin{remark}
Implicit here and in what follows is Dirichlet's theorem asserting the
existence of infinitely many primes in arithmetic progressions of gcd 1.
\end{remark}

\begin{construction}
\label{inflation-gdd}
Suppose there exists a GDD$_q(g^u,k)$ of index $q$, a prime power.
Then there exists a GDD$((gq^*)^u,k)$, where $q^*$ is a sufficiently large
power of $q$.
\end{construction}

\begin{proof}
This extends the main lemma in \cite{RMW2} from the case $g = 1$.  Suppose
the ingredient design is $(X,\Pi,\cA)$.  Each block $\{x,y,\dots\} \in \cA$
is lifted onto a base block $\{(x,a),(y,b),\dots\}$ of $X \times \F_{q^*}$
in the same way as in \cite{RMW2}.  After developing additively in
$\F_{q^*}$, two points $(x,a),(y,b)$ appear together in exactly one block if
$x$ and $y$ are in distinct groups of $\Pi$, and in zero blocks otherwise.
It follows that we have a GDD with group type $(gq^*)^u$ and index one.
\end{proof}

\subsection{Wilson's fundamental construction}

The following construction for group divisible designs illustrates the
flexibility and utility of these objects.  R.M.~Wilson made crucial use of
this in his existence theory for pairwise balanced designs, and we will use 
several variations of this construction.

\begin{construction}[\cite{Wilsonconst}]
\label{wfc}
Let $(V,\Pi=\{V_1,\dots,V_u\},\cB)$ be a GDD, and consider a function
$\omega  : V \rightarrow \mathbb{N} \cup \{0\}$. Suppose, for each block $B
\in \cB$, that there exists a
$K$-GDD of type $(\omega(x) : x\in B)$. Then there exists a $K$-GDD of type
$(\sum_{x\in V_i} \omega(x) : i = 1,\dots,u)$.
\end{construction}

\begin{remark} 
It is typical to call the starting GDD $(V,\Pi,\cB)$ the `master'
design, $\omega$ a `weighting', and the $K$-GDDs of type $(\omega(x) : x\in
B)$
the `ingredients'.  The construction itself is abbreviated `WFC'.
\end{remark}

In this paper, our use of Construction~\ref{wfc} has constant weighting (so that the ingredients are uniform GDDs).

\subsection{Thick classes and the Rees construction}

Consider any design defined on a set $V$ of points and with
blocks $\cB$.  A $\sigma$-\emph{parallel class} in $\cB$ is a subset $\cR
\subseteq \cB$
such that every element of $V$ appears exactly $\sigma$ times.  Let $\Sigma$
be some list of positive integers $\sigma_1,\dots,\sigma_t$.  A
$\Sigma$-\emph{resolution} of $\cB$ is a partition $\mathfrak{r} =
\{\cR_1,\dots,\cR_t\}$ of $\cB$ into classes, where $\cR_i$ is an
$\sigma_i$-parallel class for $i=1,\dots,t$.  Finally, a design which admits
a $\Sigma$-resolution is called $\Sigma$-\emph{resolvable}.
This coincides with the usual notion of resolvability when $\Sigma =
(1,1,\dots,1)$.

We now develop a condition on transversal designs for the purpose of
`spreading out' $\sigma$-parallel classes in a direct product.
A $\sigma$-\emph{group partition} of a TD$(k,n)$ is a triple
$(\bG,\bH,\mathfrak{c})$, where $\bG$ is an algebraic group of order $n$
used to label each group of the TD, $\bH \subseteq \bG$ with $|\bH|=\sigma$,
and $\mathfrak{c}$ is a partition of the blocks into aggregates so that, for
every class $\mathcal{C} \in \mathfrak{c}$, the set $\{h*C:h \in \bH, C \in
\mathcal{C} \}$ is a parallel class.  Here, $h * C$ denotes the natural
(componentwise) action of $h$ on (the group labels in) $C$.  Note that $\bH$
need not consist of automorphisms of the TD.

Any TD$(k,n)$ admits a trivial $n$-group partition with $\bH=\bG(=\Z_n$,
say) and singleton aggregates.  An RTD$(k,n)$ admits a 1-group partition by
taking $\bH$ to be the identity and each parallel class as an aggregate.
Intermediate examples arise naturally from taking direct products;
we will see an example of this later in Lemma~\ref{td-pgroup}.

The following construction modifies a construction of  Rolf Rees,
\cite{Rees}, to
allow the use of TDs with smaller block sizes.

\begin{construction}
\label{modrees}
Let $(V,\cR)$ be a $\sigma$-parallel class of blocks of order $k$.  Suppose
there exists a TD$((k-1)\sigma+1,n)$ which admits a $\sigma$-group partition
based on the group $\bG$.  Then there exist $\sigma n$ disjoint parallel
classes on $\bG \times V$ that cover all pairs between $\bG \times \{i\}$
and $\bG \times \{j\}$ the same number of times as $\cR$ covers $\{i,j\} \in
\binom{V}{2}$.
\end{construction}

This is essentially recasting Construction 2 of \cite{Rees} to fit the
language of $\sigma$-group partitions.  However,  some comments are needed.
First, observe that the graph of pairwise coverages by blocks in $\cR$ on
the
points of $V$  has maximum degree at most $(k-1)\sigma$.
 It follows that we may
(greedily) color $V$, using at most $(k-1)\sigma+1$ colors,
so that the blocks of $\cR$ are transverse to the color classes. (This is
sometimes called a ``strong'' vertex coloring relative to $\cR$.)
Using this coloring, we can now view $\cR$ as a  partial GDD with
at most $(k-1)\sigma+1$  groups.  This is what allows us to use
a smaller block size for the TDs (instead of the block size $\sim v$ used
in the original construction in \cite{Rees}).

Next, like the Rees constructions, this construction is also a direct
product. In this case,
 the $\sigma$-group partition is used to construct the parallel classes:
$\cR$ is spread out into a parallel
class on $V \times \bH$ and then $\bH$ acts on aggregates of the TD.  The
remark on pairwise coverage by the product then follows.

Finally,  at the extremes for $\sigma$, Construction~\ref{modrees}
reduces to known constructions.   If $\sigma$ is
as large as the replication number, then we are back in the case of the
original Rees construction, \cite{Rees}.
If $\sigma =1$, then the TD is resolvable
and we are back in the case of the standard `direct product'.
Since this case is important later, we state it here separately.

\begin{construction}[Direct Product]
\label{rtd-product}
If there exists an RGDD$(g^u,k)$ and an RTD$(k,n)$, then there exists an
RGDD$((gn)^u,k)$
which contains as a subdesign an RGDD$(g^u,k)$.
\end{construction}

A crucial observation for this type of construction is that if
we have a $\Sigma$-resolvable GDD, Construction~\ref{modrees} or
Construction~\ref{rtd-product} can be applied one class at a time.  Then,
the resulting
parallel classes can be assembled into a resolvable GDD in which the group
sizes
have been inflated by a factor of $n$.


\section{First Examples}

To construct our first examples of  RGDDs of large order, we begin with
existence
for some large index. Recall $g_{\min}$, defined as in (\ref{gmin-def}), is
a function of the desired block size $k$ and number of groups $u$.

\begin{lemma}
\label{large-lambda}
Given integers $u \ge k \ge 2$, there exists RGDD$_{\Lambda}(g_{\min}^u,k)$
for some positive integer $\Lambda$.
\end{lemma}

\begin{proof}
Let $\Gamma$ denote the complete multipartite graph with $u$ parts of size
$g_{\min}$.  Note that $k$ divides the number of vertices of $\Gamma$.
Now, take our block collection $\cB$ to be the (multiset) union of all
possible parallel classes with block size $k$ embedded on $\Gamma$.
Given any two edges $e,e'$ of $\Gamma$, there is a natural bijection (simply
a relabelling) mapping the parallel classes covering $e$ to those covering
$e'$.  It follows that every edge of $\Gamma$ gets covered the same number
of times by blocks in $\cB$.
Moreover, $\cB$ is automatically resolvable by construction.
\end{proof}

\begin{remark}
There are in general many repeated blocks in the above construction, and the
$\Lambda$ obtained in this way is surely far larger than needed.  Also,
observe that we can obtain the same result for the smaller group size
$k/\gcd(u,k)$, which divides $g_{\min}$.  More importantly, with this same
$\Lambda$, we
obtain RGDD$_{\Lambda}(g^u,k)$ for all sufficiently large $g \equiv 0
\pmod{g_{\min}}$ from a direct product using an RTD with $u$ groups.
\end{remark}

Next, we inflate to obtain a resolvable HGDD, and then fill holes to get a
GDD with many parallel classes and a few thick classes.

\begin{lemma}
\label{hgdd-existence}
Given integers $u \ge k \ge 2$ and $g \equiv 0 \pmod{g_{\min}}$, there
exists, for some large prime power $q$, a resolvable HGDD$(q \times g^u,k)$.
Consequently, for large such $g$, there exists a $\Sigma$-resolvable
GDD$((gq)^u,k)$, where the list $\Sigma$ of class thicknesses contains $g
(q-1)(u-1)/(k-1)$ occurrences of $1$ and one occurrence of $g (u-1)/(k-1)$.
\end{lemma}

\begin{proof}
For the resolvable HGDD, we simply apply Construction~\ref{inflation-hgdd}
to the output of Lemma \ref{large-lambda}, choosing $q \equiv 1
\pmod{\Lambda}$.
It is easy to count that this HGDD has $g (q-1)(u-1)/(k-1)$ parallel
classes.
Now, use Construction~\ref{fill-hgdd} and the main result of \cite{M}, which
gives the existence of GDD$(g^u,k)$ for large $g \equiv 0 \pmod{g_{\min}}$.
The $q$ copies of this latter GDD themselves form a $\sigma$-parallel class
for $\sigma=g (u-1)/(k-1)$, this simply being its replication number.
\end{proof}

\begin{remark}
By amalgamating single parallel classes with the thick one, the remaining
thickness can be assumed to equal some prime, say $p$, between $\sigma$ and
$2\sigma$.  The existence of such a prime follows from Bertrand's postulate.
\end{remark}

Now, we apply Construction~\ref{modrees} to get three examples with
`additively independent' group sizes.  Together with our recursive
constructions, these
examples are enough to prove Theorem~\ref{main}.
In order to apply Construction~\ref{modrees} ,
we need the existence of  the ingredient TDs with $\sigma$-group partitions.
We use the natural partitioning from a standard direct product to help
construct the necessary $\sigma$-group partitions.

\begin{lemma}
\label{td-pgroup} Let $n$ and $k$ be positive integers.
Suppse that $p$ is a prime with  $p\ge k$ and suppose that $n$ is
sufficiently
large with $p^2 \mid n$.  Then there exists an RTD$(p(k-1)+1,n)$ admitting a
$p$-group partition.
\end{lemma}

\begin{proof}
Since $p \ge k$, it easily follows that $p^2 \ge p(k-1)+1$.  Therefore, there exists an RTD$(p(k-1)+1,p^2)$ arising from the standard finite field construction.  So we may assume the points of each group are identified with $\Z_{p} \times \Z_{p}$, and that the blocks of this RTD are developed and resolve under this group action.  Each parallel class can therefore be partitioned into $p$ sub-classes, each of $p$ blocks, according to (say) the first $\Z_p$-coordinate in the first group.  Now take a direct product of each sub-class with an RTD$(p(k-1)+1,n/p^2)$.  The resulting RTD$(p(k-1)+1,n)$ can have its groups identified with $\bG=\Z_p \times \Z_{n/p}$.  To verify the $p$-group partition, aggregates arise from the direct product with individual sub-classes (i.e. are constant within each group on the first $\Z_p$-coordinate of $\bG$).  The subgroup $\bH=\Z_p \times \{0\}$ develops each such aggregate into a parallel class.
\end{proof}


\begin{proposition}
\label{mainexamples}
Given $u \ge k \ge 2$, there exist RGDD$(g_i^u,k)$  for $i=1,2,3$ for
arbitrarily large integers $g_1,g_2,g_3$ satisfying
$\gcd(g_1,g_2)=\gcd(g_1g_2,g_3) =g_{\min}$.
\end{proposition}

\begin{proof}
This amounts to a selection of several large and distinct primes for the
preceding constructions.  First, choose distinct primes $a_1,a_2,a_3$ large
enough for the existence of GDD$((a_ig_{\min})^u,k)$, appealing to \cite{M}.
Working from these groupsizes, we next choose, using Dirichlet's Theorem, three new large
primes $q_1,q_2,q_3 \equiv 1 \pmod{\Lambda}$ for the application of
Lemma~\ref{hgdd-existence}.  Finally, by amalgamating classes, the
nontrivial class thicknesses can be assumed to be three new primes
$p_1,p_2,p_3$ to facilitate an easy application of
Construction~\ref{modrees} with Lemma~\ref{td-pgroup}.
We obtain RGDD$(g_i^u,k)$ having groupsizes
$g_i=a_iq_ip_i^2 g_{\min}$ for $i=1,2,3$.  The numerical requirements are
easy to fulfill if we simply avoid in our selection any prime factors of
$g_{\min}$.
\end{proof}

\section{Recursion and Proof}

We set up some recursive constructions with the goal of combining our
examples from Proposition~\ref{mainexamples}.

\subsection{Incomplete designs and recursive constructions}

An \emph{incomplete group divisible design}, or IGDD, is a quadruple
$(V,\Pi,\Pi',\cB)$ such that $V$ is a set of $v$ points, $\Pi =
\{V_1,\dots,V_u)$ is a partition of $V$ into `groups',
$\Pi'=\{W_1,\dots,W_u\}$ with $W_i \subseteq V_i$ for each $i$, and $\cB
\subseteq \binom{V}{\ge 2}$ is a set of blocks such that
\begin{itemize}
\item
two points get covered by a block (exactly one block) if and only if they
come from different groups, say $V_i$ and $V_j$, $i \neq j$, {\bf and} they
do not both belong to the corresponding holes $W_i$ and $W_j$.
\end{itemize}

As with GDDs, the type of an IGDD can be written by listing, using
exponential notation when appropriate, the pairs $(|V_i|;|W_i|)$ of group
size and corresponding hole size.  So, for example, a (uniform)
\emph{incomplete group divisible design} of type $(g;h)^u$ with block size
$k$ is denoted IGDD$((g;h)^u,k)$.

In the special case when $u=k$, $g=n$ and $h=m$, an incomplete GDD is
an \emph{incomplete transversal design} and we write ITD$(k,n;m)$.  These
objects are equivalent to $k-2$ incomplete mutually orthogonal latin squares
of order $n$ with aligned $m \times m$ holes.

The following  existence result for ITDs with small holes is sufficient for
our applications.

\begin{lemma}[\cite{CCLW}]
\label{itd-existence}
Let $k$ and $i$ be integers with $k \geq 2$ and $0 \leq i \leq k$. For all
sufficiently
large $n$,
an ITD$(k,n + i;i)$ exists.
\end{lemma}

In a uniform IGDD$((g;h)^u,k)$, there are two replication numbers:
$r_1:=(g-h)(u-1)/(k-1)$ for points in a hole $W_i$, and $r_2:=g(u-1)/(k-1)$
for points in some $V_i \setminus W_i$.  Let us call such an IGDD
\emph{resolvable} if it partitions into $r_1$ full parallel classes and
$r_2-r_1$ partial classes missing the union $\cup_{i=1}^u W_i$ of all holes.
As is standard, we use IRGDD as an abbreviation.

It is useful to recall that
an ITD$(k+1,n + i;i)$ is equivalent to an IRGDD$((n+i;i)^{k},k)$.  The next
construction is an application  of Construction~\ref{wfc} where the master 
design is an RGDD 
and copies of an ITD (IRGDD) are used as ingredients.  More details can be
found in the book \cite{FMY}.
%The first construction is used in this section.

\begin{lemma}[\cite{FMY}]
\label{irgdd}
If there exists an RGDD$(g^u,k)$ and an ITD$(k+1,n+j;j)$, then there is an
IRGDD$( (gn +gj;gj)^u, k)$.
\end{lemma}

Our main recursive construction is a generalization of Wilson's construction
for TDs, \cite{RMWTD}. The IRGDDs used in our application come 
from Lemma~\ref{irgdd}.

%This result also appears in \cite{FMY}; more recently it was used in\cite{GEL}.

\begin{lemma}[\cite{FMY,GEL}]
\label{gluing}
Suppose that there exists an RTD$(u+1,t)$ and an IRGDD$((m+e_i;e_i)^u,k)$
for each $i$, $1\leq i\leq t$.  Then there is an IRGDD$( (mt+e;e)^u,k)$ with
$e=\sum_{1\leq i\leq t} e_i$. Furthermore if there exists an RGDD$(e^u,k)$,
then there exists an RGDD$((mt+e)^u,k)$.
\end{lemma}

We will also use a special case of this construction which sets $e_i  = 0$
and $w$
and uses the existence
of the subdesign and the RTD to get the existence of the last subdesign.
This
corollary without the resolvability conditions was used in \cite{M}.

\begin{corollary}
\label{cor-glue}
If there exists an RGDD$(n^u,k)$, an RGDD$((n+w)^u,k)$ containing an
RGDD$(w^u,k)$, an RTD$(u+1,s)$, and an RTD$(k,p) $ with $p\leq s$, then
there exists an RGDD$((sn + pw)^u, k)$ which contains an RGDD$((pw)^u,k)$ as a subdesign.
\end{corollary}

\subsection{Proof of Theorem~\ref{main}.}

The broad idea is to get the two ingredient RGDDs of Corollary~\ref{cor-glue},
where gcd$(n,w)=g_{\min}$, using a sequence of earlier constructions.  We thus obtain constructions for groupsizes which are various 
integral linear combinations of $n$ and $w$.  Such combinations are shown to be sufficient with a
representation lemma for large integers due to Moh\'acsy.

\begin{lemma} [\cite{M}]
\label{largeint}
Let $n$ and $w$ be positive integers such that gcd$(n,w)=c$. Then all
sufficiently large multiples of $c$ can be represented in the form $sn +pw$, where $s$ and $p$ are integers with $n < p \le s$.
\end{lemma}

We begin the proof of Theorem~\ref{main}.  Using
Proposition~\ref{mainexamples}, choose large integers $g_i$ such that there
exist RGDD$(g_i^u,k)$ for $i=1,2,3$ satisfying
$\gcd(g_1,g_2)=\gcd(g_1g_2,g_3) =g_{\min}$.

In particular, we take $g_1$ and $g_2$  sufficiently large so that there exist
RTD$(k,g_i)$ and ITD$(k+1,g_i +1;1)$ for
$i=1,2$. In fact, in view of the theorem of Chowla, Erd\H{o}s and Strauss, we may assume similar designs exist with larger groupsizes.
We also choose $g_3$ large enough to apply Lemma~\ref{largeint} with $n=g_1$ and $w=g_2$,
writing $g_3 = s g_1 + p g_2$ where
$s$ and $p$ are non-negative integers such that $g_1 < p \leq s$.

Now use Lemma~\ref{irgdd} twice: once with $n=g_2$ and $g=g_1$ to construct
an
IRGDD$((g_1g_2 + g_1;g_1)^u,k)$ and then again with $n=g_1$ and $g=g_2$ to
construct an IRGDD$((g_1g_2 + g_2;g_2)^u,k)$.  Observe also that Construction~\ref{rtd-product} gives an RGDD$((g_1g_2)^u,k)$.

Next, choose $t$ to be a positive integer relatively prime to $g_3$ and also sufficiently large so that $t \geq
s + p$, and also there exists an RTD$(u+1,x)$ for any $x \ge t$.

With the preceding ingredient designs, apply Lemma~\ref{gluing} with
$m=g_1g_2$, and $e_i \in \{0,g_1,g_2\}$. This gives an IRGDD$((g_1g_2t +e;e)^u,k)$ where
$e=sg_1 + pg_2$.
Recall that $g_3 =sg_1 + pg_2$ and there exists an RGDD$(g_3^u,k)$.
So we have constructed an RGDD$((g_1g_2t + g_3)^u,k)$ with a sub-RGDD$(g_3^u,k)$.

Since $t$ and $g_3$ were chosen relatively prime, we have gcd$(g_1g_2t,g_3)=\gcd(g_1g_2,g_3)=g_{\min}$.

Let $g$ be large and divisible by $g_{\min}$. Use Lemma~\ref{largeint} again, this time with
$n=g_1g_2t$ and $w=g_3$ to write $g=s'n + p'w$, where $s'$ and $p'$ are non-negative integers and
$n < p' \leq  s'$. These integers are large enough for the existence of RTD$(u+1,s')$ and RTD$(k,p')$.  We also have 
an RGDD$(n^u,k)$, from Construction~\ref{rtd-product}.  It follows from Corollary~\ref{cor-glue} that there exists an RGDD$(g^u,k)$.
This completes the proof.

\section{Graph RGDDs}

In this section, we extend Theorem~\ref{main} to the more general case of graph
decompositions.

\subsection{Graph decompositions}

Consider the complete multipartite graph $K_T$, where $T$ denotes the
partition type.  A group divisible design GDD$(T,k)$ is equivalent to an
edge-decomposition of $K_T$ into cliques $K_k$.  A clique in this
decomposition corresponds with a block of size $k$.  If, more generally, we
wish to edge-decompose the same graph $K_T$  into copies of some fixed graph
$G$, we adopt similar notation: GDD$(T,G)$ instead of GDD$(T,k)$, and so on.
Sometimes, even a set of allowed graphs is desired.  We refer the reader to
\cite{CDLL,DL,LW} for more details on the notation and terminology for graph
decompositions which we use below.

In what follows, let $G$ be a simple undirected graph with $k$ vertices, $e$
edges, and degree sequence $d_1,\dots,d_k$, and let $d =\gcd(d_1,\dots,d_k)$.
For an ordinary (not necessarily resolvable) GDD$(g^u,G)$, the divisibility conditions 
generalizing those in Theorem~\ref{asymptotic-largegp} are
$g(u-1) \equiv 0 \pmod{d}$ and
$g^2u(u-1) \equiv 0 \pmod{2e}$.  These are known to be sufficient for fixed
$g$ and large $u$; see for instance \cite{Chan}.  In this section, we are
interested in fixed $u$ and large $g$.

For an RGDD$(g^u,G)$,  we must also have
\begin{equation}
\label{graph-rgdd-res}
gu \equiv 0 \pmod{k};
\end{equation}
this simply reiterates (\ref{rgdd-res}) since a parallel class of $G$-blocks
again partitions the $gu$ points.  The necessary divisibility condition
extending (\ref{rgdd-local}) is discussed in \cite{CDLL}.  We have
\begin{equation}
\label{graph-rgdd-local}
g(u-1) \equiv 0 \pmod{\alpha^*(G)},
\end{equation}
where
where $\alpha^*(G)$ is the least positive integer $A$ so that the
system
\begin{align*}
x_1+\dots+x_k &= A \frac{k}{2e}, \\
d_1x_1+\dots+d_k x_k &= A
\end{align*}
has an integer solution $(x_1,\dots,x_k)$.  For example, in the case when
$G$ is $d$-regular, we have $\alpha^*(G)=d$, seen by taking $x_1=1$ and
$x_i=0$ for each $i=2,3,\dots,k$.  In general, $\gcd(d_1,\dots,d_k) \mid
\alpha^*(G)$.

Recall that for a GDD$(g^u,k)$, there is a necessary inequality $u \ge k$ on
the number of groups.  In the case of graph decompositions GDD$(g^u,G)$,
this is relaxed
to $u \ge \chi(G)$, since now vertices of some block can coexist in the same
group provided they form an independent set in $G$.

\begin{example}
Let $G=K_{a,b}$, the complete bipartite graph.  We have $\chi(G)=2$ as the
minimum possible number of groups.  It is shown in \cite{U} that $K_{n,n}$
edge-decomposes into $K_{a,b}$ if and only if $ab \mid n^2$, $a,b \le n$ and
there exist at least two distinct expressions $n=ax+by$ for nonnegative
integers $x,y$.
It follows that the necessary conditions on $g$ for GDD$(g^2,K_{a,b})$ are
sufficient if $g$ is (mildly) large relative to $a,b$.  We can join copies
of such a GDD to obtain GDD$(g^u,K_{a,b})$ for any $u \ge 2$ (although the
necessary conditions on $g$ may weaken).  As a side note, the question of
edge-decomposing $K_{n,n}$ into $K_{a,b}$ is closely related with the famous
problem of decomposing an $n \times n$ square into $a \times b$ rectangles,
except that we do not demand that such rectangles be `contiguous'.
\end{example}

We remark that, in general, allowing $u < k$ increases the complexity of the
degree condition on $g(u-1)$.  In this case, degrees $g(u-1)$ in some group
of the GDD must be formed as an integral linear combination of the degree
`vectors' of entire colour classes placed on that group.  For this reason,
we are mainly interested in the case where $u \ge k$ and where graph blocks
are only placed across the groups.

For a graph $G$ and positive integers $g,u$, define a \emph{transverse} graph GDD,
denoted by GDD$^!_\lambda(T,G)$,
as an edge-decomposition of the $\lambda$-fold multigraph $K_T^{(\lambda)}$
into copies of $G$ such that each $G$-block and each group (partite set)
share at most one vertex in common.  Clearly, a GDD$_\lambda(T,K_k)$ is equivalent to
a GDD$^!_\lambda(T,K_k)$ but the latter is stronger for general graphs.  We point out that 
standard construction methods for large $u$, such as edge-colored graph decompositions (see \cite{Chan,LW})
yield transverse graph GDDs.  In other words, in many cases there is no loss in discarding those
$G$-blocks with two points together in a group.

A resolvable transverse
graph GDD is denoted RGDD$^!(T,G)$.  We use similar notation for IRGDDs.

%We are interested in the existence of transverse graph GDDs and resolvable
%transverse graph GDDs. 
Recall that our proof of Theorem~\ref{main} used the 
existence of three `numerically independent' examples, Proposition~\ref{mainexamples}, and then applied 
the recursive constructions from Section 4. In each of the cases for graph designs, 
we construct an analogue of Proposition~\ref{mainexamples} by extending our 
techniques from Section 3 or from \cite{M} to construct a set of examples for 
graph GDDs. Once we show that the recursive constructions in Section 4 can 
also be extended with little difficulty to the more general setting of graphs, 
we use the same proof to establish the existence results.  
Instead of repeating all proofs, we point out the key differences in working 
with graph GDDs.

\subsection{Theorem~\ref{asymptotic-largegp} for graphs}

We first consider the existence question for GDD$^!(g^u,G)$; that is,
without resolvability imposed. In this case, necessary conditions are
$g(u-1) \equiv 0 \pmod{d}$ and $g^2u(u-1)  \equiv 0
\pmod{2e}$.
We begin with a few results that roughly correspond with the treatment for
blocks ($G=K_k$) in \cite{M}.

The starting point is a `large index' result.  For this, it is technically
convenient to assume that our graph
$G$ satisfies the \emph{four point condition}: for every edge $\{x,y\} \in
E(G)$, there exist two other vertices $w,z$ of $G$ such that none of $\{w,y\}$, $\{w,z\}$, $\{x,z\}$ are edges of $G$.
If necessary, we can include two additional isolated vertices to $G$ so that it satisfies this condition.  One impact is that, for transverse
GDDs, it is then necessary that the number of groups satisfies $u \ge |V(G)|+2$.  Of course, when considering the existence of a decomposition
into $G$, isolated vertices are immaterial.

\begin{figure}[htpb]
\begin{center}
\begin{tikzpicture}
\filldraw (0,0) circle [radius=.1];
\filldraw (0,1) circle [radius=.1];
\filldraw (1,0) circle [radius=.1];
\filldraw (1,1) circle [radius=.1];

\draw[dashed] (0,1)--(1,1);
\draw[dashed] (0,0)--(1,1);
\draw[dashed] (0,1)--(1,0);
\draw (0,0)--(1,0);

\node at (-.3,-.3) {$x$};
\node at (1.3,-.3) {$y$};
\node at (-.3,1.3) {$w$};
\node at (1.3,1.3) {$z$};
\end{tikzpicture}
\end{center}
\caption{The four point condition}
\label{4pt-cond}
\end{figure}

\begin{lemma}
\label{large-lam-graphs}
Let $G$ be a simple graph with $k$ vertices, $e$ edges, and degree sequence
$d_1,\dots,d_k$.
Suppose that $G$ satisfies the four point condition and let $u \ge k \ge 2$
and $g \ge 1$. Then
there exists GDD$^!_\Lambda(g^u,G)$ for all sufficiently large $\Lambda$
satisfying $\gcd(d_1,\dots,d_k) \mid \Lambda g(u-1)$ and $e \mid \Lambda g^2
\binom{u}{2}$.
\end{lemma}

\begin{proof}[Proof sketch.]
Let $\lam_{\min}$ denote the positive generator of the ideal of integers $\Lambda$ satisfying
the two divisibility conditions.  
Following \cite{LW,M,Wilson75}, we proceed in two steps.  First, we prove the existence of a
`signed GDD' with index $\lam_{\min}$, and then we add sufficiently many multiples of a `complete GDD'
so that all $G$-blocks occur with nonnegative multiplicity.  Since the latter step is quite standard and occurs in nearly
identical form in the references, we focus on the signed decomposition.

Consider the family $\mathcal{G}$ of all edge-$g^2$-colored bi-directed graphs isomorphic to $G$, where
edge colors are induced by vertex labellings $V(G) \rightarrow [g]$.  That is, if $\{x,y\}$ is an edge of $G$
with $x$ labelled $i$ and $y$ labelled $j$, then $(x,y)$ is colored $(i,j)$ and $(y,x)$ is colored $(j,i)$ in this
graph in $\mathcal{G}$.  Our `signed GDD' is a solution to the equations
$\sum_{H \in \mathcal{G}: \epsilon \in H} X_H = \lam$,
where there is one variable $X_H$ for each $H \in \mathcal{G}$ and one equation for each (colored) edge $\epsilon \in K_u^{g^2}$.
To obtain the desired integral solution $\{X_H\}$, we apply \cite[Lemma 5.4]{LW} to this system.
(Note that the four point condition essentially appears in the argument on \cite[p. 167]{LW}.)

Admissibility of $\mathcal{G}$ follows by symmetry considerations.
The calculation of $\alpha(\mathcal{G})$ and $\beta(\mathcal{G})$ proceeds
as a straightforward combination of \cite[Lemma 2.1]{DL} and \cite[Theorem
8.1]{LW}.
\end{proof}

\begin{remark}
If $G$ is edgeless, that is if $e=0$, then only $\Lambda=0$ is admissible.
\end{remark}

Next, we adapt Construction~\ref{inflation-gdd} to $G$-blocks.  There is no
sustantial difference in the proof, since the key idea is just the scheme
for lifting blocks in the inflation.

\begin{construction}
\label{inflation-graphgdd}
Suppose there exists a GDD$_q(g^u,G)$ of index $q$, a prime power.
Then there exists a GDD$((gq^*)^u,G)$, where $q^*$ is a sufficiently large
power of $q$.
\end{construction}

As in \cite[Lemma 6.2]{M}, for fixed $G$ and $u$, the necessary numerical 
conditions on $g$ for existence of a GDD$^!(g^u,G)$ generate an ideal for
admissible $g$, summarized as $g \equiv 0 \pmod{g_{\min}}$. 
In this case,  $ g_{\min}$ has a  complicated form; however, for our purposes, it is 
sufficient to know  that $g_{\min}$ exists.  

%For fixed $G$ and $u$, the necessary numerical conditions on $g$ for
%existence of a GDD$^!(g^u,G)$ appear in Lemma~\ref{large-lam-graphs} when
%$\Lambda$ is set to equal 1.  These conditions generate an ideal for
%admissible $g$, summarized as $g \equiv 0 \pmod{g_{\min}}$, where now
%$g_{\min}$ has the more complicated definition
%\begin{equation}
%\label{gmin-graph}
%g_{\min} = \lcm \left(\frac{u-1}{\gcd(u-1,d_1,\dots,d_k)},
%\sqrt[\Z]{\frac{u(u-1)}{\gcd(u(u-1),2e)}} \right),
%\end{equation}
%and where, for $n \in \mathbb{N}$, we use $\sqrt[\Z]{n}$ to denote the least
%positive integer $m$ such that $n \mid m^2$.

At this point, we can apply Lemma~\ref{large-lam-graphs} with $g=g_{\min}$ to
obtain three large and distinct prime values of $\Lambda$, say $p_i$ for
$i=1,2,3$.
After inflating via Construction~\ref{inflation-graphgdd}, we have mirrored
Proposition~\ref{mainexamples} for transverse GDDs and have constructed 
the three examples needed for the recursive constructions.  There is no need in this 
case to use HGDDs and the Rees product, since resolvability is not (yet) being considered.

The graph-adapted recursive constructions, whose details we reference
forward to the next subsection, together with these three examples 
yield the following existence theorem for graph GDDs.

\begin{theorem}
\label{asym-gdd-largegroups}
Let $G$ be a simple graph on $k$ vertices, $e$ edges, and gcd of degrees
$d$.
Suppose either $u \ge k+2$, or that $G$ satisfies the four point condition
and $u \ge k$.
Then there exists a GDD$^!(g^u,G)$ for all sufficiently large $g$ satisfying
$g(u-1) \equiv 0 \pmod{d}$ and $g^2u(u-1)  \equiv 0
\pmod{2e}$.
\end{theorem}

For our application in the resolvable case, we will need a slightly stronger condition.
A decomposition into simple graphs $G$ is called \emph{equireplicate} if
every point belongs to the same number of $G$-blocks.  A large-order
existence theory for general equireplicate $G$-decompositions was
established in \cite{DM} and used in constructions of resolvable
$G$-decompositions in \cite{DL}. We note that Lemma~\ref{large-lam-graphs}
is easily adapted to equireplicate GDDs, with the only change being that
$\gcd(d_1,\dots,d_k)$ becomes $\alpha^*(G)$.  Also,
Construction~\ref{large-lam-graphs} respects the equireplicate property due
to the transitive action of the finite field on $G$-blocks.

The numerically allowed group sizes for a (uniform) equireplicate graph GDD
with given parameters again form an ideal.  In the equireplicate case, 
$d=\gcd(d_1,\dots,d_k)$ is replaced by
$\alpha^*(G)$.  The equireplicate version of
Theorem~\ref{asym-gdd-largegroups} is stated below, with further details
omitted.

\begin{theorem}
\label{asym-equireplicate-gdd}
Let $G$ be a simple graph on $k$ vertices.
Suppose either $u \ge k+2$, or that $G$ satisfies the four point condition
and $u \ge k$.
Then there exists an equireplicate GDD$^!(g^u,G)$ for all sufficiently large
$g$ satisfying $g(u-1) \equiv 0 \pmod{\alpha^*(G)}$ and $g^2u(u-1)  \equiv 0
\pmod{2e}$.
\end{theorem}

\subsection{Resolvability and recursive constructions}

We turn now to constructions for graph RGDDs.  We omit details of the
essentially similar steps and focus on the key differences. In this case, we adapt 
the techniques we used in Section 3 to graphs to construct our basic three examples.  
Again, we note that  for fixed 
$G$ and $u$, the necessary numerical conditions for the existence of an
RGDD$^!(g^u,G)$,  $(\ref{graph-rgdd-res})$ and $(\ref{graph-rgdd-local})$,
generate an ideal for admissable $g$, summarized as $g \equiv 0 \pmod{g_{\min}}$.

First, it is routine to extend Lemma~\ref{large-lambda} and
Constructions~\ref{fill-hgdd} and \ref{inflation-hgdd} to graphs; in fact,  
\cite[Lemma 3.2]{DL} used in  \ref{inflation-hgdd} was originally proved for graphs.   
Using our own graph GDD result Theorem~\ref{asym-equireplicate-gdd} in 
place of $k$-GDDs to fill in the holes of the HGDD, we
obtain an extension of Lemma~\ref{hgdd-existence} to the graph case.
Instead of  $g(q-1)(u-1)/(k-1)$ parallel classes, we have $g(q-1)(u-1)k/2e$ parallel 
classes,
and instead of one class of thickness $g(u-1)/(k-1)$, we have one of thickness $g(u-1)k/2e$.
It is important to note that the latter class has constant thickness because
equireplicate GDD$^!(g^u,G)$ were used.  So with the hypothesis of 
Theorem~\ref{asym-equireplicate-gdd} for $G$ and fixed $u$, we have 
constructed a  $\Sigma$-resolvable
GDD$((gq)^u,k)$, where the list $\Sigma$ contains one thick class which is 
a $p$-paralllel class for some prime $p$. Our next step is to apply the Rees 
construction.

The Rees product, Construction~\ref{modrees}, extends with no difficulty to
the case of $G$-blocks.  We remark that a $G$-block is acted on by the
transversal design group as a labeled graph; that is, adjacencies between
vertices get preserved.

\begin{construction}
\label{modrees-gr}
Let $H$ be a simple undirected graph with $k$ vertices.
Let $(V,\cR)$ be a $\sigma$-parallel class of $H$-blocks.  Suppose
there exists a TD$((k-1)\sigma+1,n)$ which admits a $\sigma$-group partition
based on the group $\bG$.  Then there exist $\sigma n$ disjoint parallel
classes on $\bG \times V$ that cover all pairs between $\bG \times \{i\}$
and $\bG \times \{j\}$ the same number of times as $\cR$ covers $\{i,j\} \in
\binom{V}{2}$.
\end{construction}

It is helpful to recall the special case of resolvable GDDs, in which
$\sigma=1$ for all classes.  This direct product simply results from
replacing each $G$-block with a copy of the graph Cartesian product $G
\times \overline{K_n}$, and using labels of an RTD$(k,n)$ to (resolvably)
$G$-decompose this product.

\begin{construction}
\label{dp2-graph}
Let $G$ be a simple undirected graph with $k$ vertices.
If there exists an RGDD$^!(g^u,G)$ and an RTD$(k,n)$, then there exists a
RGDD$^!((gn)^u,G)$.
\end{construction}

It is important to distinguish Construction~\ref{dp2-graph} from a standard
direct product, which replaces  each block of an RTD$(u,n)$ with a copy of some RGDD$(g^u,G)$.  This latter product is actually an instance of WFC, where it is 
straightforward to see that  if each of the ingredients is a graph GDD
with $G$-blocks, then
the so is the resulting design.  It is important here that the master be an
`ordinary' GDD with blocks (rather than $G$-blocks).
We state this adaptation without proof.

\begin{construction}
\label{WFC-graph}
Let $(V,\Pi=\{V_1,\dots,V_u\},\cB)$ be an ordinary GDD and $\omega  : V
\rightarrow \mathbb{N} \cup \{0\}$
a weighting.  Suppose, for each block $B \in \cB$, that there exists a
GDD$^!(T_B,G)$, where $T_B=(\omega(x) : x\in B)$. Then there exists a
GDD$^!(T,G)$, where
$T=(\sum_{x\in V_i} \omega(x) : i=1,\dots,u)$.
\end{construction}

We have  now shown that the techniques of Section 3 can be adapted to construct 
our three basic examples for RGDD$^!(g^u,G)$. Next, we  turn to the recursive  constructions 
used in Section 4.

First we recall that the key Lemma~\ref{irgdd} comes from
WFC.  As a minor variation, we can reverse the role of master and ingredient designs
to produce the same IRGDD using an ITD$(u+1,n+j;j)$ and an RGDD$(g^u,k)$.
This is similar to \cite[Theorem 3.4.4]{FMY}.  Now, using
Construction~\ref{WFC-graph}, this is easily adapted to $G$-blocks.

\begin{lemma}
\label{irgdd2-gr}
Let $G$ be a simple undirected graph with $k$ vertices.
If there exists an ITD$(u+1,n+j;j)$ and an RGDD$^!(g^u,G)$, then there is an
IRGDD$^!( (gn +gj;gj)^u, G)$.
\end{lemma}

Since Wilson's construction for transversal designs uses the same idea as
WFC (where the RTD acts as is the `master' design),
Lemma~\ref{gluing} can also be adapted for graph designs.

\begin{lemma}
\label{gluing-gr}
Let $G$ be a simple undirected graph with $k$ vertices.
Suppose that there exists an RTD$(u+1,t)$. If there exists an
IRGDD$^!((m+e_i;e_i)^u,G)$
for any $i$, $1\leq i\leq t$, then there is an IRGDD$^!( (mt+e;e)^u,G)$ with
$e=\sum_{1\leq i\leq t} e_i$. Furthermore if there exists an
RGDD$^!(e^u,G)$,
then there exists an RGDD$^!((mt+e)^u,G)$.
\end{lemma}

Corollary~\ref{cor-glue} constructs an RGDD$((sn + pw)^u, k)$ with a
subdesign
RGDD$((pw)^u,k)$.  A direct product is used to construct the missing
subdesign.  In order to generalize  Corollary~\ref{cor-glue} to
accommodate $G$-blocks, we use the direct 
product in Construction~\ref{dp2-graph} (rather than the standard one 
that arises from applying WFC).   

\begin{corollary}
\label{cor-glue-gr}
Let $G$ be a simple graph with $k$ vertices.
If there exists an RGDD$^!(n^u,G)$, an RGDD$^!( (n+w)^u,G)$ containing an
RGDD$^!(w^u,G)$, an RTD$(u+1,s)$, and an RTD$(k,p) $ with $p\leq s$, then
there exists an RGDD$^!((sn + pw)^u, G)$ which contains as a subdesign an
RGDD$^!((pw)^u,G)$.
\end{corollary}

Finally we note that Lemma~\ref{irgdd2-gr}, Lemma~\ref{gluing-gr}, and
Corollary~\ref{cor-glue-gr} all hold without the resolvability conditions.
In particular, they can be used to construct
GDD$(g^u,G)$. It is also important to note that if all of the graph GDDs
used in the hypotheses  have transverse $G$-blocks, then the resulting
designs will as well.  Thus, we have verified that all of the constructions used 
in Section 4 can be adapted to accommodate $G$-blocks. This gives us all of 
the machinery needed to complete the proof of Theorem~\ref{asym-gdd-largegroups}.

Returning to the resolvable case, we have adapted the constructions in Section 
3 to construct our necessary basic examples, and  we have now 
shown that all of the constructions
used in Section 4.2 (the proof of Theorem~\ref{main}) carry over to
transverse $G$-blocks. This gives us the following for the graph case.

\begin{theorem}
\label{asym-rgdd-largegroups}
Let $G$ be a simple graph on $k$ vertices.  Suppose that either $u \ge k+2$
or $G$ satisfies the four point condition and $u \ge k$.
Then there exists an RGDD$^!(g^u,G)$ for all sufficiently large
$g$ satisfying $(\ref{graph-rgdd-res})$ and $(\ref{graph-rgdd-local})$.
\end{theorem}


\section{Future directions}

We would like to be able to drop the four point condition in
Theorem~\ref{asym-rgdd-largegroups} and especially for the case of what might be
called
`graph transversal designs' GDD$^!(n^{|V(G)|},G)$.
These directions may require new ideas for constructing the underlying
signed decompositions used in the proof of Lemma~\ref{large-lam-graphs}.

There remains considerable work in the cases when $G$-blocks get packed more
tightly than in transverse GDDs.  Even the normally obvious divisibility
conditions appear to be nontrivial when the number of groups is as
small as, say, the chromatic number of $G$.

It should be remarked that our existence theory for RGDD$(g^u,G)$ having $u$ fixed and $g$ large can lead to a new construction for the reverse problem, in which $g$ is fixed and $u$ is large.  This latter graph decomposition problem was first considered in \cite{CDLL} following a complete solution for blocks.  However, the case of general graphs $G$ was only solved in the case when $\gcd(|V(G)|,\alpha^*(G))=1$.  The main idea converting RGDDs with large group size into many groups of fixed size is to use block coloring and `weaving' parallel classes; see \cite[Lemma 2.1]{CDLL}.  Our transverse graph RGDDs from Section 5 can take the place of transversal designs.  However, this approach is not yet sufficiently general to settle the full conjecture which extends Theorem~\ref{asymptotic-rgdd} to graphs.

\begin{conjecture}
Given a positive integer $g$ and simple graph $G$ on $k$ vertices and at least one edge, there exists
RGDD$(g^u,G)$ for all sufficiently large $u$ satisfying
$gu \equiv 0 \pmod{k}$ and $g(u-1) \equiv 0 \pmod{\alpha^*(G)}.$
\end{conjecture}

Returning to the case of blocks $K_k$, it is very natural to consider
arbitrary index $\lam$.  The
necessary condition (\ref{rgdd-local}) weakens to
\begin{equation}
\label{rgdd-lam-local}
\lam g(u-1) \equiv 0 \pmod{k-1}.
\end{equation}
Although many steps in our method easily accommodate general index $\lam$,
the existence problem for GDD$_\lam(g^u,k)$ and GDD$_\lam(g^u,G)$ with fixed
$u$, resolvable or not, remains open.  
Recent progress has been made extending  the `block spreading construction' 
to general $\lam$ in \cite{M2}, and   
%It is perhaps the `block spreading construction' which requires the most care 
%for the extension to general$\lam$.  Still, 
we feel safe with the guess that (\ref{rgdd-res}),
(\ref{rgdd-lam-local}) and $g \gg 0$ are sufficient conditions.

\begin{conjecture}
Given integers $u \ge k \ge 2$ and $\lam \ge 1$, there exist RGDD$_\lam(g^u,k)$ for all
sufficiently large $g$ satisfying $gu \equiv 0 \pmod{k}$ and $\lam g(u-1) \equiv 0 \pmod{k-1}$.
\end{conjecture}

\begin{thebibliography}{99}

\bibitem{Chan}
J.H.~Chan, Asymptotic existence results on specific graph decompositions,
M.Sc. thesis, University of Victoria, 2010.

\bibitem{CES}
S.~Chowla, P.~Erd\H os, and E.G.~Strauss, On the maximal number of pairwise
orthogonal latin squres of a given order.
{\em Canad. J. Math.} 12 (1960), 204--208.

\bibitem{Handbook}
C.J.~Colbourn and J.H.~Dinitz, eds., The CRC Handbook of Combinatorial
Designs, 2nd edition, CRC Press, Boca Raton, 2006.

\bibitem{CDLL}
J.H.~Chan, P.J.~Dukes, E.R.~Lamken and A.C.H. Ling, Asymptotic existence of
resolvable group divisible designs.
{\em J. Combin. Des.} 21 (2013) 112--126.

\bibitem{CCLW}
Y.M.~Chee, C.J.~Colbourn, A.C.H.~Ling, and R.M.~Wilson,
Covering and packing for pairs.
\emph{J. Combin. Theory Ser. A} 120  (2013), 1440--1449.

\bibitem{DL}
P.~Dukes and A.C.H.~Ling, Asymptotic existence of resolvable graph designs.
\emph{Canad. Math. Bull.} 50 (2007), 504--518.

\bibitem{DM}
P.~Dukes and A.~Malloch, An existence theory for loopy graph decompositions.
\emph{J. Combin. Des.}, 19 (2011), 280--289.

\bibitem{FMY}
S.~Furino, Y.~Miao, and J.~Yin, Frames and resolvable designs.  {\em CRC
Press}, New
York, 1996.

\bibitem{GEL}
G.~Ge and A.C.H.~Ling, Asymptotic results on the existence of $4$-RGDDs and
Uniform $5$-GDDS.
\emph{J. Combin. Des.} 13 (2005), 222--237.

\bibitem{LW}
E.R.~Lamken and R.M.~Wilson, Decompositions of edge-colored complete graphs.
{\em J. Combin. Theory Ser. A} 89 (2000), 149--200.

\bibitem{miaodgdd}
Y. Miao, 
Some constructions and uses of double group divisible designs.
\emph{Bull. Inst. Combin. Appl.} 10 (1994), 66--72.

\bibitem{M}
H.~Moh\'acsy,
The asymptotic existence of group divisible designs of large order with
index one.  {\em J. Combin. Theory Ser. A} 118 (2011), 1915--1924.

\bibitem{M2}
H.~Moh\'acsy,
A new infinite family of group divisible $t$-designs with strength $t \geq 2$ and index 
$\lam$, preprint.

\bibitem{RCW}
D.K.~Ray-Chaudhuri and R.M.~Wilson,
The existence of resolvable block designs, in ``A Survey of combinatorial
theory" ({\em Proc. Internat. Sympos., Colorado State Univ., Fort Collins,
Colo.}) (J.N. Srivastava, et. al., Eds.) (1973), 361--376.

\bibitem{Rees}
R.~Rees, Two new direct product-type constructions for resolvable
group-divisible designs.
{\em J. Combin. Des.} 1 (1993) 15--26.

\bibitem{U}
K.~Ushio,
Bipartite decomposition of complete multipartite graphs.
\emph{Hiroshima Math. J.} 11 (1981), 321--345.

\bibitem{Vanst}
S.A.~Vanstone,
Doubly resolvable designs.
{\em Discrete Math.} 29 (1980), 77--86.

\bibitem{wangrhgdds}
C.~Wang,
Resolvable holey group divisible design with block size 3.
{\em Australasian J. Combin.}  39 (2007) 191--206.

\bibitem{RMWTD}
R.M.~Wilson, Concerning the number of mutually orthogonal Latin squares.
{\em Discrete Math.} 9 (1974), 181--198.

\bibitem{RMW1}
R.M.~Wilson, An existence theory for pairwise balanced designs II: The
structure
of PBD-closed sets and the existence conjectures. {\em J. Combin. Theory
Ser. A}
13 (1972), 246--273.

\bibitem{RMW2}
R.M.~Wilson,
An existence theory for pairwise balanced designs III: Proof of the
existence conjectures.
{\em J. Combin. Theory Ser. A} 18 (1975), 71--79.

\bibitem{Wilsonconst}
R.M.~Wilson,
Constructions and uses of pairwise balanced designs,
in Mathematisch Centre Tracts, vol 55, Mathematisch Centrum, Amersterdam,
1974, 18--41.

\bibitem{Wilson75}
R.M.~Wilson,
Decompositions of complete graphs into subgraphs isomorphic to a given
graph.
{\em Congressus Numerantium} XV (1975), 647--659.


\end{thebibliography}


\end{document}