%%templete of seminar report
\documentclass[12pt]{report}
\usepackage{amsfonts}
\usepackage{graphicx}
%title page
\title {CS 5400
Graduate Seminar\\
Technical Report\\
\vskip 40pt
{\bf MGDD with block size 4 and its application to sampling designs}}
\vskip 60pt
\author{
G. Sample\thanks{Research supported by NSERC grant 239135-01}\\
Department of Computer Science \\
Lakehead University\\
Thunder Bay\\
Ontario, Canada P7B 5E1\\
\vspace{2.0 cm}\\
Instructor: Dr. R. Wei}
\newtheorem{Theorem}{Theorem}[chapter]
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Construction}[Theorem]{Construction}
\newtheorem{Corollary}[Theorem]{Corollary}
%\makeindex
\begin{document}
\maketitle
\tableofcontents
\chapter*{Abstract}\addcontentsline{toc}{chapter}{Abstract}
In this report we give a complete solution of the
existence of modified group divisible designs with block size 4. Then we give an
application of the design to some interesting sampling designs.
This is a sample report for the purpose of \LaTeX template. So most content
is omitted.
\chapter{Introduction}
In this chapter, we give the background and overview of this
topic.
\[ \cdots \cdots \cdots \]
A {\em group divisible design} (GDD) is a triple $(X, {\cal G, B})$
which satisfies the following properties:
\begin{enumerate}
\item ${\cal G}$ is a partition of a set $X$ (of points) into subsets called
{\it groups},
\item ${\cal B}$ is a family of subsets of $X$ (called {\it blocks})
such that
a group and a block contain at most one common point,
\item every pair of points from distinct groups occurs in exactly $\lambda$
blocks.
\end{enumerate}
A {\em modified group divisible
design} (MGDD) was first introduced in \cite{a}.
\begin{Definition} Let $X$ be a set of mn
points where the points of $X$ are denoted as
$(x_i,y_j), 0 \le i \le m - 1, 0 \le j \le
n-1$. Let $\cal B$ be a collection of subsets of $X$ ( called blocks),
which satisfies the following
conditions:
\begin{enumerate}
\item $|B|$ = k for every block B $\in \cal B$;
\item every pair of points $(x_{i_1},y_{j_1})$ and $(x_{i_2},y_{j_2}) $ of $X$
are contained in exactly
$\lambda $ blocks, where $i_1 \not = i_2$ and $j_1 \not = j_2.$
\item the pair of points $(x_{i_1},y_{j_1})$ and $(x_{i_2},y_{j_2})$
with $i_1 = i_2$ or
$j_1 = j_2$ are not contained in any blocks.
\end{enumerate}
Then we call $(X, {\cal B})$ a modified group divisible design and
denote
it by\linebreak
$MGD[k,\lambda ,m,mn]$. The subsets $\{ (x_i,y_j) | \ 0 \le i \le m -1
\}$, where $0 \le j \le n -1$ are called {\em groups} and the subsets
$\{ (x_i,y_j) | \ 0 \le j \le n -1 \}$, where $0 \le i \le m -1$ are
called {\em holes}.
\end{Definition}
Modified group divisible designs are motivated by the existence
problem of resolvable group divisible designs. An MGDD can be seen
as a GDD with holes.
\chapter{Related work}
\section{Lemmas and Theorems}
By simple calculation, we can easily obtain the following necessary conditions
for the existence of an MGDD.
\begin{Lemma}. The necessary conditions for the existence of an $MGD[k,
\lambda ,m,nm]$ are that $m \ge k, n \ge k,
\lambda (n-1)(m-1) \equiv 0 \pmod{k - 1} $ and $
\lambda nm(n-1)(m-1) \equiv 0 \pmod{k(k-1)}$.
\end{Lemma}
In \cite{a} it is proved that the necessary conditions are sufficient when k =
3.
However, when k = 4, these conditions are not sufficient. A counter-example
is that an
$MGD[4,1,6,24]$ does not exist because there do not exist two mutually
orthogonal
Latin squares of order 6. The existence of MGDD with block size four was
discussed in \cite{aw,lc}. The following theorem gives an almost complete
solution.
\begin{Theorem}[\cite{aw, lc}]
An $MGD[4,\lambda, m, nm]$exists whenever $m , n \ge 4,
\lambda (n-1)(m-1) \equiv 0 \pmod{3} $, except when $\lambda = 1$ and $\{m,n
\} = \{ 6,4\}$, and possibly when $\lambda = 1$ and $\{ m,n \} \in \{ \{6,16\},
\{ 6,22\}, \{ 10,15\}, \{ 10,18\} \}$.
\end{Theorem}
In this note, we will construct the four unknown designs directly and give the
following complete solution for the existence of MGDD with block size 4.
\begin{Theorem}
An $MGD[4,\lambda, m, nm]$exists if and only if $m , n \ge 4$ and $
\lambda (n-1)(m-1) \equiv 0 \pmod{3} $, except when $\lambda = 1$ and $\{m,n
\} = \{ 6,4\}$.
\end{Theorem}
\section{Other conditions}
\begin{center}
\includegraphics[width=5.5in]{cp300.eps}
\end{center}
\chapter{Constructions}
In this section, we give the constructions of four MGDD. First we
construct an $MGD[4,1,10,10\cdot 18]$. To do that, we consider an
incomplete MGDD. Suppose that the points of one hole is deleted
from an $MGD[4,1,m,nm]$. Then the blocks can be divided into two
parts: one part with blocks of size 4 and other part with blocks
of size 3. Furthermore, all the blocks of size 3 can be
partitioned into $m$ partial parallel classes such that the points
in the blocks of each class contain all the points of the MGDD
except the points of one group and the missing hole.
\section{An example}
In the following, the notation "$+d$ mod $g$" denotes that all
elements of the base blocks should be taken cyclically by adding
$d$ (mod $g$) to them, while the infinite point x, if it occurs in
the base block, is always fixed.
$MGD[4,1,10,10\cdot 18]$ with a missing hole $\{ x_i, 1\le i \le
10\}$:
Point set: $Z_{170} \cup \{ x_i, 1\le i \le 10\}$
Groups:
Holes:
Base blocks: developed by ($+2 \bmod 170)$
\[
\begin{array}{lll}
\{2 , 21 , 125 , 144 \}; &
\{1 , 2 , 4 , 96 \}; &
\{2 , 27 , 64 ,148 \};\\
\{2 , 93 ,108 , 115 \};&
\{1 , 32 , 135 , 144 \};&
\{2 , 17 , 45 , 103 \}; \\
\{2 , 15 , 146 , 150 \};&
\{2 , 38 , 76 ,149 \};&
\{1 , 28 , 110 , 115 \};\\
\{2 , 71 , 83 ,116 \};&
\{2 , 14 , 118 , 119 \};&
\{1 , 53 , 94 , 117 \};\\
\{2 , 31 , 39 , 55 \};&
\{2 , 10 , 54 , 151 \};&
\{1 , 33 , 40 ,138 \};\\
\{1 , 43 , 165 , 167 \};&
\{1 , 116 ,127 , 162 \};&
\{1 , 63 , 126 , 140 \};\\
\{1 , 26 , 83 , 97 \};&
\{1 , 27 , 76 , 108 \};&
\{2 , 5 , 43 , 154 \}\\
\end{array}
\]
\[
\begin{array}{lll}
\{ 9 , 14 , 81\};&
\{ 8 , 107 , 162\};&
\{ 13 , 26 , 105 \}; \\
& &+ 10 \bmod 170 \mbox{\rm \ missing } {0, 10, ...}\\
\{ 14 , 136 , 142\};&
\{ 10 , 93 , 169\};&
\{ 5 , 48 , 157 \} .\\
& &+ 10 \bmod 170 \mbox{\rm \ missing } {1,11,...}
\end{array}
\]
\section{General constructions}
\chapter{An application}
We give an application of MGDD to some kind of sampling designs in this chapter.
\chapter{Recommendations}
We can put future works or research plan, etc here.
\begin{thebibliography}{99}\addcontentsline{toc}{chapter}{Bibliography}
\bibitem{a} A. Assaf, { Modified group divisible designs,} Ars Combinatoria
29(1990), 13-20.
%\bibitem{a} A. Assaf, { An application of modified group divisible designs},
%J. Combinatorial Theory (A), 68(1994), 152-168.
\bibitem{aw}
A. Assaf and R. Wei, Modified group divisible designs with block size 4 and
$\lambda = 1$, Discrete Math., 195(1999), 15-25.
\bibitem{crc} C.J. Colburn, J.H. Dinitz,
CRC Handbook of Combinatorial
Designs, CRC Press, Boca Raton FL, 1996.
\bibitem{ds} J.H. Dinitz, D.R. Stinson, { MOLS with holes,} Discrete Math.
44(1983), 145-154.
\bibitem{lc}
A.C.H. Ling and C.J. Colbourn, Modified group divisible designs with block size
four, Discrete Math., 219(2000), 207-221.
\bibitem{w} R. Wei, { Group divisible designs with equal-sized holes,} Ars
Combinatoria 35(1993), 315-323.
\end{thebibliography}
\end{document}