%% "Longest partial transversals in plexes"
%% as submitted to DCC in August 2012

\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}

%\usepackage{array,color,colortbl}

\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\le}{\leqslant}
\def\dfrac#1#2{\lower0.15ex\hbox{\large$\frac{#1}{#2}$}} % bdm's tricky fracs
\newcommand{\st}[1]{#1^{\ast}}

\title{Decomposing dense bipartite graphs into $4$-cycles}

\author{
Nicholas J. Cavenagh \\
\small Department of Mathematics\\[-0.8ex]
\small The University of Waikato\\[-0.8ex]
\small Private Bag 3105 \\
\small Hamilton 3240, New Zealand.\\
\small\tt nickc@waikato.ac.nz\\ 
}

\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\small Mathematics Subject Classification: 05C51, 05D99}

\begin{document}

\maketitle

\begin{abstract}
Let $G$ be an even bipartite graph with partite sets $X$ and $Y$ such that 
$|Y|$ is even and the minimum degree of a vertex in $Y$ is $95|X|/96$. Suppose furthermore that 
the number of edges in $G$ is divisible by $4$. Then $G$ decomposes 
into $4$-cycles.
\end{abstract}


\section{Introduction}
The {\em order} and {\em size} of a graph $G$ 
indicate the number of vertices and edges in $G$, respectively. All graphs are assumed to be simple (i.e. no loops or multiple edges) unless otherwise stated. 
Given a graph $G$, a set ${\mathcal D}$ of subgraphs of $G$ is said to be 
a {\em decomposition} of $G$ if each edge of $G$ is an edge of precisely 
one element of ${\mathcal D}$.
If, furthermore, each element of ${\mathcal D}$ is isomorphic to a fixed graph 
$H$, we say that $G$ {\em decomposes} into $H$.  

We discuss related results along two strands: the problem of finding decompositions of large graphs with high minimum degree 
and the problem of decomposing bipartite graphs into $4$-cycles (and related decompositions). 

\subsection{Dense decompositions}
In its most general form, the decomposition problem is NP-complete. 
That is, deciding whether an arbitrary graph $G$ decomposes into a given graph $H$ is NP-complete (unless $H$ has at most $2$ edges; \cite{DT}).
However, what if we allow the order and size of $G$ to be arbitrarily large (relative to $H$)? 
There are two necessary conditions for a decomposition that may fail no matter how large  
$G$ is relative to $H$:
\begin{enumerate}
\item[{\rm (C1)}]  
If $G$ decomposes into $H$ then the size of $H$ divides the size of $G$. 
\item[{\rm (C2)}]
If $G$ decomposes into $H$ and 
$d$ is the greatest common divisor of the degrees of vertices in
$H$, then $d$ must divide the degree of each vertex in $G$. 
\end{enumerate} 
On the other hand, if $G$ and $H$ satify conditions (C1) and (C2) above we say that $G$ is {\em $H$-divisible}. 

 Wilson (\cite{Wi}) showed that these necessary conditions are sufficient for sufficiently large complete multigraphs:
\begin{theorem} {\rm (Theorem 24.10 of \cite{BE})} 
For a fixed graph $H$ and integer $\lambda$, there exists an integer 
$N(H,\lambda)$ such that if $n>N(H,\lambda)$ and  
$\lambda K_n$ is $H$-divisible, then
$\lambda K_n$ decomposes into $H$. 
\end{theorem}

In this note we are interested in the problem of showing that graphs which are both sufficiently large and sufficiently dense (specifically, sufficiently large minimum degree) are decomposable.  
Indeed,  Wilson's result above has been generalized to the dense case 
first by Gustavsson (\cite{Gu}) and more recently in  a submitted work (\cite{BKLO}):
\begin{theorem} {\rm \cite{Gu,BKLO}}  
Given a non-empty graph $H$, there exists a positive constant $\gamma$ (a function of $H$) such that if a graph $G$ has $n$ vertices, minimum degree $(1-\gamma +o_n(1))n$ and 
$G$ is $H$-divisible, 
then $G$ decomposes into $H$. 
\label{guss}
\end{theorem}
This powerful theorem has been used to develop a host of related results and generalizations. 
These include showing decompositions ${\mathcal D}$ of sufficiently dense and 
large graphs where:
\begin{itemize}
\item ${\mathcal D}$ is a set of closed trails of arbitrary lengths \cite{Bal}; 
\item Each graph in ${\mathcal D}$ is isomorphic to a graph from a fixed (and finite) list \cite{CaYu2}.  
\end{itemize}
%Other results 
%Theorem \ref{guss} has also been used to give a precisely optimal packing of the edges of $K_n$ with copies of a graph $H$ 

The constant $\gamma$ in Theorem \ref{guss} is small; even if $H$ is a $3$-cycle, 
the constant $\gamma$ is $10^{-24}$ (\cite{Gu}),  
(improved to $0.044$ in \cite{BKLO}).  
In general, if $H$ has $k$ vertices then $\gamma$ is $10^{-37}k^{-94}$ (\cite{Gu}),  
 (improved to $(9k^{10})^{-1}$ in \cite{BKLO}).  
We may compare this to a conjecture by Nash-Williams (\cite{NW}) that any 
graph $G$ of order $n$ and minimum degree at least $3n/4$ decomposes into $3$-cycles 
(so long as $G$ is $3$-cycle-divisible.) 

Asymptotically optimal lower bounds for the minimum degree 
of a $H$-divisible graph $G$ to ensure the existence of 
a $H$-decomposition have been obtained in the case when 
 $H$ has a vertex of degree $1$ and $H$ is bipartite (\cite{Yu1}); and 
 $H$ is an even cycle of length at least $6$ (\cite{BKLO}). 
In both of these cases the 
 minimum degree bound is 
 $n/2(1+o_n(1))$.  (Indeed it is not hard to show this can't be improved if $H$ is connected.) 

Such a bound cannot be obtained for $4$-cycles; one can 
construct arbitrarily large graphs of minimum degree $3n/5-1$ which satisfy 
{\rm (C1)} and {\rm (C2)}, but do not decompose into $4$-cycles (see \cite{Yu1}; attributed to Winkler and Kahn). 
In \cite{BC} it is shown that if $G$ is $4$-cycle-divisible and has minimum degree $31n/32(1+o_n(1))$ then $G$ decomposes into $4$-cycles; the fraction $31/32$ is improved to $2/3$ in \cite{BKLO}. 

Finally, in \cite{BC} it is shown that if $G$ is a $4$-cycle-divisible bipartite graph with  
partite sets $X$ and $Y$ (each of size $n$) and minimum degree $31n/32(1+o_n(1))$, then $G$ decomposes into $4$-cycles. The results in this paper, in contrast, allow the partite sets to have different sizes.  

%Thus there is a need for new methods in the case that $H$ is a 
%$2$-regular graph, which motivates the main result in this paper. 
%In this paper $H$ is a $4$-cycle but our graph $G$ is restricted to bipartite graphs. 

\subsection{Decompositions of complete bipartite graphs into $4$-cycles and related decompositions}

We next discuss what is known about related decompositions of complete (rather than sufficiently dense) graphical structures. 
If we take a broad net there are dozens of papers which are in some way related to decompositions of bipartite graphs into $4$-cycles; rather than making a comprehensive survey, we mention only the few which are most directly related. 
Determining necessary and sufficient conditions for the decomposition of a complete bipartite graph $K_{m,n}$ into $4$-cycles is easy. 
Applying necessary conditions {\rm (C1)} and {\rm (C2)}, $m$ and $n$ must be even. 
These conditions suffice; simply partition the vertices from 
each partite set into pairs, any two such pairs from different partite sets induce a $4$-cycle.  The resultant $4$-cycles form a decomposition. 

The problem becomes more challenging if we specify a constraint that no pair of $4$-cycles shares more than one vertex; such decompositions are {\em monogamous} and necessary and sufficient conditions for them are given in \cite{LiRo}. 
These structures are of interest because of their relation to symmetric $H$-squares and self-orthogonal $1$-factorizations (\cite{LiRo}).  

Necessary and sufficient conditions to decompose $G$ into $H$ 
are known for the following pairs $G$ and $H$:
\begin{itemize}
\item $G$ is a complete bipartite graph and $H$ is a cycle of fixed length (\cite{So}); 
\item $G$ is a complete multipartite graph and $H$ is a $4$-cycle (\cite{CaBi}). 
\end{itemize}





\section{The general approach}

The main result of the paper is the following. 

\begin{theorem} 
Let $G$ be a bipartite graph with partite sets $X$ and $Y$ such that 
$|X|=m$, and $|Y|=n$ (where $n$ is even and $m,n\geq 2$), each vertex of $G$ has even degree and the minimum degree of a vertex in $Y$ is at least $dm$, where $d=95/96$. 
Then $G$ decomposes into $4$-cycles.
\label{biggo}
\end{theorem}

We give a proof of the above theorem in Section 4; in this section we outline our general approach. 

It is convenient to present the details of our proof 
in terms of an array representation. 
To this end, suppose that a bipartite graph $G$ with partite sets $X=\{x_1,x_2,\dots ,x_m\}$ and $Y=\{y_1,y_2,\dots ,y_n\}$ has a decomposition  
${\mathcal D}=\{H_1,H_2,\dots ,H_{\ell}\}$, for some $l\geq 1$. 
Then we may construct a corresponding array $M=M({\mathcal D})$ of dimensions $m\times n$, where
the cell in row $i$ and column $j$ contains the entry $k$ 
(if the edge $\{x_i,y_j\}$ belongs to the subgraph $H_k$) or $0$ (if the edge $\{x_i,y_j\}$ does not belong to $G$). 
We say that $M({\mathcal D})$ is the {\em decomposition array} corresponding to 
the decomposition ${\mathcal D}$.
%For convenience, we may label the rows and columns of $M$; consecutive labelling of rows does not necessarily imply they are %adjacent. 

Next, suppose that ${\mathcal D}_1$ and ${\mathcal D}_2$ are disjoint, non-empty decompositions of the same graph $G$ (for our purposes some subgraph of the bipartite graph we are trying to decompose).   
Then we refer to the pair $({\mathcal D}_1,{\mathcal D}_2)$  as a {\em trade} and we say that ${\mathcal D}_1$ {\em trades} with ${\mathcal D}_2$.  

Our approach to prove Theorem \ref{biggo} is as follows. 
Let $G$ be the bipartite graph we wish to decompose into $4$-cycles. 
We start by placing a $0$ is each cell of $M$ which corresponds to an edge that does not belong to $G$. 
Next, partition the rows and columns of $M$ of into pairs 
${\mathcal P}_R$ and ${\mathcal P}_C$ 
(possibly with one row omitted, if the number of rows is odd). 
The intersection of each 
$P_1\in {\mathcal P}_R$ and $P_2\in {\mathcal P}_C$  
gives a $2\times 2$ subarray; if none of these $4$ cells contain $0$ the corresponding edges form a $4$-cycle in $G$. We let the set of such $4$-cycles be ${\mathcal C}_0$. 
Any cells corresponding to edges from ${\mathcal C}_0$ are initially classified as {\em available}. All remaining cells are classified as {\em unavailable}.  

Next, we pack as many $4$-cycles as possible into the edges of $G$ not used by cycles in ${\mathcal C}_0$. Let ${\mathcal C}_1$ be the set of such $4$-cycles. 
Finally, the remaining edges of $G$ decompose into a set of even-length cycles 
 (which we call ${\mathcal C}_2$). 

The $4$-cycles of ${\mathcal C}_1$ are never changed in our construction. 
However the $4$-cycles in ${\mathcal C}_0$ are sometimes combined with cycles from ${\mathcal C}_2$ to form a trade with a set of $4$-cycles only. 
Each time we do this, any available cells used are reclassified as unavailable. 
The minimum degree condition will ensure there are always enough available cells to choose from to make the necessary trades. 

The following properties (P1) and (P2) will be invariant to the application of our trades. 
For each column $c$ of $M$ and for each pair $P=\{r,r'\}\in {\mathcal P}_R$, the two cells 
$(r,c)$ and $(r',c)$ are either both available or both 
 unavailable (property {\rm (P1)}). 
The total number of available cells within a pair of rows from ${\mathcal P}_R$ is always divisible by $4$ (property {\rm (P2)}). 
These properties ensure that after all trades are completed, within each 
pair of rows $P\in {\mathcal P}_R$ any remaining 
available cells easily decompose into $4$-cycles.

%We now illustrate this approach with an example. 


\section{Some useful trades and a bit of graph theory}

In this section we build up the necessary tools and methods to prove our main result (Theorem \ref{biggo}).  Many of the constructions are most easily understood by studying examples first; we encourage the reader to look ahead to the various examples given. 
The following lemma shows how to trade a cycle of length divisible by $4$ and a specified configuration of $4$-cycles with a set of $4$-cycles only. 

\begin{lemma}
Let  
$\{r_1,r_2,\dots ,r_{2k}\}$ (respectively, $\{c_1,c_2,\dots ,c_{2k}\}$) be a set of distinct rows (respectively, columns) of a decomposition array $M$, where $k\geq 2$. 
For each $i$, $1\leq i\leq k-1$, let $\{r_{2i-1}',r_{2i}'\}$ 
be a set of distinct rows of $M$. 
Let $T$ be a $4k$-cycle on the set of cells 
$$\{(r_1,c_1),(r_{2k},c_{2k})\}\cup \{(r_i,c_{i+1}),(r_{i+1},c_i)\mid 1\leq i\leq 2k-1\}.$$
For each $i$, $1\leq i\leq k-1$, let $S_i$ be the set of cells 
$$S_i=\{(r_{2i-1}',c_{j}),(r_{2i}',c_j)\mid 2i-1\leq j\leq 2i+2 \};$$
in effect two disjoint $4$-cycles. 
 Suppose furthermore that the sets of cells 
$T,S_1,S_2,\dots ,S_{k-1}$ are pairwise disjoint.
Then the edges corresponding to the union of these sets of cells   
 decompose into $4$-cycles.
\label{zerm8}
\end{lemma}

\begin{proof}
%(This lemma is most easily understand by looking at an example; we refer the reader to the example after this proof.)  
For each $i$ such that $1\leq i\leq k-1$, observe that the eight cells from the rows
$r_{2i}$, $r_{2i+1}$ and $r_{2i}'$ may be used by two $4$-cycles.   
For each $i$ such that $1\leq i\leq k-2$, the four cells 
in rows $r_{2i-1}'$ and $r_{2i+1}'$ and columns $c_{2i+1}$ and $c_{2i+2}$ 
may be used by a $4$-cycle. The eight remaining cells belong to the set
$$\{(r_1,c_1),(r_1,c_2),(r_1',c_1),(r_1',c_2)\}\cup 
\{(r_{2k},c_{2k-1}),(r_{2k},c_{2k}), 
(r_{2k-3}',c_{2k-1}),(r_{2k-3}',c_{2k})\}$$  
which give the remaining two $4$-cycles in the decomposition. 
\end{proof}


\begin{example}
We illustrate the method of the above lemma 
with $k=3$:
$$\begin{array}{r|c|c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{c_1} & 
\multicolumn{1}{c}{c_2} & 
\multicolumn{1}{c}{c_3} & 
\multicolumn{1}{c}{c_4} & 
\multicolumn{1}{c}{c_5} & 
\multicolumn{1}{c}{c_6} \\
\cline{2-7}
r_1 & 1 & 1 & & & & \\
\cline{2-7}
r_2 & 2 &  & 2 & & & \\
\cline{2-7}
r_3 &  & 3 &  & 3 & & \\
\cline{2-7}
r_4 &  &  & 4 &  & 4 & \\
\cline{2-7}
r_5 &  &  &  & 5 &  & 5  \\
\cline{2-7}
r_6 &  &  &  & & 6 & 6  \\
\cline{2-7}
r_1' & 1 & 1 & 7 & 7 &  &   \\
\cline{2-7}
r_2' & 2 & 3 & 2 & 3 &  &   \\
\cline{2-7}
r_3' &  &  & 7 & 7 & 6 & 6  \\
\cline{2-7}
r_4' &  &  & 4 & 5 & 4 & 5  \\
\cline{2-7}
\end{array}$$ 
\end{example}


\begin{corollary}
Let $C$ be a cycle of length divisible by $4$ (and at least $8$) within a decomposition 
matrix $M$ (satisfying {\rm (P1)} and {\rm (P2)}), where the cells of $C$ are classified as unavailable.   
Suppose that for any subset of $4$ columns from $M$, 
there exist $2$ elements of ${\mathcal P}_R$ which are available in all of these 
columns.
Then, there exists a trade $({\mathcal D}_1,{\mathcal D}_2)$ where ${\mathcal D}_1$ consists of $C$ and  some $4$-cycles whose edges correspond to available cells with a set ${\mathcal D}_2$ of $4$-cycles only. 
Moreover, after reclassifying any available cells from ${\mathcal D}_1$ as 
unavailable, the matrix $M$ still satisfies properties {\rm (P1)} and 
{\rm (P2)}. 
\label{zeromodfour}
\end{corollary}

The following technical lemma makes it possible to assume 
that any two cycles with 
lengths congruent to $2$ (mod $4$) share at most one vertex within a given partite set.  

\begin{lemma}
Let $C_1$ and $C_2$ be two edge-disjoint cycles in a bipartite graph (with partite sets $X$ and $Y$), each of length 
congruent to $2$ (mod $4$). 
Suppose that $C_1$ and $C_2$ share 
at least two common vertices from partite set $Y$. 
Then  $\{C_1,C_2\}$ may be traded with 
either 
$\{C_3,E\}$, where
$C_3$ is a cycle of length divisible by $4$ and $E$ is an even graph, or
$\{C_4,C_5,E\}$, where $C_4$ and $C_5$ have length congruent to 
$2$ (mod $4$) and share at most one common vertex within $Y$.  
\end{lemma}

\begin{proof}
Consider the even graph $G$ formed by combining the edges of $C_1$ and $C_2$. 
If $G$ contains a cycle of length divisible by $4$, we are done. Otherwise, 
since the number of edges in $G$ is divisible by $4$, there are at least two edge-disjoint cycles in $G$. Let 
$C$ and $C'$ be a pair of such cycles such that the total number of edges in $C$ and $C'$ is minimum. 

Suppose that $C$ and $C'$ intersect at exactly two vertices ($v$ and $w$, say).
If $v$ and $w$ belong to distinct partite sets, the lemma is satsified. 
Otherwise there exist four paths within the union of these cycles, each starting at $v$ and ending at $w$ with an even number of edges, with internal vertices  pairwise disjoint. 
Since $C$ and $C'$ both have lengths congruent to $2$ (mod $4$), at least two of these paths have length divisible by $4$. 
Thus we may join two paths to create a cycle of length 
of length divisible by $4$, and we are done. 

Next, suppose that $C$ and $C'$ intersect at at least three vertices. 
Thus there exist vertices $v$, $w$ and $x$ which belong to both $C$ and $C'$ 
and paths $vP_1w$ and $wP_2x$ within $C$ such that no internal vertices of $P_1$ 
or $P_2$ belong to $C'$. 
There thus exist paths $vQ_1w$, $wQ_2x$ and $xQ_3v$ within $C_2$ such that the 
set of paths $\{P_1,P_2,Q_1,Q_2,Q_3\}$ are pairwise internally vertex-disjoint.

However, the paths $P_1,P_2,Q_1$ and $Q_2$ together form 
a pair of edge-disjoint cycles, contradicting the minimality assumed in the first paragraph of this proof.
Hence $C$ and $C'$ share at most one vertex in the partite set $Y$, as required. 
\end{proof}

\begin{corollary}
Any even, bipartite graph with partite sets $X$ and $Y$ 
has a decomposition ${\mathcal D}$ into cycles such that if  
$C_1,C_2\in {\mathcal D}$ and $C_1$ and $C_2$ each have length congruent 
to $2$ (mod $4$), then $C_1$ and $C_2$ share at most one common vertex within 
the partite set $Y$.  
\label{atmostone}
\end{corollary}


The next lemma trades two cycles which are either column-disjoint or share at most one column (and have length at least $10$), each of length congruent to $2$ (mod $4$) and a set of specified $4$-cycles with a set of $4$-cycles only. 

\begin{lemma}
Let $k,l\geq 1$.  
Within a decomposition matrix $M$, let 
$$\{r_1,r_2,\dots ,r_{2k+1}\},  
\{r_1',r_2',\dots ,r_{2l+1}'\},  
\{u_1,u_2,u_3,u_4\}, \{s_1,s_2,\dots ,s_{2k-2}\},
\{s_1',s_2',\dots ,s_{2l-2}'\}$$ be sets of distinct rows and 
let $$\{c_1,c_2,\dots ,c_{2k+1},  
c_1',c_2',\dots ,c_{2l+1}'\}$$ be a set of distinct columns
(with possibly $c_{2l+1}'=c_{2k+1}$ if $k,l\geq 2$). 
%Suppose furthermore that the sets $\{c_1,c_2,c_3\}$ and $\{c_1',c_2',c_3'\}$ 
%are pairwise disjoint.   
Let $T$ and $T'$ be disjoint sets of cells  corresponding to cycles of 
length $4k+2$ and $4l+2$, respectively.  
Let $T$ occupy the set of cells
$$\{(r_1,c_1),(r_{2k+1},c_{2k+1})\}\cup \{(r_i,c_{i+1}),(r_{i+1},c_i)\mid 
1\leq i\leq 2k\}$$
and let $T'$ occupy the set of cells
$$\{(r_1',c_1'),(r_{2l+1}',c_{2l+1}')\}\cup \{(r_i',c_{i+1}'),(r_{i+1}',c_i')\mid 1\leq i\leq 2l\}.$$
Let $U_1$ and $U_2$ be the sets of cells given by:
$$U_1=\{(u_i,c_j),(u_i,c_j')\mid 1\leq i\leq 2, 1\leq j\leq 3\},\quad 
U_2=\{(u_i,c_j),(u_i,c_j')\mid 3\leq i\leq 4, 2\leq j\leq 3 \}.$$
For each $i$, $1\leq i\leq k-1$, let $S_i$  
be the set of cells 
$$S_i=\{(s_{2i-1},c_{j}),(s_{2i},c_j)\mid 2i\leq j\leq 2i+3 \}.$$
For each $i$, $1\leq i\leq l-1$, let $S_i'$  
be the set of cells 
$$S_i'=\{(s_{2i-1}',c_j'),(s_{2i}',c_j')\mid 2i\leq j\leq 2i+3 \}.$$
 Suppose furthermore that each of the above sets of cells are pairwise disjoint.
Then the edges corresponding to the union of these sets of cells decompose into $4$-cycles.   
\label{genodd}
\end{lemma}

\begin{proof}
The following sets of cells each correspond to $4$-cycles:
$$
\begin{array}{ll}
\{(r_1,c_1),(r_1,c_2),(u_1,c_1),(u_1,c_2)\}, & 
\{(r_2,c_1),(r_2,c_3),(u_2,c_1),(u_2,c_3)\}, \\ 
\{(r_1',c_1'),(r_1',c_2'),(u_1,c_1'),(u_1,c_2')\}, & 
\{(r_2',c_1'),(r_2',c_3'),(u_2,c_1'),(u_2,c_3')\}, \\ 
\{(u_1,c_3),(u_1,c_3'),(u_4,c_3),(u_4,c_3')\}, & 
\{(u_2,c_2),(u_2,c_2'),(u_4,c_2),(u_4,c_2')\}.
\end{array}$$ 
The remaining $4$-cycles in the decomposition may be found in a similar manner to Lemma \ref{zerm8}.  
\end{proof}
%The next lemma trades two $6$-cycles which share precisely one column and a set of specified $4$-cycles with a set of $4$-cycles only. 
\begin{example}
We illustrate the previous lemma with an example. 
In our example to save space we have made many rows equal, however in general this is not a necessary condition in the construction. 
$$\begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{c_1} & 
\multicolumn{1}{c}{c_2} & 
\multicolumn{1}{c}{c_3} & 
\multicolumn{1}{c}{c_4} & 
\multicolumn{1}{c}{c_5} &  
\multicolumn{1}{c}{c_1'} & 
\multicolumn{1}{c}{c_2'} & 
\multicolumn{1}{c}{c_3'} & 
\multicolumn{1}{c}{c_4'} & 
\multicolumn{1}{c}{c_5'} &
\multicolumn{1}{c}{c_6'} & 
\multicolumn{1}{c}{c_7'} 
 \\ 
\cline{2-13}
r_1=r_1' & 1 & 1 & & & & 6 & 6 & & & & &  \\
\cline{2-13}
r_2=r_2' & 2 &  & 2 & & & 7 &  & 7 & & & &  \\
\cline{2-13}
r_3=r_3' &  & 3 &  & 3 & &  & 8 &  & 8 & & &  \\
\cline{2-13}
r_4=r_4' &  &  & 4 &  & 4 &  &  & 9 &  & 9 & &  \\
\cline{2-13}
r_5=r_5' &  &  &  & 5 & 5 &  &  &  & 10 &  & 10 &  \\
\cline{2-13}
r_6' &  &  &  &  &  &  &  &  & & 11 & & 11 \\
\cline{2-13}
r_7' &  &  &  &  &  &  &  &  & & & 12  & 12 \\
\cline{2-13}
u_1 & 1 & 1 & 13 &  &  & 6  & 6  & 13  & & &  &  \\
\cline{2-13}
u_2 & 2 & 14 & 2 &  &  & 7  & 14 & 7  & & &  &  \\
\cline{2-13}
u_3 &  & 15 & 15 &  &  &   & 16 & 16  & & &  &  \\
\cline{2-13}
u_4 &  & 14 & 13 &  &  &   & 14 & 13  & & &  &  \\
\cline{2-13}
s_1=s_1' &  & 15 & 15 & 5 & 5 &   & 16 & 16  & 17 & 17 &  &  \\
\cline{2-13}
s_2=s_2' &  & 3 & 4 & 3 & 4 &   & 8 & 9  & 8 & 9 &  &  \\
\cline{2-13}
s_3' &  &  &  &  &  &   &  &   & 17 & 17 & 12 & 12  \\
\cline{2-13}
s_4' &  &  &  &  &  &   &  &   & 10 & 11 & 10 & 11  \\
\cline{2-13}
\end{array}$$
\end{example}

In the next lemma we deal with the case of one $6$-cycle and another cycle with length congruent to $2$ (mod $4$), overlapping at one column.  

\begin{lemma}
Let $l\geq 1$. 
Within a decomposition array $M$, 
let $\{r_1,r_2,r_3\}$, $\{r_1',r_2'\dots ,r_{2l+1}'\}$, 
$\{u_1,u_2,u_3,u_4\}$ and 
$\{s_1',s_2',\dots ,s_{2l-2}'\}$ (if $l\geq 2$ only) 
each be sets of distinct rows and 
$\{c_1,c_2,c_3,c_2',c_3',\dots ,c_{2l+1}'\}$ be a set 
of distinct columns. 
%Within a decomposition array $M$, 
%let $\{t_1,t_2,t_3\}$, $\{u_1,u_2,u_3\}$, $\{s_1,s_2\}$ and $\{r_1,r_2\}$ each be sets of distinct rows and let $\{c_1,c_2,c_3,c_4,c_5\}$ be a set of distinct columns. 
Let $R$ be the set of cells:  
$$\{(r_1,c_1),(r_1,c_2),(r_2,c_1),(r_2,c_3),(r_3,c_2),(r_3,c_3)\}.$$
Defining $c_1'=c_1$, let $R'$ be the set of cells:  
$$\{(r_1',c_1'),(r_{2l+1}',c_{2l+1}')\}\cup \{(r_i',c_{i+1}'),(r_{i+1}',c_i')\mid 1\leq i\leq 2l\}.$$
Let $U_1$ be the set of cells:
$$\{(u_1,c_1),(u_1,c_2),(u_1,c_2'),(u_1,c_3'),
(u_2,c_1),(u_2,c_2),(u_2,c_2'),(u_2,c_3')
\}.$$
Let $U_2$ be the set of cells:
$$\{(u_3,c_1),(u_3,c_2),(u_3,c_3),(u_3,c_2'),
(u_4,c_1),(u_4,c_2),(u_4,c_3),(u_4,c_2')\}.$$
For each $i$, $1\leq i\leq l-1$, let $S_i'$  
be the set of cells 
$$S_i'=\{(s_{2i-1}',c_j'),(s_{2i}',c_j')\mid 2i\leq j\leq 2i+3 \}.$$
 Suppose furthermore that each of the above sets of cells are pairwise disjoint.
Then the edges corresponding to the union of these sets of cells decompose into $4$-cycles.   
%$$\{(s_i,c_j)\mid 1\leq i\leq 2,j\in\{1,2,4,5\} \}.$$
%Let $R$ be the set of cells: 
%$$\{(r_i,c_j)\mid 1\leq i\leq 2, 1\leq j\leq 4\}.$$
% Suppose furthermore that $R,S,T$ and $U$ are pairwise disjoint.
%Then the edges corresponding to the union of these sets of cells   
% decompose into $4$-cycles.
\label{sixsux}
\end{lemma}

\begin{proof}
The following sets of cells each correspond to $4$-cycles:
$$
\begin{array}{ll}
\{(r_1,c_1),(r_1,c_2),(u_1,c_1),(u_1,c_2)\}, & 
\{(r_2,c_1),(r_2,c_3),(u_3,c_1),(u_3,c_3)\}, \\ 
\{(r_3,c_2),(r_3,c_3),(u_4,c_2),(u_4,c_3)\}, & 
\{(r_1',c_1),(r_1',c_2'),(u_4,c_1),(u_4,c_2')\}, \\ 
\{(r_2',c_1),(r_2',c_3'),(u_2,c_1),(u_2,c_3')\},  &
\{(u_2,c_2),(u_2,c_2'),(u_3,c_2),(u_3,c_2')\}. 
\end{array}$$ 
The remaining $4$-cycles in the decomposition may be found in the same manner
as in Lemma \ref{zerm8}.  
\end{proof}

\begin{example}
We exhibit the cases $l=1$ and $l=2$ from the previous lemma 
in the arrays below. 
$$
\begin{array}{r|c|c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{c_1} & 
\multicolumn{1}{c}{c_2} & 
\multicolumn{1}{c}{c_3} & 
\multicolumn{1}{c}{c_2'} & 
\multicolumn{1}{c}{c_3'} \\ 
\cline{2-6}
r_1 & 1 & 1 & & &  \\
\cline{2-6}
r_2 & 2 &  & 2 & &  \\
\cline{2-6}
r_3 &  & 3 & 3 &  &  \\
\cline{2-6}
r_1' & 4 &  &  & 4 &   \\
\cline{2-6}
r_2' & 5 &  &  &  & 5    \\
\cline{2-6}
r_3' &  &  &  & 6 & 6    \\
\cline{2-6}
u_1 & 1 & 1 &  & 6 & 6    \\
\cline{2-6}
u_2 & 5 & 7 &  & 7 & 5    \\
\cline{2-6}
u_3 & 2 & 7 & 2 & 7 &     \\
\cline{2-6}
u_4 & 4 & 3 & 3 & 4 &     \\
\cline{2-6}
\end{array}
\quad 
\begin{array}{r|c|c|c|c|c|c|c|c|}
\multicolumn{1}{c}{} & 
\multicolumn{1}{c}{c_1} & 
\multicolumn{1}{c}{c_2} & 
\multicolumn{1}{c}{c_3} & 
\multicolumn{1}{c}{c_2'} & 
\multicolumn{1}{c}{c_3'} &  
\multicolumn{1}{c}{c_4'} & 
\multicolumn{1}{c}{c_5'} 
\\ 
\cline{2-8}
r_1 & 1 & 1 & & & & &  \\
\cline{2-8}
r_2 & 2 &  & 2 & & & &  \\
\cline{2-8}
r_3 &  & 3 & 3 &  & & &  \\
\cline{2-8}
r_1' & 4 &  & & 4 & & &   \\
\cline{2-8}
r_2' & 5 &  & & & 5 & &    \\
\cline{2-8}
r_3' &  &  &  & 6 & & 6 &   \\
\cline{2-8}
r_4' &  &  &  &  &7 &  & 7  \\
\cline{2-8}
r_5' &  &  &  &  & & 8 & 8  \\
\cline{2-8}
u_1 & 1 & 1 &  & 10 & 10 & &   \\
\cline{2-8}
u_2 & 5 & 9 &  & 9 & 5 & &   \\
\cline{2-8}
u_3 & 2 & 9 & 2 & 9 & & &    \\
\cline{2-8}
u_4 & 4 & 3 & 3 & 4 &  & &    \\
\cline{2-8}
s_1' &  &  &  & 10 & 10 & 8  & 8   \\
\cline{2-8}
s_2' &  &  &  &6  & 7 &6 & 7   \\
\cline{2-8}
\end{array}
$$ 
\end{example}

%The next lemma deals with the remaining cases where we trade two cycles (each of length congruent to $2$ (mod $4$)) and some specified $4$-cycles with a set of $4$-cycles only. 


The preceding lemmas combine to apply the following. 
%Recall the definitions of available, unavilable and the conditions (P1) and (P2). 

\begin{corollary}
Let $C_1$ and $C_2$ be two cell-disjoint cycles, each of length congruent to $2$ (mod $4$) within a decomposition array $M$ (which satisfies {\rm (P1)} and {\rm (P2)}). 
Suppose furthermore that $C_1$ and $C_2$ share at most one column, and that the cells of $C_1$ and $C_2$ are all unavailable. 
%Suppose that no pair of columns occurs in a 
%row of $C_1$ {\em and} a row of $C_2$. 
%Let ${\mathcal P}$ be a partition of the rows of $M$ into pairs.  
Suppose that:
\begin{itemize}
\item for each subset of $6$ columns, there exist at least $1$ pair from ${\mathcal P}_R$ which is available in all of these columns (condition {\rm (Q1)}); and
%\item for each subset of $5$ columns, there exist at least $2$ elements of ${\mathcal P}$ which are available in all of these columns (condition {\rm (Q1)}); and
\item for each subset of $4$ columns, there exist at least $4$ elements of ${\mathcal P}_R$ which are available in all of these columns (condition {\rm (Q2)}).
\end{itemize}
Then, there exists a trade ${\mathcal D}_1$ of $C_1$, $C_2$ and $4$-cycles whose edges correspond to available cells with a set ${\mathcal D}_2$ of $4$-cycles only. 
Moreover, after reclassifying any available cells from ${\mathcal D}_1$ as unavailable, the matrix $M$ still satisfies properties {\rm (P1)} and {\rm (P2)}. 
\label{twomodfour}
\end{corollary}

\begin{proof}
The idea is similar to Corollary \ref{zeromodfour}.  
Suppose first that $C_1$ is a $6$-cycle sharing a column with $C_2$. 
Applying Lemma \ref{sixsux}, we choose pairs from ${\mathcal P}_R$ in the order: 
$$\{u_1,u_2\}, 
 \{u_3,u_4\}, \{s_1',s_2'\}, \{s_3',s_4'\}, \dots , \{s_{2l-3}',s_{2l-2}'\}.$$
Condition {\rm (Q2)} allows us to make these choices so that the sets $R'$, $U_1$, $U_2$ and $S_i'$ ($1\leq i\leq l-1$) are each pairwise disjoint.

Next, suppose that $C_1$ and $C_2$ are disjoint. 
We seek to apply 
Lemma \ref{genodd} in this case.   
Condition {\rm (Q1)} allows us to choose the pair $\{u_1,u_2\}$ so that $U_1$ 
is disjoint from $C_1$ and $C_2$. 
Condition {\rm (Q2)} allows us to choose the pair $\{u_3,u_4\}$ so that $U_2$ 
is disjoint from $C_1$, $C_2$ and $U_1$. 
Since $C_1$ and $C_2$ are disjoint, condition (Q2) allows us to choose
the remaining pairs from ${\mathcal P}_R$ so that the required sets are disjoint, in the order: 
$$
 \{s_1,s_2\}, \{s_3,s_4\}, \dots , \{s_{2k-3},s_{2k-2}\}, 
 \{s_1',s_2'\}, \{s_3',s_4'\}, \dots , \{s_{2l-3}',s_{2l-2}'\}. 
$$

Finally, suppose that $C_1$ and $C_2$ each have length at least $10$ and 
share one column. Again we apply Lemma \ref{genodd}.   
We proceed as above, taking notice of the extra constraint $c_{2l+1}'=c_{2k+1}$. This potentially effects our choice for the final pair; we must ensure that $S_{l-1}'$ and $S_{k-1}$ are disjoint. Since 
(Q2) allows four choices of pairs, this is no problem.  (We only possibly need four choices in the case where $C_1$ and $C_2$ are  $10$-cycles sharing a common vertex.) 
\end{proof}

\section{The main result}


In this section we prove the main result of the paper (Theorem \ref{biggo}). 

Let $X=\{x_1,x_2,\dots ,x_{m}\}$ and 
 $Y=\{y_1,y_l,\dots ,y_{n}\}$.  
%Let $M$ be an $n\times n$ matrix 
% such that $M_{ij}=0$ if the edge $\{x_i,y_j\}$ does not belong to $G$. 
As outlined in Section 2, we associate with $G$ an $m\times n$ matrix $M$ where cell
$(i,j)$ corresponds with the edge $\{x_i,y_j\}$. 
%An outline of the proof is as follows. 
Our goal is to decompose $G$ into $4$-cycles. 
We achieve this by first packing the empty cells of $G$ with $4$-cycles in a 
structured way (creating a set of $4$-cycles ${\mathcal C}_0$), then in a 
greedy way (creating a set of $4$-cycles ${\mathcal C}_1$).
 The remaining edges must decompose into even length cycles (the set 
${\mathcal C}_2$); using the corollaries above, 
we trade these with cycles from ${\mathcal C}_0$ to obtain the full 
decomposition. 

%Let $M$ be an $m\times n$ array with 
%rows and columns each labelled with the integers from $1$ to $n$.
Cells from $M$ corresponding to edges not in $G$ are filled with the symbol $0$ (these obviously will not be used in any $4$-cycle.)  
As previously, let ${\mathcal P}_R$ be some partition of the rows into pairs (and at most one singleton) and let 
${\mathcal P}_C$ be a partition of the columns into pairs.  
%and columns; without loss of generality, 
%for each $i$, $1\leq i\leq n/2$, let $P_i=\{2i-1,2i\}$ and let
%${\mathcal P}$ be the partition $\bigcup_{1\leq i\leq n/2} P_i$.
For each $P_1$ and $P_2$ such that $|P_1|=2$, $P_1\in {\mathcal P}_R$ and 
$P_2\in {\mathcal P}_C$, 
if cell $(i,j)$ is empty for each $i\in P_1$ and $j\in P_2$, then 
we place a $4$-cycle on these four cells. Let the set of these 
$4$-cycles be ${\mathcal C}_0$. (Some of the $4$-cycles from ${\mathcal C}_0$ will be adjusted later in our proof.) 
We initially classify every cell from ${\mathcal C}_0$ as {\em available} and the remaining cells in 
$M$ as {\em unavailable}. Note that $M$ initially satisfies conditions {\rm (P1)} and {\rm (P2)} (see Section 2).  

In each 
% row or 
column of $M$, at most $(1-d)m-1$ cells contain $0$.  
Let $P$ be a pair of columns from ${\mathcal P}_C$; 
at most $2(1-d)m-2$ cells within columns from $P$ contain $0$. 
Thus each column has at most $2(1-d)m-2$ pairs of cells which are 
classified unavailable. 

%It follows that each pair of 
%rows/
%columns from ${\mathcal P}$ contain  
%at least $n/2-2(1-d)n=n(4d-3)/2$ cycles from ${\mathcal C}_0$. 
%For each column $c$, we say that $P\in {\mathcal P}$ is {\em available} if 
%the pair of rows from $P$ belong to ${\mathcal C}_0$ (within the column $c$); 
%therwise $P$ is said to be {\em unavailable}. 
%Thus each column $c$ has at most $n/2-n(4d-3)/2=2n(1-d)$ pairs of cells 
%which are unavailable. 
%I THINK THERE IS AN EASIER WAY TO COUNT THIS. 

Next, pack as many $4$-cycles as possible in the remaining empty cells.  
Let the set of such $4$-cycles be ${\mathcal C}_1$, where ${\mathcal C}_1$ is disjoint from ${\mathcal C}_0$. 
(These $4$-cycles remain unchanged for the rest of the proof.)

After the edges from the $4$-cycles of ${\mathcal C}_0\cup {\mathcal C}_1$ are 
removed from $G$, the resultant graph $G'$ is even; thus $G'$ decomposes into a set of cycles ${\mathcal C}_2$. 
Since ${\mathcal C}_0\cup {\mathcal C}_1$ is a maximal packing of $4$-cycles, each cycle from ${\mathcal C}_2$ contains at least $6$ edges. 
Now, as each vertex of $G$ has even degree and $Y$ has even size, the number of edges in $G$ is divisible by $4$. 
It follows that the total number of edges in ${\mathcal C}_2$ is divisible by $4$. 
Thus there is a partition ${\mathcal Q}$ of  
 ${\mathcal C}_2$ into singletons or pairs, so that the total number of edges 
in each element of ${\mathcal Q}$ is divisible by $4$. That is, each element of ${\mathcal Q}$ contains either a single cycle with length divisible by $4$ or two cycles, each of which have lengths congruent to $2$ (mod $4$). 
From Corollary \ref{atmostone}, we may also assume in the latter case that the two cycles share at most one common column. 

%We aim to trade the edges from each element of ${\mathcal P}'$ with some
%edges from cycles from ${\mathcal C}_0$.  
By Corollaries \ref{zeromodfour} and \ref{twomodfour}, we can take each 
element of ${\mathcal Q}$ and identify extra available cells, then trade the corresponding edges with $4$-cycles, {\em provided} there are enough available choices for available cells.
After each trade, any available cells used are reclassified as unavailable. 
Observe that conditions {\rm (P1)} and {\rm (P2)} are invariant to the application of trades.  

The trades are in effect using some edges from some of the cycles from 
${\mathcal C}_0$.  However, after all trades have been applied, 
within each pair of rows $P\in {\mathcal P}_R$, (P2) implies that 
we have used each edge from ${\mathcal C}_0$ from an {\em even} number of 
columns. Thus any remaining available cells from $P$ may be decomposed into $4$-cycles.
       
Thus it remains to ensure that there are always enough available cells to perform the required trades. 
Consider a column $c$. From above, at most $2m(1-d)-2$ 
pairs of rows from ${\mathcal P}_R$ are unavailable.  
 Thus at most 
$4m(1-d)-3$ cells in column $c$ are involved with cycles from $C_2$. 
(The extra $1$ here is a possible contribution from the final row, when $m$ is odd.)
It then follows that at most $2m(1-d)-2$ cycles from $C_2$ use column $c$, 
since each cycle uses either $2$ or $0$ cells from a column. 

So, if we are dealing with a particular cycle $C\in {\mathcal C}_2$ which 
intersects a column $c$, we have already 
dealt with at most $2m(1-d)-3$ other cycles from ${\mathcal C}_2$ which also 
involve column $c$, each of which may have ``used'' up to $3$ pairs of rows 
from ${\mathcal P}_R$ containing cells from ${\mathcal C}_0$. 
(The maximum number may occur via an application of Lemma \ref{genodd} or Lemma \ref{sixsux}.) 
Thus for a given column $c$, at most $2m(1-d)-2+3(2m(1-d)-3)=8m(1-d)-11$ pairs of 
rows from ${\mathcal P}_R$ are either unavailable or used by another cycle from ${\mathcal C}_2$. 
  
It follows that amongst any $6$ columns of $C$, there exist 
at least $(m-1)/2-6(8m(1-d)-11)=m(96d-95)/2 +131/2>1$ 
pair of rows from ${\mathcal P}_R$ which is simultaneously available for each of these 6 columns, and moreover have not been previously used. 
Similarly, amongst any $4$ columns of $C$ there exist at least 
at least $(m-1)/2-4(8m(1-d)-11)=m(64d-63)/2 + 87/2>4$ 
pairs of rows from ${\mathcal P}_R$ which are simultaneously available for each of these 4 columns, and moreover have not been previously used. 

By Corollaries \ref{zeromodfour} and \ref{twomodfour} and the above, we may 
thus perform the necessary trades so that ${\mathcal C}_0\cup {\mathcal C}_1$ 
(and thus $G$) decomposes into $4$-cycles. 
This completes the proof of Theorem \ref{biggo}. 


\section{Lower bounds on the minimum degree}

Using notation similar to \cite{Yu1}, we define $b(n)$ to be the least integer 
such that whenever a bipartite graph $G$ with partite sets of size $n$  
satisfies (C1) and (C2) and has minimum degree at least $b(n)$, then $G$ decomposes into $4$-cycles. 
We furthermore let $B=\lim \sup_{n\rightarrow \infty} b(n)/n$. 
and $B_{even}=\lim \sup_{n\rightarrow \infty} b(2n)/(2n)$. 
Thus our main result Theorem \ref{biggo} implies that $B_{even}\leq 95/96$. The following theorem suggests that $B\geq 1/2$; we conjecture that 
$B=B_{even}=1/2$. 

\begin{theorem}
For each even $n$, $n\geq 6$, there exists an even bipartite graph with partite sets 
of size $n$, size divisible by $4$ and minimum degree 
$4\lfloor (n+2)/8\rfloor-2$ which does not decompose into $4$-cycles.  
\end{theorem}

\begin{proof}
Let $X=X_1\cup X_2,Y=Y_1\cup Y_2$ be the partite sets of $G$, where 
$X_1\cap X_2=Y_1\cap Y_2=\emptyset$. 
Let 
$|X_1|=|Y_1|=4\lfloor (n+2)/8\rfloor-1$. 
Remove from $G$ all edges between $X_1$ and $Y_2$, all edges between $X_2$ and $Y_1$, a $1$-factor between 
$X_1$ and $Y_1$ and a $1$-factor between $X_2$ and $Y_2$.  
 Observe that $G$ is an even graph with minimum degree 
$4\lfloor (n+2)/8\rfloor-2$ and consists of two components, each with size 
(number of edges) congruent to $2$ (modulo $4$).
\end{proof}

\section{Conclusion}

There are several ways in which the lemmas of the previous section may be strengthened. As far as I can see the changes 
 do not improve the main result. However we mention them here in 
case they are applicable to future results. 

Firstly, in Lemma  
\ref{zerm8}, the  
 lemma still holds even if $S_i$ and $S_{i+1}$  share the same row set (for any $i$ such that  $1\leq i\leq k-2$); it is not hard to see how the decomposition may be modified to cope with this scenario. 
It follows in Corollary \ref{zeromodfour}, we only require {\em one} valid choice for the pair of rows $P$ (rather than $2$). 
Similarly, in Lemma \ref{genodd} 
we may have $S_1$ or $S_1'$ sharing the same pair of rows as $U_2$, or 
$S_{i}$ and $S_{i+1}$ sharing the same row set (for any $i$ such that $1\leq i\leq k-2$) or 
$S_{i}'$ and $S_{i+1}'$ sharing the same row set (for any $i$ such that $1\leq i\leq l-2$).  
In Lemma \ref{sixsux}, 
we may have $S_1'$ sharing the same pair of rows as $U_1$, or 
$S_{i}'$ and $S_{i+1}'$ sharing the same row set (for any $i$ such that $1\leq i\leq l-2$).  
Consequently, in Condition (Q2) of Corollary \ref{twomodfour}, $2$ elements of ${\mathcal P}$ suffice. 

Furthermore, it might be possible to ensure that for any column, there exists at most one (or some finite number) of trades which use available cells from three distinct pairs of rows. This would allow us to improve our bound from $95/96$ to $71/72$. 
 I have decided that attempting such an approach risks making the proof convoluted. It seems unlikely that $71/72$ is the best possible bound, so it may not be worth the effort. 

We have chosen arbitrary pairings ${\mathcal P}_R$ of the rows and ${\mathcal P}_C$ columns. It may be possible to choose these in some wise fashion, significantly increasing the number of cycles in ${\mathcal C}_0$. 
However, techniques above are unlikely to prove that $B=1/2$ (see the previous section); to do so would require innovation not directly suggested in this paper.  

Finally, there is no obvious reason why the main result in this paper should not be true when $n$ is odd. This remains an open problem. 




\begin{thebibliography}{10}

\bibitem{Bal} P.\ Balister, {\it Packing closed trails into dense graphs}, Journal Combin. Theory Ser. B {\bf 88} (2003), 107--118. 

\bibitem{BKLO} B.\ Barber, D.\ K\"{u}hn, A.\ Lo and D.\ Osthus, 
{\it Edge-decompositions of graphs with high minimum degree}, 
\arxiv{1410.5750} 

\bibitem{BC} D.\ Bryant and N.\ Cavenagh, {\it Decomposing graphs with high minimum degree into $4$-cycles}, J. Graph Theory (to appear), \doi{10.1002/jgt.21816}.    

\bibitem{BE} D.\ Bryant and S. El-Zanati, 
{\em Graph Decompositions}, in: C.J. Colbourn and J.H. Dinitz (ed.), Handbook of Combinatorial Designs, 2nd Edition (Chapman and Hall/CRC, Boca Raton, 2007).

\bibitem{CaYu2} 
Y.\ Caro and R.\ Yuster, {\it List decomposition of graphs}, Discrete Math. 
{\bf 253} (2002), 67--77.  


\bibitem{CaBi} N.\ Cavenagh and E.\ Billington, {\em Decomposition of complete multipartite graphs into cycles of even length}, Graphs Combin. {\bf 16} (2000), 49--65. 

\bibitem{DT} D.\ Dor and M.\ Tarsi, {\it Graph decomposition is NP-complete: A complete proof of Hoyler's conjecture}, SIAM J. Comput. {\bf 26} (1997), 1166--1187. 

\bibitem{Gu} T.\ Gustavsson, Decompositions of large graphs and digraphs with high minimum degree, {\em Ph.D Thesis, University of Stockholm}, 1991.

\bibitem{LiRo} C.C.\ Lindner and A.\ Rosa, {\it Mongoamous decompositions of complete bipartite graphs, symmetric $H$-squares, and self-orthogonal $1$-factorizations}, Australas. J. Combin. {\bf 20} (1999), 251--256. 

\bibitem{NW} C.\ St.\ J.\ A.\ Nash-Williams, {\it An unsolved problem concerning decomposition of graphs into triangles}, in: Combinatorial theory and its applications III ed., pp. 1179--1183, 1970. 

\bibitem{So} D.\ Sotteau, {\it Decomposition of $K_{m,n}(K_{m,n}^*)$ into cycles (circuits) of length $2k$}, J. Combin. Theory Ser. B. {\bf 30} (1981). 

\bibitem{Wi} R.M.\ Wilson, {\it Decompositions of complete graphs into subgraphs isomorphic to a given graph }, Congr. Numer. {\bf 15} (1976), 647--659. 


\bibitem{Yu1} R.\ Yuster, {\it The decomposition threshold for bipartite graphs with minimum degree one}, Random Struct. Alg. {\bf 21} (2002), 121--134.  



\end{thebibliography}

\end{document}