% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.7}{23(4)}{2016} % 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 % we recommend these ams packages %\usepackage{amsthm,amsmath,amssymb} \usepackage{amsthm,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}}} \def \H {{\cal{H}}} \def \E {{\cal{E}}} \def \K {{\cal{K}}} \def \O {\mathcal O} \def \a {\alpha} \def \b {\beta} \def \l {\lambda} \def \binom#1#2{{#1\choose#2}} % 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} \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{\bf On almost-regular edge colourings of hypergraphs} % 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{Darryn Bryant\thanks{Supported under the Australian Research Council's Discovery Projects funding scheme, project numbers DP120100790, DP150100506, DP150100530.}\\ \small Department of Mathematics\\[-0.8ex] \small University of Queensland \\[-0.8ex] \small Qld 4072, Australia\\ \small\tt db@maths.uq.edu.au\\ %\and %Forgotten Second Author \qquad Forgotten Third Author\\ %\small School of Hard Knocks\\[-0.8ex] %\small University of Western Nowhere\\[-0.8ex] %\small Nowhere, Australasiaopia\\ %\small\tt \{fsa,fta\}@uwn.edu.ao } % \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{Dec 28, 2015}{Sep 29, 2016}{Oct 14, 2016}\\ \small Mathematics Subject Classifications: 05C15, 05C65, 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 if $\H=(V(\H),\E(\H))$ is a hypergraph, $\gamma$ is an edge colouring of $\H$, and $S\subseteq V(\H)$ such that any permutation of $S$ is an automorphism of $\H$, then there exists a permutation $\pi$ of $\E(\H)$ such that $|\pi(E)|=|E|$ and $\pi(E)\setminus S=E\setminus S$ for each $E\in\E(\H)$, and such that the edge colouring $\gamma'$ of $\H$ given by $\gamma'(E)=\gamma(\pi^{-1}(E))$ for each $E\in\E(\H)$ is almost regular on $S$. The proof is short and elementary. We show that a number of known results, such as Baranyai's Theorem on almost-regular edge colourings of complete $k$-uniform hypergraphs, are easy corollaries of this theorem. \end{abstract} %\section{Introduction} There are many results in the literature concerning edge colorings of various families of ``complete'' hypergraphs such that the colouring is ``almost regular''. In this short note, we give a general theorem of this kind and present several corollaries. These corollaries are all known results, or at least very similar to known results. The purpose here is to demonstrate the generality of the theorem, and in particular to present its simple proof. A similar proof for the corresponding result in the special case of ordinary graphs appeared in \cite{BryMae}. Results of the above-mentioned kind can be loosely described as generalisations of a well-known theorem of Baranyai \cite{Bar1}. There is a multitude of generalisations of Baranyai's Theorem, for example see \cite{Bah1,Bar2,Bar3,Bar4,BroSch,ColFanHor,HagHel}, and a comprehensive discussion of these and the overlaps and relationships between existing results and consequences of our theorem would be rather lengthy and involved. Instead we present just a few of the cleaner corollaries to our theorem, and give some pointers to closely related results in the literature. In \cite{Bah1}, Bahmanian proves results along somewhat similar lines to our main theorem, and also obtains several generalisations of Baranyai's Theorem as corollaries. Bahmanian's main theorem applies the method of amalgamations of graphs \cite{AndRod} to hypergraphs. His proof is considerably more substantial and involved than ours, and uses a result of Nash-Williams \cite{Nas} on laminar families of sets. A {\em hypergraph} $\H$ consists of a vertex set $V(\H)$ and a collection $\E(\H)$ of edges where each $E\in\E(\H)$ is a subset of $V(\H)$. The elements of an edge $E$ are called its {\em endpoints}. A hypergraph may have edges with different cardinalities, and may have multiple edges with the same endpoints. We say that a hypergraph $\H'$ is a subhypergraph of a hypergraph $\H$ if $V(\H')\subseteq V(\H)$ and $\E(\H')\subseteq\E(\H)$. If $\phi$ is a permutation of a set $N$ and $X\subseteq N$, then $\phi(X)$ is defined by $\phi(X)=\{\phi(x):x\in X\}$. A permutation $\phi$ of $V(\H)$ is an automorphism of $\H$ if the multiplicity in $\H$ of $\phi(X)$ equals the multiplicity in $\H$ of $X$ for every $X\subseteq V(\H)$, where the {\em multiplicity} of any $X\subseteq V(\H)$ is defined to be the number of edges in $\E(\H)$ that have precisely the elements of $X$ as their endpoints. A hypergraph $\H$ is {\em almost regular} if $|\deg_\H(x)-\deg_\H(y)|\leq 1$ for all $x,y\in V(\H)$, and is {\em almost regular on $S\subseteq V(\H)$} if $|\deg_\H(x)-\deg_\H(y)|\leq 1$ for all $x,y\in S$. If $\gamma$ is an edge colouring of $\H$ and $c$ is one of the colours, then the spanning subhypergraph of $\H$ whose edges are those assigned colour $c$ by $\gamma$ is called {\em colour class $c$} and is denoted by $\H^\gamma_c$. An edge colouring $\gamma$ of $\H$ is {\em almost regular} if each colour class is almost regular, and is {\em almost regular on $S\subseteq V(\H)$} if each colour class is almost regular on $S$. Our main result is the following theorem. \begin{theorem}\label{maintheorem} If $\H$ is a hypergraph, $\gamma$ is an edge colouring of $\H$, and $S\subseteq V(\H)$ such that any permutation of $S$ is an automorphism of $\H$, then there exists a permutation $\pi$ of $\E(\H)$ such that $|\pi(E)|=|E|$ and $\pi(E)\setminus S=E\setminus S$ for each $E\in\E(\H)$, and such that the edge colouring $\gamma'$ of $\H$ given by $\gamma'(E)=\gamma(\pi^{-1}(E))$ for each $E\in\E(\H)$ is almost regular on $S$. \end{theorem} \proof If $\gamma$ is almost regular on $S$, then we let $\pi$ be the identity and we are finished. Otherwise, there exists a colour $c$ and vertices $\a,\b\in S$ such that $\deg_{\H_c^\gamma}(\a)-\deg_{\H_c^\gamma}(\b)>1$ and $\deg_{\H_c^\gamma}(\a)\geq\deg_{\H_c^\gamma}(x)\geq\deg_{\H_c^\gamma}(\b)$ for all $x\in S$. Let $\E_{\a\setminus\b}=\{E\in\E(\H):\a\in E,\b\notin E\}$ and let $\theta$ be an involution of $\E(\H)$ induced by the transposition $(\a\,\b)$. Note that ${\rm image}(\theta)\subseteq\E(\H)$, because the transposition $(\a\,\b)$ is an automorphism. Construct an auxiliary multigraph $G$, possibly containing loops, with a vertex for each colour, and with an edge $\{\gamma(E),\gamma(\theta(E))\}$ for each edge $E\in \E_{\a\setminus\b}$ (so $\{\gamma(E),\gamma(\theta(E))\}$ is a loop if $E$ and $\theta(E)$ are the same colour). Now define an orientation $\O$ of the edges of $G$ by orienting $\{\gamma(E),\gamma(\theta(E))\}$ from $\gamma(E)$ to $\gamma(\theta(E))$ for each $E\in \E_{\a\setminus\b}$. Observe that for each colour $x$ we have $\deg^+_G(x)-\deg^-_G(x)=\deg_{\H_x^\gamma}(\a)-\deg_{\H_x^\gamma}(\b)$ where $\deg^+_G(x)$ and $\deg^-_G(x)$, respectively, denote the outdegree and indegree, respectively, of $x$ in $G$. It is easily shown that there is an orientation of any multigraph such that the indegree of each vertex differs from its outdegree by at most 1. One way to obtain such an orientation is to add a new vertex which is joined to every vertex of odd degree, greedily decompose the resulting graph into edge-disjoint cycles, orient each of these cycles to form a directed cycle, and then delete the added vertex. Let $\O^*$ be an orientation of $G$ such that the indegree of each vertex differs from its outdegree by at most 1, and define $\pi^*$ to be the involution of $\E(\H)$ that transposes $E$ and $\theta(E)$ precisely when $E\in \E_{\a\setminus\b}$ and $\{\gamma(E),\gamma(\theta(E))\}$ has opposite orientation in $\O$ and $\O^*$. It follows that for each $E\in \E(\H)$ we have $|\pi^*(E)|=|E|$ and $\pi^*(E)\setminus S=E\setminus S$ (recall that $\a,\b\in S$). Moreover, since in $G$ with orientation $\O^*$ the indegree of each vertex differs from its outdegree by at most 1, the edge colouring $\gamma^*$ given by $\gamma^*(E)=\gamma({\pi^*}^{-1}(E))$ for each $E\in \E(\H)$ is almost regular on $\{\a,\b\}$. Also, for each colour $x$, we have $\deg_{\H_x^{\gamma^*}}(\a)+\deg_{\H_x^{\gamma^*}}(\b)=\deg_{\H_x^{\gamma}}(\a)+\deg_{\H_x^{\gamma}}(\b)$. Noting that relative to the edge colouring $\gamma$, colour class $c$ of $\gamma^*$ is strictly ``closer'' to almost regular on $S$, and that no colour class of $\gamma^*$ is ``further'' from almost regular on $S$, it is clear that the required permutation $\pi$ can be obtained by repeating the above-described procedure until colour class $c$ is almost regular on $S$, and then repeating for each colour. \qed \vspace{0.3cm} A hypergraph is {\em $k$-uniform} if each edge has exactly $k$ endpoints. Let $n$ be a positive integer, let $N=\{1,2,\ldots,n\}$, and for $k=0,1,\ldots,n$ let $\binom Nk=\{X\subseteq N:|X|=k\}$ be the set of all $k$-subsets of $N$. The hypergraph with vertex set $N$, and edge set $\binom Nk$ is called the {\em complete $k$-uniform hypergraph} (of order $|N|$) and is denoted $\K^k_N$. The most well-known version of Baranyai's Theorem \cite{Bar1} is obtained from the following immediate corollary of Theorem \ref{maintheorem} by putting $t=\binom{n-1}{k-1}$ and $a_1=a_2=\cdots=a_t=\frac nk$ in the case $k$ divides $n$. \begin{corollary}\label{BaranyaiThoerem} If $n$, $k$, $t$ and $a_1,a_2,\ldots,a_t$ are positive integers such that $a_1+a_2+\cdots+a_t=\binom nk$, then the complete $k$-uniform hypergraph of order $n$ has an almost-regular edge colouring with $t$ colours $c_1,c_2,\ldots,c_t$ such that the number of edges of colour $c_i$ is $a_i$ for $i=1,2,\ldots,t$. \end{corollary} \proof Arbitrarily colour the $\binom nk$ edges of the complete $k$-uniform hypergraph $\H$ so that there are $a_i$ edges of colour $c_i$ for $i=1,2,\ldots,t$, and then apply Theorem \ref{maintheorem} with $S=V(\H)$. \qed \vspace{0.3cm} Let $N=\{1,2,\ldots,n\}$. For any vector $\Lambda=(\lambda_0,\lambda_1,\ldots,\lambda_n)$ of non-negative integers, the hypergraph $\K^\Lambda_N$ has vertex set $V(\K^\Lambda_N)=N$, and $\E(\K^\Lambda_N)$ ;given by including $\lambda_r$ copies of each $r$-subset of $N$ for $r=0,1,\ldots,n$. Thus, the hypergraph whose edges are the elements of the power set of $N$ is denoted $\K_N^{(1,1,\ldots,1)}$, and the complete $k$-uniform hypergraph $\K^k_N$ is the graph $\K^{(\lambda_0,\lambda_1,\ldots,\lambda_n)}_N$ with $\lambda_k=1$ and $\lambda_j=0$ for $j\neq k$. The {\em type} of any collection of subsets of $N$ is the vector $(r_0,r_1,\ldots,r_n)$ such that for $j=0,1,\ldots,n$, $r_j$ is the number of subsets of cardinality $j$ in the collection. In Corollary \ref{firstcorollary}, if we put $\l_j=1$ for $j=0,1,\ldots,n$, and choose $r_{i,j}$ so that $\sum_{j=0}^nr_{i,j}\leq n$ for $i=1,2,\ldots,t$, then we obtain a theorem from \cite{ColFanHor}. See \cite{Bah2} for a general result along these lines. \begin{corollary}\label{firstcorollary} Let $n$ and $t$ be positive integers, let $N=\{1,2,\ldots,n\}$, let $\lambda_0,\lambda_1,\ldots,\lambda_n$ be non-negative integers, and let $r_{i,j}$ be a non-negative integer for $i=1,2,\ldots,t$ and $j=0,1,\ldots,n$. There is an almost-regular edge colouring of some almost-regular spanning subhypergraph of $\K^{(\lambda_0,\lambda_1,\ldots,\lambda_n)}_N$ with $t$ colours $c_1,c_2,\ldots,c_t$ such that the edges in colour class $c_i$ are of type $(r_{i,0},r_{i,1},\ldots,r_{i,n})$ for $i=1,2,\ldots,t$ if and only if $\sum_{i=1}^t r_{i,j}\leq\lambda_j\binom nj$ for $j=0,1,\ldots,n$. \end{corollary} \proof The condition that $\sum_{i=1}^t r_{i,j}\leq\lambda_j\binom nj$ for $j=0,1,\ldots,n$ is clearly necessary for the existence of the required colouring of $\K^{(\lambda_0,\lambda_1,\ldots,\lambda_n)}_N$. It says that across all the colour classes, the required number of edges with exactly $j$ endpoints does not exceed the number of edges in $\K^{(\lambda_0,\lambda_1,\ldots,\lambda_n)}_N$ with exactly $j$ endpoints. Now conversely suppose $\sum_{i=1}^t r_{i,j}\le\lambda_j\binom nj$ holds for $j=0,1,\ldots,n$. Let $r_{t+1,j}=\lambda_j\binom nj-\sum_{i=1}^t r_{i,j}$ for $j=0,1,\ldots,n$, and arbitrarily colour the edges of $\K^{(\lambda_0,\lambda_1,\ldots,\lambda_n)}_N$ so that the edges in colour class $c_i$ are of type $(r_{i,0},r_{i,1},\ldots,r_{i,n})$ for $i=1,2,\ldots,t+1$. The result now follows by applying Theorem \ref{maintheorem} with $S=N$, and then removing the edges in colour class $c_{t+1}$. \qed \vspace{0.3cm} Theorem \ref{maintheorem} can be used to prove results on hypergraphs in which the vertex set $V$ is partitioned into parts $V_1,V_2,\ldots,V_n$ and for $i=1,2,\ldots,n$ any permutation of $V_i$ is an automorphism. Existing results on almost-regular edge colourings of such graphs appear in \cite{Bah1,Bah2,Bar3,Bar4,HagHel}. One family of such graphs is complete $k$-uniform $n$-partite hypergraphs. The complete $k$-uniform $n$-partite hypergraph $\K^k_{M_1,\ldots,M_n}$ has vertex set $V=M_1\cup M_2\cup\cdots\cup M_n$, where $M_i\cap M_j=\emptyset$ for $i\neq j$, and has an edge $\{x_1,x_2,\ldots,x_k\}$ for each $k$-subset of $V$ where $x_1,x_2,\ldots,x_k$ are from $k$ distinct parts. We use Theorem \ref{maintheorem} to prove the following result. \begin{corollary}\label{partitecorollary} Let $m$, $n$, $k$, $t$ and $r_1,r_2,\ldots,r_t$ be positive integers with $k\leq n$, and let $M_1,M_2,\ldots,M_n$ be pairwise disjoint sets with $|M_1|=|M_2|=\cdots=|M_n|=m$. There is an almost-regular edge colouring of $\K_{M_1,M_2,\ldots,M_n}^k$ with $t$ colours $c_1,c_2,\ldots,c_t$ such that the number of edges in colour class $c_i$ is $r_i$ for $i=1,2,\ldots,t$ if and only if $\sum_{i=1}^t r_i=m^k\binom nk$. \end{corollary} \proof If the edge colouring exists, then the condition $\sum_{i=1}^t r_i=m^k\binom nk$ clearly holds because $m^k\binom nk$ is the number of edges in $\K_{M_1,M_2,\ldots,M_n}^k$. Now conversely suppose $\sum_{i=1}^t r_i=m^k\binom nk$ holds, let $N=\{1,2,\ldots,n\}$, and consider the hypergraph $\H=\K_N^{\l_0,\ldots,\l_n}$ where $\l_k=m^k$ and $\l_j=0$ for $j\neq k$. That is, the hypergraph with vertex set $N$ and with $m^k$ edges having endpoints $\{x_1,x_2,\ldots,x_k\}$ for each $k$-subset $\{x_1,x_2,\ldots,x_k\}$ of $N$. Note that the number of edges in $\H$ is $m^k\binom nk$; the same as the number of edges in $\K_{M_1,M_2,\ldots,M_n}^k$. Arbitrarily assign the colours $c_1,c_2,\ldots,c_t$ to the edges of $\H$ so that the number of edges in colour class $c_i$ is $r_i$ for $i=1,2,\ldots,t$, and apply Theorem \ref{maintheorem} with $S=N$ to obtain an almost-regular edge colouring $\gamma$ of $\H$. Now arbitrarily assign colours to the edges of $\K_{M_1,M_2,\ldots,M_n}^k$ so that for $i=1,2,\ldots,t$ and for each $k$-subset $\{x_1,x_2,\ldots,x_k\}$ of $N$, the number of edges of colour $c_i$ having an endpoint in each of the parts $M_{x_1},M_{x_2},\ldots,M_{x_k}$ is equal to the number of edges of $\H$ that have endpoints $x_1,x_2,\ldots,x_k$ and are assigned colour $c_i$ by the edge colouring $\gamma$. This is possible because the number of edges having vertices in parts $M_{x_1},M_{x_2},\ldots,M_{x_k}$ is $m^k$; the same as the number of edges in $\H$ having endpoints $x_1,x_2,\ldots,x_k$. If we now apply Theorem \ref{maintheorem} taking $S$ to be $M_1$, and then taking $S$ to be $M_2$, and so on, then the result is the required almost-regular edge colouring of $\K_{M_1,M_2,\ldots,M_n}^k$. \qed \vspace{0.3cm} An {\em $s$-factor} of a hypergraph $\H$ is a spanning $s$-regular subhypergraph, and an {\em $s$-factorisation} is a set of $s$-factors that partitions the edges of $\H$. We shall think of the $s$-factors in an $s$-factorisation as colour classes in an edge colouring. Thus, an $s$-factorisation is an edge colouring where each colour class is an $s$-factor. Let $M\subseteq N$. An $s$-factorisation $\gamma'$ of $\K_N^k$ is an {\em extension} of an $r$-factorisation $\gamma$ of $\K_M^k$ if $\gamma'(E)=\gamma(E)$ for each $E\in \E(\K_M^k)$. If there exists an $s$-factorisation of $\K_N^k$ which is an extension of an $r$-factorisation of $\K_M^k$, then we say that the $r$-factorisation of $\K_M^k$ is {\em extendable} to an $s$-factorisation of $\K_N^k$. We now consider necessary conditions for the extension of an $r$-factorisation of $\K_M^k$ to an $s$-factorisation of $\K_N^k$. Results on extensions of factorisations can be found in \cite{BahNew,BahRod,BarBro,HagHel}, and Corollary \ref{extendfactorisation} below is similar to Corollary 10 in \cite{BahNew}. Let $m=|M|$, let $n=|N|$, let $t=\binom{m-1}{k-1}/r$ and let $u=\binom{n-1}{k-1}/s$ so that $t$ is the number of colours in an $r$-factorisation of $\K_M^k$ and $u$ is the number of colours in an $s$-factorisation of $\K_N^k$. If $\gamma$ is an $r$-factorisation of $\K_M^k$, then the number of edges in each colour class is $\frac{rm}k$. We say that $(k,r,m,s,n)$ is {\em admissible} if $s$ divides $\binom{n-1}{k-1}$ and there exist non-negative integers $x_{i,j}$, $i\in\{1,2,\ldots,u\}$, $j\in\{1,2,\ldots,k\}$, such that \begin{itemize} \item [(1)] $\displaystyle\sum_{i=1}^u x_{i,j}=\textstyle\binom{m}{k-j}\binom{n-m}{j}$ for $j\in\{1,2,\ldots,k\}$; \item [(2)] $\displaystyle\sum_{j=1}^{k}jx_{i,j}=s(n-m)$ for $i\in\{1,2,\ldots,u\}$; \item [(3)] $\displaystyle\sum_{j=1}^{k}(k-j)x_{i,j}=(s-r)m$ for $i\in\{1,2,\ldots,t\}$; and \item [(4)] $\displaystyle\sum_{j=1}^{k}(k-j)x_{i,j}=sm$ for $i\in\{t+1,t+2,\ldots,u\}$. \end{itemize} It is easy to see that if an $r$-factorisation of $\K_M^k$ is {\em extendable} to an $s$-factorisation of $\K_N^k$, then $(k,r,m,s,n)$ is admissible. It is clear that $s$ must divide $\binom{n-1}{k-1}$ because $\binom{n-1}{k-1}$ is the degree of $\K_N^k$. Moreover, if we let $x_{i,j}$ be the number of edges of colour $c_i$ that have exactly $j$ endpoints in $N\setminus M$ for $i=1,2,\ldots,u$ and $j=1,2,\ldots,k$, where $c_1,c_2,\ldots,c_t$ are the colours in the $r$-factorisation of $\K_M^k$, and $c_1,c_2,\ldots,c_u$ are the colours in the $s$-factorisation of $\K_N^k$, then simple counting guarantees that Conditions (1)-(4) hold. Condition (1) is obtained by counting the number of edges of $\K_N^k$ that have exactly $j$ endpoints in $N\setminus M$, Condition (2) is obtained by counting the number of endpoints in $N\setminus M$ of edges of colour $c_i$, and Conditions (3) and (4), respectively, are obtained by counting the number of endpoints in $M$ of the edges of colour $c_i$ in $\E(\K_N^k)\setminus\E(\K_M^k)$, when $i=1,2,\ldots,t$ and when $i=t+1,t+2,\ldots,u$, respectively. \begin{corollary}\label{extendfactorisation} Let $M$ and $N$ be sets with $M\subseteq N$, let $m=|M|$ and let $n=|N|$. An $r$-factorisation of $\K_M^k$ is extendable to an $s$-factorisation of $\K_N^k$ if and only if $(k,r,m,s,n)$ is admissible. \end{corollary} \proof The discussion preceding the statement of the corollary shows that $(k,r,m,s,n)$ being admissible is necessary for the existence of the extension. Now conversely suppose that $(k,r,m,s,n)$ is admissible, let $\gamma$ be any $r$-factorisation of $\K_M^k$, let $t=\binom{m-1}{k-1}/r$ and $u=\binom{n-1}{k-1}/s$, let the colours assigned by $\gamma$ be $c_1,c_2,\ldots,c_t$, and define $x_{i,j}$ for $i\in\{1,2,\ldots,u\}$ and $j\in\{1,2,\ldots,k\}$ so that the $x_{i,j}$ satisfy Conditions (1)-(4) in the definition of admissible. Let $\H$ be the hypergraph with $V(\H)=N$ and $\E(\H)=\E(\K_N^k)\setminus \E(\K_M^k)$, and define an edge colouring $\gamma_0$ of $\H$ by arbitrarily assigning colours $c_1,\ldots,c_u$ so that the number of edges of colour $c_i$ that have exactly $j$ endpoints in $N\setminus M$ is $x_{i,j}$ for $i\in\{1,2,\ldots,u\}$ and $j\in\{1,2,\ldots,k\}$. Apply Theorem \ref{maintheorem} to $\H$ with edge colouring $\gamma_0$; first with $S=M$, and then with $S=N\setminus M$. The union of the resulting edge colouring of $\H$ and $\gamma$ is the required $s$-factorisation of $\K_N^k$. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\subsection*{Acknowledgements} %Thanks to Professor Querty for suggesting the proof of %Lemma~\ref{lem:Technical}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{99} \bibitem{AndRod} L. D. Andersen and C. A. Rodger, Decompositions of complete graphs: embedding partial edge-colourings and the method of amalgamations, Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 307:\ 7--41, 2003. \bibitem{Bah1} M. A. Bahmanian, Detachments of Hypergraphs I: The Berge-Johnson Problem, {\it Combin. Probab. Comput.}, 21:\ 483--495, 2012. \bibitem{Bah2} M. A. Bahmanian, Detachments of amalgamated 3-uniform hypergraphs: factorization consequences, {\it J. Combin. Des.}, 20:\ 527--549, 2012. \bibitem{BahNew} A. Bahmanian and M. Newman, Embedding Factorizations for $3$-Uniform Hypergraphs II: $r$-factorizations into $s$-factorizations, {\it Electron. J. Combin.}, 23(2):\ Paper \#P.42 14 pp., 2016. \bibitem{BahRod} A. Bahmanian and C. Rodger, Embedding factorizations for 3-uniform hypergraphs, {\it J. Graph Theory}, 73:\ 216--224, 2013. \bibitem{Bar1} Zs. Baranyai, On the factorization of the complete uniform hypergraph. {\it Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\H{o}s on his 60th birthday), Vol. I}, pp. 91--108. Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam, 1975. \bibitem{Bar2} Z. Baranyai, Some applications on equalized matrices, {\it Math. Programming Stud.}, 8:\ 217--225, 1978. \bibitem{Bar3} Z. Baranyai, The edge-coloring of complete hypergraphs. I, {\it J. Combin. Theory Ser. B}, 26:\ 276--294, 1979. \bibitem{Bar4} Z. Baranyai, La coloration des ar\^etes des hypergraphes complets. II. La coloration \'equitable de $K^h_{n_1\cdots n_h}$ {\it Probl\`emes combinatoires et th\'eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)}, pp. 19--21, Colloq. Internat. CNRS, 260, CNRS, Paris, 1978. \bibitem{BarBro} Z. Baranyai and A. E. Brouwer, Extension of colorings of the edges of a complete (uniform hyper)graph, Math. Centre Report ZW91 (Mathematisch Centrum Amsterdam). Zbl. 362.05059, 1977. \bibitem{BroSch} A. E. Brouwer and A. Schrijver, Uniform hypergraphs. In A. Schrijver, editor, {\it Packing and Covering in Combinatorics}, pages 39--73. Mathematical Centre Tracts 106, Math. Centr., Amsterdam, 1979. \bibitem{BryMae} D. Bryant and B. Maenhaut, Almost regular edge colourings and regular decompositions of complete graphs, {\it J. Combin. Des.}, 16:\ 499--506, 2008. \bibitem{ColFanHor} C. J. Colbourn, B. Fan and D. Horsley, Disjoint Spread Systems and Fault Location, {\it SIAM J. Discrete Math.}, to appear. \bibitem{HagHel} R. H\"aggkvist and T. Hellgren, Extensions of edge-colourings in hypergraphs. I. {\it Combinatorics, Paul Erd\H{o}s is eighty}, Vol. 1, 215--238, Bolyai Soc. Math. Stud., {\it J\'anos Bolyai Math. Soc., Budapest}, 1993. \bibitem{Nas} C. St. J. A. Nash-Williams, Amalgamations of almost regular edge-colourings of simple graphs, {\it J. Combin. Theory Ser. B}, 43:\ 322--342, 1987. \end{thebibliography} \end{document}