% 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 % 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}}} % 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} \newcommand{\divides}{\bigm|} \usepackage{enumerate}%,enumitem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Embedding factorizations for 3-uniform hypergraphs II: $r$-factorizations into $s$-factorizations} % 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{Amin Bahmanian\\%\thanks{Supported by NASA grant ABC123.}\\ \small Department of Mathematics\\[-0.8ex] \small Illinois State University\\[-0.8ex] \small Normal, Illinois, U.S.A.\\ \small 61790-4520\\ \and Mike Newman \thanks{Research supported by NSERC}\\ \small Department of Mathematics and Statistics\\[-0.8ex] \small University of Ottawa\\[-0.8ex] \small Ottawa, Ontario, Canada\\ \small\tt mnewman@uottawa.ca } % \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{\today} \date{\dateline{November 17, 2015}{May 17, 2016}\\ \small Mathematics Subject Classifications: 05C70, 05C65, 05C15, 05B40, 05B05} \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} Motivated by a 40-year-old problem due to Peter Cameron on extending partial parallelisms, we provide necessary and sufficient conditions under which one can extend an $r$-factorization of a complete $3$-uniform hypergraph on $m$ vertices, $K_m^3$, to an $s$-factorization of $K_n^3$. This generalizes an existing result of Baranyai and Brouwer--where they proved it for the case $r=s=1$. \bigskip\noindent \textbf{Keywords:} factorizations; embedding; detachments; amalgamations; edge-colorings; hypergraphs \end{abstract} \section{Introduction} Let $V$ be a given finite set of cardinality $n$; the elements of $V$ will be called points. We denote the set of all $h$-subsets of $V$ by $\binom{V}{h}$. A {\it parallelism} of $\binom{V}{h}$ is a partition of $\binom{V}{h}$ whose classes are themselves partitions of $V$; the classes are called {\it parallel classes}. Note that a parallelism satisfies the usual Euclidean axiom for parallels: for every point $v \in V$ and for each $h$-subset $U$ of $V$, there is exactly one $h$-subset $U'$ which is parallel to $U$ (that is, contained in the same parallel class as $U$) and contains $V$. Obviously, a parallelism can exist only if $h$ is a divisor of $n$. It was conjectured by Sylvester that this condition is sufficient as well, and Baranyai proved this conjecture \cite{MR0416986}. The direction of research in similar subjects such as Steiner triple systems and Latin squares for which general existence theorems have been proved suggests the following problem. \begin{question} \textup{(Cameron \cite[Question 1.2]{MR0419245})} \label{cameronbookprob} Under what conditions can partial parallelisms be extended to parallelisms? \end{question} There are different possible interpretations based on the precise notion of ``partial'' and ``extend''. To formulate this problem precisely, let us first introduce some basic terminology. Let $K_n^h$ denote the {\it complete $h$-uniform} hypergraph on $n$ vertices which is a hypergraph on $n$ vertices whose edges are all $h$-subset of the vertex set. An {\it $r$-factorization} of a hypergraph is a partition (coloring) of the edges into $r$-regular spanning sub-hypergraphs. The following %more general and more precise formulation of Problem \ref{cameronbookprob} was investigated by the first author and Rodger in \cite{MR3056885}: \begin{question} \label{arbitToRfac} %\textup{(Bahmanian, Rodger \cite[Question xxx]{MR3056885})} Under what conditions can arbitrary edge-colorings of $K_m^h$ be extended to $r$-factorizations of $K_n^h$? \end{question} In this direction, it has been proven that \begin{theorem}\textup{(Bahmanian, Rodger \cite[Theorem 3.1]{MR3056885})}\label{facembedgen1} Suppose that $n\geq (2+\sqrt{2})m$. Then a $q$-edge-coloring of $\mathcal F=K_m^3$ can be extended to an $r$-factorization of $K_{n}^3$ if and only if \begin{itemize} \item [\textup {(i)}] $3\divides rn,$ \item [\textup {(ii)}] $r \divides \binom{n-1}{2},$ \item [\textup {(iii)}] $q\leq\binom{n-1}{2}/r,$ and \item [\textup {(iv)}] $d_{\mathcal F(j)}(v)\leq r$ for each $v\in V(\mathcal F)$ and $1\leq j \leq q.$ \end{itemize} \end{theorem} Here $d_{\mathcal F(j)}(v)$ is the degree of vertex $v$ in the sub-hypergraph of $\mathcal F$ induced by color $j$. In this paper, we investigate the following formulation of Cameron's problem which is a special case of Problem \ref{arbitToRfac}: We are given $K_n^h$ which has $K_m^h$ as a sub-hypergraph, and the edges of $K_m^h$ have been colored so that the degree of each vertex within each color class is $r$ (so that we have an $r$-factorization of $K_m^h$). Can we color the remaining edges of $K_n^h$ so as to achieve an $s$-factorization of $K_n^h$? \begin{question} \label{r-fac2s-fac} %\textup{(Bahmanian, Rodger \cite[Question xxx]{MR3056885})} Under what conditions can an $r$-factorization of $K_m^h$ be extended to an $s$-factorization of $K_n^h$? \end{question} Baranyai and Brouwer \cite{BaranBrouwer77} conjectured that a 1-factorization of $K_m^h$ can be extended to a 1-factorization of $K_n^h$ if and only if $h$ divides $m,n$, and $n\geq 2m$. They proved this for $h=2,3$, and for arbitrary $h$ when $n$ is sufficiently large. This conjecture of Baranyai and Brouwer was beautifully settled by H{\"a}ggkvist and Hellgren \cite{MR1249714}. \begin{theorem}\textup{(H{\"a}ggkvist, Hellgren \cite[Theorem 2]{MR1249714})}\label{HaggHell} Let $n=qt$ and $m=pt$, where $p\leq q/2$. Suppose that we are given a coloring of a subgraph $K_m^t$, using $\binom{m-1}{t-1}$ colors. Then this coloring can be extended to a coloring of $K_n^t$ using $\binom{n-1}{t-1}$ colors. \end{theorem} In an attempt to generalize this result and extend Theorem \ref{facembedgen1} for larger values of $h$, in an earlier paper we showed that %\cite{BahNewm1} \begin{theorem}\textup{(Bahmanian, Newman \cite[Theorem 1.7]{BahNewm1})}\label{thm:main-r} If $\gcd(m,n,h) = \gcd(n,h)$, then an $r$-factorization of $K_m^h$ can be extended to an $r$-factorization of $K_n^h$ if and only if \item [\textup {(G1)}] $h\divides rm$, $h\divides rn;$ \item [\textup {(G2)}] $r\divides\binom{m-1}{h-1}$, $r\divides\binom{n-1}{h-1};$ \item [\textup {(G3)}] $n\geq 2m$. \end{theorem} In this paper, we completely solve Problem \ref{r-fac2s-fac} for $h=3$, which can be seen as an improvement of Theorem \ref{facembedgen1} for the case when the arbitrary edge-coloring of $K_m^h$ is replaced by a regular edge-coloring (see Theorem \ref{embedfac1}). Studying embedding factorization of graphs dates back to over 40 years ago, see for example the classical paper by Cruse \cite{MR0329925}, and its extensions by Andersen and Hilton \cite{MR584118}. For results concerning embedding connected factorization of graphs we refer the reader to \cite{MR1983358, MR2325799, MR1315436}. This paper is organized as follows. In Section \ref{neccsec}, we discuss the necessary conditions. In Section \ref{detachsec}, we give the prerequisites, and in Section \ref{emb3graphsec}, we prove our main result. \section{General Necessary Conditions} \label{neccsec} Throughout this paper we assume that $m,n,r,s,h\in \mathbb N$. Moreover, in order to avoid trivial cases we assume that \begin{equation}\label{basicassump} h\geq 2, \mbox{ and } n> m>h. \end{equation} \begin{lemma} \label{embedfac1nec} If an $r$-factorization of $K_m^h$ can be embedded into an $s$-factorization of $K_{n}^h$, then \begin{itemize} \item [\textup {(N1)}] $h\divides rm$, $h\divides sn;$ \item [\textup {(N2)}] $r\divides\binom{m-1}{h-1}$, $s\divides\binom{n-1}{h-1};$ \item [\textup {(N3)}] $1\leq s/r\leq \binom{n-1}{h-1}/\binom{m-1}{h-1};$ \item [\textup {(N4)}] $n\geq \frac{h}{h-1}m $ if $1q$. Let $e_j$ be the number of edges of color $j$ in $K_m^h$ for $1\leq j\leq k$. In an $s$-factorization of $K_n^h$, each of the $n-m$ new vertices is adjacent with exactly $s$ edges of each color class, therefore all the $n-m$ new vertices are adjacent with at most $s(n-m)$ edges of each color class. Since in an $s$-factorization of $K_n^h$ the number of hyperedges of each color class is $sn/h$, for $1\leq j\leq k$ we have $$s(n-m)+e_j\geq sn/h.$$ If $1r$ and $k>q$), then since $e_j=0$ for $q+1\leq j\leq k$, we have $s(n-m)\geq sn/h$ which proves (N4). If $s/r=1$ (or $s=r$), fix a color $j\in\{1,\dots,q\}$. Since $r=s$, there is no edge colored $j$ between $V(K_m^h)$ and the new vertices. Therefore, in order to to form an $s$-factor in $K_n^h$, there must be $r(n-m)/h$ edges colored $j$ in $K_{n-m}^h$ (the subgraph induced by the new vertices). But the total number of edges in $K_{n-m}^h$ is $\binom{n-m}{h}$. Therefore $$\binom{n-m}{h}\geq \frac{\binom{m-1}{h-1}}{r}\frac{r(n-m)}{h}.$$ Thus $\frac{h}{n-m}\binom{n-m}{h}\geq \binom{m-1}{h-1}$ which implies $\binom{n-m-1}{h-1}\geq \binom{m-1}{h-1}$, and so $n-m-1\geq m-1$, and so $n\geq 2m$. This proves (N5) and the proof is complete. \end{proof} \begin{remark}\textup{ Note that if $1= s/r= \binom{n-1}{h-1}/\binom{m-1}{h-1}$, then $n=m$ which is a trivial case. }\end{remark} \section{Fair Detachments of Hypergraphs} \label{detachsec} If $x,y\in \mathbb R$, by $x \approx y$ we mean that $\lfloor y \rfloor \leq x \leq \lceil y \rceil$. For the purpose of this paper, a {\it hypergraph} $\mathcal G$ is a pair $(V(\mathcal G),E(\mathcal G))$ where $V(\mathcal G)$ is a finite set called the {\it vertex} set, $E(\mathcal G)$ is the {\it edge} multiset, where every edge is itself a multi-subset of $V(\mathcal G)$. This means that not only can an edge occur multiple times in $E(\mathcal G)$, but also each vertex can have multiple occurrences within an edge. By an edge of the form $\{u_1^{m_1},u_2^{m_2},\dots,u_r^{m_r}\}$, we mean an edge in which vertex $u_i$ occurs $m_i$ times for $1\leq i\leq r$. The total number of occurrences of a vertex $v$ among all edges of $E(\mathcal G)$ is called the {\it degree}, $d_{\mathcal G}(v)$ of $v$ in $\mathcal G$. The {\it multiplicity} of an edge $e$ in $\mathcal G$, written $m_{\mathcal G} (e)$, is the number of repetitions of $e$ in $E(\mathcal G)$ (note that $E(\mathcal G)$ is a multiset, so an edge may appear multiple times). If $\{u_1^{m_1},u_2^{m_2},\dots,u_r^{m_r}\}$ is an edge in $\mathcal G$, then we abbreviate $m_{\mathcal G}(\{u_1^{m_1},u_2^{m_2},\dots,u_r^{m_r}\})$ to $m_{\mathcal G}(u_1^{m_1},u_2^{m_2},\dots,u_r^{m_r})$. If $U_1,\dots,U_r$ are multi-subsets of $V(\mathcal G)$, then $m_{\mathcal G}(U_1,\dots,U_r)$ means $m_{\mathcal G}(\bigcup_{i=1}^r U_i)$, where the union of $U_i$s is the usual union of multisets. Whenever it is not ambiguous, we drop the subscripts; for example we write $d(v)$ and $m(e)$ instead of $d_{\mathcal G}(v)$ and $m_{\mathcal G} (e)$, respectively. For a positive integer $h$, $\mathcal G$ is said to be $h$-{\it uniform} if $|e|=h$ for each $e\in E$. For a positive integer $r$, an $r$-factor in a hypergraph $\mathcal G$ is a spanning $r$-regular sub-hypergraph, and an {\it $r$-factorization} is a partition of the edge set of $\mathcal G$ into $r$-factors. The hypergraph $K_n^h:=(V,\binom{V}{h})$ with $|V|=n$ (by $\binom{V}{h}$ we mean the collection of all $h$-subsets of $V$) is called a {\it complete} $h$-uniform hypergraph. A {\it $k$-edge-coloring} of $\mathcal G$ is a mapping $f:V(\mathcal G)\rightarrow C$ (often the set of colors $C$ is $\{1,\dots,k\}$) and color class $j$ of $\mathcal G$, written $\mathcal G(j)$, is the sub-hypergraph of $\mathcal G$ induced by the edges of color $j$. Let $\mathcal G$ be a hypergraph, let $U$ be some finite set, and let $\Psi : V(\mathcal G) \to U$ be a surjective mapping. The map $\Psi$ extends naturally to $E(\mathcal G)$. For $A \in E(\mathcal G)$ we define $\Psi(A) = \{\Psi(x) : x \in A\}$. Note that $\Psi$ need not be injective, and $A$ may be a multiset. Then we define the hypergraph $\mathcal F$ by taking $V(\mathcal F)=U$ and $E(\mathcal F)=\{ \Psi(A) : A \in E(\mathcal G) \}$. We say that $\mathcal F$ is an {\it amalgamation} of $\mathcal G$, and that $\mathcal G$ is a {\it detachment} of $\mathcal F$. Associated with $\Psi$ is a function $g$ defined by $g(u)=|\Psi^{-1}(u)|$; to be more specific we will say that $\mathcal G$ is a $g$-detachment of $\mathcal F$. Then $\mathcal G$ has $\sum_{u\in V(\mathcal F)} g(u)$ vertices. Note that $\Psi$ induces a bijection between the edges of $\mathcal F$ and the edges of $\mathcal G$, and that this bijection preserves the size of an edge. We adopt the convention that it preserves the color also, so that if we amalgamate or detach an edge-colored hypergraph the amalgamation or detachment preserves the same coloring on the edges. We make explicit a straightforward observation: Given $\mathcal G$, $V(\mathcal F)$ and $\Psi$ the amalgamation is uniquely determined, but given $\mathcal F$, $V(\mathcal G)$ and $\Psi$ the detachment is in general far from uniquely determined. We need the following special case of a general result in \cite{MR2942724}. \begin{theorem}\textup{(Bahmanian \cite[Theorem 4.1]{MR2942724})}\label{mainthhypgen1} Let $\mathcal F$ be a $k$-edge-colored hypergraph and let $g:V(\mathcal F)\rightarrow {\mathbb N}$. Then there exists a $g$-detachment $\mathcal G$ (possibly with multiple edges) of $\mathcal F$ whose edges are all sets, with amalgamation function $\Psi:V(\mathcal G)\rightarrow V(\mathcal F)$, $g$ being the number function associated with $\Psi$, such that: \begin{enumerate} \item [\textup{(F1)}] $d_{\mathcal G(j)}(v) \approx d_{\mathcal F(j)}(u)/g(u)$ for each $u\in V(\mathcal F)$, each $v\in \Psi^{-1}(u)$ and $1\leq j\leq k;$ \item [\textup{(F2)}] $m_\mathcal G(U_1,\dots,U_r) \approx m_\mathcal F(u_1^{m_1},\dots,u_r^{m_r})/\Pi_{i=1}^r\binom {g(u_i)}{m_i} $ for distinct $u_1,\dots,u_r\in V(\mathcal F)$ and $U_i\subset \Psi^{-1}(u_i)$ with $|U_i|=m_i\leq g(u_i)$ for $1\leq i\leq r$. \end{enumerate} \end{theorem} An immediate consequence of Theorem \ref{mainthhypgen1} is the following that will be most useful throughout this paper. \begin{corollary} \label{maindetachcor} Let $\mathcal F$ be a hypergraph with vertex set $\{u,v\}$ such that $m(u^{i},v^{h-i})=\binom{m}{i}\binom{n-m}{h-i}$ for $0\leq i\leq h-1$. Then an $r$-factorization of $K_m^h$ can be embedded into an $s$-factorization of $K_n^h$ if and only if we can color the edges of $\mathcal F$ with $k$ colors so that \begin{equation} \label{maindetachcoreq} d_j(u) = \left \{ \begin{array}{ll} m(s-r) & \mbox { for } 1\leq j\leq q, \\ sm & \mbox { for } q+1\leq j\leq k, \mbox { if } k>q, \end{array} \right.\\ \end{equation} \begin{equation} \label{maindetachcoreq2} d_j(v)=s(n-m) \mbox{\quad for } 1\leq j\leq k. \end{equation} where $q=\binom{m-1}{h-1}/r, k=\binom{n-1}{h-1}/s$, and $q,k\in \mathbb N$. \end{corollary} \begin{proof} First, suppose that an $r$-factorization of $K_m^h$ can be embedded into an $s$-factorization of $K_n^h$. By Lemma \ref{embedfac1nec}, $q,k$ both are integers. By removing the edges of $K_m^h$ from $K_n^h$, amalgamating those $m$ vertices in $K_n^h$ that belong to $K_m^h$ into a single vertex $u$, and the remaining $n-m$ vertices of $K_n^h$ into a vertex $v$, we obtain the hypergraph $\mathcal F$. The $k$-edge-coloring of $K_n^h$ (in which each color class is an $s$-factor) induces a $k$-edge-coloring in $\mathcal F$ that satisfies (\ref{maindetachcoreq}) and (\ref{maindetachcoreq2}). Conversely, suppose that an $r$-factorization of $K_m^h$ is given, and the edges of $\mathcal F$ are colored with $k$ colors so that (\ref{maindetachcoreq}) and (\ref{maindetachcoreq2}) are satisfied. We show that we can embed the given $r$-factorization of $K_m^h$ into as $s$-factorization of $K_n^h$. Let $g:V(\mathcal F)\rightarrow {\mathbb N}$ with $g(u)=m$, $g(v)=n-m$. By Theorem \ref{mainthhypgen1}, there exists a $g$-detachment $\mathcal G$ of $\mathcal F$ such that: \begin{enumerate} [(a)] \item By (F1), for each $w\in \Psi^{-1}(u)$ \begin{equation*} d_{\mathcal G(j)}(w) \approx d_{j}(u)/g(u)= \left \{ \begin{array}{ll} m(s-r)/m=s-r & \mbox { for } 1\leq j\leq q, \\ sm/m=s & \mbox { for } q+1\leq j\leq k, \mbox { if } k>q, \end{array} \right.\\ \end{equation*} and for each $w\in \Psi^{-1}(v)$, \begin{equation*} d_{\mathcal G(j)}(w) \approx d_{j}(v)/g(v)=s(n-m)/(n-m)=s \mbox { for } 1\leq j\leq k. \end{equation*} \item By (F2), $m_\mathcal G(U,V) \approx \frac{m(u^{i},v^{h-i})} { {\binom {g(u)}{i}}{\binom {g(v)}{h-i}}}=\frac{\binom{m}{i}\binom{n-m}{h-i}}{\binom{m}{i}\binom{n-m}{h-i}}=1$ for $U\subset \Psi^{-1}(u),V\subset \Psi^{-1}(v)$ with $|U|=i, |V|=h-i$, for $0\leq i\leq h-1$. \end{enumerate} Let us assume that $V(K_m^h)=\Psi^{-1}(u)$, and think of the given $r$-factorization of $K_m^h$ as a $q$-edge-coloring of $K_m^h$ so that each color class induces an $r$-factor. Let $\mathcal H$ be a hypergraph whose vertex set is $V(\mathcal G)$, whose edges are $E(K_m^h)\cup E(\mathcal G)$, and its edges are colored according to the colors of edges of $K_m^h$ and $\mathcal G$. Obviously, $\mathcal H$ contains an $r$-factorization of $K_m^h$. Moreover, the definition of $\mathcal H$ together with $(a)$ and (b) respectively implies that $d_{\mathcal H(j)}(x)=s$ for $1\leq j\leq k$, and $\mathcal H\cong K_n^h$. This completes the proof. \end{proof} \section{The Main Result} \label{emb3graphsec} In order to prove our main result, let us first review the obvious necessary conditions. \begin{lemma} \label{embedfaclemma1} If an $r$-factorization of $K_m^3$ can be embedded into an $s$-factorization of $K_{n}^3$, then \begin{itemize} \item [\textup {(C1)}] $3\divides rm$, $3\divides sn;$ \item [\textup {(C2)}] $r\divides\binom{m-1}{2}$, $s\divides\binom{n-1}{2};$ \item [\textup {(C3)}] $1\leq s/r\leq \binom{n-1}{2}/\binom{m-1}{2};$ \item [\textup {(C4)}] $n\geq 3m/2 $ if $1q$, there are four cases to consider. \begin{enumerate}[(a)] \item $\alpha=\beta=0$: In this case $m$ is even or $r,s$ are even, and so (\ref{maineq2rf1}) is equivalent to $m\binom{n-m}{2}\geq 0$ which is trivial. \item $\alpha=0,\beta=1/2$: In this case $m,s,r$ are odd, and so (\ref{maineq2rf1}) is equivalent to $m\binom{n-m}{2}\geq k-q$, and we have \small{ \begin{eqnarray} m\binom{n-m}{2}&\geq& \frac{\binom{n-1}{2}}{s}-\frac{\binom{m-1}{2}}{r} \iff \nonumber \\ rsm\binom{n-m}{2} &\geq& r \binom{n-1}{2}-s\binom{m-1}{2} \nonumber \\ &=&r[ \binom{m-1}{2} +\binom{n-m}{2} +(n-m)(m-1) ] -s\binom{m-1}{2} \iff \nonumber \\ \quad\quad\quad r(n-m)(m-1)&\leq & r\binom{n-m}{2}( sm-1 ) +(s-r)\binom{m-1}{2} \label{lastmsrodd}. \end{eqnarray}} By (\ref{basicassump}) $m\geq 4$, but $m$ is odd, and so $m\geq 5$, which implies that $n-m\geq 3$. Therefore $\binom{n-m}{2} \geq n-m$, which proves (\ref{lastmsrodd}). \item $\alpha=\beta=1/2$: In this case $m,s$ are odd and $r$ is even, and so (\ref{maineq2rf1}) is equivalent to $m\binom{n-m}{2}\geq k$, and we have \begin{eqnarray*} sm\binom{n-m}{2}\geq \binom{n-1}{2}=\binom{m-1}{2}+\binom{n-m}{2}+(n-m)(m-1) &\iff& \\ (sm-1)\binom{n-m}{2} \geq \binom{m-1}{2}+(n-m)(m-1)&\iff& \\ (sm-1)(n-m)(n-m-1) \geq (m-1)(m-2)+2(n-m)(m-1)&=&\\ =(m-1)(2n-m-2). \end{eqnarray*} Since $m$ is odd, by (\ref{basicassump}) $m\geq 5$, and we have $m^2-4m+1\geq 0$ or $(m+1)(m-3)\geq 2(m-2)$. But $m$ is odd and so by (C4) $n-m\geq \frac{m+1}{2}$ which implies $2(n-m)(n-m-2)\geq \frac{m+1}{2}(\frac{m+1}{2}-2) \geq m-2$ and so $2(n-m)^2-4(n-m)\geq m-2$. Thus, $$2(n-m)(n-m-1)=2(n-m)^2-2(n-m)\geq 2n-m-2.$$ Since $r$ is even, and $s$ is odd, we have $s>r\geq 2$. Therefore $$(sm-1)(n-m)(n-m-1)> 2(m-1)(n-m)(n-m-1)\geq (m-1)(2n-m-2).$$ \item $\alpha=1/2,\beta=0$: In this case $m,r$ are odd and $s$ is even , and thus (\ref{maineq2rf1}) is equivalent to $m\binom{n-m}{2}\geq q$. So we need to show that $rm\binom{n-m}{2}\geq \binom{m-1}{2}$ or equivalently, $rm(n-m)(n-m-1)\geq (m-1)(m-2)$. Since $m^2-4m+7 \geq 0$, we have $(m+1)(m-1) \geq 4m-8$, so $\frac{m+1}{2}(\frac{m+1}{2}-1) \geq m-2$, and since $r\geq 1$ and for $m$ odd by (C4), $n\geq m+\frac{m+1}{2}$, we have \begin{eqnarray*} rm(n-m)(n-m-1)&>& (m-1)(n-m)(n-m-1)\\ & \geq& (m-1)\frac{m+1}{2}(\frac{m+1}{2}-1)\geq (m-1)(m-2). \end{eqnarray*} \end{enumerate} If $k=q$, there are two cases to consider. \begin{enumerate}[(a)] \item If $m(s-r)$ is even, then (\ref{maineq2rf1}) is equivalent to $m\binom{n-m}{2}\geq 0$ which is trivial. \item If $m(s-r)$ is odd, then (\ref{maineq2rf1}) is equivalent to $m\binom{n-m}{2}\geq q$ which is true by (C6). \end{enumerate} \end{proof} Case $r=s$ of the following result is proved using a different method by the authors in \cite{BahNewm1}. %%%%%%%%%%%% MAIN RESULT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{theorem} \label{embedfac1} An $r$-factorization of $K_m^3$ can be embedded into an $s$-factorization of $K_{n}^3$ if and only if \begin{itemize} \item [\textup {(C1)}] $3\divides rm$, $3\divides sn;$ \item [\textup {(C2)}] $r\divides\binom{m-1}{2}$, $s\divides\binom{n-1}{2};$ \item [\textup {(C3)}] $1\leq s/r\leq \binom{n-1}{2}/\binom{m-1}{2};$ \item [\textup {(C4)}] $n\geq 3m/2 $ if $1r}$}: We color the edges of the form $\{u^2,v\}$ so that \begin{eqnarray} \label{f-edges1} sm-sn/3-2rm/3 & \leq m_j(u^2,v) \leq & m(s-r)/2 \quad\mbox {for } 1\leq j\leq q, \nonumber\\ sm-sn/3 & \leq m_j(u^2,v) \leq & ms/2 \quad\quad \quad \mbox {for } q+1\leq j\leq k, \mbox { if } k>q. \end{eqnarray} In order to show that such a coloring is possible, first note that $ms/2\geq sm-sn/3$ is equivalent to $n\geq 3m/2$, which is true if $k>q$ (by (C4)). Moreover, $m(s-r)/2\geq sm-sn/3-2rm/3$ is equivalent to $n\geq \frac{m}{2}(3-r/s)$ which is true by (\ref{basicassump}), and the following sequence of equivalences. \begin{eqnarray*} n\geq \frac{m}{2}(3-r/s) =\frac{m}{2}[3-\binom{m-1}{2}/\binom{n-1}{2}]&\iff& \\ 2n\geq 3m-\frac{m(m-1)(m-2)}{(n-1)(n-2)}&\iff& \\ 2n(n-1)(n-2)\geq 3m(n-1)(n-2)-m(m-1)(m-2)&\iff&\\ 2(n-m)(n-m-1)(2n+m-4)\geq 0. \end{eqnarray*} Therefore, it is enough to show that \begin{equation*} q(sm-sn/3-2rm/3)+(k-q)(sm-sn/3)\leq m(u^2,v) \leq q\lfloor m(s-r)/2\rfloor+(k-q)\lfloor ms/2\rfloor, \end{equation*} which is true by Lemmas \ref{elem1} and \ref{elem3}. Then, we color the edges of the form $\{u,v^2\}$ so that \begin{equation*} m_j(u,v^2) =\left \{ \begin{array}{ll} m(s-r)-2m_j(u^2,v) & \mbox { for } 1\leq j\leq q, \\ sm-2m_j(u^2,v)& \mbox { for } q+1\leq j\leq k, \mbox { if } k>q. \end{array} \right. \end{equation*} This is possible, because by (\ref{f-edges1}) $m_j(u,v^2)\geq 0$ for $1\leq j\leq k$ , and \begin{eqnarray*} \sum_{j=1}^k m_j(u,v^2) & = & qm(s-r)+sm(k-q)-2\sum_{j=1}^k m_j(u^2,v)\\ &=&ksm-qrm-2(n-m)\binom{m}{2}\\ &=&m\binom{n-1}{2}-m\binom{m-1}{2}-2(n-m)\binom{m}{2}\\ &\mathop= \limits^{\scriptsize{\mbox {lem. }} \ref{elem0}(a)}&m\binom{n-m}{2}=m(u,v^2). \end{eqnarray*} Finally, we color the edges of the form $\{v^3\}$ so that \begin{equation*} m_j(v^3) =\left \{ \begin{array}{ll} sn/3-sm+m_j(u^2,v)+2rm/3 & \mbox { for } 1\leq j\leq q, \\ sn/3-sm+m_j(u^2,v)& \mbox { for } q+1\leq j\leq k, \mbox { if } k>q. \end{array} \right. \end{equation*} This coloring is possible, because by (C1) $m_j(v^3)$ is an integer for $1\leq j\leq k$, by (\ref{f-edges1}) $m_j(v^3)\geq 0$ for $1\leq j\leq k$, and \begin{eqnarray*} \sum_{j=1}^k m_j(v^3) & = & q (sn/3-sm+2rm/3)+(k-q)(sn/3-sm)+\sum_{j=1}^k m_j(u^2,v)\\ &=&(n-m)\binom{m}{2}+skn/3-skm+2qrm/3\\ &=&(n-m)\binom{m}{2}+n\binom{n-1}{2}/3-m\binom{n-1}{2}+2m\binom{m-1}{2}/3\\ &=&(n-m)\binom{m}{2}+\binom{n}{3}-m\binom{n-1}{2}+2\binom{m}{3}\\ &\mathop= \limits^{\scriptsize{\mbox {lem. }} \ref{elem0}(b)}&\binom{n-m}{3}=m(v^3). \end{eqnarray*} Using (\ref{degreeid}), we verify that the described edge-coloring satisfies (\ref{maindetachcoreq}) and (\ref{maindetachcoreq2}). \begin{equation*} d_j(u) =\left \{ \begin{array}{ll} 2m_j(u^2,v)+m(s-r)-2m_j(u^2,v)=m(s-r) & \mbox { for } 1\leq j\leq q, \\ 2m_j(u^2,v)+sm-2m_j(u^2,v)=sm& \mbox { for } q+1\leq j\leq k, \mbox { if } k>q. \end{array} \right. \end{equation*} For $1\leq j\leq q$, \begin{equation*} d_j(v) =3(sn/3-sm+m_j(u^2,v)+2rm/3)+2(sm-rm-2m_j(u^2,v))+m_j(u^2,v)=s(n-m), \end{equation*} and for $q+1\leq j\leq k$, if $k>q$ \begin{equation*} d_j(v) =3(sn/3-sm+m_j(u^2,v))+2(sm-2m_j(u^2,v))+m_j(u^2,v)=s(n-m). \end{equation*} \noindent {\bf Case 2. $\boldsymbol{r=s}$:} We color the edges of the form $\{u^2,v\}$ so that \begin{eqnarray} \label{f-edges2} &m_j(u^2,v) = & 0 \quad\quad\quad\mbox {for } 1\leq j\leq q, \nonumber\\ rm-rn/3 \leq & m_j(u^2,v) \leq & rm/2 \quad \mbox {for } q+1\leq j\leq k. \end{eqnarray} In order to show that such a coloring is possible, first note that $rm/2\geq rm-rn/3$ is equivalent to $n\geq 3m/2$, which is true by (C5). Therefore, it is enough to show that $$ (k-q)(rm-rn/3)\leq m(u^2,v) \leq (k-q)\lfloor rm/2\rfloor, $$ which is true by Lemmas \ref{elem1} and \ref{elem3}. Then, we color the edges of the form $\{u,v^2\}$ so that \begin{equation*} m_j(u,v^2) =\left \{ \begin{array}{ll} 0 & \mbox { for } 1\leq j\leq q, \\ rm-2m_j(u^2,v)& \mbox { for } q+1\leq j\leq k. \end{array} \right. \end{equation*} This is possible, because by (\ref{f-edges2}) $m_j(u,v^2)\geq 0$ for $1\leq j\leq k$ , and \begin{eqnarray*} \sum_{j=1}^k m_j(u,v^2) & = & rm(k-q)-2\sum_{j=q+1}^k m_j(u^2,v)\\ &=&m\binom{n-1}{2}-m\binom{m-1}{2}-2(n-m)\binom{m}{2}\\ &\mathop= \limits^{\scriptsize{\mbox {lem. }} \ref{elem0}(a)}&m\binom{n-m}{2}=m(u,v^2). \end{eqnarray*} Finally, we color the edges of the form $\{v^3\}$ so that \begin{equation*} m_j(v^3) =\left \{ \begin{array}{ll} r(n-m)/3 & \mbox { for } 1\leq j\leq q, \\ rn/3-rm+m_j(u^2,v)& \mbox { for } q+1\leq j\leq k. \end{array} \right. \end{equation*} This coloring is possible, because by (C1) $m_j(v^3)$ is an integer for $1\leq j\leq k$, by (\ref{f-edges2}) $m_j(v^3)\geq 0$ for $1\leq j\leq k$, and \begin{eqnarray*} \sum_{j=1}^k m_j(v^3) & = & \sum_{j=1}^q m_j(v^3)+\sum_{j=q+1}^k m_j(v^3)\\ &=&qr(n-m)/3+(k-q)(rn/3-rm)+m(u^2,v)\\ &=&(n-m)\binom{m}{2}+2qrm/3+krn/3-krm\\ &=&(n-m)\binom{m}{2}+2\binom{m}{3}+\binom{n}{3}-m\binom{n-1}{2}\\ &\mathop= \limits^{\scriptsize{\mbox {lem. }} \ref{elem0}(b)}&\binom{n-m}{3}=m(v^3). \end{eqnarray*} Using (\ref{degreeid}), we verify that the described edge-coloring satisfies (\ref{maindetachcoreq}) and (\ref{maindetachcoreq2}). \begin{equation*} d_j(u) =\left \{ \begin{array}{ll} 0 & \mbox { for } 1\leq j\leq q, \\ 2m_j(u^2,v)+rm-2m_j(u^2,v)=rm& \mbox { for } q+1\leq j\leq k. \end{array} \right. \end{equation*} For $1\leq j\leq q$, \begin{equation*} d_j(v) =3r(n-m)/3=r(n-m), \end{equation*} and for $q+1\leq j\leq k$, \begin{equation*} d_j(v) =3(rn/3-rm+m_j(u^2,v))+2(rm-2m_j(u^2,v))+m_j(u^2,v)=r(n-m). \end{equation*} Applying Corollary \ref{maindetachcor} to $\mathcal F$, completes the proof. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\subsection*{Acknowledgements} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \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}{10} \bibitem{MR584118} L.~D. Andersen and A.~J.~W. Hilton. \newblock Generalized {L}atin rectangles. {II}. {E}mbedding. \newblock {\em Discrete Math.}, 31(3):235--260, 1980. \bibitem{MR2942724} M.~A. Bahmanian. \newblock Detachments of hypergraphs {I}: {T}he {B}erge-{J}ohnson problem. \newblock {\em Combin. Probab. Comput.}, 21(4):483--495, 2012. \bibitem{BahNewm1} M.~A. Bahmanian and Mike Newman. \newblock Extending factorizations of complete uniform hypergraphs. \newblock {\em Submitted}. \bibitem{MR3056885} M.~A. Bahmanian and C.~A. Rodger. \newblock Embedding factorizations for 3-uniform hypergraphs. \newblock {\em J. Graph Theory}, 73(2):216--224, 2013. \bibitem{MR0416986} Zs. Baranyai. \newblock On the factorization of the complete uniform hypergraph. \newblock In {\em Infinite and finite sets ({C}olloq., {K}eszthely, 1973; dedicated to {P}. {E}rd{\H o}s on his 60th birthday), {V}ol. {I}}, pages 91--108. Colloq. Math. Soc. J\'an\=os Bolyai, Vol. 10. North-Holland, Amsterdam, 1975. \bibitem{BaranBrouwer77} Zs. Baranyai and A.~E. Brouwer. \newblock Extension of colorings of the edges of a complete (uniform hyper)graph. \newblock Technical report, Mathematisch Centrum Amsterdam, Math. Centre Report ZW91, Zbl. 362.05059, 1977. \bibitem{MR0419245} Peter~J. Cameron. \newblock {\em Parallelisms of complete designs}. \newblock Cambridge University Press, Cambridge-New York-Melbourne, 1976. \newblock London Mathematical Society Lecture Note Series, No. 23. \bibitem{MR0329925} Allan~B. Cruse. \newblock On embedding incomplete symmetric {L}atin squares. \newblock {\em J. Combinatorial Theory Ser. A}, 16:18--22, 1974. \bibitem{MR1249714} R.~H{\"a}ggkvist and T.~Hellgren. \newblock Extensions of edge-colourings in hypergraphs. {I}. \newblock In {\em Combinatorics, {P}aul {E}rd{\H o}s is eighty, {V}ol.\ 1}, Bolyai Soc. Math. Stud., pages 215--238. J\'anos Bolyai Math. Soc., Budapest, 1993. \bibitem{MR1983358} A.~J.~W. Hilton, Matthew Johnson, C.~A. Rodger, and E.~B. Wantland. \newblock Amalgamations of connected {$k$}-factorizations. \newblock {\em J. Combin. Theory Ser. B}, 88(2):267--279, 2003. \bibitem{MR2325799} Matthew Johnson. \newblock Amalgamations of factorizations of complete graphs. \newblock {\em J. Combin. Theory Ser. B}, 97(4):597--611, 2007. \bibitem{MR1315436} C.~A. Rodger and E.~B. Wantland. \newblock Embedding edge-colorings into {$2$}-edge-connected {$k$}-factorizations of {$K_{kn+1}$}. \newblock {\em J. Graph Theory}, 19(2):169--185, 1995. \end{thebibliography} \bibliographystyle{plain} %\bibliography{rKmh23} \end{document}