Amalgamations and Detachments of Graphs and Hypergraphs
by
M. Amin Bahmanian
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial fulfillment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
August 4, 2012
Keywords: detachments, amalgamations, decomposition, embedding, graphs, edge-coloring
Copyright 2012 by M. Amin Bahmanian
Approved by
Chris A. Rodger, Chair, Don Logan Endowed Chair of Mathematics, Department of
Mathematics and Statistics
Charles Curtis Lindner, Distinguished University Professor, Department of Mathematics
and Statistics
Peter D. Johnson, Jr., Professor, Department of Mathematics and Statistics
Abstract
A detachment of a graph H is a graph obtained from H by splitting some or all of its
vertices into more than one vertex. If g is a function from VpHq into N, then a g-detachment
of H is a detachment of H in which each vertex u of H splits into gpuq vertices. H is an
amalgamation of G if there exists a function ? called an amalgamation function from VpGq
onto VpHq and a bijection ?1 : EpGq ?EpHq such that e joining u and v is in EpGq iff ?1peq
joining ?puq and ?pvq is in EpHq.
We prove that for a given edge-colored graph there exists a detachment so that the result
is a graph in which the edges are shared among the vertices in ways that are fair with respect
to several notions of balance (such as between pairs of vertices, degrees of vertices in both
the graph and in each color class, etc.). The connectivity of color classes is also addressed.
Most results in the literature on amalgamations focus on the detachments of amalgamated
complete graphs and complete multipartite graphs. Many such results follow as immediate
corollaries to the main result, which addresses amalgamations of graphs in general.
We exhibit some applications of this result in Hamiltonian decomposition of several
families of graphs, and also we show that many known graph decomposition results can be
obtained by a short proof using the main theorem. We study the companion embedding
problems with many applications.
We then extend various results by Hilton, Nash-Williams and Rodger to hypergraphs.
Such extensions provide a powerful tool to generalizes Baranyai?s Theorems, and related
results by Berge and Johnson.
We study several hypergraph embedding problems which will extend results of Brouwer,
Schrijver, Baranyai, H?aggkvist and Hellgren.
ii
In connection with Baranyai-Katona conjecture, we provide necessary and sufficient
conditions for a complete uniform hypergraph to be connected factorizable, answering a
question by Katona.
iii
Acknowledgments
Iwould to thankto my supervisor professor Chris Rodgerfor hisconstant encouragement
and support. I am also grateful to professors C.C. Lindner, Pete Johnson, Dean Hoffman,
Andras Bezdek, N. K. Govil, W. Kuperberg, Doug Leonard, Luc Teirlinck, R.P. Holmes,
Huajun Huang, Olav Kallenberg, A. J. Meir, Jerzy Szulga, Tin-Yau Tam, Richard Zalik,
Michel Smith, Greg Harris, Edward Slaminka, and my fellow Auburn graduate students who
provided me with a welcoming and nourishing environment for the past four years. Last but
not least, I would like to thank the department secretaries Gwen Kirk, Lori Bell and Carolyn
Donegan.
I would like to dedicate this work to Saeed Bahmanian and Mansour Hemayati.
iv
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 What are graph amalgamations? . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Multiply Balanced Edge Colorings of Multigraphs . . . . . . . . . . . . . . . . . 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Terminology and More Definitions . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Hamiltonian Decomposition of Kpn1,...,nm;?,?q . . . . . . . . . . . . . . . . 34
3.1 Hamiltonian Decomposition of Kpn1 ...,nm;?,?q . . . . . . . . . . . . . . 35
3.2 Hamiltonian Decomposition of Kpn1,...,nm;?,?q with a 1-factor leave . . . 40
4 Embedding an Edge-colored Kpappq;?,?q into a Hamiltonian Decomposition of
Kpapp`rq;?,?q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2 Amalgamation and Graph Embedding . . . . . . . . . . . . . . . . . . . . . 47
5 Detachments of Amalgamated 3-uniformHypergraphs : FactorizationConsequences 57
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Notation and More Precise Definitions . . . . . . . . . . . . . . . . . . . . . 59
5.3 Statement of the Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Factorization Consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.4.1 Factorizations of ?K3n . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
v
5.4.2 Factorizations of K3m1,...,mn . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Proof of the Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.5.1 Construction of G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.5.2 Relations Between Fi`1 and Fi . . . . . . . . . . . . . . . . . . . . . 69
5.5.3 Relations Between Fi and F . . . . . . . . . . . . . . . . . . . . . . 73
5.5.4 Relations Between G ?Fn and F . . . . . . . . . . . . . . . . . . . 85
5.6 Algorithmic Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6 Mathematicians Collaboration Problem . . . . . . . . . . . . . . . . . . . . . . . 87
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.2 Proof of the Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7 Embedding factorizations for 3-uniform hypergraphs . . . . . . . . . . . . . . . 92
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.2 Detachments of Amalgamated Hypergraphs . . . . . . . . . . . . . . . . . . 94
7.3 Embedding Partial Hyperedge-colorings into Factorizations . . . . . . . . . . 96
7.4 Extending Restrictions of Partial Edge-colorings . . . . . . . . . . . . . . . . 100
8 Detachments of Hypergraphs: The Berge-Johnson Problem . . . . . . . . . . . . 103
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.2 Terminology and Precise Definitions . . . . . . . . . . . . . . . . . . . . . . . 104
8.3 Amalgamations and Detachments . . . . . . . . . . . . . . . . . . . . . . . . 106
8.4 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.5 Proof of Theorem 8.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
8.5.1 Inductive Construction of G . . . . . . . . . . . . . . . . . . . . . . . 108
8.5.2 Relations Between Fi`1 and Fi . . . . . . . . . . . . . . . . . . . . . 109
8.5.3 Relations Between Fi and F . . . . . . . . . . . . . . . . . . . . . . 111
8.5.4 G satisfies (A1)?(A4) . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.6 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9 Connected Baranyai Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
vi
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
9.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9.3 Proof of the Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
10 Polynomial Time Parallelisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
10.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
10.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
11 Recent Results and Future Directions . . . . . . . . . . . . . . . . . . . . . . . 134
11.1 Amalgamations and Connected Fair Detachments . . . . . . . . . . . . . . . 134
11.1.1 Edge-Coloring Techniques . . . . . . . . . . . . . . . . . . . . . . . . 135
11.2 Fair Detachments of Hypergraphs . . . . . . . . . . . . . . . . . . . . . . . . 135
11.2.1 Laminar Families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
11.3 Edge-Decompositions and Edge-Colorings . . . . . . . . . . . . . . . . . . . 136
11.4 Hypergraph Edge-Colorings and Baranyai?s Theorem . . . . . . . . . . . . . 137
11.4.1 The Berge-Johnson Problem . . . . . . . . . . . . . . . . . . . . . . 138
11.4.2 Baranyai-Katona Conjecture . . . . . . . . . . . . . . . . . . . . . . . 139
11.4.3 Connected Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . 139
11.4.4 Kneser Graphs and the Middle Levels Problem . . . . . . . . . . . . . 140
11.5 Extending Partial Decompositions and Graph Embedding Problems . . . . . 140
11.6 Embedding Problems for Hypergraphs . . . . . . . . . . . . . . . . . . . . . 141
11.7 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
vii
List of Figures
1.1 Walecki Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Hamiltonian decomposition of K7 . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Embedding a path decomposition of K5 into a Hamiltonian decomposition of K7 3
1.4 A graph G with one of its amalgamations H . . . . . . . . . . . . . . . . . . . 4
1.5 A graph G with one of its detachments H . . . . . . . . . . . . . . . . . . . . . 5
2.1 Construction of Bi from Hi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Detachment of Hyi pjq into Hyi`1pjq . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1 A Hamiltonian Decomposition of Kp2p3q;2,1q . . . . . . . . . . . . . . . . . . . 35
4.1 G1 and its detachment G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 G3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.1 Representation of a hypergraph F . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 The three types of edges in a hypergraph G in which |HpG,eq| ? 3 for every edge e 61
5.3 Amalgamation G of the hypergraph F in Example 5.1 . . . . . . . . . . . . . . 63
5.4 The four possibilities for detachment of a single edge incident with ? . . . . . . 71
6.1 A visual representation of a hypergraph F with an amalgamation G . . . . . . 88
viii
7.1 A visual representation of a hypergraph F with an amalgamation G . . . . . . 95
8.1 Representation of a hypergraph G . . . . . . . . . . . . . . . . . . . . . . . . . 106
9.1 A hypergraph G and the set of all its ?-wings . . . . . . . . . . . . . . . . . . . 122
10.1 Digraph D with circulation f . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
ix
Chapter 1
What are graph amalgamations?
1.1 Introduction
Edouard Lucas (1842?1891), the inventor of the Towers of Hanoi problem, discussed
the probl?eme de ronde that asked the following [64]: Given 2n`1 people, is it possible to
arrange them around a single table on n successive nights so that nobody is seated next to
the same person on either side more than once? This problem is equivalent to a Hamiltonian
decomposition of K2n`1; that is partitioning the edge set of K2n`1 into spanning cycles. A
solution to this problem for n? 3 is illustrated in Figure 1.1, which is due to Walecki. This
can be easily generalized to any complete graph by ?rotating? an initial cycle.
v1
v2
v3
v4
v7
v6
v5
Figure 1.1: Walecki Construction
In 1984, Hilton [44] suggested a different approach to solving this problem, one of which
is useful for solving another family of problems as well. He first fused all the vertices of Kn
1
(this is called amalgamation) which results in having `n2? loops incident with a vertex. Then
he shared the loops evenly between different color classes. (In this dissertation, the ith color
class of G is defined to be the spanning subgraph of G that contains precisely the edges
colored i.) Finally he reversed the fusion by splitting the single vertex into n vertices (this
is called detachment), so that each color class is a Hamiltonian cycle. This is illustrated in
Figure 1.2 for K7. It is not obvious how we can detach the loops so that each color class is a
v1
21 loops
v2
v3
v4
v5
v6
v7
v4
v1
v2
v6
v5
v3v7
amalgamation edge-coloring detachment
Figure 1.2: Hamiltonian decomposition of K7
Hamiltonian cycle. The second problem that Hilton solved was an embedding problem [44].
Given an edge-coloring of Km, in which each color class is a path, he used amalgamations to
extend this coloring to an edge-coloring of Km`n, so that each color class is a Hamiltonian
cycle in Km`n (so m `n must be odd). The idea is to add a new vertex, say u to Km
incident with `n2? loops so that there are n edges between this vertex and every other vertex.
Let us call this graph K`m. (In fact K`m is an amalgamation of Km`n in which all further n
vertices are contracted in one point.) One can easily color all the edges incident with u so
that the valency ofufor each color class is exactly 2n. Finally by detaching uinto n vertices,
say u1,...,un and sharing the edges of each color class incident with u among u1,...,un
as evenly as possible and ensuring that each color class is connected, provides the desired
2
outcome: a Hamiltonian decomposition of Km`n. This is illustrated for m ? 5,n ? 2 in
Figure 1.3. To provide more explanation, first we give some definitions.
v5
v2
v1
v3
v4
v5
v2
v1
v4
v3
v
?
v5
v2
v1
v4
v3
v
v6
v7
v5
v1
v2
v3
v4
Figure 1.3: Embedding a path decomposition of K5 into a Hamiltonian decomposition of K7
Throughout this dissertation, all graphs are finite and undirected (possibly with loops
and multiple edges). The lettersGandH denote graphs. Sets may contain repeated elements
(so are really multisets). Each edge is represented by a 2-element multisubset of the vertex
set; in particular tu,uu represents a loop on the vertex u. A k-edge-coloring of a graph G is
a mapping f : EpGq ? C, where C is a set of k colors (often we use C ? t1,...,ku). It is
often convenient to have empty color classes, so we do not require f to be surjective.
In this dissertation, x ? y means tyu ? x ? rys, ?puq denotes the number of loops
incident with vertexu,dpuq denotes the degree of vertexu(loops are considered to contribute
two to the degree of the incident vertex), the subgraph of G induced by the edges colored
j is denoted by Gpjq, ?pGq is the number of components of G, the multiplicity of a pair
of vertices u,v of G, denoted by mpu,vq, is the number of edges joining u and v in G, Kn
denotes the complete graph with n vertices, and Km,...,m denotes the complete multipartite
graph each part having m vertices. If we replace every edge of G by ? multiple edges, then
we denote the new graph by ?G.
Informally speaking, amalgamating a finite graph G can be thought of as taking G,
partitioning its vertices, then for each element of the partition squashing the vertices to
form a single vertex in the amalgamated graph H. Any edge incident with an original vertex
3
in G is then incident with the corresponding new vertex in H, and any edge joining two
vertices that are squashed together in G becomes a loop on the new vertex in H.
More precisely, H is an amalgamation of G if there exists a function ? called an amal-
gamation function from VpGq onto VpHq and a bijection ?1 : EpGq ? EpHq such that e
joining u and v is in EpGq if and only if ?1peq joining ?puq and ?pvq is in EpHq; We write
?pGq ? H. In particular, this requires that e be a loop in H if and only if, in G, it either
is a loop or joins distinct vertices u,v, such that ?puq ? ?pvq. (Note that ?1 is completely
determined by ?.) Associated with ? is the number function ? : VpHq ? N defined by
?pvq ? |??1pvq|, for each v PVpHq. We also shall say that G is a detachment of H in which
each vertex v of H splits (with respect to ?) into the vertices in ??1ptvuq (see Figure 1.4).
HG
amalgamation
Figure 1.4: A graph G with one of its amalgamations H
A detachment of H is, intuitively speaking, a graph obtained from H by splitting some
or all of its vertices into more than one vertex (see Figure 1.5). If ? is a function from VpHq
into N, then an ?-detachment of H is a detachment of H in which each vertex u of H splits
into?puq vertices. In other words, Gis an?-detachment ofH if there exists an amalgamation
function ? of G onto H such that |??1ptuuq| ??puq for every uPVpHq. Some authors refer
to detachments as disentanglements (see [58, 60, 61]).
Since two graphs G and H related in the above manner have an obvious bijection
between the edges, an edge-coloring of G or H, naturally induces an edge-coloring on the
4
G
u
w
v
H
Figure 1.5: A graph G with one of its detachments H
other graph. Hence an amalgamation of a graph with colored edges is a graph with colored
edges.
One of the most useful properties that one can obtain using the techniques described
here, is that many graph parameters (such as colors, degrees, multiple edges) can be simul-
taneously shared evenly during the detachment process. This is often the most desirable
property.
Theorem 1.1. (Bahmanian, Rodger [5, Theorem 3.1]) Let H be a k-edge-colored graph
and let ? be a function from VpHq into N such that for each v P VpHq, ?pvq ? 1 implies
?Hpvq ? 0. Then there exists a loopless ?-detachment G of H in which each v P VpHq is
detached into v1,...,v?pvq, such that G satisfies the following conditions:
(A1) dGpuiq ?dHpuq{?puq for each uPVpHq and 1 ?i??puq;
(A2) dGpjqpuiq ?dHpjqpuq{?puq for each uPVpHq, 1 ?i??puq, and 1 ?j ?k;
(A3) mGpui,ui1q ??Hpuq{`?puq2 ? for each uPVpHq with ?puq ? 2 and 1 ?i?i1 ??puq;
5
(A4) mGpjqpui,ui1q ? ?Hpjqpuq{`?puq2 ? for each u P VpHq with ?puq ? 2, 1 ? i ? i1 ? ?puq,
and 1 ?j ?k;
(A5) mGpui,vi1q ? mHpu,vq{p?puq?pvqq for every pair of distinct vertices u,v P VpHq, 1 ?
i??puq, and 1 ?i1 ??pvq;
(A6) mGpjqpui,vi1q ? mHpjqpu,vq{p?puq?pvqq for every pair of distinct vertices u,v P VpHq,
1 ?i??puq, 1 ?i1 ??pvq, and 1 ?j ?k;
(A7) If for some j, 1 ? j ? k, dHpjqpuq{?puq is even for each u P VpHq, then ?pGpjqq ?
?pHpjqq.
The proof uses edge-coloring techniques and will be given in the next chapter. An edge-
coloring of a multigraph is (i) equalized if the number of edges colored with any two colors
differs by at most one, (ii) balanced if for each pair of vertices, among the edges joining the
pair, the number of edges of each color differs by at most one from the number of edges of
each other color, and (iii) equitable if, among the edges incident with each vertex, the number
of edges of each color differs by at most one from the number of edges of each other color. In
[80, 81, 82, 83] de Werra studied balanced equitable edge-coloring of bipartite graphs. The
following result is used to prove Theorem 1.1.
Theorem 1.2. Every bipartite graph has a balanced, equitable and equalized k-edge-coloring
for each k P N.
Here we show that this result is simply a consequence of Nash-Williams lemma. A
family A of sets is laminar if, for every pair A,B of sets belonging to A, either A ?B, or
B ?A, or AXB ? ?.
Lemma 1.3. (Nash-Williams [70, Lemma 2]) If A,B are two laminar families of subsets
of a finite set S, and nP N, then there exist a subset A of S such that for every P PA YB,
|AXP| ? |P|{n.
6
Proof of Theorem 1.2. Let B be a bipartite graph with vertex bipartition tV1,V2u. For
i ? 1,2 define the laminar set Li to consist of the following sets of subsets of edges of B:
(i) The edges between each pair of vertices v1 P V1 and v2 P V2, (ii) For each v P Vi, the
edges incident with v, (iii) All the edges in B. Applying Lemma 1.3 with n ? k provides
one color class. Remove these edges then reapply Lemma 1.3, with n ? k ? 1 to get the
second class. Recursively proceeding in this way provides the k-edge-coloring of B. It is
straightforward to see that this produces the result by observing that the edges in subsets
defined in (i), (ii) and (iii) guarantee that the k-edge-coloring is balanced, equitable, and
equalized respectively.
1.2 Applications
In this section we demonstrate the power of Theorem 1.1. The results are not new, and
many follow from earlier, more restrictive versions of Theorem 1.1. But the point of this
section is to give the reader a feel for how amalgamations can be used.
Theorem 1.4. (Walecki [64]) ?Kn is Hamiltonian decomposable (with a 1-factor leave, re-
spectively) if and only if ?pn?1q is even (odd, respectively).
Proof. The necessity is obvious. To prove the sufficiency, letH be a graph with VpHq ? tvu,
?pvq ? ?`n2? and ?pvq ? n , and let k ? t?pn? 1q{2u. Color the loops so that ?Hpjqpvq ? n,
for 1 ? j ? k (and ?Hpk`1qpvq ? n{2, if ?pn?1q is odd). Applying Theorem 1.1 completes
the proof.
The following result is essentially proved in [44], but the result is stated in less general
terms.
Theorem 1.5. (Hilton [44]) A k-edge-colored Km can be embedded into a Hamiltonian de-
composition of Km`n (with a 1-factor leave, respectively) if and only if pm`n?1q is even
(odd, respectively), k ? rpm`n?1q{2s, and each color class of Km (except one color class,
say k, respectively) is a collection of at most n disjoint paths, (color class k consists of paths
7
of length at most 1, at most n of which are of length 0, respectively), where isolated vertices
in each color class are to be counted as paths of length 0.
Proof. The necessity is obvious. To prove the sufficiency, let pi ?n be the number of paths
colored i, 1 ? i ? k. Form a graph H by adding a new vertex u to Km so that ?puq ? `n2?,
mpu,vq ?n for each v PVpKmq, and ?puq ?n. Color the new edges incident with vertices in
Km so thatdHpjqpvq ? 2 forv PVpKmq, 1 ?j ?k (ifm`nis even, do it so thatdHpkqpvq ? 1
forv PVpKmq; so at mostnsuch edges are incident withuby necessary conditions). Clearly,
each color appears on an even number of such edges (except possibly color k when m`n is
odd). Color the loops so that dHpjqpuq ? 2n for 1 ?j ?k (if m`n is even, then the coloring
must be so that dHpkqpuq ?n). This is possible since each color appears on p2n?2piq{2 ? 0
loops. Now applying Theorem 1.1 completes the proof.
A similar result can be obtained for embedding ?Km into a Hamiltonian decomposition
of ?Km`n. A more general problem is the following enclosing problem
Problem 1. Find necessary and sufficient conditions for enclosing an edge-colored ?Km
into a Hamiltonian decomposition of ?Km`n for ???.
An pr1,...,rkq-factorization of a graph G is a partition (decomposition) tF1,...,Fku of
EpGq in which Fi is an ri-factor for i ? 1,...,k. The following is a corollary of a strong
result of Johnson [51] in which each color class can have a specified edge-connectivity. A
special case of this is proved by Johnstone in [52].
Theorem 1.6. ?Kn is pr1,...,rkq-factorizable if and only if rin is even for 1 ?i ?k, and
?k
i?1ri ??pn?1q. Moreover, for 1 ?i?k each ri-factor can be guaranteed to be connected
if ri is even.
Proof. The necessity is obvious. To prove the sufficiency, start from the graph H as in the
proof of Theorem 1.4, but color the loops so that ?Hpjqpvq ?nrj{2 for 1 ?j ?k. Then apply
Theorem 1.1.
8
The following result was proved for the special case r1 ?...?rk ?r in [3, 74].
Theorem 1.7. A k-edge-coloring of Km can be embedded into an pr1,...
,rkq-factorization of Km`n if and only if ripm`nq is even for 1 ?i?k, ?ki?1ri ?m`n?1,
dKmpiqpvq ? r?piq for each v P VpKmq, 1 ? i ? k, and some permutation ? P Sk, and
|EpKmpiqq| ?r?piqpm?nq{2.
Proof. The necessity is obvious. To prove the sufficiency, start from the graph H as in the
proof of Theorem 1.5. Color the new edges incident with vertices in Km so that dHpjqpvq ?
r?pjq forv PVpKmq, 1 ?j ?k. Then color the loops incident withuso thatdHpjqpuq ?r?pjqm
for 1 ? j ? k (the last necessary condition guarantees that the number of required loops is
non-negative), and apply Theorem 1.1.
Problem 2. Find necessary and sufficient conditions for enclosing an edge-colored ?Kn into
an pr1,...,rkq-factorization of ?Km`n for ???.
The case ??? can be obtained by altering the proof of Theorem 1.7 slightly.
Some of the above results can be easily generalized to complete multipartite graphs.
Theorem 1.8. (Laskar, Auerbach [57]) ?Kn1,...,nm is Hamiltonian decomposable (with a 1-
factor leave, respectively) if and only if n1 ? ??? ? nm :? n, and ?npm? 1q is even (odd,
respectively).
Proof. The necessity is obvious. To prove the sufficiency, consider the graph H :? ?n2Km,
and ? : VpHq ? N with ?pvq ? n for each v P VpHq. Using Theorem 1.6, find a connected
2n-factorization of H and apply Theorem 1.1.
Another very nice requirement that one can ask of a Hamiltonian decomposition of a
complete multipartite graph is that it be fair; that is, in each Hamiltonian cycle, the number
of edges between each pair of parts is within one of the number of edges between each other
pair of parts. This result can be proved by being more careful in the construction of the
edge-coloring of the graph H described in the proof of Theorem 2.5; ensure that for each
9
color class the number of edges between each pair of vertices in H is within 1 of the number
of edges between each other pair of vertices (one could think of this color class as being
?equimultiple?). Leach and Rodger [59] used this approach to prove that
Theorem 1.9. Kn1,...,nm is fair Hamiltonian decomposable if and only if n1 ? ??? ?nm :?n,
and npm?1q is even.
Problem 3. Find necessary and sufficient conditions for enclosing ak-edge-colored?Kn1,...,nm
into a (fair) Hamiltonian decomposition of ?Kn11,...,n1
m1
for ni ? n1i, 1 ? i ? m ? m1, and
???.
Theorem 1.10. ?Kn1,...,nm is pr1,...,rkq-factorizable if and only if n1 ? ??? ? nm :? n,
rinm is even for 1 ?i?k, and ?ki?1ri ??npm?1q.
Proof. The necessity is obvious. To prove the sufficiency, use Theorem 1.6 to find an
pnr1,...,nrkq-factorization of the graph H described in the proof of Theorem 1.8; then
apply Theorem 1.1.
Problem 4. Find necessary and sufficient conditions for enclosing ak-edge-colored?Kn1,...,nm
into an pr1,...,rkq-factorization of ?Kn11,...,n1
m1
for ni ?n1i, 1 ?i?m?m1, and ???.
The Oberwolfach problemOPpra11 ,...,rakk q asks whether or not it is possible to partition
the edge set of Kn, n odd, or Kn with a 1-factor removed when n is even, into isomorphic 2-
factors such that each 2-factor consists ofaj cycles of lengthrj, 1 ?j ?k, andn? ?kj?1rjaj.
In [46] some new solutions to the Oberwolfach problem are given using the amalgamation
technique.
10
Chapter 2
Multiply Balanced Edge Colorings of Multigraphs
2.1 Introduction
In this chapter, a theorem is proved that generalizes several existing amalgamation
results in various ways. The main aim is to disentangle a given edge-colored amalgamated
graph so that the result is a graph in which the edges are shared out among the vertices
in ways that are fair with respect to several notions of balance (such as between pairs of
vertices, degrees of vertices in the both graph and in each color class, etc). The connectivity
of color classes is also addressed. Most results in the literature on amalgamations focus
on the disentangling of amalgamated complete graphs and complete multipartite graphs.
Many such results follow as immediate corollaries to the main result in this chapter, which
addresses amalgamations of graphs in general, allowing for example the final graph to have
multiple edges. A new corollary (see Chapter 3) of the main theorem is the settling of the
existence of Hamilton decompositions of the family of graphsKpa1,...,ap;?,?q; such graphs
arose naturally in statistical settings.
A graph is said to be: (i) almost regular if there is an integer d such that every vertex
has degree d or d`1, (ii) equimultiple if there is an integer d such that every pair of vertices
has multiplicity d or d` 1, (iii) P-almost-regular (where P ? tP1,...,Pru is a partition of
VpGq) if for 1 ? i ? r, there is an integer di such that each vertex in Pi has degree di or
di `1.
The main goal of this chapter is to prove Theorem 2.1. Informally, it states that for
a given k-edge-colored graph H and a function ? : VpHq ? N, there exists a loopless ?-
detachment G of H with amalgamation function ? : VpGq ? VpHq, ? being the number
function associated with ?, such that: (i)Gand each of its color classes areP-almost-regular
11
where P ? t??1pvq : v P VpHqu, (ii) the subgraph of G induced by ??1pvq is equimultiple
for each v P VpHq, as are each of its color classes, (iii) the bipartite subgraph of G formed
by the edges joining vertices in ??1puq to the vertices in ??1pvq is equimultiple for every pair
of distinct u,v P VpHq, as are each of its color classes, and (iv) under certain conditions,
the subgraph induced by each color class can be guaranteed to have the same number of
components in G as in H. The conditions (ii) and (iii) can be used to force G to be
multigraphs of interest, such as ?Kn,?Km,...,m, or Kpa1,...,ap;?,?q (for the definition of
Kpa1,...,ap;?,?q, see Chapter 3). As in previous results, condition (iv) is especially useful
in the context of Hamiltonian decompositions, since it can be used to force connected color
classes in H to remain connected in G.
A Hamiltonian decomposition of a graph G is a partition of the edges of G into sets,
each of which induces a spanning cycle. Hamiltonian decompositions have been studied since
1892, when Walecki [64] proved the classic result that Kn is Hamiltonian decomposable if
and only if n is odd. In 1976 Laskar and Auerbach [57] settled the existence of Hamiltonian
decomposition of the complete multipartite graph Km,...,m and of Km,...,m ?F where F is a
1-factor. Nash-Williams [67] conjectured that every 2k-regular graph with at most 4k ` 1
vertices has a Hamiltonian decomposition.
Several techniques have been used for finding Hamiltonian decompositions. The tech-
nique of vertex amalgamation, which was developed in the 1980s by Hilton and Rodger
[44, 48], has proved to be very powerful in constructing Hamiltonian decompositions of var-
ious classes of graphs, especially in obtaining embedding results; see also [47, 51, 70, 74].
Buchanan [28] used amalgamations to prove that for any 2-factorU ofKn, nodd, Kn?EpUq
admits a Hamiltonian decomposition. Rodger and Leach [58] solved the corresponding exis-
tence problem for complete bipartite graphs, and obtained a solution for complete multipar-
tite graphs when U has no small cycles [60]. See also [23, 66] for different approach to solve
this problem. Detachments of graphs have also been studied in [18, 49], generalizing some
results of Nash-Williams [68, 69].
12
The main theorem of this chapter, Theorem 2.1, not only generalizes several well-known
graph amalgamation results, (for example, in [44, 48, 58, 61, 74], Theorem 1, Theorem 1,
Theorem 3.1, Theorem 2.1 and Theorem 2.1 respectively all follow as immediate corol-
laries)), but also provides the right tool to find necessary and sufficient conditions for
Kpa1,...,ap;?,?q to be Hamiltonian decomposable, as shown in Theorem 3.4. The lat-
ter graph, Kpa1,...,ap;?,?q, is of particular interest to statisticians, who consider group
divisible designs with two associate classes, beginning over 50 years ago with the work of
Bose and Shimamoto [22]. Recently, partitions of the edges of Kpa1,...,ap;?,?q into sets,
each of which induces a cycle of lengthm, have been extensively studied for small values ofm
[37, 38, 39]. Theorem 3.4 provides a companion to this work, settling the problem completely
for longest (i.e. Hamiltonian) cycles with a really neat proof. When a1 ? ... ? ap ? a, we
denote Kpa1,...,ap;?,?q by Kpappq;?,?q. Using Theorem 2.1, in Chapter 4 we will provide
conditions under which one can embed an edge-colored Kpappq;?,?q into an edge-colored
Kpapp`rq;?,?q such that every color class of Kpapp`rq;?,?q induces a Hamiltonian cycle.
However obtaining such results will be much more complicated than for companion results
for simple graphs, with a complete solution unlikely to be found in the near future.
We describe terminology and notation in Section 2.2. Then we prove the main result in
Section 2.3.
2.2 Terminology and More Definitions
In this thesis, R denotes the set of real numbers, N denotes the set of positive integers,
and Zk denotes the set of integers t1,...,ku. If f is a function from a set X into a set
Y and y P Y, then f?1pyq denotes the set tx P X : fpxq ? yu, and f?1rys denotes tx P
X : fpxq ? yuztyu. If x,y are real numbers, then txu and rxs denote the integers such that
x ? 1 ? txu ? x ? rxs ? x` 1, and x ? y means tyu ? x ? rys. We observe that for
x,y,z,x1,...xn P R,a,b,cP Z, and nP N: (i) a?x implies aP ttxu,rxsu, (ii) x?y implies
x{n ? y{n (iii) the relation ? is transitive (but not symmetric), (iv) xi ? x for 1 ? i ? n
13
implies p?ni?1xiq{n ? x, (v) x ? y and y ? a implies x ? a, and (vi) a ? b?c and c ? x,
implies a ? b?x. These properties of ? will be used in Section 2.3 when required without
further explanation.
IfGis ak-edge-colored graph, and ifu,v PVpGqandA,B ?VpGqwithAXB ? ?, then
mpA,Bq denotes the total number of edges joining vertices in A to vertices in B. We refer
to mpA,Bq as the multiplicity of pair A,B, naturally generalizing the multiplicity mpu,vq of
a pair of vertices u,v as used in [19]. In particular by mpu,Aq we mean mptuu,Aq. If G1,G2
are subgraphs ofGwith VpG1q ?AandVpG2q ?B, then we let mpG1,G2q denotempA,Bq,
and mpu,G1q denote mptuu,Aq. The neighborhood of vertex v, written Npvq, denotes the
set of all vertices adjacent to v (not including v).
2.3 Main Theorem
The main theorem below describes some strong properties that can be guaranteed to be
satisfied by some detachment G of a given edge-colored graph H. Condition (A1) addresses
the issue of P-almost-regularity (where P is a partition of VpGq), while conditions (A3) and
(A5) address the equimultiplicity issue inG. Conditions (A1), (A3) and (A5) have companion
conditions (A2), (A4) and (A6), respectively, that restricts the graphs considered to the color
classes of G. Condition (A7) addresses the connectivity issue of each color class of G.
Theorem 2.1. (Bahmanian, Rodger [5, Theorem 3.1]) Let H be a k-edge-colored graph and
let ? be a function from VpHq into N such that for each w P VpHq, ?pwq ? 1 implies
?Hpwq ? 0. Then there exists a loopless ?-detachment G of H with amalgamation function
? : VpGq ?VpHq, ? being the number function associated with ?, such that G satisfies the
following conditions:
(A1) dGpuq ?dHpwq{?pwq for each w PVpHq and each uP??1pwq;
(A2) dGpjqpuq ?dHpjqpwq{?pwq for each w PVpHq, each uP??1pwq and each j P Zk;
14
(A3) mGpu,u1q ? ?Hpwq{`?pwq2 ? for each w P VpHq with ?pwq ? 2 and every pair of distinct
vertices u,u1 P??1pwq;
(A4) mGpjqpu,u1q ??Hpjqpwq{`?pwq2 ? for each w PVpHq with ?pwq ? 2, every pair of distinct
vertices u,u1 P??1pwq and each j P Zk;
(A5) mGpu,vq ? mHpw,zq{p?pwq?pzqq for every pair of distinct vertices w,z P VpHq, each
uP??1pwq and each v P??1pzq;
(A6) mGpjqpu,vq ? mHpjqpw,zq{p?pwq?pzqq for every pair of distinct vertices w,z P VpHq,
each uP??1pwq, each v P??1pzq and each j P Zk;
(A7) If for somej P Zk, dHpjqpwq{?pwqis an even integer for eachw PVpHq, then?pGpjqq ?
?pHpjqq.
Remark 2.2. All existing results in [44, 48, 58, 61, 74] study amalgamations for complete
graphs or complete multipartite graphs. In these papers, Theorem 1, Theorem 1, Theorem
3.1, Theorem 2.1, and Theorem 2.1 respectively are all immediate corollaries of Theorem
2.3. Other results in the literature may have another focus, most notably in [51, 70, 74]
where the edge-connectivity of each color class is specified; such results are not generalized
by Theorem 2.3.
Proof. Let H ? pV,Eq and let n? ?
vPV
p?pvq?1q. Our proof consists of the following major
parts. First we shall describe the construction of a sequence of graphs H0 ?H,H1,...,Hn,
where Hi is an amalgamation of Hi`1 (so Hi`1 is a detachment of Hi) for 0 ? i ? n? 1
with amalgamation function ?i that combines a vertex with amalgamation number 1 with
one other vertex. To construct each Hi`1 from Hi we will use two bipartite graphs Bi,B1i.
Then we will observe some properties of B1i. We will show that these properties will impose
conditions on Hi`1 in terms of Hi. The relations between Hi`1 and Hi lead to conditions
relating each Hi, 1 ?i?n to the initial graph H. This will then show that Hn satisfies the
conditions (A1)-(A7), so we can let G?Hn.
15
Initially we let H0 ? H,?0 ? ?, and we let ?0 be the identity function from V into V.
Now assume that H0 ? pV0,E0q,...,Hi ? pVi,Eiq and ?0,...,?i have been defined for some
i ? 0. Also assume that ?0 : V0 ? N,...,?i : Vi ? N have been defined for some i ? 0 such
that for each j ? 0,...,i and each y P Vj, ?jpyq ? 1 implies ?Hjpyq ? 0. Let ?i ? ?0...?i.
If i ? n, we terminate the construction, letting G ? Hn and ? ? ?n. Otherwise, we can
select a vertex y of Hi such that ?ipyq ? 2. Hi`1 is formed from Hi by detaching a vertex
vi`1 with amalgamation number 1 from y.
To decide which edge (and loop) to detach from y and to move to vi`1, we construct
two sequences of bipartite graphs B0,...,Bn?1 and B10,...,B1n?1 together with a sequence
F0,F1,...,Fn?1 of sets of edges (possibly including loops) with Fi ?EpB1iq for i? 0,...,n?
1; each edge in Fi corresponds to an edge in Hi which will have one end detached from y
and joined to vi`1 when forming Hi`1.
Let ci1,...,cik and Li be distinct vertices which do not belong to Vi. Let Bi be a
bipartite graph whose vertex bipartition is tQi,Wiu, where
Qi ? tci1,...,ciku and Wi ?NHipyqYtLiu,
and whose edge set is
EpBiq ?
? ?
ty,uuPEpHipjqq
y?u
ttcij,uuu
??? ?
ty,yuPEpHipjqq
ttcij,Liu,tcij,Liuu
?
.
Intuitively speaking, for each color j P Zk and each vertex u P WiztLiu an edge is placed
between cij and u in Bi for each edge in Hipjq joining y to u. Moreover, two edges are placed
between cij and Li in Bi for each loop incident with y in Hipjq. This is shown in Figure 2.1.
16
Color 3
Color 2
Color 1
a
y c
b
d
b c d
ci2 ci3 cikci1
Lia
Hi
NHi(y)
Qi
Wi
Vi\NHi[y]
Bi
Figure 2.1: Construction of Bi from Hi
For Bi we have
dBipvq ?
$
???
?&
???
%
dHipjqpyq if v ?cij for some j P Zk
2?Hipyq if v ? Li
mHipy,vq otherwise.
(2.1)
By Theorem 1.2 we can giveBi an equalized, equitable and balanced ?ipyq-edge-coloring
Ki. Since Ki is equitable, for each 1 ?r ??ipyq, we have
dBiprqpvq ?
$
???
?&
???
%
dHipjqpyq{?ipyq if v ?cij for some j P Zk
2?Hipyq{?ipyq if v ? Li
mHipy,vq{?ipyq otherwise.
(2.2)
Now let Ti be formed by a subgraph of Bi induced by the edges colored 1 and 2. Since
?ipyq ? 2, this is always possible. For each color j P Zk for which
for all v PVi,dHipjqpvq{?ipvq is an even integer, (2.3)
17
define ?ij ?dHipjqpyq{?ipyq. By (2.2) for each color class r of Ki, dBiprqpcijq ?dHipjqpyq{?ipyq.
Therefore since two color classes of Ki are chosen to form Ti, if (2.3) is satisfied, then
dTipcijq ? 2dHipjqpyq{?ipyq ? 2?ij.
Let B1i be the bipartite graph whose vertex bipartition is tQ1i,Wiu, obtained by splitting
all the vertices cij in Ti for each j P Zk for which condition (2.3) holds, into ?ij vertices
ci,j,1,...,ci,j,?ij all of degree 2 as described in (M1)-(M2) below. (We don?t split vertices cij
in Ti for j P Zk for which condition (2.3) does not hold; but they and their incident edges
remain in B1i.)
(M1) First, as many of ci,j,t?s 1 ?t??ij as possible are joined by 2 edges to the same vertex
in Wi;
(M2) Then, among all ci,j,t?s 1 ? t ? ?ij with valency less than 2, as many of them as
possible are incident with two edges that correspond to edges in Hipjq that join y to
vertices that are both in the same component of Hipjqztyu.
For each j P Zk that satisfies condition (2.3), we let Cij ?
?ij?
t?1
tci,j,tu. Otherwise, we let
Cij ? tciju. By Theorem 1.2, we can give B1i an equalized, equitable and balanced 2-edge-
coloring K1i. This gives us two color classes either of which can be chosen to be Fi, say the
edges colored 1 are chosen. Since K1i is equitable, we have
dB1ip1qpvq ?
$
???
???
&
???
???
%
dHipjqpyq{?ipyq if v ?cij for j P Zk for which (2.3) does not hold
1 if v P Cij for j P Zk for which (2.3) holds
2?Hipyq{?ipyq if v ? Li
mHipy,vq{?ipyq otherwise.
(2.4)
Now we let
Aij ?
? ?
tc,vuPFi
cPCij
ty,vu
??? ?
tc,LiuPFi
cPCij
ty,yu
?
18
and
Bij ?
? ?
tc,vuPFi
cPCij
tvi`1,vu
??? ?
tc,LiuPFi
cPCij
tvi`1,yu
?
,
where vi`1 is a vertex which does not belong to Vi. Let Vi`1 ? Vi Ytvi`1u, and let ?i`1 be
a function from Vi`1 onto Vi such that
?i`1pvq ?
$
?&
?%
y if v ?vi`1
v otherwise.
Let Hi`1 ? pVi`1,Ei`1q be the ?i`1-detachment of Hi such that for each j P Zk
EpHi`1pjqq ? pEpHipjqqzAijqYBij,
and Ei`1 ? ?kj?1EpHi`1pjqq.
Intuitively speaking, Hi`1 is formed as follows. Each edge tc,vu P Fi with c P Cij and
v P WiztLiu directly corresponds to an edge ty,vu in Hipjq; replace ty,vu with the edge
tv,vi`1u colored j in Hi`1. So in forming Hi`1pjq from Hipjq the end of this edge is detached
from v and joined to the new vertex vi`1 instead. Moreover, we remove mB1ip1qpCij,Liq loops
colored j incident with y in Hi and we replace them with mB1ip1qpCij,Liq edges colored j
joining y to vi`1 in Hi`1. Note that since K1i is balanced, ?ipyq ? 2 and rdB1ipLiq{2s ?
rdBipLiq{2s ??Hipyq, at most half of the edges in B1i incident with Li are colored 1, so there
are indeed mB1ip1qpCij,Liq loops incident with y in Hi (recall that each loop in Hi corresponds
to two edges in B1i).
19
Obviously, ?i`1 is an amalgamation function fromHi`1 intoHi. Let?i`1 be the function
from Vi`1 into N such that
?i`1pvq ?
$?
???
&
???
?%
1 if v ?vi`1
?ipvq?1 if v ?y
?ipvq otherwise.
We now check that B1i, described above, satisfies the following conditions for each color
j P Zk :
(P1) mB1ip1qpCij,Liq ? 2?Hipjqpyq{?ipyq;
(P2) mB1ip1qpCij,vq ?mHipjqpy,vq{?ipyq for each v PWiztLiu;
(P3) mB1ip1qpQ1i,Wiq ?dHipyq{?ipyq;
(P4) mB1ip1qpCij,Wiq ?dHipjqpyq{?ipyq.
In order to prove (P1) and (P2) first we show that
mB1ip1qpCij,vq ? mB1ipCij,vq2 for each v PW1i.
There are two cases:
? Case 1: Cij ? tciju. Since K1i is balanced,
mB1ip1qpCij,vq ?mB1ip1qpcij,vq ? mB1ipcij,vq2 ? mB1ipCij,vq2 .
? Case 2: Cij ?
?ij?
t?1
tci,j,tu. By (M1), among all vertices in Cij, there are exactly
tmB1ipCij,vq{2u vertices of degree 2 which are joined to v (at most one vertex in Cij
is joined to v by one edge). Since K1i is balanced(or equitable), among these vertices
20
of degree 2, exactly one of them is joined to v by an edge colored 1. Therefore
mB1ip1qpCij,vq ?
?ij?
t?1
mB1ip1qpci,j,t,vq ? mB1ipCij,vq2 .
ClearlymB1ipCij,vq ?mTipcij,vq ?mBip1qpcij,vq`mBip2qpcij,vq. Ifv ? Li, from the definition
of Bi it follows that mBipcij,Liq ? 2?Hipjqpyq. Since Ki is balanced, for each 1 ? r ? ?ipyq
we have mBiprqpcij,Liq ? 2?Hipjqpyq{?ipyq. Therefore
mB1ip1qpCij,Liq ? mB1ipCij,Liq2 ? mTipcij,Liq2 ? 2?Hipjqpyq?
ipyq
.
This proves (P1).
Now let v PWiztLiu. From the definition of Bi it follows that mBipcij,vq ?mHipjqpy,vq.
Since Ki is balanced, for each 1 ? r ? ?ipyq we have mBiprqpcij,vq ? mHipjqpy,vq{?ipyq.
Therefore
mB1ip1qpCij,vq ? mB1ipCij,vq2 ? mTipcij,vq2 ? mHipjqpy,vq?
ipyq
.
This proves (P2).
SinceK1i isequalized,mB1ip1qpQ1i,Wiq ? |EpB1ip1qq| ?mB1ipQ1i,Wiq{2. ClearlymB1ipQ1i,Wiq ?
|EpB1iq| ?mTipQi,Wiq ?mBip1qpQi,Wiq`mBip2qpQi,Wiq. From the definition ofBi it follows
that mBipQi,Wiq ? |EpBiq| ? dHipyq. Since Ki is equalized, for each 1 ? r ? ?ipyq we have
mBiprqpQi,Wiq ? |EpBiprqq| ?dHipyq{?ipyq. Therefore
mB1ip1qpQ1i,Wiq ? mB1ipQ
1
i,Wiq
2 ?
mTipQi,Wiq
2 ?
dHipyq
?ipyq .
This proves (P3).
In order to prove (P4), there are two cases:
21
? Case 1: Cij ? tciju. From (2.4) it follows that
mB1ip1qpCij,Wiq ?mB1ip1qpcij,Wiq ?dB1ip1qpcijq ? dHipjqpyq?
ipyq
.
? Case 2: Cij ?
?ij?
t?1
tci,j,tu. In this case mB1ip1qpCij,Wiq ?
?ij?
t?1
mB1ip1qpci,j,t,Wiq. From (2.4)
it follows that
mB1ip1qpCij,Wiq ?
?ij?
t?1
1 ??ij ? dHipjqpyq?
ipyq
.
This proves (P4).
Most of the conditions that Hi`1 must satisfy, are numerical, and we consider them
first. The reader who is more interested in the connectivity issue, namely property (A7),
may wish to jump to the consideration of conditions (D1)-(D2) on the last three pages of
this section.
Using (2.4) and (P1)-(P4), now we show that Hi`1, described above, satisfies the fol-
lowing conditions:
(B1) ?Hi`1pyq ??Hipyqp?i`1pyq?1q{?ipyq;
(B2) ?Hi`1pjqpyq ??Hipjqpyqp?i`1pyq?1q{?ipyq for each j P Zk;
(B3) (i) dHi`1pyq{?i`1pyq ?dHipyq{?ipyq,
(ii) dHi`1pvi`1q ?dHipyq{?ipyq;
(B4) For each j P Zk
(i) dHi`1pjqpyq{?i`1pyq ?dHipjqpyq{?ipyq,
(ii) dHi`1pjqpvi`1q ?dHipjqpyq{?ipyq;
(B5) For each v PNHipyq
(i) mHi`1py,vq{?i`1pyq ?mHipy,vq{?ipyq,
22
(ii) mHi`1pvi`1,vq ?mHipy,vq{?ipyq,
(iii) mHi`1py,vi`1q{?i`1pyq ??Hipyq{`?ipyq2 ?;
(B6) For each v PNHipyq, and each j P Zk
(i) mHi`1pjqpy,vq{?i`1pyq ?mHipjqpy,vq{?ipyq,
(ii) mHi`1pjqpvi`1,vq ?mHipjqpy,vq{?ipyq,
(iii) mHi`1pjqpy,vi`1q{?i`1pyq ??Hipjqpyq{`?ipyq2 ?.
Note that ?i`1pyq ??ipyq?1. Let us fix v PNHipyq, and j P Zk.
From the construction of Hi`1, we have ?Hi`1pyq ? ?Hipyq ? dB1ip1qpLiq. By (2.4),
dB1ip1qpLiq ? 2?Hipyq{?ipyq. Hence
?Hi`1pyq ??Hipyq? 2?Hipyq?
ipyq
? ?Hipyqp?ipyq?2q?
ipyq
? ?Hipyqp?i`1pyq?1q?
ipyq
.
This completes the proof of (B1).
Clearly,?Hi`1pjqpyq ??Hipjqpyq?mB1ip1qpCij,Liq. By(P1),mB1ip1qpCij,Liq ? 2?Hipjqpyq{?ipyq.
Hence
?Hi`1pjqpyq ??Hipjqpyq? 2?Hipjqpyq?
ipyq
? ?Hipjqpyqp?ipyq?2q?
ipyq
? ?Hipjqpyqp?i`1pyq?1q?
ipyq
.
This completes the proof of (B2).
Construction ofHi`1 follows that, dHi`1pyq ?dHipyq?mB1ip1qpQ1i,Wiq, and dHi`1pvi`1q ?
mB1ip1qpQ1i,Wiq. By (P3), mB1ip1qpQ1i,Wiq ?dHipyq{?ipyq. Hence
dHi`1pyq ?dHipyq? dHipyq?
ipyq
? dHipyqp?ipyq?1q?
ipyq
? dHipyq?i`1pyq?
ipyq
,
and dHi`1pvi`1q ?dHipyq{?ipyq. This completes the proof of (B3).
23
From the construction of Hi`1, we have that dHi`1pjqpyq ? dHipjqpyq ?mB1ip1qpCij,Wiq,
and dHi`1pjqpvi`1q ?mB1ip1qpCij,Wiq. By (P4), mB1ip1qpCij,Wiq ?dHipjqpyq{?ipyq. Hence
dHi`1pjqpyq ?dHipjqpyq? dHipjqpyq?
ipyq
? dHipjqpyqp?ipyq?1q?
ipyq
? dHipjqpyq?i`1pyq?
ipyq
,
and dHi`1pjqpvi`1q ?dHipjqpyq{?ipyq. This completes the proof of (B4).
It is easy to see that, mHi`1py,vq ? mHipy,vq?mB1ip1qpQ1i,vq ? mHipy,vq?dB1ip1qpvq,
and mHi`1pvi`1,vq ?dB1ip1qpvq. By (2.4), dB1ip1qpvq ?mHipy,vq{?ipyq. Hence
mHi`1py,vq ?mHipy,vq? mHipy,vq?
ipyq
? mHipy,vqp?ipyq?1q?
ipyq
? mHipy,vq?i`1pyq?
ipyq
,
andmHi`1pvi`1,vq ?mHipy,vq{?ipyq. Moreover,mHi`1py,vi`1q ?mB1ip1qpQ1i,Liq ?dB1ip1qpLiq.
By (2.4), dB1ip1qpLiq ? 2?Hipyq{?ipyq. Therefore mHi`1py,vi`1q ? 2?Hipyq{?ipyq. Hence
mHi`1py,vi`1q
?i`1pyq ?
2?Hipyq
?ipyq?i`1pyq ?
?Hipyq`
?ipyq
2
?.
This completes the proof of (B5).
Finally, from the construction of Hi`1, mHi`1pjqpy,vq ?mHipjqpy,vq?mB1ip1qpCij,vq, and
mHi`1pjqpvi`1,vq ?mB1ip1qpCij,vq. By (P2), mB1ip1qpCij,vq ?mHipjqpy,vq{?ipyq. Hence
mHi`1py,vq ?mHipjqpy,vq? mHipjqpy,vq?
ipyq
? mHipjqpy,vqp?ipyq?1q?
ipyq
? mHipjqpy,vq?i`1pyq?
ipyq
,
and mHi`1pjqpvi`1,vq ? mHipjqpy,vq{?ipyq. Moreover, mHi`1pjqpy,vi`1q ? mB1ip1qpCij,Liq. By
(P1), mB1ip1qpCij,Liq ? 2?Hipjqpyq{?ipyq. Therefore mHi`1pjqpy,vi`1q ? 2?Hipjqpyq{?ipyq. Hence
24
mHi`1pjqpy,vi`1q
?i`1pyq ?
2?Hipjqpyq
?ipyq?i`1pyq ?
?Hipjqpyq`
?ipyq
2
? .
This completes the proof of (B6).
Recall that?i ??0...?i, that ?0 : V ?V, and that ?i : Vi ?Vi?1 fori? 0. Therefore
?i : Vi ? V and thus ??1i : V ? Vi. Now we use (B1)-(B6) to prove that for 0 ? i ? n, Hi
satisfies the following conditions:
(C1) (i) ?Hipwq{`?ipwq2 ? ??Hpwq{`?pwq2 ? for each w PV with ?pwq ? 2, ?ipwq ? 2,
(ii) ?Hipwq ??Hipvrq ? 0 for each w PV with ?ipwq ? 1 and each 1 ?r ?i;
(C2) ?Hipjqpwq{`?ipwq2 ? ? ?Hpjqpwq{`?pwq2 ? for each w P V with ?pwq ? 2, ?ipwq ? 2 and each
j P Zk;
(C3) For each w PV
(i) dHipwq{?ipwq ?dHpwq{?pwq,
(ii) dHipvrq ?dHpwq{?pwq for each vr P??1i rws;
(C4) For each w PV and each j P Zk
(i) dHipjqpwq{?ipwq ?dHpjqpwq{?pwq,
(ii) dHipjqpvrq ?dHpjqpwq{?pwq for each vr P??1i rws;
(C5) For each w PV
(i) mHipw,vrq{?ipwq ??Hpwq{`?pwq2 ? for each vr P??1i rws,
(ii) mHipvr,vsq ??Hpwq{`?pwq2 ? for every pair of distinct vertices vr,vs P??1i rws;
(C6) For each w PV, and each j P Zk
(i) mHipjqpw,vrq{?ipwq ??Hpjqpwq{`?pwq2 ? for each vr P??1i rws,
25
(ii) mHipjqpvr,vsq ??Hpjqpwq{`?pwq2 ? for every pair of distinct vertices vr,vs P??1i rws;
(C7) For every pair of distinct vertices w,z PV
(i) mHipw,zq{p?ipwq?ipzqq ?mHpw,zq{p?pwq?pzqq,
(ii) mHipvr,vsq ?mHpw,zq{p?pwq?pzqq for each vr P??1i rws and each vs P??1i rzs,
(iii) mHipw,vsq{?ipwq ?mHpw,zq{p?pwq?pzqq for each vs P??1i rzs;
(C8) For every pair of distinct vertices w,z PV, and each j P Zk
(i) mHipjqpw,zq{p?ipwq?ipzqq ?mHpjqpw,zq{p?pwq?pzqq,
(ii) mHipjqpvr,vsq ?mHpjqpw,zq{p?pwq?pzqq for eachvr P??1i rws and each vs P??1i rzs,
(iii) mHipjqpw,vsq{?ipwq ?mHpjqpw,zq{p?pwq?pzqq for each vs P??1i rzs.
Let w,z be an arbitrary pair of distinct vertices of V, and let j P Zk. We prove (C1)-(C8) by
induction. Let us first verify (C1)-(C8) for i? 0. Recall that H0 ?H, and ?0pwq ??pwq.
If ?pwq ? 2, obviously ?H0pwq{`?0pwq2 ? ? ?Hpwq{`?pwq2 ?. If ?pwq ? 1, by hypothesis of
Theorem 2.1, ?Hpwq ? 0. This proves (C1) for i ? 0. (C2) can be proved in a similar way.
Obviously dH0pwq{?0pwq ?dHpwq{?pwq and (C3)(ii) is obvious, so this proves (C3) for i? 0.
The proof for (C4) is similar and (C5)-(C8) are sufficiently obvious.
Now we will show that if Hi satisfies the conditions (C1) - (C8) for some i ? n, then
Hi`1 (formed from Hi by detaching vi`1 from the vertex y) satisfies these conditions by
replacing i with i` 1; we denote the corresponding conditions for Hi`1 by (C1)1-(C8)1. If
?i`1pwq ? ?ipwq, then (C1)1-(C6)1 are obviously true. So we just check (C1)1-(C6)1 in the
case where w ? y. Also if ?i`1pwq ? ?ipwq and ?i`1pzq ? ?ipzq, then (C7)1-(C8)1 are clearly
true. So in order to prove (C7)1 - (C8)1 we shall assume that either ?i`1pwq ? ?ipwq ? 1
or ?i`1pzq ? ?ipzq ? 1. (so y P tw,zu; the asymmetry in condition (iii) of (C7)1 and (C8)1
prevents us from assuming that w ?y.)
(C1)1 If?i`1pyq ? 2, by (B1)?Hi`1pyq ??Hipyqp?i`1pyq?1q{?ipyq, and by (C1)(i) of the induc-
tion hypothesis, ?Hipyq{`?ipyq2 ? ??Hpyq{`?pyq2 ?. Also note that`?ipyq2 ? ??ipyqp?ipyq?1q{2.
26
Therefore
?Hi`1pyq`
?i`1pyq
2
? ? ?Hipyqp?i`1pyq?1q`?
i`1pyq
2
??
ipyq
? ?Hipyq`?
ipyq
2
? ? ?Hpyq`?pyq
2
?.
This proves (C1)1(i).
Clearly ?Hi`1pvi`1q ? 0 and ?Hi`1pvrq ? ?Hipvrq ? 0 for each 1 ? r ? i. Therefore
?Hi`1pvrq ? 0 for each 1 ? r ? i` 1. Also if ?i`1pyq ? 1, by (B1) ?Hi`1pyq ? 0. This
proves (C1)1(ii).
(C2)1 The proof is similar to the proof of (C1)1(i), following from (B2) and (C2) of the
induction hypothesis.
(C3)1 By (B3)(i),dHi`1pyq{?i`1pyq ?dHipyq{?ipyq, and by (C3)(i) of the induction hypothesis,
dHipyq{?ipyq ?dHpyq{?pyq. Therefore
dHi`1pyq
?i`1pyq ?
dHpyq
?pyq .
This proves (C3)1(i).
By (B3)(ii), dHi`1pvi`1q ? dHipyq{?ipyq, and by (C3)(ii) of the induction hypothesis,
dHipvrq ? dHpyq{?pyq for each vr P ??1i rys. Since in forming Hi`1 no edge is detached
from vr for each vr P ??1i rys, we have dHi`1pvrq ? dHipvrq. Therefore dHi`1pvrq ?
dHpyq{?pyq for each vr P??1i`1rys. This proves (C3)1(ii).
(C4)1 The proof is similar to the proof of (C3)1, following from (B4) and (C4) of the induction
hypothesis.
27
(C5)1 By (B5)(i), mHi`1py,vrq{?i`1pyq ?mHipy,vrq{?ipyq for each vr P??1i rys. By (C5)(i) of
the induction hypothesis, mHipy,vrq{?ipyq ? ?Hpyq{`?pyq2 ? for each vr P ??1i rys. There-
fore
mHi`1py,vrq
?i`1pyq ?
?Hpyq`
?pyq
2
?.
for each vr P ??1i rys. Moreover, by (B5)(iii) mHi`1py,vi`1q{?i`1pyq ? ?Hipyq{`?ipyq2 ?,
and by (C1)(i) of the induction hypothesis, ?Hipyq ??Hpyq`?ipyq2 ?{`?pyq2 ?. Therefore
mHi`1py,vi`1q
?i`1pyq ?
?Hpyq`?ipyq2 ?`
?pyq
2
?`?
ipyq
2
? ? ?Hpyq`?pyq
2
?.
This proves (C5)1(i).
By (B5)(ii), mHi`1pvi`1,vrq ? mHipy,vrq{?ipyq for each vr P ??1i rys. By (C5)(i) of the
induction hypothesis, mHipy,vrq{?ipyq ??Hpyq{`?pyq2 ? for each vr P??1i rys. Therefore
mHi`1pvi`1,vrq ? ?Hpyq`?pyq
2
?
for eachvr P??1i rys. By (C5)(ii) of the induction hypothesis, mHipvr,vsq ??Hpyq{`?pyq2 ?
for every pair of distinct vertices vr,vs P ??1i rys. Since in forming Hi`1 no edge is
detached from vr for each vr P??1i rys, we have mHi`1pvr,vsq ?mHipvr,vsq. Therefore
mHi`1pvr,vsq ? ?Hpyq`?pyq
2
?
for every pair of distinct vertices vr,vs P??1i`1rys. This proves (C5)1(ii).
(C6)1 The proof is similar to the proof of (C5)1, following from (B6) and (C6) of the induction
hypothesis.
(C7)1 If z RNHpwq then mHpw,zq ? 0 and (C7)1 is trivial. So we assume that z PNHpwq.
28
(i) If ?i`1pwq ??ipwq?1 (so w ?y), by (B5)(i) mHi`1py,zq{?i`1pyq ?mHipy,zq{?ipyq,
and since?i`1pzq ??ipzq, we havemHi`1py,zq{p?i`1pyq?i`1pzqq ?mHipy,zq{p?ipyq?ipzqq.
By (C7)(i) of the induction hypothesis, mHipy,zq{p?ipyq?ipzqq ? mHpy,zq{p?pyq?pzqq.
Therefore
mHi`1py,zq
?i`1pyq?i`1pzq ?
mHpy,zq
?pyq?pzq.
The other case, ?i`1pzq ??ipzq?1), is similar. This proves (C7)1(i).
(ii) By (C7)(ii) of the induction hypothesismHipvr,vsq ?mHpw,zq{p?pwq?pzqqfor each
vr P??1i rws and each vs P??1i rzs ???1i`1rzs. Since in forming Hi`1 no edge is detached
from vr and vs for each vr P ??1i rws and each vs P ??1i rzs, we have mHi`1pvr,vsq ?
mHipvr,vsq. Therefore mHi`1pvr,vsq ? mHpw,zq{p?pwq?pzqq for each vr P ??1i rws and
each vs P ??1i`1rzs. If ?i`1pyq ? ?ipyq ? 1 (so w ? y), by (B5)(ii) mHi`1pvi`1,vsq ?
mHipy,vsq{?ipyq for each vs P ??1i rzs ? ??1i`1rzs. By (C7)(iii) of induction hypothesis,
mHipy,vsq{?ipyq ?mHpy,zq{p?pyq?pzqq. So
mHi`1pvi`1,vsq ? mHpy,zq?pyq?pzq.
The other case, ?i`1pzq ??ipzq?1, is similar. This proves (C7)1(ii).
(iii)If?i`1pyq ??ipyq?1(sow ?y), then by (B5)(i)mHi`1py,vsq{?i`1pyq ?mHipy,vsq{?ipyq
foreachvs P??1i rzs ???1i`1rzs. But by(C7)(iii) of induction hypothesis,mHipy,vsq{?ipyq ?
mHpy,zq{p?pyq?pzqq for each vs P??1i rzs. Therefore
mHi`1py,vsq
?i`1pyq ?
mHpy,zq
?pyq?pzq
for each vs P ??1i`1rzs. If ?i`1pzq ? ?ipzq ? 1 (so z ? y), then since in forming Hi`1
no edge is detached from vs for each vs P ??1i rys, we have mHi`1pw,vsq ? mHipw,vsq
for each vs P ??1i rys. Therefore mHi`1pw,vsq{?i`1pwq ? mHipw,vsq{?ipwq for each
29
vs P ??1i rys. Moreover, by (B5)(ii) mHi`1pw,vi`1q ? mHipw,yq{?ipyq. Therefore
mHi`1pw,vi`1q{?i`1pwq ? mHipw,yq{p?ipwq?ipyqq. By (C7)(i) of induction hypothe-
sis, mHipw,yq{p?ipwq?ipyqq ?mHpw,yq{p?pwq?pyqq. Hence
mHi`1pw,vi`1q
?i`1pwq ?
mHpw,yq
?pwq?pyq.
This proves (C7)1(iii).
(C8)1 The proof is similar to the proof of (C7)1, following from (B6) and (C8) of the induction
hypothesis.
As a result of (C1)-(C8), we prove that G is loopless, and satisfies conditions (A1)-(A6) of
Theorem 2.1. Recall that Hn ? G, ?n ? ?, and ?npwq ? 1 for each w P V. Let w,z be an
arbitrary pair of distinct vertices of V, and let j P Zk. Now in (C1)-(C8) we let i?n. From
C1(ii) it is immediate that G is loopless.
From (C3)(i) it follows that dHnpwq{?npwq ? dHpwq{?pwq, so dGpwq ? dHpwq{?pwq.
From (C3)(ii), dHnpvrq ?dHpwq{?pwq for each vr P??1n rws, so dGpvrq ?dHpwq{?pwq for each
vr P??1rws. Therefore G satisfies (A1).
From (C5)(i) it follows that mHnpw,vrq{?npwq ? ?Hpwq{`?pwq2 ? for each vr P ??1n rws, so
mGpw,vrq ? ?Hpwq{`?pwq2 ? for each vr P ??1rws. From (C5)(ii), mHnpvr,vsq ? ?Hpwq{`?pwq2 ?
for every pair of distinct vertices vr,vs P??1n rws, so mGpvr,vsq ??Hpwq{`?pwq2 ? for every pair
of distinct vertices vr,vs P??1rws. Therefore G satisfies (A3).
From(C7)(i) it followsthatmHnpw,zq{p?npwq?npzqq ?mHpw,zq{p?pwq?pzqq, somGpw,zq ?
mHpw,zq{p?pwq?pzqq. From (C7)(ii), mHnpvr,vsq ? mHpw,zq{p?pwq?pzqq for each vr P
??1n rws and each vs P??1n rzs, so mGpvr,vsq ?mHpw,zq{p?pwq?pzqq for each vr P??1rws and
each vs P ??1rzs. From (C7)(iii) it follows that mHnpvr,zq{?npzq ? mHpw,zq{p?pwq?pzqq
for each vr P ??1n rws, so mGpvr,zq ? mHpw,zq{p?pwq?pzqq for each vr P ??1rws. From
(C7)(iii), mHnpw,vsq{?mpwq ? mHpw,zq{p?pwq?pzqq for each vs P ??1n rzs, so mGpw,vsq ?
mHpw,zq{p?pwq?pzqq for each vs P??1rzs. Therefore G satisfies (A5).
30
A similar argument shows that G satisfies (A2), (A4), (A6). In order to prove that G
satisfies the last condition (A7) of Theorem 2.1, it suffices to show that if for some j P Zk,
dHipjqpvq{?ipvq is even for all v PVi, then
(D1) dHi`1pjqpvq{?i`1pvq is an even integer for all v PVi`1, and
(D2) ?pHi`1pjqq ??pHipjqq.
For then, if for each v PVpHq ?V0, dHpjqpvq{?pvq ?dH0pjqpvq{?0pvq is an even integer, then
it follows inductively that for each 0 ? r ? n and each v P Vr, dHrpjqpvq{?rpvq is an even
integer and
?pHrpjqq ??pH0pjqq.
Therefore ?pGpjqq ? ?pHnpjqq ? ?pH0pjqq ? ?pHpjqq. This will complete the proof of
Theorem 2.1.
So we now establish (D1) and (D2). Let j P Zk be a color for which for all v P Vi,
dHipjqpvq{?ipvq is an even integer. Recall that y is the vertex for which ?i`1pyq ? ?ipyq? 1.
To establish (D1), there are three cases to consider:
? Case 1: v R ty,vi`1u. Clearly dHi`1pjqpvq ? dHipjqpvq and ?i`1pvq ? ?ipvq. So
dHi`1pjqpvq{?i`1pvq ?dHipjqpvq{?ipvq which is an even integer.
? Case 2: v ?y. From (B4)(i), it follows that dHi`1pjqpyq{?i`1pyq ?dHipjqpyq{?ipyq which
is an even integer.
? Case 3: v ? vi`1. From (B4)(ii), it follows that dHi`1pjqpvi`1q ? dHipjqpyq{?ipyq which
is an even integer.
This proves (D1).
In order to prove (D2), let Hyi pjq be the component of Hipjq which contains y. It is
enough to showthat?pHyi`1pjqq ??pHyi pjqq. Let?ij ??pHyi pjqztyuqand let ?i,j,1,...,?i,j,?ij
be the vertex sets of the components of Hyi pjqztyu. Note that ?i,j,r is a subset of VpBiq,
31
?i,j,?ij
?i,j,1
y
vi+1
y
Hyi+1(j)Hyi (j)
?i,j,1
?i,j,?ij
Figure 2.2: Detachment of Hyi pjq into Hyi`1pjq
of VpTiq, and of VpB1iq for 1 ? r ? ?ij. Since dHipjqpvq{?ipvq is an even integer for each
v PVi, it follows that dHipjqpvq is an even integer for each v PVi. Therefore Hipjq is an even
graph (all vertices are of even degree). Since dHipjqpyq is even, so is dHipjqpyq ? 2?Hipjqpyq.
Since Hipjq is an even graph, and the sum of the degree of the vertices in any graph must
be even, it follows that mHipjqpy,?i,j,tq ? mBipcij,?i,j,tq is even for 1 ? t ? ?ij. (In fact
every edge cut in Hipjq is even.) Now from (M2) it follows that for each t, 1 ? t ? ?ij,
mB1ip1qpCij,?i,j,tq ?mB1ipCij,?i,j,tq{2. There are two cases to consider:
? Case 1: mTipcij,?i,j,tq ?mBipcij,?i,j,tq. In this case we have
mB1ip1qpCij,?i,j,tq ? mB1ipCij,?i,j,tq2 ? mTipcij,?i,j,tq2 ? mBipcij,?i,j,tq2 .
32
? Case 2: mTipcij,?i,j,tq ?mBipcij,?i,j,tq. In this case we have
mB1ip1qpCij,?i,j,tq ? mB1ipCij,?i,j,tq2 ? mTipcij,?i,j,tq2 ? mBipcij,?i,j,tq2 .
Therefore in both cases mB1ip1qpCij,?i,j,tq ? mBipcij,?i,j,tq{2 for 1 ? t ? ?ij. This is shown
in Figure 2.2. This means, at most half of the edges joining y to ?i,j,t, 1 ? t ? ?ij, are
moved to vi`1 in forming Hi`1. So from each vertex u ? vi`1 in Hyi`1pjq, there is a path
of edges colored j from u to y. Moreover, vi`1 is either adjacent with y or is adjacent with
another vertex in Hyi`1pjq, so vi`1 is also joined to y by a path of edges colored j. Therefore
?pHyi`1pjqq ??pHyi pjqq. This proves (D2) and the proof of Theorem 2.1 is complete.
33
Chapter 3
Hamiltonian Decomposition of Kpn1,...,nm;?,?q
Let n1,...,nm P N, and ?,? P NYt0u. Let G ? Kpn1,..., nm;?,?q denote a graph
with m parts, the ith part having size ni, in which multiplicity of each pair of vertices in
the same part (in different parts) is ? (?, respectively). In other words, G is a graph with
m parts V1,...,Vm, with |Vi| ? ni for 1 ? i ? m, mGpu,vq ? ? for every pair of distinct
vertices u,v PVi for 1 ?i?m, and mGpu,vq ?? for each uPVi,v PVj for 1 ?i?j ?m.
When n1 ? ... ? nm ? n, we denote Kpn1,...,nm;?,?q by Kpnpmq;?,?q. In [5],
we settled the existence of Hamiltonian decomposition for Kpn1,...,nm;?,?q, a graph of
particular interest to statisticians, who consider group divisible designs with two associate
classes.
Example 3.1. Figure 3.1 illustrates a Hamiltonian decomposition of Kp2p3q;2,1q.
In this chapter, we present a constructive proof of this existence and we also solve the
companion problem; that is the Hamiltonian decompositions problem forKpn1,...,nm;?,?q
when it is a regular graph of odd degree (see [9]). The details are provided in order that the
reader may become more familiar with the nuances of using amalgamations.
A graph G is said to be even if all of its vertices have even degree. Let k be a positive
integer. We say that G has an evenly-equitable k-edge-coloring if G has a k-edge-coloring
for which, for each v PVpGq
(i) dGpiqpvq is even for 1 ?i?k, and
(ii) |dGpiqpvq?dGpjqpvq| P t0,2u for 1 ?i,j ?k.
34
Figure 3.1: A Hamiltonian Decomposition of Kp2p3q;2,1q
We need the following theorem of Hilton [43]. (It may help to recall that the definition
of k-edge-coloring allows some color classes to be empty. It is also worth noting that the
following theorem is true even if the graph contains loops.)
Theorem 3.2. (Hilton [43, Theorem 8]) Each finite even graph has an evenly-equitable
k-edge-coloring for each positive integer k.
3.1 Hamiltonian Decomposition of Kpn1 ...,nm;?,?q
Walecki?s construction for Hamiltonian decomposition of Kn and Kn ?F where F is a
1-factor [64], easily provides the following result:
Theorem 3.3. The graph ?Kn is Hamiltonian decomposable if and only if ?pn? 1q is an
even integer.
35
Using this result, together with Theorem 3.2 and Theorem 2.1, now we are able to find
necessary and sufficient conditions for Kpn1...,nm;?,?q to be Hamiltonian decomposable.
Let us first look at some trivial cases:
(i) If m ? 1, then G? ?Kn1 which by Theorem 3.3, is Hamiltonian decomposable if and
only if ?pn1 ?1q is even.
(ii) Ifm? 1,?? 0, thenG?
m?
i?1
?Kni. ClearlyGis disconnected and so is not Hamiltonian
decomposable.
(iii) If ni ? 1 for 1 ? i ? m, then G ? ?Km which is Hamiltonian decomposable if and
only if ?pm?1q is even.
(iv) If ? ? ?, then G ? ?Kn1`???`nm which is Hamiltonian decomposable if and only if
?p
m?
i?1
ni ?1q is even.
We exclude the above four cases from our theorem:
Theorem 3.4. (Bahmanian, Rodger [5, Theorem 4.3]) Let m ? 1, ? ? 0, and ? ? 1, with
??? be integers. Let n1,...,nm be positive integers with n1 ?...?nm, and nm ? 2. Then
G?Kpn1,...,nm;?,?q is Hamiltonian decomposable if and only if the following conditions
are satisfied:
(i) ni ?nj :?n for 1 ?i?j ?m;
(ii) ?pn?1q`?npm?1q is an even integer;
(iii) ???npm?1q.
Proof. Let s ?
m?
i?1
ni. To prove the necessity, suppose G is Hamiltonian decomposable.
For v P Vi, 1 ? i ? m, we have dGpvq ? ?pni ? 1q `?ps?niq. Since G is Hamiltonian
decomposable, it is regular. So we have ?pni ? 1q`?ps?niq ? ?pnj ? 1q`?ps?njq for
every pair 1 ? i ? j ? m. Equivalently ?pni ?njq ? ?pni ?njq. So p???qpni ?njq ? 0
36
and since ???, we have ni ?nj :?n for every pair 1 ?i?j ?m. So we can assume that
G?Kpnpmq;?,?q. Therefores?mnanddGpvq ??pn?1q`?pmn?nq ??pn?1q`?npm?1q.
Now by the Hamiltonian decomposability of G, the degree of each vertex
?pn?1q`?npm?1q is an even integer.
By the preceding paragraph, the number of Hamiltonian cycles of G is 12p?pn? 1q `
?npm? 1qq. Let us say that an edge is pure if both of its endpoints belong to the same
part. Each Hamiltonian cycle passes through every vertex of every part exactly once. Hence
each Hamiltonian cycle contains at most pn?1q pure edges from each part. Since the total
number of pure edges in each part is ?`n2?, we have
?
?n
2
?
? pn?1q2 p?pn?1q`?npm?1qq.
So,
?npn?1q
2 ?
pn?1q
2 p?pn?1q`?npm?1qq.
Since n ? 1, it implies that ?n ? ?pn? 1q`?npm? 1q. Thus ? ? ?npm? 1q. Therefore
conditions (i)-(iii) are necessary. Note that the necessity of condition (iii) can also be seen
as an edge-connectivity issue. Of course G has edge-connectivity at most ?n2pm? 1q, as
deleting all the edges incident with vertices in a fixed part disconnects the graph. SinceGhas
a Hamiltonian decomposition, it clearly has degree equal to its edge-connectivity. Therefore,
the degree of G, namely ?pn?1q`?npm?1q, is at most ?n2pm?1q.
To prove the sufficiency, suppose conditions (i)-(iii) are satisfied and let H be a graph
with |VpHq| ? m,?Hpyq ? ?`n2? for every y P VpHq, and mHpy,zq ? ?n2 for every pair
y,z P VpHq and let ? be a function from VpHq into N with ?pyq ? n for all y P VpHq. We
note that H is p?npn?1q`?n2pm?1qq-regular. It is easy to see that H is an amalgamation
of G. In what follows we shall find an appropriate edge-coloring for H and then we shall
37
apply Theorem 2.1, to show that H has a ?-detachment G in which every color class induces
a Hamiltonian cycle.
Let H? be the spanning subgraph of H whose edges are the non-loop edges of H. It
is easy to see that H? ? ?n2Km. We claim that ?npm? 1q is even. To see this, suppose
?npm? 1q is odd; then a is odd and ?pn? 1q is even. But then ?pn? 1q `?npm? 1q is
odd, contradicting condition (ii) of the theorem. Therefore ?n2pm?1q is even and thus by
Theorem 3.3, H? is Hamiltonian decomposable.
Since ?n2Km is ?n2pm?1q-regular, it is decomposable into ?n2pm?1q{2 Hamiltonian
cycles by Theorem 3.3. Now define k ? `?pn?1q`?npm?1q?{2. From (ii), k is an integer.
Now since n? 1 and ?npm?1q ??, we have the following sequence of equivalences:
pn?1qp?npm?1q??q ? 0 ??npm?1qpn?1q??pn?1q ? 0 ?
?n2pm?1q??pn?1q??npm?1q ? 0 ? ?n
2pm?1q
2 ?
?pn?1q`?npm?1q
2 .
Hence, the number of Hamiltonian cycles inH? is at leastk. Now letC1,...,Ck bek arbitrary
Hamilton cycles of a Hamiltonian decomposition ofH?. Let K? be a (partial)k-edge-coloring
of H? such that all edges of each cycle Ci are colored i, for each iP Zk. Now let H?? be the
spanning subgraph of H whose edges are all the edges of H that are uncolored in H?. Recall
that H is 2nk-regular, so for each v P VpH??q we have dH??pvq ? 2nk ? 2k ? 2pn? 1qk.
Therefore H?? is an even graph and so by Theorem 3.2 it has an evenly-equitable edge-
coloring K?? with k colors 1,...,k (Note that we are using the same colors we used to
color edges of H?). Therefore for each j, 1 ? j ? k, and for each y P VpH??q, we have
dH??pjqpyq ? 2pn?1qk{k ? 2pn?1q. Now we can define the edges coloring K : EpHq ? Zk
for H as below:
Kpeq ?
$
?&
?%
K?peq if ePEpH?qzEpH??q,
K??peq if ePEpH??q.
38
So for each j P Zk, for each y P VpHq, we have dHpjqpyq ? 2 ` 2pn? 1q ? 2n. Note that
since all edges of each Hamiltonian cycle Cj are colored j, 1 ? j ? k, each color class Hpjq
is connected.
So we have a k-edge-colored graph H for which, for each y,z P VpHq,y ? z, and
each j P Zk, ?pyq ? n ? 2, ?Hpyq ? ?`n2?, mHpy,zq ? ?n2, dHpyq ? 2nk, dHpjqpyq ? 2n,
?pHpjqq ? 1.
Now by Theorem 2.1 there exists a loopless ?-detachment G? of H with amalgamation
function ? : VpG?q ? VpHq, ? being the number function associated with ?, such that for
each y,z PVpHq,y ?z, and each j P Zk the following conditions are satisfied:
? mG?pu,u1q ??`n2?{`n2? ?? for every pair of distinct vertices u,u1 P??1pyq;
? mG?pu,vq ??n2{pnnq ?? for each uP??1pyq and each v P??1pzq;
? dG?pjqpuq ? 2n{n? 2 for each uP??1pyq;
? ?pG?pjqq ??pHpjqq ? 1, since dHpjqpyq{?pyq? 2n{n? 2.
From the first two conditions it follows thatG? ?Kpnpmq;?,?q ?G. The last two conditions
tells us that each color class is 2-regular and connected, respectively; that is each color class
is a Hamiltonian cycle. So we obtained a Hamiltonian decomposition of Kpnpmq;?,?q and
the proof is complete.
Remark 3.5. We may prove the necessity of condition (iii) of Theorem 3.4 by a different
counting argument. Let us say an edge is mixed if its endpoints are from different parts of
G. Each Hamiltonian cycle starts from a vertex of a part Vi for some 1 ?i ? m and it will
pass through every part at least once and it will eventually come back to the initial vertex
in Vi. Hence each Hamiltonian cycle contains at least m mixed edges. On the other hand,
the total number of mixed edges is ?n2`m2?. Therefore,
?n2
?m
2
?
?m12p?pn?1q`?npm?1qq.
39
So,
?n2mpm?1q
2 ?
mp?pn?1q`?npm?1qq
2 .
It implies that, ?npm?1qpn?1q??pn?1q ? 0, so pn?1qp?npm?1q??q ? 0 and since
n? 1, we have ???npm?1q.
Remark 3.6. Observe that the equality in condition (iii) of Theorem 3.4 holds if and only
if for each Hamiltonian decomposition, each Hamiltonian cycle contains exactly pn?1q pure
edges from every part, and exactly m mixed edges.
3.2 Hamiltonian Decomposition of Kpn1,...,nm;?,?q with a 1-factor leave
Let us first look at some trivial cases:
(i) If m ? 1, then G ? ?Kn1 which by Theorem 1.4, is decomposable into Hamiltonian
cycles and a single 1-factor if and only if ?pn1 ?1q is odd.
(ii) If m ? 1, ? ? 0, then G ?
m?
i?1
?Kni. Clearly G is disconnected it does not have any
Hamiltonian cycle.
(iii) If ni ? 1 for 1 ?i?m, then G??Km which is decomposable into Hamiltonian cycles
and a single 1-factor if and only if ?pm?1q is odd.
(iv) If ? ? ?, then G ? ?Kn1`???`nm which is decomposable into Hamiltonian cycles and a
single 1-factor if and only if ?p
m?
i?1
ni ?1q is even.
(v) If ? ? 0, and ni ? n for 1 ? i ? m, then G ? ?Kn,...,nlooomooon
m
which is decomposable into
Hamiltonian cycles and a single 1-factor if and only if ?npm?1q is odd (see [57]).
We exclude the above five cases from our theorem:
Theorem 3.7. Let m ? 1. Let n1,...,nm be positive integers with n1 ? ... ? nm, and
nm ? 2, and ?,? ? 1 with ? ? ?. Then G ? Kpn1,...,nm;?,?q is decomposable into
Hamiltonian cycles and a single 1-factor if and only if the following conditions are satisfied:
40
(i) ni ?nj :?n for 1 ?i?j ?m;
(ii) ?pn?1q`?npm?1q is an odd integer;
(iii) ???npm?1q if n? 3, and ??1 ? 2?pm?1q otherwise.
Proof. Let s ? ?mi?1ni. To prove the necessity, suppose G is Hamiltonian decomposable.
For v P Vi, 1 ? i ? m, we have dGpvq ? ?pni ? 1q `?ps?niq. Since G is Hamiltonian
decomposable, it is regular. So we have ?pni ? 1q`?ps?niq ? ?pnj ? 1q`?ps?njq for
1 ? i ? j ? m. It follows that ni ? nj :? n for 1 ? i ? j ? m. So we can assume that
G?Kpnpmq;?,?q. Therefore dGpvq ??pn?1q`?npm?1q. Now since G is decomposable
into Hamiltonian cycles and a single 1-factor
?pn?1q`?npm?1q is an odd integer.
By the preceding paragraph, the number of Hamiltonian cycles of G is `?pn ? 1q `
?npm? 1q ? 1?{2. Let us say that an edge is pure if both of its endpoints belong to the
same part. Each Hamiltonian cycle passes through every vertex of every part exactly once.
Hence each Hamiltonian cycle contains at most n?1 pure edges from each part. Since the
total number of pure edges in each part is ?`n2?, and a 1-factor contains at most ta{2u pure
edges from each part, we have
?
?n
2
?
? pn?1q2 `?pn?1q`?npm?1q?1?` tn2u.
So,
?npn?1q
2 ?
pn?1q
2
`?pn?1q`?npm?1q?1?` tn
2u.
Since n? 1, it implies that
?n??pn?1q`?npm?1q?1` 2t
n
2u
n?1.
41
It follows that if n is odd, then we have ? ? ?npm?1q, and if n ? 2 is even, then we have
???npm?1q`1{pn?1q, which is equivalent to ???npm?1q. Moreover, if n? 2, then
we have ??1 ? 2?pm?1q. Therefore conditions (i)-(iii) are necessary.
To prove the sufficiency, suppose conditions (i)-(iii) are satisfied. We first solve the
special case of n? 2. Since ?`2?pm?1q is odd, so is ?. Also ??1 ? 2?pm?1q. Therefore,
by Theorem 3.4, Kp2pmq;?? 1,?q is Hamiltonian decomposable. Adding an edge to each
part of Kp2pmq;? ? 1,?q (which is a 1-factor) will form Kp2pmq;?,?q. Thus we obtain a
decomposition of Kp2pmq;?,?q into Hamiltonian cycles and a single 1-factor. To prove the
sufficiency for n ? 3, let H be a graph with |VpHq| ? m,?Hpyq ? ?`n2? for every y P VpHq,
and mHpy,zq ? ?n2 for every pair y,z P VpHq and let ? be a function from VpHq into N
with ?pyq ? n for all y P VpHq. Now define k ? `?pn ? 1q ` ?npm? 1q ? 1?{2. From
(ii), k is an integer. We note that H is p2k` 1qn-regular. In what follows we shall find an
appropriate edge-coloring for H and then we shall apply Theorem 2.1, to show that H has
an ?-detachment G in which every color class except one induces a Hamiltonian cycle, the
exceptional color class being a -factor.
Let H? be the spanning subgraph of H whose edges are the non-loop edges of H. It is
easy to see that H? ? ?n2Km. We shall find a pk` 1q-edge-coloring for H. There are two
cases to consider, but first we observe that:
pn?1q`?npm?1q??? ? 0 ??
?npm?1qpn?1q??pn?1q ? 0 ??
?n2pm?1q??pn?1q??npm?1q ? 0 ??
?n2pm?1q
2 ?
?pn?1q`?npm?1q
2 .
(3.1)
? Case 1: n is even. It follows that ?n2pm? 1q is even and thus by Theorem 1.4,
H? is decomposable into ?n2pm?1q2 Hamiltonian cycles. Now since n ? 1, and since by
(iii) ?npm? 1q ? ?, by (3.1) it follows that the number of Hamiltonian cycles in H?
42
is greater than k. Now let C1,...,Ck be k arbitrary Hamilton cycles of a Hamiltonian
decomposition of H?. Let K? be a (partial) k-edge-coloring of H? such that all edges
of each cycle Ci are colored i, for each 1 ? i ? k. Now let L be a spanning subgraph
of H in which every vertex is incident with n{2 loops (observe that ?`n2? ? n{2); so
the graph L consists only of loops. Now let H?? be the spanning subgraph of H whose
edges are all edges in EpHqzEpLq that are uncolored in H?. Recall that H is p2k`1qn-
regular, so for each v PVpH??q we have dH??pvq ? p2k`1qn?2k?2pn{2q ? 2kpn?1q.
Therefore H?? is an even graph and so by Theorem 3.2 it has an evenly-equitable
edge-coloring K?? with k colors 1,...,k (Note that we are using the same colors we
used to color edges of H?). Therefore for each j, 1 ?j ?k, and for each y PVpH??q,
we have dH??pjqpyq ? 2pn? 1qk{k ? 2pn? 1q. Now we can define the pk ` 1q-edges
coloring K for H as below:
Kpeq :?
$
???
&
???
?%
K?peq if ePEpH?qzEpH??q,
K??peq if ePEpH??q,
k`1 if ePEpLq.
So for each y PVpHq,
dHpjqpyq ?
$?
&
?%
2pn?1q`2 ? 2n if 1 ?j ?k,
2pn{2q ?n if j ?k`1.
? Case 2: n is odd. Since ?pn?1q is even, and by (ii), ?pn?1q`?npm?1q is odd,
it follows that ?npm?1q is odd. So ?n2pm?1q is odd. Thus by Theorem 1.4, H? is
decomposable into `?n2pm?1q?1?{2 Hamiltonian cycles and a single 1-factor F.
By (3.1), it follows that
?n2pm?1q?1
2 ?
?pn?1q`?npm?1q?1
2 ?k.
43
Hence, the number of Hamiltonian cycles in H? is at least k. Now let C1,...,Ck be
k arbitrary Hamilton cycles of a Hamiltonian decomposition of H?. Let K? be a
(partial) k-edge-coloring of H? such that all edges of each cycle Ci are colored i, for
each 1 ? i ? k, and the single 1-factor F is colored k` 1. Now let L be a spanning
subgraph of H in which every vertex is incident with pn? 1q{2 loops (observe that
?`n2? ? pn? 1q{2). Now let H?? be the spanning subgraph of H whose edges are all
edges in EpHqzEpLq that are uncolored in H?. Recall that H is p2k`1qn-regular, so
for each v P VpH??q we have dH??pvq ? p2k`1qn?2k?1?2pn?1q{2 ? 2kpn?1q.
Therefore H?? is an even graph and so by Theorem 3.2 it has an evenly-equitable
edge-coloring K?? with k colors 1,...,k (Note that we are using the same colors we
used to color edges of H?). Therefore for each j, 1 ?j ?k, and for each y PVpH??q,
we have dH??pjqpyq ? 2pn? 1qk{k ? 2pn? 1q. Now we can define the pk ` 1q-edges
coloring K for H as below:
Kpeq :?
$
???
&
???
%
K?peq if ePEpH?qzEpH??q,
K??peq if ePEpH??q,
k`1 if ePEpLq.
So for each y PVpHq,
dHpjqpyq ?
$
?&
?%
2pn?1q`2 ? 2n if 1 ?j ?k,
1`2pn?1q{2 ?n if j ?k`1.
Note that since all edges of each Hamiltonian cycle Cj are colored j, 1 ? j ? k, each color
classHpjq is connected for 1 ?j ?k. Therefore in both cases, we have a pk`1q-edge-colored
graphH for which, for eachy,z PVpHq,y ?z, ?pyq ?n? 2, ?Hpyq ??`n2?,mHpy,zq ??n2,
44
dHpyq ? p2k`1qn, ?pHpjqq ? 1 for each 1 ?j ?k, and
dHpjqpyq ?
$
?&
?%
2n if 1 ?j ?k,
n if j ?k`1.
Now by Theorem 2.1, there exists a loopless ?-detachment G? of H in which each v PVpHq
is detached into v1,...,v?pvq such that for each u,v P VpHq,u ? v the following conditions
are satisfied:
? mG?pui,ui1q ??`n2?{`n2? ?? for 1 ?i?i1 ??puq;
? mG?pui,vi1q ??n2{pnnq ?? for 1 ?i??puq and 1 ?i1 ??pvq;
? dG?pjqpuiq ?
$
?&
?%
2n{n? 2 if 1 ?j ?k,
n{n? 1 if j ?k`1,
for 1 ?i??puq;
? ?pG?pjqq ? ?pHpjqq ? 1 for each 1 ? j ? k, since dHpjqpuq{?puq ? 2n{n ? 2 for
1 ?j ?k.
From the first two conditions it follows that G?Kpnpmq;?,?q. The last two conditions tells
us that each color class 1 ?j ?k is 2-regular and connected respectively; that is each color
class 1 ?j ?k is a Hamiltonian cycle. Furthermore, the color class k`1 is 1-regular. So we
obtained a decomposition of Kpnpmq;?,?q into Hamiltonian cycles and a single 1-factor.
45
Chapter 4
Embedding an Edge-colored Kpappq;?,?q into a Hamiltonian Decomposition of
Kpapp`rq;?,?q
4.1 Introduction
Recall that Kpappq;?,?q is a graph with p parts, each part having size a, in which the
multiplicity of each pair of vertices in the same part (in different parts) is? (?, respectively).
In this chapter we consider the following embedding problem: When can a graph decom-
position of Kpappq;?,?q be extended to a Hamiltonian decomposition of Kpapp`rq;?,?q for
r ? 0? A general result is proved, which is then used to solve the embedding problem for
all r ? ??a ` p?1a?1. The problem is also solved when r is as small as possible in two different
senses, namely when r ? 1 and when r ? ??a ?p`1.
LetG? pV,Eqbe a graph and letH ? tHiuiPI be a family of graphs whereHi ? pVi,Eiq.
We say that G has an H-decomposition if tEi : i P Iu partitions E and each Ei induces
an isomorphic copy of Hi. Graph decomposition in general has been studied for many
classes of graphs. The decomposition of a graph into paths [79], cycles [76] or stars [78]
has been of special interest over the years. Of particular interest is the decomposition of
a graph into Hamiltonian cycles; that is a Hamiltonian Decomposition. In 1892 Walecki
[64] proved the classic result that the complete graph Kn is decomposable into Hamiltonian
cycles if and only if n is odd. Laskar and Auerbach [57] settled the existence of Hamiltonian
decomposition of the complete multipartite graph Km,...,m. Alspach, Gavlas, and ?Sajna
[1, 76, 77] collectively solved the problem of decomposing the complete graph into isomorphic
cycles, but the problem remains open for different cycle lengths.
Another challenge is the companion embedding problem:
46
Let H ? tHiuiPI and H? ? tH?j ujPJ be two families of graphs. Given a graph G
with an H-decomposition and a graph G? which is a supergraph of G (or G is a subgraph
of G?), under what circumstances one can extend the H-decomposition of G into an H?-
decomposition of G?? In other words, given an edge-coloring of G (that can be considered
as a decomposition when each color class induces a graph in H), is it possible to extend this
coloring to an edge-coloring of G? so that each color class of G? induces a graph in H??
In this direction, Hilton [44] found necessary and sufficient conditions for a decom-
position of Km to be embedded into a Hamiltonian decomposition of Km`n, which later
was generalized by Nash-Williams [70]. Hilton and Rodger [48] considered the embedding of
Hamiltonian decompositions for complete multipartite graphs. For embedding factorizations
see [47, 74], where the connectivity of the graphs inH? is one defining property. We also note
that embedding problems first were studied for latin squares by M. Hall [41]. For extensions
of Hall?s theorem see [2, 3, 63].
The graphKpa1,...,ap;?,?qis of particular interest to statisticians, who consider group
divisible designs with two associate classes, beginning over 50 years ago with the work of
Bose and Shimamoto [22]. Decompositions of Kpa1,...,ap;?,?q into cycles of length m
have been studied for small values of m [37, 38, 39]. Recently, Bahmanian and Rodger have
settled the existence problem completely for longest (i.e. Hamiltonian) cycles in [5]. In this
chapter, we study conditions under which one can embed a decomposition of Kpappq;?,?q
into a Hamiltonian decomposition of Kpapp`rq;?,?q for r ? 0. Our proof is largely based on
our results in [5] (see Theorem 2.1).
4.2 Amalgamation and Graph Embedding
Recall that a detachment of H is, intuitively speaking, a graph G obtained from H by
splitting some or all of its vertices into more than one vertex. That is, to each vertex ? of
H there corresponds a subset V? of VpGq such that an edge joining two vertices ? and ? in
H will join some element of V? to some element of V?. If ? is a function from VpHq into
47
N (the set of positive integers), then an ?-detachment of H is a detachment of H in which
each vertex u of H splits into ?puq vertices. For a more precise definition of amalgamation
and detachment, we refer the reader to Chapter 1.
Since two graphs G and H related in the above manner have an obvious bijection
between the edges, an edge-coloring of G or H, naturally induces an edge-coloring on the
other graph. Hence an amalgamation of a graph with colored edges is a graph with colored
edges.
The technique of vertex amalgamation, which was developed in the 1980s by Rodger
and Hilton, has proved to be very powerful in decomposing of various classes of graphs. For
a survey about the method of amalgamation and embedding partial edge-colorings we refer
the reader to [4]. In [5], the authors proved a general detachment theorem for multigraphs.
For the purpose of this chapter we use a very special case of this theorem as follows:
Theorem 4.1. Let H be a k-edge-colored graph all of whose color classes are connected, and
let ? be a function from VpHq into N such that for each v P VpHq: (i) ?pvq ? 1 implies
?Hpvq ? 0, (ii) dHpjqpvq{?pvq is an even integer for 1 ? j ? k, (iii) `?pvq2 ? divides ?Hpvq,
and (iv) ?pvq?pwq divides mHpv,wq for each w P VpHqztvu. Then there exists a loopless
?-detachment G of H in which each v P VpHq is detached into v1,...,v?pvq, all of whose
color classes are connected, and for v PVpHq:
(i) mGpvi,vi1q ??Hpvq{`?pvq2 ? for 1 ?i?i1 ??pvq if ?pvq ? 2,
(ii) mGpvi,wi1q ?mHpv,wq{p?pvq?pwqq for w PVpHqztvu, 1 ?i??pvq and 1 ?i1 ??pwq,
and
(iii) dGpjqpviq ?dHpjqpvq{?pvq for 1 ?i??pvq and 1 ?j ?k.
Here is our main result:
48
Theorem 4.2. (Bahmanian, Rodger [10, Theorem 2]) Let G ? Kpappq;?,?q with a ? 1,
?? 0, ?? 1, ???, r ? 1, and let ?j ??`Gpjq?. For 1 ?j ?k, define
sj ??j pmod rq with 1 ?sj ?r, (4.1)
and suppose
k?
j?1
sj ?kr??a2
?r
2
?
. (4.2)
Then a k-edge-coloring of G can be embedded into a Hamiltonian decomposition of G? ?
Kpapp`rq;?,?q if and only if:
(i) k ? `?pa?1q`?app`r?1q?{2,
(ii) ???app`r?1q,
(iii) Every component of Gpjq is a path (possibly of length 0) for 1 ?j ?k, and
(iv) ?j ?ar for 1 ?j ?k.
Proof. By Theorem 3.4, for Kpapp`rq;?,?q to be Hamiltonian decomposable, conditions (i)
and (ii) are necessary and sufficient. (Condition (i) follows since k must be dG?pvq{2. Con-
dition (ii) follows since each Hamiltonian cycle must use at least p`r mixed edges, so there
must be sufficiently many mixed edges for all pure edges to be used.) For 1 ? j ? k, for
Gpjq to be extendable to a Hamiltonian cycle in Kpapp`rq;?,?q, the degree of each vertex
has to be at most 2, and thus every component must be a path. Moreover, since each new
vertex can link together two disjoint paths, the number of components of every color class
can not exceed the number of new vertices, ar. This proves the necessity of (i)?(iv).
Let G? pV,Eq, and let u be a vertex distinct from vertices in V. Define the new graph
G1 ? pV1,E1q with V1 ? V Ytuu by adding to G the vertex u incident with ?a2`r2? loops,
and adding ?ar edges between u and each vertex v in V (see Figure 4.1). Note that for each
v PV, dG1pvq ??pa?1q`?app?1q`?ar ??pa?1q`?app`r?1q ? 2k. Now we extend
49
?ar
?ar
w
G1
v
G
?puq ??a2`r2?
u
G2
w
G
?a2
u2u1
ur
?a
?a
v
Figure 4.1: G1 and its detachment G2
the k-edge-coloring of G to a pk`1q-edge-coloring of G1 as follows:
(A1) Each edge in G has the same color as it does in G1,
(A2) For every v P V, color the ?ar edges between v and u so that dG1pjqpvq ? 2 for
1 ? j ? k. Since dGpjqpvq ? 2 for 1 ? j ? k, and since dG1pvq ? 2k, this can be
done. Notice that for every component of Gpjq (which is a path), exactly two edges
(from end points of the path) are connected to u; so at this point dG1pjqpuq ? 2?j for
1 ?j ?k.
(A3) For 1 ?j ?k color r?sj (? 0) loops with j. This coloring of loops can be done, since
by condition (2) of the theorem we have:
k?
j?1
sj ?kr??a2
?r
2
?
??
k?
j?1
r?
k?
j?1
sj ??a2
?r
2
?
??
k?
j?1
pr?sjq ??a2
?r
2
?
??G1puq.
Moreover we color the remaining ?kj?1sj ?kr`?a2`r2? (? 0) loops with the new color
k`1. Thus for 1 ?j ?k,
dG1pjqpuq ? 2?j `2pr?sjq ? 2r`2p?j ?sjq,
50
and dG1pk`1qpuq ? 2
??
k
j?1sj ?kr`?a
2`r
2
??. By (1) d
G1pjqpuq is an even multiple of
r for 1 ? j ? k. Now to show that dG1pk`1qpuq is an even multiple of r, first we show
that ?kj?1?j ??a2pr{2.
?k
j?1?j ?
?k
j?1ppa?|EpGpjqq|q
? kpa?|E|
? pa`?pa?1q`?app`r?1q?{2?pa`?pa?1q`?app?1q?{2
? ?a2pr{2.
Notice that ?app`r?1q is even, since otherwise, in particular a would be odd, so k
would not be an integer. Thus,
dG1pk`1qpuq ? 2
?k
j?1?j `?a
2rpr?1q
? ?a2pr`?a2rpr?1q
? ?a2rpp`r?1q
? 0 pmod 2rq.
Let b1,...,bk`1 be even integers such that dG1pjqpuq ?bjr for 1 ?j ?k`1. Note that
for 1 ?j ?k, we have
bj{2 ? 1` ?j ?sjr ? 1` tar?1r u ? 1`pa?1q ?a.
Since each component ofGpjq is joined touinG1pjq, each color class ofG1 is connected.
Let ? be a function from V1 into N such that ?pvq ? 1 for each v PV, and ?puq ?r. Now by
Theorem 4.1, there exists an?-detachment G2 ofG1, all of whose color classes are connected,
(see Figure 4.1) in which u is detached into r new vertices u1,...,ur such that:
(a) mG2pui,ui1q ??a2`r2?{`r2? ??a2, for 1 ?i?i1 ?r;
51
(b) mG2pui,vq ??ar{r ??a for each v PV and each i, 1 ?i?r;
(c) dG2pjqpuiq ?bjr{r ?bj for 1 ?i?r and 1 ?j ?k`1.
We observe that dG2puiq ? app?aq ` pr ? 1q?a2 ? ?a2pp ` r ? 1q for 1 ? i ? r, and is
even. Note that by (c), dG2pjqpuiq ? dG2pjqpui1q and is even for 1 ? i ? i1 ? r, and we
know that dG2puiq ? 2ka for 1 ? i ? r. Therefore, since Gpk ` 1q is an even graph, (so
it has a 2-factorization), we can recolor each 2-factor of color class k ` 1 with a color j,
1 ? j ? k such that dG2pjqpuiq ? 2a. We let b11,...,b1k be even integers such that in the
resulting edge-coloring of G2 obtained from recoloring the color class k`1, dG2pjqpuq ? b1jr
for 1 ?j ?k.
Now we define the new graph G3 by adding ?`a2? loops on every vertex ui in G2, for
1 ? i ? r (see Figure 4.2). We extend the k-edge-coloring of G2 to a k-edge-coloring of G3
w
G
?a2
u2u1
ur
?a
?a
v
?`a2? loops
G3
Figure 4.2: G3
such that:
(B1) Each edge in G2 has the same color at it does in G3,
52
(B2) For 1 ?i?r and 1 ?j ?k, there are a?b1j{2 (? 0) loops incident with ui colored j.
This is possible, for the following reason:
k?
j?1
pa?b1j{2q ? ka? 12
k?
j?1
dG2pjqpu1q
? ka? 12dG2pu1q
? ka? 12?a2pp`r?1q
? a2`?pa?1q`?app`r?1q?? 12?a2pp`r?1q
? a2?pa?1q ??G3pu1q.
Since for1 ?j ?k,G2pjqisa connected spanning subgraph ofG3pjq,G3pjqis also connected.
Let ?1 be a function from V3 into N such that ?1pvq ? 1 for each v P V, and ?1puiq ? a for
1 ? i ? r. Now by Theorem 4.1, there exists an ?1-detachment G4 of G3, all of whose color
classes are connected, in which ui is detached into a new vertices ui1,...,uia for 1 ? i ? r
such that:
? mG4puij,uij1q ??`a2?{`a2? ?? for 1 ?i?r and 1 ?j ?j1 ?a;
? mG4puij,ui1j1q ??a2{a2 ?? for 1 ?i?i1 ?r and 1 ?j ?j1 ?a;
? mG4puij,vq ??a{a ?? for each v PV and for 1 ?i?r; and
? dG4pjqpuii1q ? 2a{a ? 2 for 1 ?i?r, 1 ?i1 ?a.
Therefore G4 ? Kpapp`rq;?,?q, and each color class in G4 is a Hamiltonian cycle, so the
proof is complete.
A natural perspective of this embedding problem is to keep a,p,? and ? fixed, and ask
for which values of r the embedding is possible. The following result completely settles this
question for all r ? ?pa?1q`?app?1q?apa?1q .
53
Theorem 4.3. (Bahmanian, Rodger [10, Theorem 3]) Let G ? Kpappq;?,?q with a ? 1,
?? 0, ?? 1, ???, and
r ? ?pa?1q`?app?1q?apa?1q . (4.3)
Then ak-edge-coloring ofGcan be embedded into a Hamiltonian decomposition ofKpapp`rq;?,?q
if and only if (i)?(iv) of Theorem 4.2 are satisfied.
Proof. It is enough to show that (4.3) implies (4.2). Since sj ? 1 for 1 ?j ?k, ?kj?1sj ?k.
Thus, if we show that k ?kr??a2`r2?, we are done. This is true by the following sequence
of equivalences:
kpr?1q ??a2
?r
2
?
??
pr?1q`?pa?1q`?app`r?1q? ??a2rpr?1q ??
?pa?1q ??apar?p?r`1q ??a`rpa?1q?pp?1q? ??
?pa?1q{p?aq ?rpa?1q?pp?1q ??
r ? ?pa?1q`?app?1q?apa?1q .
Another immediate corollary of Theorem 4.2 is the following complete solution to the
embedding problem when r ? 1:
Corollary 4.4. Let G ? Kpappq;?,?q with a ? 1, ? ? 0, ? ? 1, ? ? ?. Then a k-edge-
coloring of G can be embedded into a Hamiltonian decomposition of Kpapp`1q;?,?q if and
only if:
(i) k ? `?pa?1q`?ap?{2,
(ii) ???ap,
(iii) Every component of Gpjq is a path (possibly of length 0) for 1 ?j ?k, and
54
(iv) ?j ?a for 1 ?j ?k.
Proof. Since r ? 1, we have s1 ? ... ? sk ? 1, so k ? ?kj?1sj ? k??a2`12? ? k, and thus
condition (4.2) of Theorem 4.2 is satisfied.
Proposition 4.5. Whenever ???a and p?a, the embedding problem is completely solved
for all values of r ? 1.
Proof. Condition 4.3 can be rewritten as r ? ??a ` p?1a?1. Since we are assuming that ? ? ?a
and p ? a, we have ??a ` p?1a?1 ? 2. Therefore the result follows from Theorem 4.3 and
Corollary 4.4.
Example 4.6. A k-edge-coloring of Kp10p7q;2,5q can be embedded into a Hamiltonian
decomposition of Kp10p7`rq;2,5q for r ? 1 if and only if (i)?(iv) of Theorem 4.2 are satisfied.
The following result completely settles the embedding problem for the smallest value of
r in another sense, namely with respect to the inequality (ii) of Theorem 4.2; so it settles the
case where ???app`r?1q, or equivalently where r ? ??a ?p`1. The proof is similar to
that of Theorem 4.2, so only an outline of the proof is provided, the details being omitted.
The proof of the necessity of condition (ii) of Theorem 4.2 shows that, in a Hamiltonian
decomposition of Kpappq;?app`r ? 1q,?q, each Hamiltonian cycle contains exactly a? 1
pure edges from each part, and exactly p`r mixed edges.
Theorem 4.7. (Bahmanian, Rodger [10, Theorem 4]) Let a ? 1 and r,? ? 1. A k-edge-
coloring of G?Kpappq;?app`r?1q,?q can be embedded into a Hamiltonian decomposition
of G? ?Kpapp`rq;?app`r?1q,?q if and only if:
(i) k ??a2pp`r?1q{2,
(ii) Every component of Gpjq is a path (possibly of length 0) for 1 ?j ?k,
(iii) Gpjq has exactly a? 1 pure edges from each part, and at most p? 1 mixed edges for
1 ?j ?k, and
55
(iv) ?j ?r for 1 ?j ?k.
Proof. The necessity of (i)?(iii) follows as described in Theorem 4.2. Let mj be the number
of mixed edges in Gpjq. To extend each component P of Gpjq to a Hamiltonian cycle in G?,
two mixed edges have to join P to the new vertices, and since each Hamiltonian cycle in G?
contains exactly p`r mixed edges, we have that
mj `2?j ?p`r. (4.4)
Since Gpjq is a collection of paths, for 1 ? j ? k, we have |VpGpjqq| ? |EpGpjqq| ` ?j.
Therefore ap?mj `ppa?1q`?j and thus
mj `?j ?p. (4.5)
Combining (4.4) and (4.5) implies (iv).
To prove sufficiency, we define the graph G1 as it is defined in Theorem 4.2. We extend
the k-edge-coloring of G to a k-edge-coloring of G1 such that dG1pjqpvq ? 2 for each v P V
and 1 ? j ? k. This is possible by the same argument as in Theorem 4.2. At this point
dG1pjqpuq ? 2?j ? 2r for 1 ? j ? k. So we can color the loops incident with u such that
dG1pjqpuq ? 2r for 1 ?j ?k, simply by assigning the color j to r??j loops.
Now we detach the vertex u into r new vertices u1,...,ur to obtain the new graph G2
(as we did in the proof of Theorem 4.2). Note that dG2pjqpuiq ? 2r{r ? 2 for each i, 1 ?i?r
and each j, 1 ? j ? k. Now we define the new graph G3 by adding a? 1 loops of color j,
1 ?j ?k, on every vertex ui in G2, for each i, 1 ?i?r. So we have dG3pjqpuiq ? 2a. Using
Theorem 4.1, detach each vertex ui into a new vertices ui1,...,uia for 1 ? i ? r, to obtain
the new graph G4 in which, G4pjq is connected and dG4pjqpuii1q ? 2a{a ? 2 for 1 ? j ? k,
1 ?i?r, 1 ?i1 ?a. This completes the proof.
56
Chapter 5
Detachments of Amalgamated 3-uniform Hypergraphs : Factorization Consequences
5.1 Introduction
A detachment of a hypergraph F is, informally speaking, a hypergraph obtained from
F by splitting some or all of its vertices into more than one vertex. If G is a detachment of
F, thenF is an amalgamation ofG. AmalgamatingG, intuitively speaking, can be thought
of as taking G, partitioning its vertices, then for each element of the partition squashing the
vertices to form a single vertex in the amalgamated hypergraph F. We shall give more
precise definition for amalgamation and detachment in Section 5.2.
Perhaps the most interesting use of amalgamations has been to prove embedding results;
see, for example [2, 3, 47, 51, 70, 74]. Detachments of graphs have also been studied in
[18, 49], generalizing some results of Nash-Williams [69, 68]. For a survey about the method
of amalgamation and embedding partial edge-colorings we refer the reader to [4].
Most of the results in graph amalgamation have used edge-coloring techniques due to
de Werra [80, 81, 82, 83], however Nash-Williams [70] proved a lemma (see Lemma 1.3) to
generalize theorems of Hilton and Rodger. In this chapter we apply Nash-Williams technique
to produce a general detachment theorem for 3-uniform hypergraphs (see Theorem 5.3).
This result is not only a substantial generalization of previous amalgamation theorems,
but also yields several consequences on factorizations of complete 3-uniform multipartite
(multi)hypergraphs. To demonstrate the power of our detachment theorem, we show that
the complete 3-uniformn-partite multi-hypergraph ?K3m1,...,mn can be expressed as the union
G1 Y...YGk of k edge-disjoint factors, where for i? 1,...,k, Gi is ri-regular, if and only if:
(i) mi ?mj :?m for all 1 ?i,j ?k,
57
(ii) 3 cwmrimn for each i, 1 ?i?k, and
(iii) ?ki?1ri ??`n?12 ?m2.
It is expected that Theorem 5.3 can be used to provide conditions under which one
can embed a k-edge-colored complete 3-uniform hypergraph K3n into an edge-colored K3n`m
such that ith color class of K3n`m induces an ri-factor for i ? 1,...,k. However obtaining
such results will require more advanced edge-coloring techniques and it will be much more
complicated than for companion results for simple graphs, with a complete solution unlikely
to be found in the near future (see [11]).
In connection with Kirkman?s famous Fifteen Schoolgirls Problem [56], Sylvester re-
marked in 1850 that the complete 3-uniform hypergraph with 15 vertices, is 1-factorizable.
Several generalizations of this problem were solved during the last 70 years (see for exam-
ple [71, 73, 15, 16]). It was Baranyai, who died tragically in his youth, who settled this
120-year-old problem (1-factorization of complete uniform hypergraphs) ingeniously [15, 16].
Baranyai?s proof actually yields a method for constructing a 1-factorization recursively.
However, this approach would not be very efficient and its complexity is exponential [53].
Baranyi?s original theorem was spurred by Peltesohn?s result [71] which was a direct con-
struction, and it was polynomial time to implement. Brouwer and Schrijver gave an elegant
proof for 1-factorizations of the complete uniform hypergraph for which the algorithm is
more efficient [25]. Our construction leads to an algorithm similar to that of Brouwer and
Schrijver. This is discussed briefly in Section 5.6, but for more details we refer the reader to
Chapter 10.
Notation and more precise definitions will be given in Section 5.2. Any undefined term
may be found in [20]. In Section 5.3, we state our main result and we postpone its proof to
Section 5.5. In Section 5.4, we exhibit some applications of our result by providing several
factorization theorems for 3-uniform (multi)hypergraphs. The key idea used in proving the
main theorem is short and is given in 5.5.1. The rest of Section 5.5 is devoted to the
verification of all conditions in Theorem 5.3.
58
5.2 Notation and More Precise Definitions
Forthepurpose ofthischapter, a hypergraph G isan ordered quintuplepVpGq,EpGq,HpGq,
?,?q where VpGq,EpGq,HpGq are disjoint finite sets, ? : HpGq ? VpGq is a function and
? : HpGq ?EpGq is a surjection. Elements of VpGq,EpGq,HpGq are called vertices, hyper-
edges and hinges of G, respectively. A vertex v and hinge h are said to be incident with
each other if ?phq ? v. A hyperedge e and hinge h are said to be incident with each other
if ?phq ? e. A hinge h is said to attach the hyperedge ?phq to the vertex ?phq. In this
manner, the vertex ?phq and the hyperedge ?phq are said to be incident with each other.
If e P EpGq, and e is incident with n hinges h1,...,hn for some n P N, then the hyperedge
e is said to join (not necessarily distinct) vertices ?ph1q,...,?phnq. If v P VpGq, then the
number of hinges incident with v is called the degree of v and is denoted by dGpvq.
The number of vertices incident with a hyperedge e, denoted by |e|, is called the size of
e. If |e| ? 1 then e is called a loop. If for all hyperedges e of G, |e| ? 2 and |??1peq| ? 2,
then G is a graph. If n ? 1 and e1,...,en are n distinct hyperedges of G, incident with the
same set of vertices, then e1,...,en is said to be multiple hyperedges. A multi-hypergraph is
a hypergraph with multiple hyperedges.
Thus a hypergraph, in the sense of our definition is a generalization of a finite hypergraph
as usually defined, but for convenience, we imagine each hyperedge of a hypergraph to be
attached to the vertices which it joins by in-between objects called hinges. In fact if for every
edge e, |e| ? |??1peq|, then our definition is essentially the same as the usual definition. One
can think of a hypergraph as a bipartite multigraph, where E forms one class, V forms
other class, and the hinges H form the edges. A hypergraph may be drawn as a set of
points representing the vertices. An edge is represented by a simple closed curve enclosing
its incident vertices. A hinge is represented by a small line attached to the vertex incident
with it (see Figure 5.1).
59
Example 5.1. Let F ? pV,E,H,?,?q, with V ? tvi : 1 ? i ? 7u,E ? te1,e2,e3u,H ?
thi : 1 ? i ? 9u, such that ?ph1q ? v1,?ph2q ? ?ph3q ? v2,?ph4q ? v3,?ph5q ? ?ph6q ?
?ph7q ? v4,?ph8q ? v5,?ph9q ? v6 and ?ph1q ? e1,?ph2q ? ?ph3q ? ?ph4q ? ?ph5q ?
?ph6q ? e2,?ph7q ? ?ph8q ? ?ph9q ? e3. Moreover |e1| ? 1,|e2| ? |e3| ? 3, and dpv1q ?
dpv3q ?dpv5q ?dpv6q ? 1,dpv2q ? 4,dpv4q ? 3,dpv7q ? 0.
h7
h6
h5
v7
v5
h8
v6
h9
e3
e2
e1
v1
h1
h4
v3
v2
h3
h2
F
v4
Figure 5.1: Representation of a hypergraph F
Throughout this chapter, the letters F and G denote hypergraphs (possibly with loops
and multiple hyperedges). The set of hinges of G which are incident with a vertex v
(a hyperedge e), is denoted by HpG,vq (HpG,eq, respectively). Thus if e P EpGq, then
HpG,eq ? ??1peq. If v P VpGq, then HpG,vq ? ??1pvq, and |HpG,vq| is the degree dpvq of
v. If S is a subset of VpGq or EpGq, then HpG,Sq denotes the set of those hinges of G which
are incident with an element of S. If S1 ?VpGq and S2 ?EpGq, then HpG,S1,S2q denotes
HpG,S1qXHpG,S2q. If v PVpGq and S ?EpGq, then HpG,v,Sq denotes HpG,tvu,Sq. To
avoid ambiguity, subscripts may be used to indicate the hypergraph in which hypergraph-
theoretic notation should be interpreted ? for example, dGpvq.
Let G be a hypergraph in which each hyperedge is incident with exactly three hinges.
If u,v,w are three (not necessarily distinct) vertices of G, then ?pu,v,wq denotes the set of
hyperedges which are incident with u,v,w. For each hyperedge e incident with three hinges
h1,h2,h3 there are three possibilities (see Figure 5.2):
60
(i) e is incident with exactly one vertex u. In this case u is incident with h1,h2,h3. We
denote ?pu,u,uq by ?pu3q.
(ii) e is incident with exactly two distinct vertices u,v. In this case one of the vertices, say
uis incident with two hinges, sayh1,h2 and v is incident with h3. We denote ?pu,u,vq
by ?pu2,vq.
(iii) e is incident with three distinct vertices u,v and w.
For multiplicity we use mp.q rather than |?p.q|. A hypergraph G is said to be k-uniform
u
h2
e
(ii) (iii)
e v
h1
h3
(i)
e
u
h2
h3
v
u
h1
w
h1
h2
h3
Figure 5.2: The three types of edges in a hypergraph G in which |HpG,eq| ? 3 for every
edge e
if |e| ? |HpG,eq| ? k for each e P EpGq. A k-uniform hypergraph with n vertices is said
to be complete, denoted by Kkn, if every k distinct vertices are incident within one edge. A
3-uniform hypergraph with vertex partition tV1,...,Vnu with |Vi| ? mi for i ? 1,...,n, is
said to be (i) n-partite, if every edge is incident with at most one vertex of each part, and (ii)
complete n-partite, denoted by K3m1,...,mn, if it is n-partite and every three distinct vertices
from three different parts are incident.
If we replace every hyperedge of G by ? (? 2) multiple hyperedges, then we denote the
new (multi) hypergraph by ?G. A k-hyperedge-coloring of G is a mapping K : EpGq ? C,
61
where C is a set of k colors (often we use C ? t1,...,ku), and the hyperedges of one color
form a color class. The sub-hypergraph of G induced by the color class j is denoted by Gpjq.
A hypergraphG is said to be (i) regular if there is an integerdsuch that every vertex has
degree d, and (ii) k-regular if every vertex has degree k. A factor of G is a regular spanning
sub-hypergraph of G. A k-factor is a k-regular factor. A factorization is a decomposi-
tion (partition) of EpGq into factor(s). Let r1,...,rk be (not necessarily distinct) positive
integers. An pr1,...,rkq-factorization is a factorization in which there is one ri-factor for
i? 1,...,k. An prq-factorization is called simply an r-factorization. A hypergraph G is said
to be factorizable if it has a factorization. The definition for k-factorizable and pr1,...,rkq-
factorizable hypergraphs is similar.
If F ? pV,E,H,?,?q is a hypergraph and ? is a function from V onto a set W, then
we shall say that the hypergraph G ? pW,E,H,???,?q is an amalgamation of F and that
F is a detachment of G. In this manner, ? is called an amalgamation function, and G is
the ?-amalgamation of F. Associated with ? is the number function g : W ? N defined
by gpwq ? |??1pwq|, for each w P W, and we shall say that F is a g-detachment of G.
Intuitively speaking, a g-detachment of G is obtained by splitting each u P VpGq into gpuq
vertices. Thus F and G have the same hyperedges and hinges, and each vertex v of G is
obtained by identifying those vertices of F which belong to the set ??1pvq. In this process,
a hinge incident with a vertex u and a hyperedge e in F becomes incident with the vertex
?puq and the edgeeinG. Since two hypergraphsF andG related in the above manner have
the same hyperedges, coloring the hyperedges of one of them is the same thing as coloring the
hyperedges of the other. Hence an amalgamation of a hypergraph with colored hyperedges
is a hypergraph with colored hyperedges.
Example 5.2. Let F be the hypergraph of Example 5.1. Let ? : V ? tw1,w2,w3,w4u be
the function with ?pv1q ? ?pv7q ? w1, ?pv2q ? w2, ?pv3q ? ?pv4q ? w3, ?pv5q ? ?pv6q ?
w4. The hypergraph G in Figure 5.3 is the ?-amalgamation of F.
62
h9
h6
w3
e1
h1 h7
h3
w4
h8
h2w
2
h5
h4
G
w1
e3
e2
Figure 5.3: Amalgamation G of the hypergraph F in Example 5.1
5.3 Statement of the Main Theorem
In the remainder of this chapter, all hypergraphs are either 3-uniform or are amalgama-
tions of 3-uniform hypergraphs. That is, for every hypergraph F we have
1 ? |e| ? |HpF,eq| ? 3 for every e in F. (5.1)
Therefore every edge is of one the types shown in Figure 5.2. For g : VpFq ? N, we define
the symmetric function ?g : V3pFq ? N such that for distinct x,y,z P VpFq, ?gpx,x,xq ?
`gpxq
3
?, ?gpx,x,yq ? `gpxq
2
?gpyq, and ?gpx,y,zq ? gpxqgpyqgpzq. Also we assume that for each
x P VpFq, gpxq ? 2 implies mFpx3q ? 0, and gpxq ? 1 implies mFpx2,yq ? 0 for every
y PVpFq.
Theorem 5.3. Let F be ak-hyperedge-colored hypergraph and let g be a function from VpFq
into N. Then there exists a 3-uniform g-detachment G (possibly with multiple hyperedges) of
F with amalgamation function ? : VpGq ? VpFq, g being the number function associated
with ?, such that G satisfies the following conditions:
(A1) dGpuq ?dFpxq{gpxq for each xPVpFq and each uP ??1pxq;
(A2) dGpjqpuq ?dFpjqpxq{gpxq for each xPVpFq, each uP ??1pxq and each j P t1,...,ku;
63
(A3) mGpu,v,wq ? mFpx,y,zq{?gpx,y,zq for every x,y,z P VpFq with gpxq ? 3 if x ?
y ? z, and gpxq ? 2 if |tx,y,zu| ? 2, and every triple of distinct vertices u,v,w with
uP ??1pxq, v P ??1pyq and w P ??1pzq;
(A4) mGpjqpu,v,wq ? mFpjqpx,y,zq{?gpx,y,zq for every x,y,z P VpFq with gpxq ? 3 if
x ? y ? z, and gpxq ? 2 if |tx,y,zu| ? 2, every triple of distinct vertices u,v,w with
uP ??1pxq, v P ??1pyq and w P ??1pzq and each j P t1,...,ku.
5.4 Factorization Consequences
Throughout this section n? 3. It is easy to see that every factorizable hypergraph must
be regular. If G is a 3-uniform hypergraph with an r-factor, since each edge contributes 3
to the sum of the degree of all vertices in an r-factor, r|VpGq| must be divisible by 3.
5.4.1 Factorizations of ?K3n
We first note that ?K3n is ?`n?12 ?-regular, and |Ep?K3nq| ? ?`n3?. Throughout this
section, F is a hypergraph consisting of a single vertex x and ?`n3? loops incident with x,
and g : VpFq ? N is a function with gpxq ?n. Note that ?K3n is a g-detachment of F.
Theorem 5.4. ?K3n is pr1,...,rkq-factorizable if and only if
(i) 3 cwmrin for each i, 1 ?i?k, and
(ii) ?ki?1ri ??`n?12 ?.
Proof. Suppose first that ?K3n is pr1,...,rkq-factorizable. The existence of each ri-factor
implies that 3 cwm rin for each i, 1 ? i ? k. Since each ri-factor is an ri-regular spanning
sub-hypergraph and ?K3n is ?`n?12 ?-regular, we must have ?ki?1ri ??`n?12 ?.
64
Now assume (i)?(ii). We find ak-hyperedge-coloring forF such thatmFpjqpx3q ?rjn{3
for each j P t1,...,ku. It is possible, because
k?
j?1
mFpjqpx3q ?
k?
j?1
rjn
3 ?
n
3
k?
j?1
rj
? ?n3
?n?1
2
?
??
?n
3
?
?mFpx3q.
Now by Theorem 5.3, there exists a 3-uniform g-detachment G of F with n vertices, say
v1,...,vn such that by (A2) dGpjqpviq ? rjn{n ? rj for each i ? 1,...,n and each j P
t1,...,ku; and by (A3) mGpvr,vs,vtq ? ?`n3?{`n3? ? ? for distinct r,s,t, 1 ? r,s,t ? n.
Therefore G ??K3n and each color class i is an ri-factor for i? 1,...,k.
5.4.2 Factorizations of K3m1,...,mn
We denote K3m,...,mloooomoooon
n
by K3m,...,m (so we don?t write the under-brace when it is not am-
biguous). We first note that?K3m,...,m is a?`n?12 ?m2-regular hypergraph withnmvertices and
?`n3?m3 edges. Throughout this section, F ??m3K3n with vertex set VpFq ? tx1,...,xnu,
and g : VpFq ? N is a function with gpxiq ? m for i ? 1,...,n. We observe that ?K3m,...,m
is a g-detachment of F.
Theorem 5.5. ?K3m1,...,mn is pr1,...,rkq-factorizable if and only if
(i) mi ?mj :?m for 1 ?i?j ?n,
(ii) 3 cwmrimn for each i, 1 ?i?k, and
(iii) ?ki?1ri ??`n?12 ?m2.
Proof. Suppose first that ?K3m1,...,mn is r-factorizable (so it is regular). Let u and v be
two vertices from two different parts, say pth and qth parts respectively. Then we have the
following sequence of equivalences:
65
dpuq ?dpvq ??
?
1?i?j?n
i,j?p
mimj ?
?
1?i?j?n
i,j?q
mimj ??
mq
?
1?i?n
i?p,q
mi `
?
1?i?j?n
i,jRtp,qu
mimj ?mp
?
1?i?n
i?p,q
mi `
?
1?i?j?n
i,jRtp,qu
mimj ??
mq
?
1?i?n
i?p,q
mi ?mp
?
1?i?n
i?p,q
mi ??
pmp ?mqq
?
1?i?ni?p,q mi ? 0 ??
mp ?mq :?m. pn? 3q
This proves (i). The existence of each ri-factor implies that 3 cwmrimn for each i, 1 ?i?
k. Since each ri-factor is an ri-regular spanning sub-hypergraph and K3m,...,m is ?`n?12 ?m2-
regular, we must have ?ki?1ri ??`n?12 ?m2.
Now assume (i)?(iii). Since 3 cwmrimn for each i, 1 ?i?k and ?ki?1mri ??`n?12 ?m3, by
Theorem 5.4,F ispmr1,...,mrkq-factorizable. Therefore we can find ak-hyperedge-coloring
for F such that
dFpjqpxq ?rjm @j P t1,...,ku.
Now by Theorem 5.3, there exists a 3-uniform g-detachment G of F with mn vertices, say
xij, 1 ? i ? n, 1 ? j ? m (xi1,...,xim are obtained by splitting xi into m vertices for
i ? 1,...,n) such that by (A2) dGptqpxijq ? rtm{m ? rt for each i ? 1,...,n, j ? 1,...,m,
and each t P t1,...,ku; by (A3) mGpxij,xij1,xij2q ? 0 for i ? 1...,n and distinct j,j1,j2,
1 ? j,j1,j2 ? m, if m ? 3; by (A3) mGpxij,xij1,xi1j2q ? 0 for distinct i,i1, 1 ? i,i1 ? n and
distinct j,j1, 1 ?j,j1,j2 ?m, if m? 2; and by (A3) mGpxij,xi1j1,xi2j2q ??m3{pmmmq ??
for distinct i,i1,i2, 1 ? i,i1,i2 ? n and 1 ? j,j1,j2 ? m. Therefore G ? ?K3m,...,m and each
color class i is an ri-factor for each iP t1,...,ku.
66
5.5 Proof of the Main Theorem
Recall that x ? y means tyu ? x ? rys. We observe that for x,y P R,a,b,c P Z, and
n P N (i) a ? x implies a P ttxu,rxsu, (ii) x ? y implies x{n ? y{n (iii) the relation ? is
transitive (but not symmetric), and (vi) a ? b?c and c ? x, implies a ? b?x. These
properties of ? will be used in this section when required without further explanation.
Let F ? pV,E,H,?,?q. Let n ? ?vPV pgpvq? 1q. Our proof of Theorem 5.3 consists
of the following major parts. First, in Section 5.5.1 we shall describe the construction of
a sequence F0 ? F,F1,...,Fn of hypergraphs where Fi is an amalgamation of Fi`1 (so
Fi`1 is a detachment of Fi) for 0 ?i?n?1 with amalgamation function ?i that combines
a vertex with amalgamation number 1 with one other vertex. To construct each Fi`1 from
Fi we will use two laminar families Ai and Bi. In Section 5.5.2 we shall observe some
properties of Fi`1 in terms of Fi. As we will see in Section 5.5.3, the relations between
Fi`1 and Fi lead to conditions relating each Fi, 1 ? i ? n to the initial hypergraph F.
Finally, in Section 5.5.4 we will show that Fn satisfies the conditions (A1)?(A4), so we can
let G ?Fn.
5.5.1 Construction of G
Initially we let F0 ?F and g0 ?g, and we let ?0 be the identity function from V into
V. Now assume that F0 ? pV0,E0,H0,?0,?0q,...,Fi ? pVi,Ei,Hi,?i,?iq and ?0,...,?i
have been defined for some i ? 0. Also assume that g0 : V0 ? N,...,gi : Vi ? N have been
defined such that for each j ? 0,...,i and each x PVj, gjpxq ? 2 implies mFjpx3q ? 0, and
gjpxq ? 1 implies mFjpx2,yq ? 0 for every y PVj. Let ?i ? ?0...?i. If i?n, we terminate
the construction, letting G ?Fn and ? ? ?n.
If i ? n, we can select a vertex ? of Fi such that gip?q ? 2. As we will see, Fi`1 is
formed from Fi by detaching a vertex vi`1 with amalgamation number 1 from ?.
Let Hij ? HpFipjq,?q for j ? 1,...,k. If e P Ei incident with ?, we let Heij ?
HpFipjq,?,eq for j ? 1,...,k. Recall that by (5.1), |Heij| ? 3. Intuitively speaking, Hij is
67
the set of all hinges which are incident with ? and a hyperedge colored j, and Heij is a subset
of Hij consisting of only those hinges incident with a single hyperedge e colored j. Now let
Ai ? tHpFi,?qu
? tH
i1,...,Hiku
? tHe
ij : eP ?p?
2,yq,y PVi,1 ?j ?ku. (5.2)
Note that
tHeij : eP ?p?2,yq,y PVi,1 ?j ?ku ? tHeij : eP ?p?3q,1 ?j ?ku
? tHe
ij : eP ?p?
2,yq,y PVizt?u,1 ?j ?ku.
If u,v PVi, let Huvi ? HpFi,?p?,u,vqq and Huvij ? HpFipjq,?,?p?,u,vqq for j ? 1,...,k.
Now let
Bi ? tHuvi : u,v PViu
? tHuv
ij : u,v PVi,1 ?j ?ku. (5.3)
It is easy to see that both Ai and Bi are laminar families of subsets of HpFi,?q. Then, by
Lemma 1.3, there exists a subset Zi of HpFi,?q such that
|Zi XP| ? |P|{gip?q, for every P PAi YBi. (5.4)
Let vi`1 be a vertex which does not belong to Vi and let Vi`1 ?Vi Ytvi`1u. Let ?i`1 be the
function from Vi`1 onto Vi such that ?i`1pvq ? v for every v P Vi and ?i`1pvi`1q ? ?. Let
Fi`1 be the detachment of Fi under ?i`1 (Fi is the ?i`1-amalgamation of Fi`1) such that
VpFi`1q ?Vi`1, and
68
HpFi`1,vi`1q ?Zi,HpFi`1,?q ?HpFi,?qzZi. (5.5)
In fact, Fi`1 is obtained from Fi by splitting ? into two vertices ? and vi`1 in such a
way that hinges which were incident with ? in Fi become incident in Fi`1 with ? or vi`1
according as they do not or do belong to Zi, respectively. Obviously, ?i is an amalgamation
function fromFi`1 intoFi. Letgi`1 be the function fromVi`1 into N, such thatgi`1pvi`1q ?
1,gi`1p?q ? gip?q? 1,gi`1pvq ? gipvq for every v P Vizt?u. This finishes the construction
of Fi`1. Now, we explore some relations between Fi`1 and Fi. In the remainder of this
chapter, dip.q, mip.q, dp.q, and mp.q will denotedFip.q, mFip.q, dFp.q, andmFp.q, respectively.
5.5.2 Relations Between Fi`1 and Fi
The hypergraph Fi`1, described in 5.5.1, satisfies the following conditions:
(B1) di`1p?q ?dip?qgi`1p?q{gip?q;
(B2) di`1pvi`1q ?dip?q{gip?q;
(B3) mi`1p?,v2q ?mip?,v2qgi`1p?q{gip?q for each v PVizt?u;
(B4) mi`1pvi`1,v2q ?mip?,v2q{gip?q for each v PVizt?u;
(B5) mi`1p?,u,vq?mip?,u,vqgi`1p?q{gip?q for every pair of distinct vertices u,v PVizt?u;
(B6) mi`1pvi`1,u,vq ?mip?,u,vq{gip?q for every pair of distinct vertices u,v PVizt?u;
(B7) mi`1pv2i`1,vq ? 0 for each v PVizt?u;
(B8) mi`1p?,vi`1,vq ? 2mip?2,vq{gip?q for each v PVizt?u;
(B9) mi`1p?2,vq ?mip?2,vqpgi`1p?q?1q{gip?q for each v PVizt?u;
(B10) mi`1pv3i`1q ?mi`1pv2i`1,?q ? 0;
(B11) mi`1p?3q ?mip?3qpgi`1p?q?2q{gip?q;
69
(B12) mi`1pvi`1,?2q ? 3mip?3q{gip?q.
Proof. Since HpFi,?q PAi, from (5.5) it follows that
di`1pvi`1q ? |HpFi`1,vi`1q| ? |Zi| ? |Zi XHpFi,?q|
? |HpFi,?q|{gip?q ?dip?q{gip?q,
di`1p?q ? |HpFi`1,?q| ? |HpFi,?q|?|Zi|
? dip?q?dip?q{gip?q ? pgip?q?1qdip?q{gip?q
? dip?qgi`1p?q{gip?q.
This proves (B1) and (B2).
If v PVizt?u, then Hvvi PBi and so
mi`1pvi`1,v2q ? |Zi XHvvi | ? |Hvvi |{gip?q ?mip?,v2q{gip?q,
mi`1p?,v2q ? |Hvvi |?|Zi XHvvi | ?mip?,v2q?mip?,v2q{gip?q
? pgip?q?1qmip?,v2q{gip?q
? mip?,v2qgi`1p?q{gip?q.
This proves (B3) and (B4) (see Figure 5.4(i)).
If u,v are a pair of distinct vertices in Vizt?u, then Huvi PBi and so
mi`1pvi`1,u,vq ? |Zi XHuvi | ? |Huvi |{gip?q ?mip?,u,vq{gip?q,
mi`1p?,u,vq ? |Huvi |?|Zi XHuvi |
? mip?,u,vq?mip?,u,vq{gip?q
? pgip?q?1qmip?,u,vq{gip?q
? mip?,u,vqgi`1p?q{gip?q.
This proves (B5) and (B6) (see Figure 5.4(ii)).
70
If v PVizt?u, and eP ?Fipjqp?2,vq, then Heij PAi, so
??Z
i XHeij
?? ? |He
ij|{gip?q ? 2{gip?q ? 1.
Therefore either |Zi XHeij| ? 1 and consequently e P ?Fi`1pvi`1,?,vq or Zi XHeij ? ? and
consequently eP ?Fi`1p?2,vq. Therefore
?Fi`1pv2i`1,vq ? ?.
This proves (B7) (see Figure 5.4(iii)). Moreover, since H?vi PBi
?
v
?
v
? v
u
v
? ?
? v
u
v
? ?
?
v
vi+1
vi+1
?
v
(i) (ii)
(iv)(iii)
u
vi+1
v
vi+1
Figure 5.4: The four possibilities for detachment of a single edge incident with ?
71
mi`1p?,vi`1,vq ? |Zi XH?vi | ? |H?vi |{gip?q ? 2mip?2,vq{gip?q,
mi`1p?2,vq ? mip?2,vq?|Zi XH?vi |
? mip?2,vq?2mip?,u,vq{gip?q
? pgip?q?2qmip?2,vq{gip?q
? mip?2,vqpgi`1p?q?1q{gip?q.
This proves (B8) and (B9). We note that from (B9) it follows that if gi`1p?q ? 1, then
mi`1p?2,vq ? 0.
If e is a loop in Fipjq incident with ?, (so gip?q ? 3,) then Heij PAi. So
|Zi XHeij| ? |Heij|{gip?q ? 3{gip?q ? 1.
Therefore either |Zi XHeij| ? 1 and consequently e P ?Fi`1p?2,vi`1q or Zi XHeij ? ? and
consequently eP ?Fi`1p?3q. Therefore
?Fi`1pv3i`1q ? ?Fi`1pv2i`1,?q ? ?.
This proves (B10) (see Figure 5.4(iv)). Moreover,
mi`1p?2,vi`1q ? |Zi XH??i | ? |H??i |{gip?q ? 3mip?3q{gip?q,
mi`1p?3q ? mip?3q?|Zi XH??i | ?mip?3q?3mip?3q{gip?q
? pgip?q?3qmip?3q{gip?q ?mip?3qpgi`1p?q?2q{gip?q.
This proves (B11) and (B12). We may note that from (B11) it follows that if gi`1p?q ? 2,
then mi`1p?3q ? 0.
A similar statement can be proved for every color class: Let us fix j P t1,...,ku, and let
u,v be a pair of distinct vertices in Vizt?u. The colored version of (B7) and (B10) is trivial.
72
Since Hij P Ai, Hvvij P Bi, Huvij P Bi, H?vij P Bi, H??ij P Bi, respectively, we can obtain a
colored version for (B1) and (B2), (B3) and (B4), (B5) and (B6), (B8) and (B9), and (B11)
and (B12), respectively.
5.5.3 Relations Between Fi and F
Recall that ?i ? ?0...?i, that ?0 : V ? V, and that ?i : Vi ? Vi?1 for i ? 0.
Therefore ?i : Vi ?V and thus ??1i : V ?Vi.
Now we use (B1)?(B12) to prove that the hypergraph Fi satisfies the following condi-
tions for 0 ?i?n :
(D1) dipxq{gipxq ?dpxq{gpxq for each xPV;
(D2) dipvrq ?dpxq{gpxq for each xPV and each vr P ??1i rxs;
(D3) mipx3q{`gipxq3 ? ?mpx3q{`gpxq3 ? for each xPV with gpxq ? 3 if gipxq ? 3, and mipx3q ? 0
otherwise;
(D4) mipv3rq ? 0 for each x PV and each vr P ??1i rxs;
(D5) mipx2,vrq{`gipxq2 ? ? mpx3q{`gpxq3 ? for each x P V with gpxq ? 3 and each vr P ??1i rxs if
gipxq ? 2, and mipx2,vrq ? 0 otherwise;
(D6) mipx,vr,vsq{gipxq ? mpx3q{`gpxq3 ? for each x P V with gpxq ? 3 and every pair of
distinct vertices vr,vs P ??1i rxs;
(D7) mipvr,vs,vtq ? mpx3q{`gpxq3 ? for each x P V with gpxq ? 3 and every triple of distinct
vertices vr,vs,vt P ??1i rxs;
(D8) mipx2,yq{p`gipxq2 ?gipyqq ? mpx2,yq{p`gpxq2 ?gpyqq for every pair of distinct vertices x,y P
V with gpxq ? 2 if gipxq ? 2, and mipx2,yq ? 0 otherwise;
(D9) mipx2,vtq{`gipxq2 ? ?mpx2,yq{p`gpxq2 ?gpyqq for every pair of distinct vertices x,y PV with
gpxq ? 2 and each vt P ??1i rys if gipxq ? 2, and mipx2,vtq ? 0 otherwise;
73
(D10) mipx,vr,yq{pgipxqgipyqq ?mpx2,yq{p`gpxq2 ?gpyqq for every pair of distinct vertices x,y P
V with gpxq ? 2 and each vr P ??1i rxs;
(D11) mipx,vr,vtq{gipxq ? mpx2,yq{p`gpxq2 ?gpyqq for every pair of distinct vertices x,y P V
with gpxq ? 2, each vr P ??1i rxs and each vt P ??1i rys;
(D12) mipvr,vs,yq{gipyq ? mpx2,yq{p`gpxq2 ?gpyqq for every pair of distinct vertices x,y P V
with gpxq ? 2 and every pair of distinct vertices vr,vs P ??1i rxs;
(D13) mipvr,vs,vtq ? mpx2,yq{p`gpxq2 ?gpyqq for every pair of distinct vertices x,y P V with
gpxq ? 2, every pair of distinct vertices vr,vs P ??1i rxs and each vt P ??1i rys;
(D14) mipx,y,zq{pgipxqgipyqgipzqq ?mpx,y,zq{pgpxqgpyqgpzqq for every triple of distinct ver-
tices x,y,z PV;
(D15) mipx,y,vtq{pgipxqgipyqq ?mpx,y,zq{pgpxqgpyqgpzqq for every triple of distinct vertices
x,y,z PV and each vt P ??1i rzs;
(D16) mipx,vs,vtq{gipxq ?mpx,y,zq{pgpxqgpyqgpzqqforevery tripleofdistinct verticesx,y,z P
V, each vs P ??1i rys and each vt P ??1i rzs;
(D17) mipvr,vs,vtq ?mpx,y,zq{pgpxqgpyqgpzqq for every triple of distinct vertices x,y,z PV,
each vr P ??1i rxs, each vs P ??1i rys and each vt P ??1i rzs.
Proof. Let x,y,z be an arbitrary triple of distinct vertices of V. We prove (D1)?(D17) by
induction. To verify (D1)?(D17) for i? 0, recall that F0 ?F, and g0pxq ?gpxq.
Obviously d0pxq{g0pxq ? dpxq{gpxq, and this proves (D1) for i ? 0. (D2) is trivial. If
gpxq ? 3, obviouslym0px3q{`g0pxq3 ? ?mpx3q{`gpxq3 ?, and ifgpxq ? 2, by hypothesis of Theorem
5.3, mpx3q ? 0. This proves (D3) for i? 0. The proof of (D4)?(D17) for i? 0 is similar and
can be verified easily.
Now we will show that if Fi satisfies the conditions (D1)?(D17) for some i ? n, then
Fi`1 (formed from Fi by detaching vi`1 from the vertex ?) satisfies these conditions by
74
replacing i with i`1; we denote the corresponding conditions for Fi`1 by (D1)1?(D17)1. If
gi`1pxq ? gipxq, then (D1)1?(D7)1 are obviously true. So we just check (D1)1?(D7)1 in the
case where x??. Also if gi`1pxq ?gipxq and gi`1pyq ?gipyq, then (D8)1?(D13)1 are clearly
true. So in order to prove (D8)1?(D13)1, we shall assume that either gi`1pxq ? gipxq ? 1
or gi`1pyq ? gipyq ? 1 (so ? P tx,yu). Similarly, if gi`1pxq ? gipyq,gi`1pyq ? gipyq, and
gi`1pzq ? gipzq, then (D14)1?(D17)1 are true. Therefore to prove (D14)1?(D17)1 we shall
assume that either gi`1pxq ? gipxq ? 1 or gi`1pyq ? gipyq ? 1 or gi`1pzq ? gipzq ? 1 (so
?P tx,y,zu).
(D1)1 By (B1), di`1p?q{gi`1p?q ? dip?q{gip?q, and by (D1) of the induction hypothesis
dip?q{gip?q ?dp?q{gp?q. Therefore
di`1p?q
gi`1p?q
(B1)? dip?q
gip?q
(D1)? dp?q
gp?q.
This proves (D1)1.
(D2)1 By(B2),di`1pvi`1q ?dip?q{gip?q, and by (D1)oftheinduction hypothesisdip?q{gip?q ?
dp?q{gp?q. Therefore
di`1pvi`1q(B2)? dip?qg
ip?q
(D1)? dp?q
gp?q.
Since in forming Fi`1 no hyperedge is detached from vr for each vr P ??1i r?s, we have
di`1pvrq ? dipvrq. By (D2) of the induction hypothesis dipvrq ? dp?q{gp?q for each
vr P ??1i r?s. Therefore
di`1pvrq ?dipvrq(D2)? dp?qgp?q
for each vr P ??1i r?s. This proves (D2)1.
75
(D3)1 Suppose gp?q ? 3. If gi`1p?q ? 3, by (B11)
mi`1p?3q`
gi`1p?q
3
? (B11)? mip?
3qpgi`1p?q?2q
gip?q`gi`1p?q3 ?
? mip?
3qpgi`1p?q?2q
gip?qgi`1p?qpgi`1p?q?1qpgi`1p?q?2q{6
? mip?
3q
`g
ip?q
3
?.
Sincegip?q ? 4 ? 3, by (D3) of the induction hypothesismip?3q{`gip?q3 ? ?mp?3q{`gp?q3 ?.
Therefore
mi`1p?3q`
gi`1p?q
3
? (B11)? mip?
3q
`g
ip?q
3
? (D3)? mp?
3q
`gp?q
3
?.
If gi`1p?q ? 3, by (B11) mi`1p?3q ? 0. This proves (D3)1.
(D4)1 By (B10), mi`1pv3i`1q ? 0. Moreover, mi`1pv3rq ? mipv3rq ? 0 for each 1 ? r ? i. This
proves (D4)1.
(D5)1 Suppose gp?q ? 3. If gi`1p?q ? 2, by (B12)
mi`1p?2,vi`1q`
gi`1p?q
2
? (B12)? 3mip?
3q
gip?q`gi`1p?q2 ?
? 3mip?
3q
gip?qgi`1p?qpgi`1p?q?1q{2
? mip?
3q
`g
ip?q
3
?.
Since gip?q ? 3, by (D3) of the induction hypothesis mip?3q{`gip?q3 ? ? mp?3q{`gp?q3 ?.
Therefore
mi`1p?2,vi`1q`
gi`1p?q
2
? (B12)? mip?
3q
`g
ip?q
3
? (D3)? mp?
3q
`gp?q
3
?.
76
By (B9) for each vr P ??1i r?s
mi`1p?2,vrq`
gi`1p?q
2
? (B9)? mip?
2,vrqpgi`1p?q?1q
gip?q`gi`1p?q2 ?
? mip?
2,vrqpgi`1p?q?1q
gip?qgi`1p?qpgi`1p?q?1q{2
? mip?
2,vrq
`g
ip?q
2
? .
Since gip?q ? 3 ? 2, by (D5) of the induction hypothesis we have mip?2,vrq{`gip?q2 ? ?
mp?3q{`gp?q3 ? for each vr P ??1i r?s. Therefore
mi`1p?2,vrq`
gi`1p?q
2
? (B9)? mip?
2,vrq
`g
ip?q
2
? (D5)? mp?
3q
`gp?q
3
?
for each vr P ??1i r?s. If gi`1p?q ? 1, by (B9) it follows that mi`1p?2,vrq ? 0 for each
vr P ??1i`1r?s. This proves (D5)1.
(D6)1 Suppose gp?q ? 3 and vr,vs are a pair of distinct vertices in ??1i r?s. From (B5) it
follows that mi`1p?,vr,vsq{gi`1p?q ? mip?,vr,vsq{gip?q. By (D6) of the induction
hypothesis mip?,vr,vsq{gip?q ?mp?3q{`gp?q3 ?. Therefore
mi`1p?,vr,vsq
gi`1p?q
(B5)? mip?,vr,vsq
gip?q
(D6)? mp?3q`
gp?q
3
?.
From (B8) it follows that
mi`1p?,vr,vi`1q
gi`1p?q
(B8)? 2mip?2,vrq
gip?qgi`1p?q ?
mip?2,vrq`
gip?q
2
? .
By (D5) of the induction hypothesis mip?2,vrq{`gip?q2 ? ?mp?3q{`gp?q3 ?. Therefore
mi`1p?,vr,vi`1q
gi`1p?q
(B8)? mip?2,vrq`
gip?q
2
? (D5)? mp?
3q
`gp?q
3
?.
77
This proves (D6)1.
(D7)1 Suppose gp?q ? 3 and vr,vs,vt are a triple of distinct vertices in ??1i r?s. Since
in forming Fi`1 no hyperedge is detached from vr,vs,vt, we have mi`1pvr,vs,vtq ?
mipvr,vs,vtq. But by (D7) of the induction hypothesis, mipvr,vs,vtq ? mp?3q{`gp?q3 ?.
Therefore
mi`1pvr,vs,vtq ?mipvr,vs,vtq(D7)? mp?
3q
`gp?q
3
?.
By (B6) mi`1pvr,vs,vi`1q ? mip?,vr,vsq{gip?q. By (D6) of the induction hypothesis
mip?,vr,vsq{gip?q ?mp?3q{`gp?q3 ?. Therefore
mi`1pvr,vs,vi`1q(B6)? mip?,vr,vsqg
ip?q
(D6)? mp?3q`
gp?q
3
?.
This proves (D7)1.
(D8)1 Case 1: If gi`1pxq ? gipxq?1 (so x ? ?), by (B9) mi`1p?2,yq ? mip?2,yqpgi`1p?q?
1q{gip?q which is 0 if gi`1p?q ? 1. If gi`1p?q ? 2, by (B9)
mi`1p?2,yq`
gi`1p?q
2
?g
i`1pyq
(B9)? mip?2,yqpgi`1p?q?1q
gip?q`gi`1p?q2 ?gi`1pyq
? mip?
2,yqpgi`1p?q?1q
gip?qgi`1p?qpgi`1p?q?1qgipyq{2
? mip?
2,yq
`g
ip?q
2
?g
ipyq
.
Since gip?q ? 3 ? 2, by (D8) of the induction hypothesis mip?2,yq{p`gip?q2 ?gipyqq ?
mp?2,yq{p`gp?q2 ?gpyqq. Therefore
mi`1p?2,yq`
gi`1p?q
2
?g
i`1pyq
(B9)? mip?2,yq`
gip?q
2
?g
ipyq
(D8)? mp?2,yq`
gp?q
2
?gpyq.
Case 2: Ifgi`1pyq ?gipyq?1 (soy ??), by (B3)mi`1px2,?q ?mipx2,?qgi`1p?q{gip?q
which is 0 by (D8) of the induction hypothesis, if gi`1pxq ? gipxq ? 1. If gi`1pxq ? 2,
78
by (B3) and (D8) of the induction hypothesis
mi`1px2,?q`
gi`1pxq
2
?g
i`1p?q
(B3)? mipx2,?q`
gi`1pxq
2
?g
ip?q
? mipx
2,?q
`g
ipxq
2
?g
ip?q
(D8)? mpx2,?q`
gpxq
2
?gp?q.
This proves (D8)1.
(D9)1 Suppose vt P ??1i rys. There are two cases:
Case 1: If gi`1pxq ?gipxq?1 (so x??), by (B9) mi`1p?2,vtq ?mip?2,vtqpgi`1p?q?
1q{gip?q which is 0 if gi`1p?q ? 1. If gi`1p?q ? 2, by (B9)
mi`1p?2,vtq`
gi`1p?q
2
? (B9)? mip?
2,vtqpgi`1p?q?1q
gip?q`gi`1p?q2 ?
? mip?
2,vtqpgi`1p?q?1q
gip?qgi`1p?qpgi`1p?q?1q{2
? mip?
2,vtq
`g
ip?q
2
? .
Since gip?q ? 3 ? 2, by (D9) of the induction hypothesis we have mip?2,vtq{`gip?q2 ? ?
mp?2,yq{p`gp?q2 ?gpyqq. Therefore
mi`1p?2,vtq`
gi`1p?q
2
? (B9)? mip?
2,vtq
`g
ip?q
2
? (D9)? mp?
2,yq
`gp?q
2
?gpyq.
Case 2: If gi`1pyq ? gipyq ? 1 (so y ? ?), since in forming Fi`1 no hyperedge is
detached from vt and x, we have mi`1px2,vtq ? mipx2,vtq which is 0 by (D9) of the
induction hypothesis, if gi`1pxq ? gipxq ? 1. If gi`1pxq ? 2, by (D9) of the induction
hypothesis
mi`1px2,vtq`
gi`1pxq
2
? ? mipx
2,vtq
`g
ipxq
2
? (D9)? mpx
2,?q
`gpxq
2
?gp?q.
By (B4), mi`1pvi`1,x2q ? mip?,x2q{gip?q which is 0 by (D8) of the induction hy-
pothesis, if gi`1pxq ? gipxq ? 1. If gi`1pxq ? 2, by (B4) and (D8) of the induction
79
hypothesis
mi`1px2,vi`1q`
gi`1pxq
2
? (B4)? mipx
2,?q
`g
i`1pxq
2
?g
ip?q
? mipx
2,?q
`g
ipxq
2
?g
ip?q
(D8)? mipx2,?q`
gpxq
2
?gp?q.
This proves (D9)1.
(D10)1 Suppose vr P ??1i rxs. There are two cases:
Case 1: Ifgi`1pxq ?gipxq?1(sox??), by (B5)mi`1p?,vr,yq{gi`1p?q ?mip?,vr,yq{gip?q.
Therefore by (D10) of the induction hypothesis
mi`1p?,vr,yq
gi`1p?qgi`1pyq
(B5)? mip?,vr,yq
gip?qgi`1pyq
? mip?,vr,yqg
ip?qgipyq
(D10)? mp?2,yq`
gp?q
2
?gpyq.
By (B8) mi`1p?,vi`1,yq ? 2mip?2,yq{gip?q. Therefore since gip?q ? 2, by (D8) of the
induction hypothesis
mi`1p?,vi`1,yq
gi`1p?qgi`1pyq
(B8)? 2mip?2,yq
gip?qgi`1p?qgi`1pyq
? mip?
2,yq
`g
ip?q
2
?g
ipyq
(D8)? mp?2,yq`
gp?q
2
?gpyq.
Case 2: If gi`1pyq ? gipyq? 1 (so y ? ?), by (B5) we have mi`1px,vr,?q{gi`1p?q ?
mipx,vr,?q{gip?q. Therefore by (D10) of the induction hypothesis
mi`1px,vr,?q
gi`1pxqgi`1p?q
(B5)? mipx,vr,?q
gi`1pxqgip?q
? mipx,vr,?qg
ipxqgip?q
(D10)? mpx2,?q`
gpxq
2
?gp?q.
This proves (D10)1.
(D11)1 Suppose vr P ??1i rxs,vt P ??1i rys. There are two cases:
Case 1: If gi`1pxq ? gipxq ? 1 (so x ? ?), by (B5) and (D11) of the induction
80
hypothesis
mi`1p?,vr,vtq
gi`1p?q
(B5)? mip?,vr,vtq
gip?q
(D11)? mp?2,yq`
gp?q
2
?gpyq.
By (B8) mi`1p?,vi`1,vtq ? 2mip?2,vtq{gip?q. Therefore by (D10) of the induction
hypothesis
mi`1p?,vi`1,vtq
gi`1p?q
(B8)? 2mip?2,vtq
gip?qgi`1p?q
? mip?,vr,yq`g
ip?q
2
? (D10)? mp?
2,yq
`gp?q
2
?gpyq.
Case 2: If gi`1pyq ? gipyq ? 1 (so y ? ?), since in forming Fi`1 no hyperedge is
detached from x,vr and vt, we have mi`1px,vr,vtq ?mipx,vr,vtq. Therefore by (D11)
of the induction hypothesis
mi`1px,vr,vtq
gi`1pxq ?
mipx,vr,vtq
gi`1pxq ?
mipx,vr,vtq
gipxq
(D11)? mpx2,?q`
gpxq
2
?gp?q.
By (B6) mi`1pvi`1,x,vrq ? mip?,x,vrq{gip?q. Therefore by (D10) of the induction
hypothesis
mi`1px,vr,vi`1q
gi`1pxq
(B6)? mipx,vr,?q
gi`1pxqgip?q ?
mipx,vr,?q
gipxqgip?q
(D10)? mpx2,?q`
gpxq
2
?gp?q.
This proves (D11)1.
(D12)1 Suppose vr,vs P ??1i rxs. There are two cases:
Case 1: If gi`1pxq ? gipxq ? 1 (so x ? ?), since in forming Fi`1 no hyperedge is
detached from vr,vs and y, we have mi`1pvr,vs,yq ?mipvr,vs,yq. Therefore by (D12)
of the induction hypothesis
mi`1pvr,vs,yq
gi`1pyq ?
mipvr,vs,yq
gi`1pyq ?
mipvr,vs,yq
gipyq
(D12)? mp?2,yq`
gp?q
2
?gpyq.
81
By (B6) mi`1pvi`1,vr,yq ? mip?,vr,yq{gip?q. Therefore by (D10) of the induction
hypothesis
mi`1pvi`1,vr,yq
gi`1pyq
(B6)? mip?,vr,yq
gip?qgi`1pyq ?
mip?,vr,yq
gip?qgipyq
(D10)? mp?2,yq`
gp?q
2
?gpyq.
Case 2: Ifgi`1pyq ?gipyq?1 (soy ??), by (B5) and (D12) of the induction hypothesis
mi`1pvr,vs,?q
gi`1p?q
(B5)? mipvr,vs,?q
gip?q
(D12)? mpx2,?q`
gpxq
2
?gp?q.
This proves (D12)1.
(D13)1 Suppose vr,vs P ??1i rxs,vt P ??1i rys. Since in forming Fi`1 no hyperedge is detached
from vr,vs and vt, we have mi`1pvr,vs,vtq ? mipvr,vs,vtq. Therefore by (D13) of the
induction hypothesis
mi`1pvr,vs,vtq(D13)? mpx
2,yq
`gpxq
2
?gpyq.
If gi`1pxq ?gipxq?1 (so x??), by (B6) and (D11) of the induction hypothesis
mi`1pvr,vi`1,vtq(B6)? mip?,vr,vtqg
ip?q
(D11)? mp?2,yq`
gp?q
2
?gpyq.
If gi`1pyq ?gipyq?1 (so y ??), by (B6) and (D12) of the induction hypothesis
mi`1pvr,vs,vi`1q(B6)? mip?,vr,vsqg
ipyq
(D12)? mpx2,?q`
gpxq
2
?gp?q.
This proves (D13)1.
82
(D14)1 If gi`1pxq ? gipxq ? 1 (so x ? ?) , by (B5) mi`1p?,y,zq{gi`1p?q ? mip?,y,zq{gip?q.
Therefore by (D14) of the induction hypothesis
mi`1p?,y,zq
gi`1p?qgi`1pyqgi`1pzq
(B5)? mip?,y,zq
gip?qgi`1pyqgi`1pzq
? mip?,y,zqg
ip?qgipyqgipzq
(D14)? mp?,y,zq
gp?qgpyqgpzq.
There are two other cases (gi`1pyq ? gipyq? 1 and gi`1pzq ? gipzq? 1) for which the
proof is similar. This proves (D14)1.
(D15)1 Suppose vt P ??1i rzs. There are three cases:
Case 1: Ifgi`1pxq ?gipxq?1(sox??), by (B5)mi`1p?,y,vtq{gi`1p?q ?mip?,y,vtq{gip?q.
Therefore by (D15) of the induction hypothesis
mi`1p?,y,vtq
gi`1p?qgi`1pyq
(B5)? mip?,y,vtq
gip?qgi`1pyq
? mip?,y,vtqg
ip?qgipyq
(D15)? mp?,y,zq
gp?qgpyqgpzq.
Case 2: If gi`1pyq ?gipyq?1 (so y ??), the proof is similar to that of case 1.
Case 3: If gi`1pzq ? gipzq ? 1 (so z ? ?), since in forming Fi`1 no hyperedge is
detached from x,y and vt, we have mi`1px,y,vtq ?mipx,y,vtq. Therefore by (D15) of
the induction hypothesis
mi`1px,y,vtq
gi`1pxqgi`1pyq ?
mipx,y,vtq
gipxqgipyq
(D15)? mpx,y,?q
gpxqgpyqgp?q.
By (B6) mi`1px,y,vi`1q ? mipx,y,?q{gip?q. Therefore by (D14) of the induction
hypothesis
mi`1px,y,vi`1q
gi`1pxqgi`1pyq
(B6)? mipx,y,?q
gi`1pxqgi`1pyqgip?q
? mipx,y,?qg
ipxqgipyqgip?q
(D14)? mpx,y,?q
gpxqgpyqgp?q.
83
This proves (D15)1.
(D16)1 Suppose vs P ??1i rys,vt P ??1i rzs. There are three cases:
Case 1: If gi`1pxq ? gipxq ? 1 (so x ? ?) , by (B5) and (D16) of the induction
hypothesis
mi`1p?,vs,vtq
gi`1p?q
(B5)? mip?,vs,vtq
gip?q
(D16)? mp?,y,zq
gp?qgpyqgpzq.
Case 2: If gi`1pyq ? gipyq ? 1 (so y ? ?), since in forming Fi`1 no hyperedge is
detached from x,vs and vt, we have mi`1px,vs,vtq ?mipx,vs,vtq. Therefore by (D16)
of the induction hypothesis
mi`1px,vs,vtq
gi`1pxq ?
mipx,vs,vtq
gipxq
(D16)? mpx,?,zq
gpxqgp?qgpzq.
By (B6) mi`1px,vi`1,vtq ? mipx,?,vtq{gip?q. Therefore by (D15) of the induction
hypothesis
mi`1px,vi`1,vtq
gi`1pxq
(B6)? mipx,?,vtq
gi`1pxqgip?q
? mipx,?,vtqg
ipxqgip?q
(D15)? mpx,?,zq
gpxqgp?qgpzq.
Case 3: If gi`1pzq ? gipzq?1 (so z ? ?), the proof is similar to that of case 2. This
proves (D16)1.
(D17)1 Suppose vr P ??1i rxs,vs P ??1i rys,vt P ??1i rzs. Since in forming Fi`1 no hyperedge
is detached from vr,vs and vt, we have mi`1pvr,vs,vtq ? mipvr,vs,vtq. Therefore by
(D17) of the induction hypothesis
mi`1pvr,vs,vtq(D17)? mpx,y,zqgpxqgpyqgpzq.
84
If gi`1pxq ?gipxq?1 (so x??) , by (B6) and (D16) of the induction hypothesis
mi`1pvi`1,vs,vtq(B6)? mip?,vs,vtqg
ip?q
(D16)? mp?,y,zq
gp?qgpyqgpzq.
There are two other cases (gi`1pyq ? gipyq? 1 and gi`1pzq ? gipzq? 1) for which the
proof is similar. This proves (D17)1.
A similar statement can be proved for every color class simply by restricting each relation
above to a color class j P t1,...,ku.
5.5.4 Relations Between G ?Fn and F
Recall that G ? Fn,? ? ?n and gnpxq ? 1 for each x P V. We claim that G satisfies
all conditions stated in Theorem 5.3.
ObviouslyG is ag-detachment ofF. Letx,y,z be an arbitrary triple of distinct vertices
of V, and let j P t1,...,ku. Now in (D1)?(D17) we let i ? n. From (D3) and (D4) it is
immediate that G is loopless. From (D5), (D8) and (D9) it follows that G has no hyperedge
of size 2. Thus G is a 3-uniform hypergraph.
From (D1) it follows that dFnpxq{gnpxq ?dpxq{gpxq, so dGpxq ?dpxq{gpxq. From (D2),
dFnpvrq ? dpxq{gpxq for each vr P ??1n rxs, so dGpvrq ? dpxq{gpxq for each vr P ??1rxs.
Therefore G satisfies (A1).
A similar argument shows that (A2) follows from the colored version of (D1) and (D2),
(A3) follows from (D6), (D7), and (D10)?(D17), and (A4) follows from the colored version
of (D6), (D7), and (D10)?(D17). This completes the proof of Theorem 5.3.
5.6 Algorithmic Aspects
To construct an r-factorization for ?K3n, we start with an amalgamation of ?K3n in
which all hyperedges are loops. We color the hyperedges among k :? ?`n?12 ?{r color classes
85
as evenly as possible, and apply Theorem 5.3. In Theorem 5.3, we detach vertices in n?1
steps. At each step, to decide how to share edges (and hinges) among the new vertices, we
define two setsA andB whose sizes are no more than 1`k``n3? and pk`1q`n2?, respectively,
and use Nash-Willimas lemma. Nash-Williams lemma builds a graph of size Opn3q (or more
precisely of size |A| ` |B|) and finds a set Z with a polynomial time algorithm. The set
Z tells us exactly how to share edges (and hinges) among the new vertices. Therefore, our
construction is polynomial in `n3?, the output size for the problem.
86
Chapter 6
Mathematicians Collaboration Problem
6.1 Introduction
In a mathematics workshop with mn mathematicians in n different areas, each area
consisting ofmmathematicians, we want to create a collaboration network. For this purpose,
we would like to schedule daily meetings between groups of size three, so that (i) two persons
of the same area meet one person of another area, (ii) each person has exactly r meetings
each day, and (iii) every two persons of the same area have exactly ? meetings with each
person of another area by the end of the workshop. We show that this can be done if: 3 cwmrm,
2 cwmrnm and r cwm 3?pn?1q`m2?.
Let K 3n?m denote a hypergraph with vertex partition tVi : 1 ? i ? nu, so that Vi ?
txij : 1 ?j ?mu for 1 ? i ?n, and with edge set E ? ttxij,xij1,xklu : 1 ? j ? j1 ? m,1 ?
i,k ? n,i ? k,1 ? l ? mu. One may notice that finding an r-factorization for ?K 3n?m is
equivalent to scheduling the meetings between mathematicians with the above restrictions.
In this chapter we use hypergraph amalgamation to solve our Mathematicians Collab-
oration Problem.
Example 6.1. Let F ? pV,E,H,?,?q, with V ? tvi : 1 ? i ? 6u,E ? te1,e2,e3u,H ?
thi : 1 ? i ? 9u, such that ?phiq ? vi for 1 ? i ? 6, ?ph7q ? v1,?ph8q ? v3,?ph9q ? v5
and ?ph5q ? ?ph6q ? ?ph7q ? e1,?ph1q ? ?ph2q ? ?ph8q ? e2,?ph3q ? ?ph4q ? ?ph9q ? e3.
Let ? : V ? tw1,w2,w3u be the function with ?pv1q ? ?pv6q ? w1, ?pv2q ? ?pv3q ? w2,
?pv4q ? ?pv5q ?w3. The hypergraph G in Figure 6.1 is the ?-amalgamation of F.
In the remainder of this chapter, we assume that n ? 3, m ? 2, and all hypergraphs
are either 3-uniform or are amalgamations of 3-uniform hypergraphs. Notice that for every
87
v3
h3h4
e3
v1
v6
h5
h7
h8
e2v2
h1
h2
h9 v4
h6
F
e1
v5 w3 w2
h3
e3
w1
h5
e2
h1
e1
h9
h4
h6h7
h8h2
G
Figure 6.1: A visual representation of a hypergraph F with an amalgamation G
hypergraph G we have
1 ? |e| ? |??1peq| ? 3 for every e in G. (6.1)
If u,v,w are three (not necessarily distinct) vertices of G, then Epu,v,wq denotes the set
of hyperedges that join u,v,w. For a graph G, we denote the set of edges joining a pair of
vertices u,v by Epu,vq.
In [6], the author proved a general detachment theorem for hypergraphs. For the purpose
of this chapter we use a very special case of this theorem as follows:
Theorem 6.2. Let F be a k-hyperedge-colored hypergraph and let g be a function from
VpFq into N such that for x,y,z P VpFq: (i) gpxq ? 2 implies Epx,x,xq ? ?, (ii)
gpxq ? 1 implies Epx,x,yq ? ?, and (iii) gpxq divides dFpjqpxq, `gpxq3 ? divides |Epx,x,xq|,
`gpxq
2
?gpyq divides |Epx,x,yq|, and gpxqgpyqgpzq divides |Epx,y,zq|. Then there exists a 3-
uniform g-detachment G of F in which each v P VpFq is detached into v1,...,vgpvq such
that G satisfies the following conditions for distinct x,y,z PVpFq :
(A1) dGpjqpxiq ?dFpjqpxq{gpxq for 1 ?i?gpxq and 1 ?j ?k;
(A2) |EGpxi,xi1,xi2q| ? |EFpx,x,xq|{`gpxq3 ? for 1 ?i?i1 ?i2 ?gpxq, if gpxq ? 3;
88
(A3) |EGpxi,xi1,yi2q| ? |EFpx,x,yq|{p`gpxq2 ?gpyqq for 1 ? i ? i1 ? gpxq if gpxq ? 2, and
1 ?i2 ?gpyq;
(A4) |EGpxi,yi1,zi2q| ? |EFpx,y,zq|{pgpxqgpyqgpzqq for 1 ? i ? gpxq, 1 ? i1 ? gpyq and
1 ?i2 ?gpzq.
6.2 Proof of the Main Theorem
LetK?n denote the hypergraph withnvertices in which |Epu,u,vq| ? 1, andEpu,u,uq?
Epu,v,wq ? ? for distinct vertices u,v,w. First we need the following simple lemma:
Lemma 6.3. If 2 cwm rin for 1 ? i ? k, and ?ki?1ri ? ?pn? 1q, then ?K?n is p3r1,...,3rkq-
factorizable.
Proof. Let G??Kn with vertex set V. Since 2 cwmrin for 1 ?i?k, and ?ki?1ri ??pn?1q,
G is pr1,...,rkq-factorizable (see [52], or [51]). So we can find a k-edge-coloring for G such
that dGpiqpvq ?ri for every v PV and every color 1 ?i?k. Now we form a hypergraph H
with vertex set V, such that |EH piqpu,u,vq| ? |EGpiqpu,vq| for every pair of distinct vertices
u,v PV. It is easy to see that H ??K?n and dH piqpvq ? 3ri for every v PV and every color
1 ?i?k. Thus we obtain a p3r1,...,3rkq-factorization for ?K?n.
Noticethat?K 3m?n isa 3?pn?1q`m2?-regularhypergraph withnmvertices and 2?m`n2?`m2?
edges.
Theorem 6.4. ?K 3m?n is pr1,...,rkq-factorizable if
(i) 3 cwmrim for 1 ?i?k,
(ii) 2 cwmrimn for 1 ?i?k, and
(iii) ?ki?1ri ? 3?pn?1q`m2?.
89
Proof. LetF ??m`m2?K?n. Note thatF is an amalgamation of?K 3m?n. Since for 1 ?i?k,
2 cwm rimn3 and ?ki?1 rim3 ? ?mpn? 1q`m2?, by Lemma 6.3, F is pmr1,...,mrkq-factorizable.
Thus, we can find a k-hyperedge-coloring for F such that
dFpjqpxq ?mri 1 ?i?k.
Let g : VpFq ? N be a function with gpxiq ? m for i ? 1,...,n. Note that K 3m?n is a
g-detachment of F. Now by Theorem 6.2, there exists a 3-uniform g-detachment G of F
with mn vertices, say xij, 1 ? i ? n, 1 ? j ? m (xi1,...,xim are obtained by splitting xi
into m vertices for i? 1,...,n) such that
? dGptqpxijq ?rt for 1 ?i?n, 1 ?j ?m, and 1 ?t?k;
? EGpxij,xij1,xij2q ? ? for 1 ?i?n and 1 ?j ?j1 ?j2 ?m, if m? 3;
? |EGpxij,xij1,xi1j2| ?? for 1 ?i?i1 ?n, 1 ?j ?j1 ?m, and 1 ?j2 ?m; and
? EGpxij,xi1j1,xi2j2q ? ? for 1 ?i?i1 ?i2 ?n and 1 ?j,j1,j2 ?m.
Therefore G ??K 3m?n and the ith color class is an ri-factor for 1 ?i?k.
In particular we solve the Mathematicians Collaboration Problem in the following case.
Corollary 6.5. ?K 3m?n is r-factorizable if
(i) 3 cwmrm,
(ii) 2 cwmrnm, and
(iii) r cwm 3?pn?1q`m2?.
We define K 3m1,...,mn similar to K 3m?n with the difference that in K 3m1,...,mn we allow
different parts to have different sizes.
Conjecture 6.6. ?K 3m1,...,mn is pr1,...,rkq-factorizable if and only if
90
(i) mi ?mj :?m for 1 ?i?j ?n,
(ii) 3 cwmrimn for each i, 1 ?i?k, and
(iii) ?ki?1ri ? 3?pn?1q`m2?.
We prove the necessity as follows. Since ?K 3m?n is factorizable, it must be regular. Let
u and v be two vertices from two different parts, say pth and qth parts respectively. Then we
have the following sequence of equivalences:
dpuq ?dpvq ??
?
1?i?ni?p
?m
i
2
?
`pmp ?1q
?
1?i?ni?p mi ?
?
1?i?ni?q
?m
i
2
?
`pmq ?1q
?
1?i?ni?q mi ??
?m
q
2
?
`
?
1?i?n
i?p,q
?m
i
2
?
`pmp ?1qpmq `
?
1?i?n
i?p,q
miq ?
?m
p
2
?
`
?
1?i?ni?p,q
?m
i
2
?
`pmq ?1qpmp `
?
1?i?ni?p,q miq ??
?m
p
2
?
?
?m
q
2
?
`mpmq ?mp ?mpmq `mq `pmp ?mqq
?
1?i?ni?p,q miq ? 0 ??
m2p ?m2q ?3mp `3mq `2pmp ?mqq
?
1?i?n
i?p,q
miq ? 0 ??
pmp ?mqqpmp `mq ?3`2
?
1?i?n
i?p,q
miq ? 0 ??
mp ?mq :?m.
This proves (i). The existence of an ri-factor implies that 3 cwmrimn for 1 ?i?k. Since each
ri-factor is an ri-regular spanning sub-hypergraph and ?K 3m?n is 3?pn? 1q`m2?-regular, we
must have ?ki?1ri ? 3?pn?1q`m2?.
It is not difficult to show that K 33,3,3 has a unique 1-factorization, but it does not satisfy
condition (ii) of Theorem 6.4. There are many other examples of this kind, but none of them
gives us a general construction.
91
Chapter 7
Embedding factorizations for 3-uniform hypergraphs
7.1 Introduction
In this chapter, two results are obtained on a hypergraph embedding problem. The
proof technique is itself of interest, being the first time amalgamations have been used to
address the embedding of hypergraphs.
The first result finds necessary and sufficient conditions for the embedding a hyperedge-
colored copy of the complete 3-uniform hypergraph of order m, K3m, into an r-factorization
of K3n, providing that n? 2m`p?1`?8m2 ?16m?7q{2.
The second result finds necessary and sufficient conditions for an embedding when not
only are the colors of the hyperedges of K3m given, but also the colors of all the ?pieces?
of hyperedges on these m vertices are prescribed (the ?pieces? of hyperedges are eventually
extended to hyperedges of size 3 in K3n by adding new vertices to the hyperedges of size 1
and 2 during the embedding process).
Both these results make progress towards settling an old question of Cameron on com-
pleting partial 1-factorizations of hypergraphs.
Let G be a hypergraph, and let H be a family of hypergraphs. We say that G has an
H -decomposition if there exists a partition tEpH1q,...,EpHmqu of EpGq such that Hi is
isomorphic to a hypergraph in H for 1 ?i?m.
The general setting for this chapter is as follows. Let H and H ? be two families of
hypergraphs. Given a hypergraph G with an H -decomposition and a hypergraph G? which
is a super-hypergraph ofG, under what circumstances can one extend theH -decomposition
of G into an H ?-decomposition of G?? In other words, given a hyperedge-coloring of G in
which each color class induces a hypergraph in H , is it possible to extend this coloring to a
92
hyperedge-coloring of G? so that each color class of G? induces a hypergraph in H ?? Most
naturally, G is usually taken to be the complete h-uniform hypergraph on m vertices, Khm.
Solving this problem requires knowledge about hypergraph decompositions; compared
to graph decompositions, very little is known about these, even for special cases. Perhaps
the best evidence for this difficulty is the long standing open problem of Sylvester in 1850
(in connection with Kirkman?s famous Fifteen Schoolgirls Problem [56]) which asks whether
it is possible to find a 1-factorization of Khn (see the next section for definitions). It took 120
years before Baranyai finally settled this conjecture [15]. After Baranyai?s proof appeared,
in 1976 Cameron [29] asked the following question:
Under what conditions can partial 1-factorizationsofKhm beextended to1-factorizations
of Khn?
This problem is wide open and to the authors1 best knowledge, the only partial results
address the very special case of embedding a 1-factorization of Khm into a 1-factorization of
Khn [17, 40].
Here we make some progress toward settling this problem, considering the following
related general embedding problem that is natural in its own right. When can a hyperedge-
coloring of a given hypergraph G on m vertices be embedded into a hyperedge-coloring of
K3n in such a way that each color class forms an r-factor? So the special case when r ? 1 and
G ? Khm addresses the Cameron question in the situation where the given partial 1-factors
are all defined on a set of m vertices.
In Section 7.3, we assume that precisely the hyperedges of size 3 on m vertices have
been colored; that is, the given hypergraph is G ? K3m), giving a complete solution if
n ? 2m ` p?1 ` ?8m2 ?16m?7q{2 (see Theorem 7.3). Lemma 7.4 then shows that
Theorem 7.3 is not true if this bound on n is replaced by n ? 2m? 1. In Section 7.4 we
assume that not only the hyperedges of size 3 are colored, but so are all the ?pieces? of
hyperedges of K3n that contain one or two of the given m vertices (i.e. n?m and `n?m2 ?
copies of the hyperedges inK2m andK1m, respectively); these pieces are built up to hyperedges
93
of size 3 when the new vertices are added. In this case the problem is completely solved in
Section 7.4, providing necessary and sufficient conditions (see Theorem 7.5).
The results in this chapter supplement embedding results for graphs. Such results
typically take a given edge-coloring of all the edges of a smaller complete graph and extend
it to an edge-coloring of all the edges of a bigger complete graph in such a way that each color
class is one of a given family of graphs. Hilton [44] used amalgamations to solve the problem
of embedding an edge-coloring of Km into a Hamiltonian decomposition of Kn. This was
later generalized by Nash-Williams [70]. Hilton and Rodger [48] considered the embedding
problem for Hamiltonian decompositions of complete multipartite graphs. For embeddings
of factorizations in which connectivity is also addressed, see [47, 51, 74].
It is worth remarking that embeddings of combinatorial structures with the same flavor
as results found in this chapter have a long history. For example, in his 1945 paper [41], Hall
proved that every p?n latin rectangle on n symbols can be embedded in a latin square of
size n. Following this classic embedding theorem, in 1951 Ryser generalized Hall?s result to
p?q latin rectangles on n symbols [75]. Ryser?s result is equivalent to embedding a proper
edge-coloring of the complete bipartite graph Kp,q into a 1-factorization of Kn,n. Doyen
and Wilson [35] solved the embedding problem for Steiner triple systems (K3-decompostions
of Kn), then Bryant and Horsley [27] addressed the embedding of partial designs, proving
Lindner?s conjecture [62] that any partial Steiner triple system of order u, PSTSpuq, can be
embedded in an STSpvq if v ? 1,3 pmod 6q and v ? 2u`1. (2u`1 is best possible in the
sense that for all u? 9 there exists a PSTSpuq that can not be embedded in an STSpvq for
any v ? 2u`1.)
7.2 Detachments of Amalgamated Hypergraphs
Note that a hypergraph as defined here corresponds to a hypergraph as usually defined
providing hyperedges are allowed to contain vertices multiple times. We imagine each hy-
peredge of a hypergraph to be attached to the vertices which it joins by in-between objects
94
called hinges. A hypergraph may be drawn as a set of points representing the vertices. A
hyperedge is represented by a simple closed curve enclosing its incident vertices. A hinge is
represented by a small line attached to the vertex incident with it (see Figure 7.1).
Example 7.1. Let F ? pV,E,H,?,?q, with V ? tvi : 1 ? i ? 8u,E ? te1,e2,e3u,H ?
thi : 1 ? i ? 9u, such that for 1 ? i ? 8, ?phiq ? vi , ?ph9q ? v6 and ?ph1q ? ?ph2q ?
?ph3q ? e1,?ph4q ? ?ph5q ? ?ph6q ? e2,?ph7q ? ?ph8q ? ?ph9q ? e3. Let ? : V ?
tw1,w2,w3,w4u be the function with ?pv1q ? ?pv2q ? ?pv3q ? w1, ?pv4q ? w2, ?pv5q ?
?pv6q ? w3, ?pv7q ? ?pv8q ? w4. The hypergraph G is the ?-amalgamation of F (see
Figure 7.1).
e1
v3
h3
h4
h7
v1
h5
v7
v8h
8
h9
h1
v2
h2
v4 v
5
h6
v6
e2
e3
F
e1 h4
h9
w2
h6
e2
e3
w1
h1
h2 h3
h5
w4
w3 h7
h8
G
Figure 7.1: A visual representation of a hypergraph F with an amalgamation G
In the remainder of this chapter, all hypergraphs are either 3-uniform or are amalgama-
tions of 3-uniform hypergraphs. This implies that for every hypergraph G we have
1 ? |e| ? |??1peq| ? 3 for every e in G. (7.1)
Ifu,v,ware three (not necessarily distinct) vertices ofG, thenmpu,v,wqdenotes the number
of hyperedges that join u, v, and w. For convenience, we let mpu2,vq ? mpu,u,vq, and
mpu3q ? mpu,u,uq. If we think of an edge as a multiset, then mpu2,vq (or mpu3q) counts
the multiplicity of an edge of the form tu,u,vu (or tu,u,uu, respectively).
95
For the purpose of this chapter, we need the following result which is a special case
of both Theorem 3.1 in [6], and Theorem 4.1 in [8]. To state it, some notation must be
introduced.
For g : VpFq ? N, we define the symmetric function ?g : V3pFq ? N such that for dis-
tinct x,y,z PVpFq, ?gpx,x,xq ? `gpxq3 ?, ?gpx,x,yq ? `gpxq2 ?gpyq, and ?gpx,y,zq ?gpxqgpyqgpzq.
Also we assume that for each xPVpFq, gpxq ? 2 implies mFpx3q ? 0, and gpxq ? 1 implies
mFpx2,yq ? 0 for every y PVpFq.
Theorem 7.2. (Bahmanian [6, Theorem 3.1]) Let F be a k-hyperedge-colored hypergraph
and let g be a function from VpFq into N. Then there exists a 3-uniform g-detachment G of
F with amalgamation function ? : VpGq ? VpFq, g being the number function associated
with ?, such that:
(A1) for each xPVpFq, each uP ??1pxq and each j P t1,...,ku
dGpjqpuq ? dFpjqpxqgpxq ; and
(A2) for every x,y,z PVpFq, with gpxq ? 3 if x?y ?z, and gpxq ? 2 if |tx,y,zu| ? 2, and
every triple of distinct vertices u,v,w with uP ??1pxq, v P ??1pyq and w P ??1pzq,
mGpu,v,wq? mFpx,y,zq?gpx,y,zq .
7.3 Embedding Partial Hyperedge-colorings into Factorizations
In this section we completely solve the embedding problem in the case where all the
hyperedges of size 3 on a set of m vertices have been colored, providing n is big enough. We
then show that some lower bound on n is needed, since the necessary conditions of Theorem
7.3 are not sufficient if n? 2m?1.
96
Theorem 7.3. Suppose that n ? 2m`p?1`?8m2 ?16m?7q{2. A q-hyperedge-coloring
of F ?K3m can be embedded into an r-factorization of G ?K3n if and only if
(i) 3 cwmrn,
(ii) r cwm `n?12 ?,
(iii) q ? `n?12 ?{r, and
(iv) dFpjqpvq ?r for each v PVpFq and 1 ?j ?q.
Proof. To prove the necessity, suppose that F with V ? VpFq can be embedded into an
r-factorization of G. Since each edge contributes 3 to the the sum of the degrees of the
vertices in an r-factor, r|VpGq| must be divisible by 3 which implies (i). Since each r-factor
is an r-regular spanning sub-hypergraph and G is `n?12 ?-regular, we must have r cwm `n?12 ?,
which is condition (ii). This r-factorization requires exactly k ? `n?12 ?{r colors which is
condition (iii), and to be able to extend each color class to an r-factor we need condition
(iv).
Now assume that conditions (i)?(iv) are true. By Baranyai?s theorem [15], the case of
m ? 3 is trivial, and so we may assume that m ? 4. Let ej ? |E`Fpjq?| for 1 ? j ? k.
In what follows, we extend the hyperedge-coloring of F into a k-hyperedge-coloring of an
amalgamation of G, and then we apply Theorem 7.2 to obtain the detachment G in which
each color class is an r-factor. The hyperedges added in steps (I), (II), and (III) correspond
to the hyperedges in G that contain one, two, and three new vertices, respectively.
(I) Let F1 be a hypergraph formed by adding a new vertex u and hyperedges to F such
that mpu,v,wq ? n?m for every pair of distinct vertices v,w P V. Of course the
hyperedges in EpFqXEpF1q are already colored. We color greedily as many of the
added pn?mq`m2? hyperedges as possible, ensuring that dF1pjqpvq ? r for 1 ? j ? k.
Suppose there exists a hyperedge incident with u,v and w that is not colored. Then
for 1 ? j ? k either dF1pjqpvq ? r or dF1pjqpwq ? r, so dF1pjqpvq `dF1pjqpwq ? r for
97
every 1 ? j ? k. Therefore 2`m?12 ?` 2pn?mqpm?1q? 2 ? dF1pvq`dF1pwq?2 ?
?k
j?1
`d
F1pjqpvq ` dF1pjqpwq
? ? ?k
j?1r ? kr ?
`n?1
2
?, in which the first inequality
follows from that fact that at least one hyperedge incident with v and w is not colored.
So, 2pm?1qpm?2q`4pn?mqpm?1q?4 ? pn?1qpn?2q. Thus n2 ?4nm`n`
2m2 `2m`2 ? 0. So
n? 2m`p?1`?8m2 ?16m?7q{2,
a contradiction. So all hyperedges can be colored greedily. Let fj be the number of
hyperedges of color j in some such coloring for 1 ?j ?k.
(II) Let F2 be a hypergraph formed by adding m`n?m2 ? further hyperedges to F1 so that
mpu2,vq ? `n?m2 ? for each v PV. Note that for each v PV,
dF2pvq ?
?m?1
2
?
`pm?1qpn?mq`
?n?m
2
?
?
?n?1
2
?
?rk.
Since dF1pjqpvq ? r for v P V and 1 ? j ? k, to ensure that dF2pjqpvq ? r, we color
r?dF1pjqpvqp? 0q hyperedges incident with v that were added in forming F2 from F1
with color j for each v P V and 1 ? j ? k. So the coloring we perform in this step
results in all the newly added hyperedges being colored. Let gj denote the number of
such hyperedges of color j for 1 ?j ?k.
(III) Let F3 be the hypergraph formed by adding `n?m3 ? further hyperedges to F2 so that
mpu3q ? `n?m3 ?. Let ?j :?rpn{3?mq`fj `2ej for 1 ?j ? k. We claim that ?j ? 0
for 1 ? j ? k. To prove this, it is enough to show that n ? 3m. Since m ? 4 ?
p3`?17q{2, we have m2 ?3m?2 ? 0. Therefore, 8m2 ?16m?7 ? 4m2 ?4m`1,
and thus ?8m2 ?16m?7 ? 2m? 1, which implies p1 ` ?8m2 ?16m?7q{2 ? m,
98
and consequently we have tp1 ` ?8m2 ?16m?7q{2u ? m. Since n ? 2m` tp1 `
?8m2 ?16m?7q{2u, we have n? 3m.
Now we color the added hyperedges such that there are exactly ?j further hyperedges
colored j for 1 ?j ?k. This is possible because
k?
j?1
?j ?
k?
j?1
`rpn{3?mq`f
j `2ej
?
? rkpn{3?mq`
k?
j?1
fj `2
k?
j?1
ej
?
?n?1
2
?
pn{3?mq`pn?mq
?m
2
?
`2
?m
3
?
? n3{6?n2m{2?n2{2`nm2{2`nm
` n{3?m3{6?m2{2?m{3
?
?n?m
3
?
?mF3pu3q.
Let us fix j P t1,...,ku. Since dF3pjqpvq ?r for v PV, we have
rm?
?
vPV
dF3pjqpvq ? 3ej `2fj `gj. (7.2)
On the other hand,
dF3pjqpuq ? 3?j `2gj `fj ?rpn?3mq`3fj `6ej `2gj `fj
? rpn?3mq`4fj `6ej `2gj.
This together with (7.2) implies that for 1 ?j ?k,
dF3pjqpuq ?rpn?3mq`2rm?rpn?mq.
99
(IV) Let g : VpF3q ? N be a function with gpuq ? n?m, and gpvq ? 1 for each v P V.
By Theorem 7.2, there exists a 3-uniform g-detachment G? of F3 with n?m new
vertices, say u1,...,un?m detached from u such that
? dG?pjqpvq ? dF3pjqpvq{gpvq ? r{1 ? r and dG?pjqpuiq ? dF3pjqpuq{gpuq ? rpn?
mq{pn?mq ?r for 1 ?i?n?m and 1 ?j ?k;
? mG?pui,ui1,ui2q ?mF3pu3q{`gpuq3 ? ? `n?m3 ?{`n?m3 ? ? 1 for 1 ?i?i1 ?i2 ?n?m;
? mG?pui,ui1,vq ? mF3pu2,vq{``gpuq2 ?gpvq? ? `n?m2 ?{`n?m2 ? ? 1 for 1 ? i ? i1 ?
n?m, and v PV, and
? mG?pui,v,wq ?mF3pu,v,wq{`gpuqgpvqgpwq?? pn?mq{pn?mq ? 1 for 1 ?i?
n?m and distinct v,w PV.
Therefore G? ?G ?K3n and each color class is an r-factor. This completes the proof.
Lemma 7.4. Conditions (i)?(iv) of Theorem 7.3 are not sufficient if n? 2m?1.
Proof. Suppose that the hyperedge-coloring of K3m induces an r-factorization. Then in the
embedding, the sub-hypergraph of K3n on the new n?m vertices induced by the hyperedges
having the original colors clearly has an r-factorization (each of the colors induces an r-
factor). Therefore n?m ? m, or equivalently n ? 2m. So if r is chosen so that 3 cwm r and
r cwmm?1, then it is easy to check that conditions (i)?(iv) of Theorem 7.3 are satisfied when
n? 2m?1, yet no embedding is possible.
7.4 Extending Restrictions of Partial Edge-colorings
If every hyperedge e of the hypergraph G is replaced with ? (? 2) copies of e then
denote the resulting (multi) hypergraph by ?G. If G1,...,Gt are hypergraphs on the vertex
set V with edge sets EpG1q...,EpGtq respectively, then let ?ti?1Gi be the hypergraph with
vertex set V and edge set ?ti?1EpGiq.
100
In this section we completely solve the embedding problem in the case where all the
hyperedges in F ?K3m Ypn?mqK2m Y`n?m2 ?K1m on a set of m vertices have been colored,
regardless of the size of n. One can think of the given colored hyperedges as being all the
?pieces? of hyperedges on these m vertices that are eventually extended to hyperedges of
size 3 by adding the new n?m vertices during the embedding process.
Let EipGpjqq denote the set of hyperedges of size i and color j in G.
Theorem 7.5. A k-hyperedge-coloring of F ?K3mYpn?mqK2mY`n?m2 ?K1m with V ?VpFq
can be extended to an r-factorization of G ?K3n if and only if
(i) 3 cwmrn,
(ii) r cwm `n?12 ?,
(iii) k ? `n?12 ?{r,
(iv) dFpjqpvq ?r for each v PV and 1 ?j ?k, and
(v) |E2pFpjqq|`2|E3pFpjqq| ?rpm?n{3q for 1 ?j ?k.
Proof. First, suppose thatF can be embedded into anr-factorization ofG. The necessity of
(i)?(iv) follow as described in the proof of Theorem 7.3; equalities in this result replace the
inequalities there because the colors of all hyperedges restricted to F have been prescribed
in this case. Let us fix j P t1,...,ku. Let ej,fj,gj, and ?j be the number of hyperedges in
EpGpjqq that are incident with exactly 3, 2, 1 and 0 vertices in V, respectively. It is easy
to see that ej ? |E3pFpjqq| and fj ? |E2pFpjqq|. Since rpn?mq ? 3?j ` 2gj `fj, and
rm?gj`2fj`3ej, we have rpn?3mq ? 3?j?3fj?6ej, and thus ?j ?rpn{3?mq`fj`2ej,
but since ?j ? 0, we must have 2ej `fj ?rpm?n{3q. This proves (v).
To prove the sufficiency, assume that conditions (i)?(v) are true. LetF1 be a hypergraph
formed by adding a new vertex u to F with mpu3q ? `n?m3 ?, and extending each hyperedge
of size one or two to a hyperedge incident with u of size two or three, respectively. We
extend the hyperedges of size one (two, respectively) such that u is incident with two (one,
respectively) hinges within that hyperedge. Ignoring colorings, F1 is isomorphic to F3 in
101
the proof of Theorem 7.3, and F1 is an amalgamation of G. We color rpn{3?mq`fj `2ej
of the new hyperedges with color j. This coloring results in all the newly added hyperedges
being colored. The rest of the proof is identical to part (IV) of Theorem 7.3.
102
Chapter 8
Detachments of Hypergraphs: The Berge-Johnson Problem
8.1 Introduction
Intuitively speaking, a detachment of a hypergraph is formed by splitting each vertex
into oneor moresubvertices, and sharing theincident edges arbitrarilyamongthesubvertices.
As the main result of this chapter (see Theorem 8.2), we prove that for a given edge-colored
hypergraph F, there exists a detachment G such that the degree of each vertex and the
multiplicity of each edge in F (and each color class of F) are shared fairly among the
subvertices in G (and each color class of G, respectively). This result is not only interesting
by itself and generalizes various graph theoretic results (see for example [5, 44, 48, 51, 58,
61, 70, 74]), but also is used to obtain extensions of existing results on edge-decompositions
of hypergraphs by Bermond, Baranyai [15, 16], Berge and Johnson [21, 50], and Brouwer
and Tijdeman [24, 26].
Given a set N of n elements, Berge and Johnson [21, 50] addressed the question of when
do there exist disjoint partitions of N, each partition containing only subsets of h or fewer
elements, such that every subset of N having h or fewer elements is in exactly one partition.
Here we state the problem in a more general setting with the hypergraph theoretic notation.
Let p?1...,?mqKh1,...,hmp1,...,pn be a hypergraph with vertex partition tV1,...,Vnu, |Vi| ? pi
for 1 ? i?n such that there are ?i edges of size hi incident with every hi vertices, at most
one vertex from each part for 1 ? i ? m (so no edge is incident with more than one vertex
of a part). We use our detachment theorem to show that the obvious necessary conditions
for p?1...,?mqKh1,...,hmp1,...,pn to be expressed as the union G1 Y...YGk of k edge-disjoint factors,
where for 1 ? i ? k, Gi is ri-regular, are also sufficient. Baranyai [15, 16] solved the case of
h1 ? ??? ? hm, ?1 ? ...,?m ? 1, p1 ? ??? ? pm, r1 ? ??? ? rk. Berge and Johnson [21, 50],
103
(and later Brouwer and Tijdeman [24, 26], respectively) considered (and solved, respectively)
the case of hi ? i, 1 ? i ? m, p1 ? ??? ? pm ? ?1 ? ??? ? ?m ? r1 ? ??? ? rk ? 1. We also
extend our result to the case where each Gi is almost regular.
In the next two sections, we give more precise definitions along with terminology. In
Section 8.4, we state our main result, followed by the proof in Section 8.5. In the last
section, we show the usefulness of the main result on decompositions of various classes of
hypergraphs. We defer the applications of the main result in solving embedding problems
to a future paper.
8.2 Terminology and Precise Definitions
For a multiset A and u P A, let ?Apuq denote the multiplicity of u in A, and let
|A| ? ?uPA?Apuq. For multisets A1,...,An, we defineA? ?ni?1Ai by ?Apuq ? ?ni?1?Aipuq.
We may use abbreviations such as turu for tu,...,ulooomooon
r
u ? for example tu2,v,w2uYtu,w2u ?
tu3,v,w4u.
Forthepurpose ofthischapter, a hypergraph G isan ordered quintuplepVpGq,EpGq,HpGq,
?,?q where VpGq,EpGq,HpGq are disjoint finite sets, ? : HpGq ? VpGq is a function and
? : HpGq ? EpGq is a surjection. Elements of VpGq,EpGq,HpGq are called vertices, edges
and hinges of G, respectively. A vertex v (edge e, respectively) and hinge h are said to be
incident with each other if ?phq ?v (?phq ?e, respectively). A hinge h is said to attach the
edge ?phq to the vertex ?phq. In this manner, the vertex ?phq and the edge ?phq are said to
be incident with each other. If ePEpGq, and e is incident with n hinges h1,...,hn for some
n P N, then the edge e is said to join (not necessarily distinct) vertices ?ph1q,...,?phnq. If
v PVpGq, then the number of hinges incident with v (i.e. |??1pvq|) is called the degree of v
and is denoted by dpvq. The number of (distinct) vertices incident with an edge e, denoted
by |e|, is called the size of e. If for all edges e of G, |e| ? 2 and |??1peq| ? 2, then G is a
graph.
104
Thus a hypergraph, in the sense of our definition, is a generalization of a hypergraph
as it is usually defined. In fact, if for every edge e, |e| ? |??1peq|, then our definition is
essentially the same as the usual definition. Here for convenience, we imagine each edge of a
hypergraph to be attached to the vertices which it joins by in-between objects called hinges.
Readers from a graph theory background may think of this as a bipartite multigraph with
vertex bipartition tV,Eu, in which the hinges form the edges. A hypergraph may be drawn
as a set of points representing the vertices. A hyperedge is represented by a simple closed
curve enclosing its incident vertices. A hinge is represented by a small line attached to the
vertex incident with it (see Figure 8.1).
The set of hinges of G which are incident with a vertex v (and an edge e, respectively),
is denoted by Hpvq (Hpv,eq, respectively). Thus if v P VpGq, then Hpvq ? ??1pvq, and
|Hpvq| is the degree dpvq of v. If U is a multi-subset ofVpGq, and uPVpGq, let EpUq denote
the set of edges e with |??1peq| ? |U| joining vertices in U. More precisely, EpUq ? te P
EpGq| for all v PVpGq,|Hpv,eq| ??Upvqu. For U1,...,Un ?V where for 1 ?i ?n each Ui
is a multiset, let EpU1,...,Unq denote Ep?ni?1Uiq. We write mpUq for |EpUq| and call it the
multiplicity of U. For simplicity, Epur,Uq denotes Epturu,Uq, and mpum11 ,...,umrr q denotes
mptum11 ,...,umrr uq. The set of hinges that are incident with u and an edge in Epur,Uq is
denoted by Hpur,Uq.
Example 8.1. Let G ? pV,E,H,?,?q, with V ? tv1,v2,v3,v4,v5u,E ? te1,e2,e3u,H ?
thi,1 ? i ? 7u, such that ?ph1q ? ?ph2q ? v1,?ph3q ? v2,?ph4q ? ?ph5q ? v3,?ph6q ?
v4,?ph7q ?v5 and ?ph1q ? ?ph2q ? ?ph3q ??ph4q ? e1,?ph5q ? ?ph6q ?e2,?ph7q ?e3. We
have:
? |e1| ? 3,|e2| ? 2,|e3| ? 1,
? dpv1q ?dpv3q ? 2,dpv2q ?dpv4q ?dpv5q ? 1,
? Hpv1q ? th1,h2u,Hpv2q ? th3u,Hpv3q ? th4,h5u,
? Hpv3,e1q ? th4u,Hpv3,e2q ? th5u,Hpv3,e3q ? ?,
105
v1
e1
e2
G
v5
h7 v4
h4
v2
h3
h1
h2
v3
h5
h6e3
Figure 8.1: Representation of a hypergraph G
? Eptv1,v2,v3uq ? ?,Eptv21,v2,v3uq ?Epv21,tv2,v3uq ? te1u,
? mpv1,v2,v3q ? 0,mpv21,v2,v3q ? 1,
? Hpv21,tv2,v3uq ? th1,h2u,Hpv1,tv2,v3uq ? ?,Hpv3,tv21,v2uq ? th4u.
A k-edge-coloring of G is a mapping f : EpGq ? C, where C is a set of k colors (often we
use C ? t1,...,ku), and the edges of one color form a color class. The sub-hypergraph of G
induced by the color class j is denoted by Gpjq. To avoid ambiguity, subscripts may be used
to indicate the hypergraph in which hypergraph-theoretic notation should be interpreted ?
for example, dGpvq, EGpv2,wq, HGpvq.
8.3 Amalgamations and Detachments
If F ? pV,E,H,?,?q is a hypergraph and ? is a function from V onto a set W, then
we shall say that the hypergraph G ? pW,E,H,???,?q is an amalgamation of F and that
F is a detachment of G. Associated with ? is the number function g : W ? N defined
by gpwq ? |??1pwq|, for each w P W; being more specific, we may also say that F is a
g-detachment of G. Intuitively speaking, a g-detachment of G is obtained by splitting each
u P VpGq into gpuq vertices. Thus F and G have the same edges and hinges, and each
vertex v of G is obtained by identifying those vertices of F which belong to the set ??1pvq.
106
In this process, a hinge incident with a vertex u and an edge e in F becomes incident with
the vertex ?puq and the edge e in G.
There are quite a lot of other papers on amalgamations and some highlights include
[36, 42, 45, 44, 48, 51, 70, 74].
8.4 Main Result
A function g : VpGq ? N is said to be simple if
|Hpv,eq| ?gpvq for v PVpGq,ePEpGq.
A hypergraph G is said to be simple if g : VpGq ? N with gpvq ? 1 for v PVpGq is simple.
It is clear that for a hypergraph F and a function g : VpFq ? N, there exists a simple
g-detachment if and only if g is simple.
Theorem 8.2. Let F be a k-edge-colored hypergraph and let g : VpFq ? N be a simple
function. Then there exists a simple g-detachment G (possibly with multiple edges) of F
with amalgamation function ? : VpGq ? VpFq, g being the number function associated
with ?, such that:
(A1) for each uPVpFq and each v P ??1puq
dGpvq ? dFpuqgpuq ;
(A2) for each uPVpFq, each v P ??1puq and 1 ?j ?k
dGpjqpvq ? dFpjqpuqgpuq ;
107
(A3) for distinct u1,...,ur PVpFq and Ui ? ??1puiq with |Ui| ?mi ?gpuiq for 1 ?i?r
mGpU1,...,Urq ? mFpu
m1
1 ,...,u
mr
r q
?ri?1`gpuiqmi ? ;
(A4) for distinct u1,...,ur P VpFq and Ui ? ??1puiq with |Ui| ? mi ? gpuiq for 1 ? i ? r
and 1 ?j ?k
mGpjqpU1,...,Urq ? mFpjqpu
m1
1 ,...,u
mr
r q
?ri?1`gpuiqmi ? .
8.5 Proof of Theorem 8.2
8.5.1 Inductive Construction of G
Let F ? pV,E,H,?,?q. Let n ? ?vPV pgpvq ? 1q. Initially we let F0 ? F and
g0 ? g, and we let ?0 be the identity function from V into V. Now assume that F0 ?
pV0,E0,H0,?0,?0q,...,Fi ? pVi,Ei,Hi,?i,?iq and ?0,...,?i have been defined for some
i? 0. Also assume that the simple functions g0 : V0 ? N,...,gi : Vi ? N have been defined
for some i ? 0. Let ?i ? ?0...?i. If i ?n, we terminate the construction, letting G ?Fn
and ? ? ?n.
If i ? n, we can select a vertex ? of Fi such that gip?q ? 2. As we will see, Fi`1 is
formed from Fi by splitting off a vertex vi`1 from ? so that we end up with ? and vi`1. Let
Ai ? tHFip?qu
? tH
Fip1qp?q,...,HFipkqp?qu
? tH
Fipjqp?,eq : ePEFipjqp?q,1 ?j ?ku, (8.1)
and let
Bi ? tHFip?t,Uq : t? 1,U ?Vizt?uu
? tH
Fipjqp?t,Uq : t? 1,U ?Vizt?u,1 ?j ?ku. (8.2)
108
It is easy to see that both Ai and Bi are laminar families of subsets of HpFi,?q.
Therefore, by Lemma 1.3, there exists a subset Zi of HpFi,?q such that
|Zi XP| ? |P|{gip?q, for every P PAi YBi. (8.3)
Let vi`1 be a vertex which does not belong to Vi and let Vi`1 ?Vi Ytvi`1u. Let ?i`1 be the
function from Vi`1 onto Vi such that ?i`1pvq ? v for every v P Vi and ?i`1pvi`1q ? ?. Let
Fi`1 be the detachment of Fi under ?i`1 such that VpFi`1q ?Vi`1, and
HFi`1pvi`1q ?Zi,HFi`1p?q ?HFip?qzZi. (8.4)
In fact, Fi`1 is obtained from Fi by splitting ? into two vertices ? and vi`1 in such a
way that hinges which were incident with ? in Fi become incident in Fi`1 with ? or vi`1
according as they do not or do belong to Zi, respectively. Obviously, ?i is an amalgamation
function fromFi`1 intoFi. Letgi`1 be the function fromVi`1 into N, such thatgi`1pvi`1q ?
1,gi`1p?q ?gip?q?1, andgi`1pvq ?gipvq for everyv PVizt?u. This finishes the construction
of Fi`1.
8.5.2 Relations Between Fi`1 and Fi
The hypergraph Fi`1, satisfies the following conditions:
(B1) dFi`1p?q ?dFip?qgi`1p?q{gip?q;
(B2) dFi`1pvi`1q ?dFip?q{gip?q;
(B3) mFi`1pvsi`1,?t,Uq ? 0 for s? 2, and t? 0;
(B4) mFi`1p?t,Uq ?mFip?t,Uqpgip?q?tq{gip?q for each U ?Vizt?u, and gip?q ?t? 1;
(B5) mFi`1p?t,vi`1,Uq ? pt`1qmFip?t`1,Uq{gip?q for each U ?Vizt?u, and t? 0.
109
Proof. Since HFip?q PAi, from (8.4) it follows that
dFi`1pvi`1q ? |HFi`1pvi`1q| ? |Zi| ? |Zi XHFip?q|
? |HFip?q|{gip?q ?dFip?q{gip?q,
dFi`1p?q ? |HFi`1p?q| ? |HFip?q|?|Zi|
? dFip?q?dFip?q{gip?q ? pgip?q?1qdFip?q{gip?q
? dFip?qgi`1p?q{gip?q.
This proves (B1) and (B2).
If t ? 1,U ? Vizt?u, and e P EFip?t,Uq, then for some j, 1 ? j ? k, HFipjqp?,eq P Ai,
so
??Z
i XHFipjqp?,eq
?? ? |H
Fipjqp?,eq|{gip?q ?t{gip?q ? 1,
where theinequality implies fromthefactthatgi is simple. Therefore either|ZiXHFipjqp?,eq| ?
1 and consequently e P EFi`1p?t?1,vi`1,U) or Zi X HFipjqp?,eq ? ? and consequently
ePEFi`1p?t,Uq. Therefore
mFi`1pvsi`1,?r,Uq ? 0,
for r ? 1, and s? 2. This proves (B3). Moreover, since HFip?t,Uq PBi, we have
mFi`1p?t?1,vi`1,Uq ? |Zi XHFip?t,Uq| ? |HFip?t,Uq|{gip?q ?tmFip?t,Uq{gip?q,
mFi`1p?t,Uq ? mFip?t,Uq?|HFip?t,Uq|{gip?q ?mFip?t,Uq?tmFip?t,Uq{gip?q
? mFip?t,Uqpgip?q?tq{gip?q.
This proves (B4) and (B5).
Let us fix j P t1,...,ku. It is enough to replace Fi with Fipjq in the statement and the
proof of (B1)?(B5) to obtain companion conditions, say (C1)?(C5) for each color class.
110
8.5.3 Relations Between Fi and F
Recall that ?i ? ?0...?i, that ?0 : V ? V, and that ?i : Vi ? Vi?1 for i ? 0.
Therefore ?i : Vi ? V and thus ??1i : V ? Vi. Now we use (B1)?(B5) to prove that the
hypergraph Fi satisfies the following conditions for 0 ?i?n :
(D1) dFipvq{gipvq ?dFpuq{gpuq for each uPV and each v P ??1i puq;
(D2) mFipua11 ,U1,...,uarr ,Urq{?rj?1`gipujqa
j
? ? m
Fpum11 ,...,umrr q{?rj?1
`gpu
jq
mj
? for distinct ver-
tices u1,...,ur P V, aj ? 0, Uj ? ??1i pujqztuju with 1 ? mj ? aj ` |Uj| ? gpujq,
1 ?j ?r if gipujq ?aj, 1 ?j ?r.
Proof. The proof is by induction. Recall that F0 ? F, and g0puq ? gpuq for u P V. Thus,
(D1) and (D2) are trivial for i? 0. Now we will show that if Fi satisfies the conditions (D1)
and (D2) for some i ? n, then Fi`1 satisfies these conditions by replacing i with i` 1; we
denote the corresponding conditions for Fi`1 by (D1)1 and (D2)1.
Let u P V. If gi`1puq ? gipuq, then (D1)1 is obviously true. So we just check (D1)1
in the case where u ? ?. By (B1) and (D1) we have dFi`1p?q{gi`1p?q ? dFip?q{gip?q ?
dFp?q{gp?q. Moreover, from (B2) and (D1) it follows that dFi`1pvi`1q ? dFip?q{gip?q ?
dFp?q{gp?q. Since in forming Fi`1 no edge is detached from vr for each vr P ??1i p?qzt?u,
we have dFi`1pvrq ? dFipvrq. Therefore dFi`1pvrq ? dFipvrq ? dFp?q{gp?q for each vr P
??1i p?qzt?u. This proves (D1)1. Let u1,...,ur be distinct vertices in V. If gi`1pujq ?gipujq
for 1 ? j ? r, then (D2)1 is clearly true. Therefore, in order to prove (D2)1, without loss of
generality we may assume that gi`1pu1q ?gipu1q?1 (so ? ?u1 and vi`1 P ??1i pu1q). First,
note that for integers a,b we always have pa?bq`ab? ? a`a?1b ? ? pb` 1q` ab`1?. If vi`1 R U1,
111
we have
mFi`1pua11 ,U1,...,uarr ,Urq
?rj?1`gi`1pujqaj ?
(B4)? mFipua11 ,U1,...,uarr ,Urqpgipu1q?a1q{gipu1q`
gipu1q?1
a1
??r
j?2
`g
ipujq
aj
?
? mFipu
a1
1 ,U1,...,u
ar
r ,Urqpgipu1q?a1q{gipu1q
pgipu1q?a1q{gipu1q`gipu1qa1 ??rj?2`gipujqaj ?
? mFipu
a1
1 ,U1,...,u
ar
r ,Urq
?rj?1`gipujqa
j
?
(D2)? mFpum11 ,...,umrr q
?rj?1`gpujqmj ? .
If vi`1 PU1, we have
mFi`1pua11 ,U1,...,uarr ,Urq
?rj?1`gi`1pujqaj ?
(B5)? mFipua1`11 ,U1ztvi`1u,...,uarr ,Urqpa1 `1q{gipu1q`
gipu1q?1
a1
??r
j?2
`g
ipujq
aj
?
? mFipu
a1`1
1 ,U1ztvi`1u,...,u
ar
r ,Urq
gipu1q{pa1 `1q`gipu1q?1a1 ??rj?2`gipujqaj ?
? mFipu
a1`1
1 ,U1ztvi`1u,...,u
ar
r ,Urq`
gipu1q
a1`1
??r
j?2
`g
ipujq
aj
?
(D2)? mFpum11 ,...,umrr q
?rj?1`gpujqmj ? .
This proves (D2)1.
Let us fix j P t1,...,ku. It is enough to replace F with Fpjq, Fi with Fipjq, Fi`1 with
Fi`1pjq, and (Bi) with (Ci) for i ? 1,2,4,5, in the statement and the proof of (D1) and
(D2) to obtain companion conditions, say (E1) and (E2) for each color class.
8.5.4 G satisfies (A1)?(A4)
Recall that G ?Fn and gnpuq ? 1 for every uPV, therefore when i ?n, (D1) implies
(A1). Moreover, if we let i ? n in (D2), we have aj P t0,1u for 1 ? j ? r and thus
?rj?1`gipujqaj ? ? ?rj?1`1aj? ? 1. This proves (A3). By a similar argument, one can prove (A2)
and (A4), and this completes the proof of Theorem 8.2.
112
8.6 Corollaries
For a matrixA, letAj denote thejth column ofA, and letspAq denote the sum of all the
elements of A. Let R? rr1...rksT (or RT ? rris1?k), ? ? r?1...?msT and H ? rh1...hmsT
be three column vectors with ri,?i P N, and hi P t1,...,nu for 1 ? i ? m, such that
h1...,hm are distinct. Let ?KHn denote a hypergraph with vertex set V, |V| ?n, such that
there are ?i edges of size hi incident with every hi vertices for 1 ?i?m. A hypergraph G is
said to bek-regular if every vertex has degreek. Ak-factor ofG is ak-regular spanning sub-
hypergraph of G. An R-factorization is a partition (decomposition) tF1,...,Fku of EpGq in
which Fi is an ri-factor for 1 ? i ? k. Notice that ?KHn is ?mi?1?i`n?1h
i?1
?-regular. We show
that the obvious necessary conditions for the existence of an R-factorization of ?KHn , are
also sufficient.
Theorem 8.3. ?KHn is R-factorizable if and only if spRq ? ?mi?1?i`n?1h
i?1
?, and there exists
a non-negative integer matrix A ? raijsk?m such that AH ? nR, and spAjq ? ?j`nh
j
? for
1 ?j ?m.
Proof. To prove the necessity, suppose that ?KHn is R-factorizable. Since each ri-factor is
an ri-regular spanning sub-hypergraph for 1 ? i ? k, and ?KHn is ?mi?1?i`n?1h
i?1
?-regular,
we must have spRq ? ?ki?1ri ? ?mi?1?i`n?1hi?1?. Let aij be the number of edges (counting
multiplicities) of size hj contributing to the ith factor for 1 ? i ? k, 1 ? j ? m. Since for
1 ?j ?m, each edge of size hj contributes hj to the the sum of the degrees of the vertices in
an ri-factor for 1 ?i?k, we must have ?mj?1aijhj ?nri for 1 ?i?k and ?ki?1aij ??j`nh
j
?
for 1 ?j ?m.
To prove the sufficiency, let F be a hypergraph consisting of a single vertex v with
mFpvhjq ? ?j`nhj? for 1 ? j ? m. Note that F is an amalgamation of ?KHn . Now we color
the edges of F so that mFpiqpvhjq ? aij for 1 ? i ? k, 1 ? j ? m. This can be done,
because:
k?
i?1
mFpiqpvhjq ?
k?
i?1
aij ??j
?n
hj
?
?mFpvhjq for 1 ?j ?m.
113
Moreover,
dFpiqpvq ?
m?
j?1
aijhj ?nri for 1 ?i?k.
Let g : VpFq ? N be a function so that gpvq ?n. Since for 1 ?i ?m, hi ?n, g is simple.
By Theorem 8.2, there exists a simple g-detachment G of F with n vertices, say v1,...,vn
such that by (A2), dGpiqpvjq ? dFpiqpvq{gpvq ? nri{n ? ri for 1 ? i ? k, 1 ? j ? n, and by
(A3), for each U ? tv1,...,vnu with |U| ? hj, mGpUq ? mFpvhjq{`nh
j
? ? ?
j
`n
hj
?{`n
hj
? ? ?
j
for 1 ? j ? m. Therefore G ? ?KHn , and the ith color class induces an ri-factor for
1 ?i?k.
In particular, if m ? 1, h :? h1, ?1 ? 1, r :? r1 ? ??? ? rk, then Theorem 8.3 implies
Baranyai?s theorem: the complete h-uniform hypergraph Khn is r-factorizable if and only if
hcwmrn and r cwm `n?1h?1?.
Now let hi ? 2 for 1 ? i ? m, and let ?KHp1,...,pn be a hypergraph with vertex partition
tV1,...,Vnu, |Vi| ? pi for 1 ? i ? n such that there are ?i edges of size hi incident with
every hi vertices, at most one vertex from each part for 1 ? i ? m (so no edge is incident
with more than one vertex of a part). If p1 ? ??? ?pn :?p, we denote ?KHp1,...,pn by ?KHn?p.
Theorem 8.4. ?KHp1,...,pn is R-factorizable if and only if p1 ? ??? ? pn :? p, spRq ?
?m
i?1?i
`n?1
hi?1
?ph
i?1, and there exists a non-negative integer matrix A ? raijsk?m such that
AH ?npR, and spAjq ??j`nhj?phj for 1 ?j ?m.
Proof. To prove the necessity, suppose that ?KHp1,...,pn is R-factorizable (so it is regular). Let
u and v be two vertices from two different parts, say ath and bth parts, respectively. Since
114
dpuq ?dpvq, we have
?
1?j?m
?j
?
1?i1?????ihj?1?n
aRti1,...,ihj?1u
pi1 ...pihj?1 ?
?
1?j?m
?j
?
1?i1?????ihj?1?n
bRti1,...,ihj?1u
pi1 ...pihj?1 ??
?
1?j?m
?j
??
1?i1?????ihj?1?n
aRti1,...,ihj?1u
pi1 ...pihj?1 ?
?
1?i1?????ihj?1?n
bRti1,...,ihj?1u
pi1 ...pihj?1
?
? 0 ??
?
1?j?m
?j
?
pb
?
1?i1?????ihj?2?npi1 ...pihj?2 ?pa
?
1?i1?????ihj?2?npi1 ...pihj?2
?
? 0 ??
ppb ?paq
?
1?j?m
?j
?
1?i1?????ihj?2?npi1 ...pihj?2 ? 0 ??
pb ?pa.
Therefore, p1 ? ??? ? pn :? p. So ?KHn?p is ?mi?1?i`n?1h
i?1
?ph
i?1-regular, and we must have
spRq ? ?ki?1ri ? ?mi?1?i`n?1hi?1?phi?1. Moreover, there must exist non-negative integers aij,
1 ? i ? k, 1 ? j ? m, such that ?mj?1aijhj ? npri for 1 ? i ? k and ?ki?1aij ? ?j`nhj?phj
for 1 ? j ? m. We note that aij is in fact the number of edges (counting multiplicities) of
size hj contributing to the ith factor.
To prove the sufficiency, let ?p ? rphi?isT1?m, and let F ? ?pKHn with vertex set
V ? tv1,...,vnu. Notice that F is an amalgamation of ?KHn?p. By Theorem 8.3, F is
pR-factorizable. Therefore, we can color the edges of F so that
dFpiqpvq ?pri for v PV,1 ?i?k.
Letg : V ? Nbe a function so thatgpvq ?pforv PV. Sincep? 1,g is simple. By Theorem
8.2, there exists a simple g-detachment G of F with np vertices, say vi is detached to
vi1,...,vip for 1 ?i?n, such that by (A2), dGpiqpvabq ?dFpiqpvaq{gpvaq ?pri{p?ri for 1 ?
i ? k, 1 ? a ? n, 1 ? b ? p, and by (A3), mGpva1b1,...,vahjbhjq ? mFpva1,...,vahjq{phj ?
phj?j{phj ? ?j for 1 ? j ? m, 1 ? a1 ? ??? ? ahj ? n, 1 ? b1,...,bhj ? p. Therefore
G ? ?KHn?p, and the ith color class induces an ri-factor for 1 ?i?k.
115
In particular, if m ? 1, h :? h1, ?1 ? 1, r :? r1 ? ??? ? rk, then Theorem 8.4 implies
another one of Baranyai?s theorems: the complete h-uniform n-partite hypergraph Khn?p is
r-factorizable if and only if hcwmnpr and r cwm `n?1h?1?ph?1.
Let JTk ? r1...1s1?k. For two column vectors Q ? rq1...qksT, R ? rr1...rksT, if
qi ? ri for 1 ? i ? k, we say that Q ? R. For a hypergraph G, a pq,rq-factor is a spanning
sub-hypergraph in which
q ?dpvq ?r for each v PVpGq.
A pQ,Rq-factorization is a partition tF1,...,Fku of EpGq in which Fi is a pqi,riq-factor for
1 ? i ? k. An almost k-factor of G is pk ? 1,kq-factor. An almost R-factorization is an
pR?Jk,Rq-factorization. The proof of the following theorems are very similar to those of
Theorem 8.3 and 8.4.
Theorem 8.5. ?KHn is pQ,Rq-factorizable if and only if spQq ? ?mi?1?i`n?1hi?1? ?spRq, and
there exists a non-negative integer matrix A ? raijsk?m such that nQ ? AH ? nR, and
spAjq ??j`nh
j
? for 1 ?j ?m.
Proof. To prove the necessity, suppose that ?KHn is pQ,Rq-factorizable. Since ?KHn is
?m
i?1?i
`n?1
hi?1
?-regular, we must have spQq ? ?k
i?1qi ?
?m
i?1?i
`n?1
hi?1
? ? ?k
i?1ri ? spRq.
Since for 1 ?j ?m, each edge of size hj contributes hj to the the sum of the degrees of the
vertices in pqi,riq-factor for 1 ?i?k, there must exist non-negative integers aij, 1 ?i?k,
1 ? j ? m, such that nqi ? ?mj?1aijhj ? nri for 1 ? i ? k and ?ki?1aij ? ?j`nh
j
? for
1 ?j ?m.
To prove the sufficiency, let F be a hypergraph consisting of a single vertex v with
mFpvhjq ? ?j`nhj? for 1 ? j ? m. Note that F is an amalgamation of ?KHn . Now we color
the edges of F so that mFpiqpvhjq ? aij for 1 ? i ? k, 1 ? j ? m. This can be done,
because:
k?
i?1
mFpiqpvhjq ?
k?
i?1
aij ??j
?n
hj
?
?mFpvhjq for 1 ?j ?m.
116
Moreover,
nqi ?dFpiqpvq ?
m?
j?1
aijhj ?nri for 1 ?i?k.
Let g : VpFq ? N be a function so that gpvq ?n. Since for 1 ?i ?m, hi ?n, g is simple.
By Theorem 8.2, there exists a simple g-detachment G of F with n vertices, say v1,...,vn
such that by (A2), qi ? nqi{n ? dGpiqpvjq ? nri{n ? ri for 1 ? i ? k, 1 ? j ? n, and by
(A3), for each U ? tv1,...,vnu with |U| ? hj, mGpUq ? mFpvhjq{`nh
j
? ? ?
j
`n
hj
?{`n
hj
? ? ?
j
for 1 ? j ? m. Therefore G ? ?KHn , and the ith color class induces a pqi,riq-factor for
1 ?i?k.
Theorem 8.6. ?KHn is almost R-factorizable if and only if spRq?k ? ?mi?1?i`n?1hi?1? ?spRq,
and there exists a non-negative integer matrix A? raijsk?m such that npR?Jkq ?AH ?nR,
and spAjq ??j`nh
j
? for 1 ?j ?m.
Proof. It is enough to take Q?R?Jk in Theorem 8.5.
Theorem 8.7. ?KHn?p is pQ,Rq-factorizable if and only ifspQq ? ?mi?1?i`n?1hi?1?phi?1 ?spRq,
and there exists a non-negative integer matrix A ? raijsk?m such that npQ ? AH ? npR,
and spAjq ??j`nh
j
?ph
j for 1 ?j ?m.
Proof. To prove the necessity, suppose that ?KHn?p is pQ,Rq-factorizable. Since ?KHn?p is
?m
i?1?i
`n?1
hi?1
?ph
i?1-regular, we must have spQq ?
?k
i?1qi ?
?m
i?1?i
`n?1
hi?1
?ph
i?1 ?
?k
i?1ri ?
spRq. Moreover, there must exist non-negative integers aij, 1 ?i?k, 1 ?j ?m, such that
npqi ? ?mj?1aijhj ?npri for 1 ?i?k and ?ki?1aij ??j`nh
j
?ph
j for 1 ?j ?m.
To prove the sufficiency, let ?p ? rphi?isT1?m, and let F ? ?pKHn with vertex set
V ? tv1,...,vnu. Notice that F is an amalgamation of ?KHn?p. By Theorem 8.5, F is
ppQ,pRq-factorizable. Therefore, we can color the edges of F so that
pqi ?dFpiqpvq ?pri for v PV,1 ?i?k.
117
Let g : V ? N be a function so that gpvq ? p for v P V. Since p ? 1, g is simple. By
Theorem 8.2, thereexists a simpleg-detachmentG ofF withnpvertices, sayvi is detached to
vi1,...,vip for 1 ?i?n, such that by (A2),qi ?pqi{p?dGpiqpvabq ?pri{p?ri for1 ?i?k,
1 ? a ? n, 1 ? b ? p, and by (A3), mGpva1b1,...,vahjbhjq ? mFpva1,...,vahjq{phj ?
phj?j{phj ? ?j for 1 ? j ? m, 1 ? a1 ? ??? ? ahj ? n, 1 ? b1,...,bhj ? p. Therefore
G ? ?KHn?p, and the ith color class induces a ppi,riq-factor for 1 ?i?k.
Theorem 8.8. ?KHn?p is almostR-factorizable if and only if spRq?k ? ?mi?1?i`n?1h
i?1
?ph
i?1 ?
spRq, and there exists a non-negative integer matrix A ? raijsk?m such that nppR?Jkq ?
AH ?npR, and spAjq ??j`nhj?phj for 1 ?j ?m.
Proof. It is enough to take Q?R?Jk in Theorem 8.7.
118
Chapter 9
Connected Baranyai Theorem
9.1 Introduction
Let Khn ? pV,`Vh?q be the complete h-uniform hypergraph on vertex set V with |V| ?n.
Baranyai showed that Khn can be expressed as the union of edge-disjoint r-regular factors if
and only if h divides rn and r divides `n?1h?1?. Using a new proof technique, in this chapter
we prove that ?Khn can be expressed as the union G1 Y...YGk of k edge-disjoint factors,
where for 1 ? i ? k, Gi is ri-regular, if and only if (i) h divides rin for 1 ? i ? k, and (ii)
?k
i?1ri ? ?
`n?1
h?1
?. Moreover, for any i (1 ? i ? k) for which r
i ? 2, this new technique
allows us to guarantee that Gi is connected, generalizing Baranyai?s theorem, and answering
a question by Katona.
A hypergraph G is a pair pV,Eq where V is a finite set called the vertex set, E is the
edge multiset, where every edge is itself a multi-subset of V. This means that not only can
an edge occur multiple times in E, but also each vertex can have multiple occurrences within
an edge. The total number of occurrences of a vertex v among all edges of E is called the
degree, dGpvq of v in G. For a positive integer r, an r-factor in a hypergraph G is a spanning
r-regular sub-hypergraph, and a partition of the edge set of G into (disjoint) r-factors is
called an r-factorizaton. The hypergraph Khn :? pV,`Vh?q with |V| ?n (by `Vh? we mean the
collection of all h-subsets of V) is called a complete h-uniform hypergraph. Avoiding trivial
cases, we assume that n?h. Baranyai proved that:
Theorem 9.1. (Baranyai [15]) Khn is r-factorizable if and only if hcwmrn and r cwm `n?1h?1?.
It is natural to ask if we can obtain a connected factorization; that is, a factorization in
which each factor is a connected hypergraph. Let m be the least common multiple of h and
119
n, and let a?m{h. Define the set of edges
K ? tt1,...,hu,th`1,...,2hu,...,tpa?1qh`1,pa?1qh`2,...,ahuu,
where the elements of the edges are considered mod n. The families obtained from K by
permuting the elements of the underlying set tnu are called wreaths. If h divides n, then a
wreath is just a partition. Baranyai and Katona conjectured that the edge set of Khn can be
decomposed into disjoint wreaths [54]. In connection with this conjecture, Katona (private
communication) suggested the problem of finding a connected factorization for Khn. In this
chapter, we solve this problem.
An pr1,...,rkq-factorization of G is a partition of the edge set of G into F1,...,Fk where
Fi is an ri-factor for 1 ? i ? k. If we replace every edge e of Khn by ? copies of e, then
we denote the new hypergraph by ?Khn. In this chapter, the main result is the following
theorem:
Theorem 9.2. ?Khn is pr1,...,rkq-factorizable if and only if h cwm rin for 1 ? i ? k, and
?k
i?1ri ??
`n?1
h?1
?. Moreover, for 1 ?i?k, if r
i ? 2, then we can guarantee that the ri-factor
is connected.
While this generalizes Baranyai?s result in various ways, we note that the major exten-
sion is the guarantee of connectivity for the r-factors when r ? 2. In particular if ? ? 1,
and h ? r1 ? ??? ?rk ? 2, Theorem 9.2 implies the classical result of Walecki [64] that the
edge set of Kn can be partitioned into Hamiltonian cycles if and only if n is odd. Here we
list some other interesting special consequences of Theorem 9.2:
Corollary 9.3. Khn is connected 2-factorizable if and only if `n?1h?1? is even and hcwm 2n.
Corollary 9.4. Khn has a connected hgcdpn,hq-factorization.
We note that the idea behind the proof of Theorem 9.2 is based on the amalgamation
technique [44, 70]. Preliminaries are given in Section 9.2, followed by the proof of Theorem
9.2 in Section 9.3.
120
We end this section with some notation we need to be able to describe hypergraphs that
arise in this setting.
Let G ? pV,Eq be a hypergraph with ? PV, and let U ? tu1,...,uzu ?Vzt?u. Recall
that each edge is a multi-subset ofV. We abbreviate an edge of the formt?,...,?looomooon
p
,u1,...,uzu
to t?p,u1,...,uzu. An h-loop incident with ? is an edge of the form t?hu, and mp?p,Uq
denotes the multiplicity of an edge of the form t?puYU. A k-edge-coloring of G is a mapping
f : E ?C, where C is a set of k colors (often we use C ? t1,...,ku), and the edges of one
color form a color class. The sub-hypergraph of G induced by the color class i is denoted by
Gi, abbreviate dGip?q to dip?q and mGip?p,Uq to mip?p,Uq.
9.2 Preliminaries
A vertex ? in a connected hypergraph G is a cut vertex if there exist two non-trivial
sub-hypergraphs I,J of G such that I YJ ? G, VpI XJq ? ? and EpI XJq ? ?. A non-
trivial connected sub-hypergraph W of a connected hypergraph G is said to be an ?-wing
of G, if ? is not a cut vertex of W and no edge in EpGqzEpWq is incident with a vertex
in VpWqzt?u. The set of all ?-wings of G is denoted by W?pGq. Figure 9.1 illustrates an
example of a hypergraph and the set of all its ?-wings.
If the multiplicity of a vertex ? in an edge e is p, we say that ? is incident with p
distinct objects, say h1,...,hp. We call these objects hinges, and we say that e is incident
with h1,...,hp. The set of all hinges in G incident with ? is denoted by HGp?q; so |HGp?q|
is in fact the degree of ?.
Intuitively speaking, an?-detachment ofG is a hypergraph obtained by splitting a vertex
? into one or more vertices and sharing the incident hinges and edges among the subvertices.
That is, in an ?-detachment G1 of G in which we split ? into ? and ?, an edge of the form
t?p,u1,...,uzu in G will be of the form t?p?i,?i,u1,...,uzu in G1 for somei, 0 ?i?p. Note
that a hypergraph and its detachments have the same hinges. Whenever it is not ambiguous,
we use d1, m1, etc. for degree, multiplicity and other hypergraph parameters in G1. Also, for
121
? ?
?
, ,
u
W?pGq ? t
?
G
Figure 9.1: A hypergraph G and the set of all its ?-wings
an ?-wing W in G and an ?-detachment G1, let W1 denote the sub-hypergraph of G1 whose
hinges are the same as those in W.
We shall present three lemmas, all of which follow immediately from definitions.
Lemma 9.5. Let G be a connected hypergraph. Let G1 be an ?-detachment of G obtained by
splitting a vertex ? into two vertices ? and ?. Then G1 is connected if and only if for some
?-wing W PW?pGq with dWp?q ? 2,
1 ? |HWp?qXHG1p?q| ?dWp?q.
Informally speaking, Lemma 9.5 says that for some ?-wing W with dWp?q ? 2, at least
one but not all the hinges incident with ? in W must be incident with ? in G1.
A family A of sets is laminar if, for every pair A,B of sets belonging to A: A?B, or
B ?A, or AXB ? ?.
Let us fix a vertex ? of a k-edge-colored hypergraph G ? pV,Eq. For 1 ? i ? k, let
Hi be the set of hinges each of which is incident with both ? and an edge of color i (so
dip?q ? |Hi|). For any edge e P E, let He be the collection of hinges incident with both ?
122
and e. Clearly, if e is of color i, then He ? Hi. For an ?-wing W, let HW ? HWp?q. For
1 ?i?k, let
Hi ?
?
WPW?pGiq,dWp?q?2
HW.
Lemma 9.6. Let
A ? tH1,...,HkuYtHW : W PW?pGiq,1 ?i?ku
Y tH1,...,HkuYtHe : ePEu.
Then A is a laminar family of subsets of Hp?q.
For each p ? 1, and each U ? Vzt?u, let HUp be the set of hinges each of which is
incident with both ? and an edge of the form t?puYU in G (so |HUp | ?pmp?p,Uq).
Lemma 9.7. Let
B ? tHUp : p? 1,U ?Vzt?uu.
Then B is a laminar family of subsets of Hp?q.
If x,y are real numbers, x ? y means tyu ? x ? rys. We need the following powerful
lemma:
Lemma 9.8. (Nash-Williams [70, Lemma 2]) If A,B are two laminar families of subsets
of a finite set S, and n is a positive integer, then there exist a subset A of S such that
|AXP| ? |P|{n for every P PA YB.
9.3 Proof of the Main Theorem
To prove Theorem 9.2, first we look at the obvious necessary conditions:
Lemma 9.9. If ?Khn is connected pr1,...,rkq-factorizable, then
123
(i) ri ? 2 for 1 ?i?k,
(ii) hcwmrin for 1 ?i?k, and
(iii) ?ki?1ri ??`n?1h?1?.
Proof. Suppose that ?Khn is connected pr1,...,rkq-factorizable. The necessity of (i) is suffi-
ciently obvious. Since each edge contributes h to the the sum of the degrees of the vertices
in an ri-factor for 1 ?i?k, we must have (ii). Since each ri-factor is an ri-regular spanning
sub-hypergraph for 1 ?i?k, and ?Khn is ?`n?1h?1?-regular, we must have (iii).
In order to get an inductive proof of Theorem 9.2 to work, we actually prove the following
seemingly stronger result:
Theorem 9.10. Let n,h,?,k,r1,...,rk be positive integers with n ? h satisfying (i)?(iii).
For any integer 1 ? ? ? n, there exists an ?-vertex k-edge-colored hypergraph G with vertex
set V (? PV) such that
dipuq ?
$
?&
?%
ripn??`1q if u??
ri if u??
for uPV,1 ?i?k, (9.1)
mp?p,Uq ??
?n??`1
p
?
for p? 0,U ?Vzt?u with |U| ?h?p, and (9.2)
Gi is connected if ri ? 2, for 1 ?i?k. (9.3)
Remark 9.11. Theorem 9.2 follows from Theorem 9.10 in the case where ? ? n as the
following argument shows. If ? ? n, then conditions (9.1)?(9.3) imply that we have an n-
vertex k-edge-colored hypergraph G in which the ith color class is ri-regular by (9.1), and
connected by (9.3). Moreover, (9.2) implies that for U ? Vzt?u, (i) mpUq ? ?`10? ? ? if
|U| ? h (when p ? 0), (ii) mp?,Uq ? ?`11? ? ? if |U| ? h ? 1 (when p ? 1), and (iii)
mp?p,Uq ??`1p? ? 0 for p? 2, and |U| ?h?p. Therefore G ??Khn.
124
Proof. The proof is by induction on ?. At each step we will assume not only that G is an ?-
vertexk-edge-colored hypergraph with vertex setV (? PV) satisfying conditions (9.1)?(9.3),
but that G also satisfies the two additional properties
|He| ?n??`1 for each edge e of G, and (9.4)
for 1 ?i?k, if ri ? 2, then ?i ?ripn??`1q (9.5)
where for 1 ?i?k, ?i ? |Hi|.
First consider the base case when ?? 1. Let F be a hypergraph with a single vertex ?
incident with?`nh?h-loops; i.e. mp?hq ??`nh?. Color theedges ofF such thatmip?hq ?rin{h
for 1 ?i?k. This is possible since by (ii) hcwmrin, and by (iii) ?ki?1mip?hq ? ?ki?1rin{h?
n{h?ki?1ri ? ?n`n?1h?1?{h ? ?`nh? ? mp?hq. Also, note that for ? ? 1, the hypergraph F
trivially satisfies (9.4), and since each h-loop is an ?-wing, F also satisfies (9.5). Therefore,
F shows that conditions (9.1)?(9.5) holds for ?? 1.
Now suppose that 1 ? ? ? n, and that G satisfies (9.1)?(9.5). The proof is completed
by showing that G has an p?` 1q-vertex ?-detachment G1 with vertex set V1 ? V Y t?u
satisfying
|H1e| ?n?? for each edge e of G1, (9.6)
d1ipuq ?
$
?&
?%
ripn??q if u??
ri if u??
for uPV1,1 ?i?k, (9.7)
m1p?p,Uq ??
?n??
p
?
for p? 0,U ?V1zt?u with |U| ?h?p, (9.8)
G1piq is connected if ri ? 2, for 1 ?i?k, and (9.9)
125
for 1 ?i?k, if ri ? 2 and if ??n?1, then
?1i ?ripn??q. (9.10)
Let A and B be the laminar families in Lemmas 9.6, and 9.7. By Lemma 9.8, there
exists a subset A of Hp?q such that
|AXP| ? |P|{pn??`1q for every P PA YB. (9.11)
Let G1 be the hypergraph obtained from G by splitting ? into two vertices ? and ? in such a
way that hinges which were incident with ? in G become incident in G1 with ? or? according
as they do not or do belong to A, respectively. More precisely,
H1p?q ?A, H1p?q ?Hp?qzA. (9.12)
Since Hi PA for 1 ?i?k, we have
d1ip?q ? |AXHi|
? |Hi|{pn??`1q ?dip?q{pn??`1q
? ripn??`1q{pn??`1q ?ri,
d1ip?q ? dip?q?d1ip?q
? ripn??`1q?ri ?ripn??q,
and for uR t?,?u, d1ipuq ?dipuq ?ri. Therefore G1 satisfies (9.7).
Let e be an edge in G incident with ?. Then He PA, and so
|AXHe| ? |He|{pn??`1q ? 1,
126
observing that the last inequality implies from (9.4). This means that either AXHe ? ?
or |A X He| ? 1. Therefore m1p?q,Uq ? 0 for q ? 2 and U ? V1. Also, note that if
|He| ? n??` 1, then |AXHe| ? 1 and thus |H1e| ? n??, and if |He| ? n??` 1, then
|H1e| ? |He| ?n??, both cases together proving (9.6).
Since for p? 1, and U ?Vzt?u, HUp PB, we have
m1p?p?1,?,Uq ? |AXHUp |
? |HUp |{pn??`1q ?pmp?p,Uq{pn??`1q
? ?p
?n??`1
p
?
{pn??`1q ??
?n??
p?1
?
,
m1p?p,Uq ? mp?p,Uq?m1p?p?1,?,Uq
? ?
?n??`1
p
?
??
?n??
p?1
?
??
?n??
p
?
.
Therefore G1 satisfies (9.8).
Let us fix an i, 1 ?i ?k such that ri ? 2. Let W be an ?-wing of Gi with dWp?q ? 2.
Then HW PA, and so
|AXHW| ? |HW|{pn??`1q ?dWp?q{pn??`1q, (9.13)
which implies that (noting that n??`1 ? 2)
|AXHW| ? |HW|. (9.14)
Moreover,
|AXHi| ? |Hi|{pn??`1q ??i{pn??`1q ?ri ? 2, (9.15)
and therefore there exists an ?-wing W in Gi with dWp?q ? 2, such that AXHW ? ?.
Therefore by Lemma 9.5, G1i is connected.
127
Now, suppose that ??n?2, or equivalently that n??`1 ? 3. Since ?i ?di, we have
that for every W PW?pGiq, dWp?q ? 2. So there is no ?-wing W in Gi with dWp?q ? 1. Let
us fix an ?-wing W in Gi. There are two cases to consider:
? Case 1: If |HW| ? 3, then since |AXHW| ? |HW|{pn??`1q ? |HW|{3, we have that
d1W1p?q ? 2, and thus ?1i ? d1ip?q ? ripn??q. Note that W1 is a sub-hypergraph of
some ?-wing S in G1 with d1Sp?q ? 2.
? Case 2: If |HW| ? 2, then |AXHW| ? |HW|{pn??` 1q ? 2{pn??` 1q ? 2{3. So
|AXHW| P t0,1u. If AXHW ? ?, we are done. So let us assume that |AXHW| ? 1.
Recall from (9.15) that |AXHi| ? 2. Therefore, there is another ?-wing T in Gi with
|HT| ? 2 such that 1 ? |AXHT| ? |HT|. Therefore, there exists an?-wingS in G1 with
W1 YT1 ?S, and d1Sp?q ? 2. Thus, in this case also we have ?1i ??i ?ri ?ripn??q.
Therefore G1 satisfies (9.10) and the proof is complete.
128
Chapter 10
Polynomial Time Parallelisms
10.1 Introduction
Throughout this chapter, k is a fixed positive integer. Let Pkpnq be the collection of all
k-element subsets of ann-set. A parallelism onPkpnq is an equivalence relation ofPkpnq such
that the members of each equivalence class form a partition of the n-set. Each equivalence
class is called a parallel class, that is a set of n{k k-subsets each of which partitions the n-
set. In connection with Kirkman?s famous Fifteen Schoolgirls Problem [56], in 1850 Sylvester
asked whether it is possible to find a parallelism on Pkpnq. Of course, it is necessary that k
divides n, and the number of parallel classes would be kn`nk? ? `n?1k?1?. For those readers with
(hyper)graph theory background, we note that finding a parallelism onPkpnq is equivalent to
finding a 1-factorization for a complete k-uniform hypergraph on n vertices. Sylvester found
a parallelism on P3p15q. Several generalizations of this problem were studied during the last
70 years (see for example [71, 73]), but the general case remained open until 1973, when
Baranyai settled this old problem [15]. Baranyai?s elegant proof actually yields a method
for constructing a parallelism on Pkpnq recursively. However, this approach is not be very
efficient, its complexity being exponential (Op2nq) [53, p. 226]. Later Brouwer and Schrijver
gave another proof for which the complexity is polynomial in `nk?, the output size for the
problem [25].
In this chapter, using our proof techniques of Chapter 5 and Chapter 8, we give a con-
structive proof of polynomial time complexity for the existence of a parallelism on Pkpnq. All
known proofs including the one we shall present here, use a form of network flow; specifically,
we use an approach which has been useful in finding detachments of graphs [70]. We note
even though our proof is very similar to that of Brouwer and Schrijver [25], it is obtained
129
independently by simplifying the proofs of Theorem 10.3 and Nash-Williams lemma. For
applications of parallelism on Pkpnq in computer science and biology (such as parallel algo-
rithms for tightening inter-atomic distance-bounds required for molecular conformation) see
[33, 34, 72]. It is shown in [55] that there are 103000 isomorphic classes of parallelisms on
P3p9q.
10.2 Terminology
Ifx,y are real numbers, then txu and rxs denote the integers such thatx?1 ? txu ?x?
rxs ? x`1, and x ? y means tyu ? x ? rys. For a multiset A and u P A, let ?Apuq denote
the multiplicity of u in A, and let |A| ? ?uPA?Apuq. For multisets A1,...,An, we define
A ? ?ni?1Ai so that ?Apuq ? ?ni?1?Aipuq. We abbreviate tu,...,ulooomooon
r
u to turu; for example
tu2,v,w2uYtu,w2u ? tu3,v,w4u.
A circulation on a digraph D is a mapping f from EpDq to the reals satisfying conserva-
tion of flow at every vertex (see [84, chap. 7]). Let N?pvq and N`pvq denote the in-neighbor
and out-neighbor of the vertex v, respectively. By pv,wq we mean a directed edge from v
to w, and we abbreviate fptv,wuq to fpv,wq. Let f be a circulation on a finite digraph
D. Then it is known that there exists an integral circulation g (obtainable by a polytime
algorithm) such that gpeq ?fpeq for every edge e (see for example [70, Lemma 1]).
10.3 Proofs
Theorem 10.1. Ifk dividesn, then the set of all `nk?k-subsets of an n-set may be partitioned
into disjoint parallel classes Ai, i? 1,...,`n?1k?1?.
In order to get an inductive proof to work, rather than prove Theorem 10.1, we prove
the stronger result Theorem 10.2 below. Let m?n{k, M ? `n?1k?1?. We use the term pm,kq-
split of a set X for a multiset A of mk-multi-subsets of X whose union contains X. For an
130
integer ? and a set A1,...,AM of pm,kq-splits of t1,...,?u, let ?ji ? ??PAj ??piq, and for
0 ?r ?k and S ? t2,...,?u with |S| ?k?r, let ?rS ? ?Mi?1?Ai`SYt1ru?.
Theorem 10.2. For any integer ?, 1 ???n, there exist a set
P ? tA1,...,AMu
of pm,kq-splits of t1,...,?u such that for 1 ? j ? M, ?j1 ? n??`1, ?ji ? 1 for 2 ? i ? ?,
and ?rS ? `n??`1r ? for 0 ? r ?k and each S ? t2,...,?u with |S| ? k?r. Moreover, P can
be obtained by a polynomial time algorithm.
Proof. We prove our assertion by induction on ?. Notice that it is true for ?? 1 by choosing
A1 ? ??? ? AM ? tt1kumu. Also notice that proving the case ? ? n will prove Theorem
10.1, since ?ji ? 1 for 1 ? i ? n means that each Aj forms a partition of t1,...,nu for
j ? 1,...,M, and ?rS ? `1r? for 0 ? r ? k and each S ? t2,...,nu with |S| ? k?r means
that every k-subset of the n-set appears exactly once in ?Mi?1Ai (the cases r ? 1 and 0
consider subsets of t1,...,nu that do and do not contain 1 respectively).
Assume for some value ? ? n that pm,kq-splits A1,...,AM exist with the required
properties. We form a digraph D with vertex multiset V ? t?,?u Y ty1,...,yMu Y tw? :
? P ?Mi?1Ai,??p1q ? 0u Y tvrS : 0 ? r ? k,S ? t2,...,?u,|S| ? k ?r,?rS ? 0u and with
a circulation f as follows. (Note that some ? may occur several times in Ai, the name w?
may occur on several vertices, so V is a multiset.)
? For 1 ?i?M, there is a directed edge from ? to yi such that fp?,yiq ? 1.
? For 1 ?i?M and for each ? P Ai with ??p1q ? 0, there is a directed edge from yi to
w? such that fpyi,w?q ???p1q{pn??`1q.
? For 0 ? r ? k, and for S ? t2,...,?u with |S| ? k ? r, if ?rS ? 0 then for each
??SYt1ru in ?Mi?1Ai, there is a directed edge from w? to vrS such that fpw?,vrSq ?
??p1q{pn??`1q, and there is a directed edge from vrS to ? such that fpvrS,?q ? `n??r?1?.
131
? There is a directed edge from ? to ? such that fp?,?q ?M.
It is straightforward to check that f is a circulation (see Figure 10.1). There is an integer
circulationg onD such thatgpeq ?fpeq for each edgeeinD. Let us fix ani, 1 ?i?M. For
each ? P Ai with ??p1q ? 0, we have gpyi,w?q P t0,1u. More important, since gp?,yiq ? 1,
there is exactly one ? in Ai such that gpyi,w?q ? 1. Now, we obtain an pm,kq-split A1i of
the set t1,...,?` 1u by letting A1i be obtained from Ai by replacing one 1 in ? P Ai with
?` 1 if gpyi,w?q ? 1. At this point, it is clear that our construction is of polynomial time
complexity.
Finally, we show that the pm,kq-splits A11,...,A1M satisfy the required properties. We
define ?1ij and ?1Sr for A11,...,A1M similarly to the way we defined them for A1,...,AM.
Obviously, ?1ij ? ?ji ? 1 for 2 ? i ? ?, 1 ? j ? M. Also ?1?`1j ? 1, and ?11j ? ?j1 ??1?`1j ?
n?? for 1 ?j ?M. Moreover, for 0 ?r ?k, S ? t1,...,?`1u with |S| ?k?r, if ?`1 PS
then ?1Sr ? gpvr`1Szt?`1u,?q ? `n??r ?, and if S ? t1,...,?u then ?1Sr ? `n??`1r ? ?gpvrS,?q ?
`n??`1
r
??`n??
r?1
? ? `n??
r
?. This completes the proof.
132
?
y1
yd
yi
..
.
..
.
..
.
1
1
1
??
p1q
n?
?`
1
..
.
??
p1q
n?
?`
1
w
?
..
.
..
.
`n
??r?1 ?
v rS
?
..
.
d
S
?
?z
t1
ru
w
?
??
p1q
n?
?`
1
Figure 10.1: Digraph D with circulation f
133
Chapter 11
Recent Results and Future Directions
In this chapter, I shall summarize my research, the significance of my results, and some
motivation for future research. For each topic, I describe the problem with a brief discussion
on proof techniques, applications and extensions together with related open problems.
11.1 Amalgamations and Connected Fair Detachments
A detachment of a graph H is a graph obtained from H by splitting some or all of its
vertices into more than one vertex. If g is a function from VpHq into N, then a g-detachment
of H is a detachment of H in which each vertex u of H splits into gpuq vertices. H is an
amalgamation of G if there exists a function ? called an amalgamation function from VpGq
onto VpHq and a bijection ?1 : EpGq ?EpHq such that e joining u and v is in EpGq iff ?1peq
joining ?puq and ?pvq is in EpHq.
A k-edge-coloring of G is a mapping f : E ? C, where E is the edge set of G and
C is a set of k colors (we often use C ? t1,...,ku), and the edges of one color form a
color class. In [5], we proved that for a given edge-colored graph there exists a detachment
so that the result is a graph in which the edges are shared among the vertices in ways
that are fair with respect to several notions of balance (such as between pairs of vertices,
degrees of vertices in both the graph and in each color class, etc.). The connectivity of color
classes is also addressed. Applications of this result are addressed in Sections 11.3 and 11.5.
Most results in the literature on amalgamations focus on the detachments of amalgamated
complete graphs and complete multipartite graphs. Many such results ([44, 48, 58, 61, 74],
Theorem 1, Theorem 1, Theorem 3.1, Theorem 2.1 and Theorem 2.1, respectively) follow as
134
immediate corollaries to our main result in [5], which addresses amalgamations of graphs in
general.
11.1.1 Edge-Coloring Techniques
An edge-coloring of a multigraph is (i) equalized if the number of edges colored with
any two colors differs by at most one, (ii) balanced if for each pair of vertices, among the
edges joining the pair, the number of edges of each color differs by at most one from the
number of edges of each other color, and (iii) equitable if, among the edges incident with each
vertex, the number of edges of each color differs by at most one from the number of edges
of each other color. In [80, 81, 82, 83] de Werra studied balanced equitable edge-colorings of
bipartite graphs. The following lemma by de Werra is used to prove the main result in [5]:
Lemma 11.1. Every bipartite graph has a balanced, equitable and equalized k-edge-coloring
@k P N.
11.2 Fair Detachments of Hypergraphs
A hypergraph G is a pair pV,Eq where V is a finite set called the vertex set, E is the
edge multiset, where every edge is a multi-subset of V. A detachment of a hypergraph is
formed by splitting each vertex into one or more subvertices, and sharing the incident edges
arbitrarily among the subvertices. Let F be a hypergraph in which each edge is of size at
most 3. In [6], I proved that for a given edge-coloring of F, there exists a detachment G such
that the degree of each vertex and the multiplicity of each edge in F (and each color class
of F) are shared fairly among the subvertices in G (and each color class of G, respectively).
11.2.1 Laminar Families
A family A of sets is laminar if, for every pairA,B of sets belonging to A, eitherA?B,
or B ? A, or AXB ? ?. To extend our main result in [5] to hypergraphs [6], I used the
following lemma by Nash-Williams [70] (Here x?y means tyu ?x? rys):
135
Lemma 11.2. If A,B are two laminar families of subsets of a finite set S, and nP N, then
there exist a subset A of S such that for every P PA YB, |AXP| ? |P|{n.
In [8], I generalized the results in [6] to arbitrary hypergraphs. Here dpvq denotes the
degree of the vertex v, Gpjq denotes the color class j of G, and mpum11 ,...,umrr q denotes the
multiplicity of an edge of the form
tu1,...,u1loooomoooon
m1
,...,ur,...,urloooomoooon
mr
u.
Theorem 11.3. Let F be a k-edge-colored hypergraph and let g : VpFq ? N. Then F
has a fair g-detachment G. That is, there exists a g-detachment G of F with amalgamation
function ? : VpGq ?VpFq ( @v PVpFq, gpvq ? |??1pvq|) such that:
(A1) dGpvq ?dFpuq{gpuq for each uPVpFq and each v P ??1puq;
(A2) dGpjqpvq ?dFpjqpuq{gpuq for each uPVpFq, each v P ??1puq and 1 ?j ?k;
(A3) mGpU1,...,Urq ? mFpum11 ,...,umrr q{?ri?1`gpuiqmi ? for distinct u1,...,ur P VpFq and
Ui ? ??1puiq with |Ui| ?mi ?gpuiq for 1 ?i?r;
(A4) mGpjqpU1,...,Urq ?mFpjqpum11 ,...,umrr q{?ri?1`gpuiqm
i
? for distinct u
1,...,ur PVpFq and
Ui ? ??1puiq with |Ui| ?mi ?gpuiq for 1 ?i?r and 1 ?j ?k.
Applications of this theorem are discussed in Sections 11.4 and 11.6.
11.3 Edge-Decompositions and Edge-Colorings
An pr1,...,rkq-factorization of a graph G is a partition (decomposition) tF1,...,Fku of
EpGq in which Fi is an ri-factor (ri-regular spanning) for i? 1,...,k. While the main result
in [5] is interesting by itself, it provides a short proof for the following well-known results
(see [9]):
136
? ?Kn (?-fold complete graph) is decomposable into Hamiltonian cycles iff ?pn? 1q is
even.
? ?Kn is pr1,...,rkq-factorizable iff rin is even for 1 ? i ? k, and ?ki?1ri ? ?pn? 1q.
Moreover, each ri-factor can be guaranteed to be connected if ri is even.
? ?Kn1,...,nm (?-fold complete multipartite graph) is Hamiltonian decomposable iff n1 ?
??? ?nm :?n, and ?npm?1q is even.
? ?Kn1,...,nm is pr1,...,rkq-factorizable iff n1 ? ??? ?nm :?n, rinmis even for 1 ?i?k,
and ?ki?1ri ??npm?1q.
Let mpu,vq denote the number of edges between u and v. Let Kpa1,...,ap;?,?q be a graph
with p parts V1,...,Vp, with |Vi| ? ai for 1 ? i ? p, mGpu,vq ? ? for every pair of distinct
vertices u,v P Vi for 1 ? i ? p, and mGpu,vq ? ? for each u P Vi,v P Vj for 1 ? i ? j ? p.
This graph arises naturally in statistical settings [22]. In [5], we found necessary and sufficient
conditions for Kpa1,...,ap;?,?q to be decomposable into Hamiltonian cycles.
The Oberwolfach problem asks whether or not it is possible to partition the edge set of
Kn, n odd, into isomorphic 2-factors such that each 2-factor consists of aj cycles of length
rj, 1 ? j ? k, and n ? ?kj?1rjaj. In [46] some new solutions to the Oberwolfach problem
are given using the amalgamation technique. I am planning to attack the following problem
using amalgamations for which I need to obtain a detachment result in which each color
class is evenly equitable:
Conjecture 11.4. (Alspach 1981) If n is odd, 3 ? c1,...,cm ? n, and ?ni?1ci ? `n2?, then
Kn decomposes into cycles of lengths c1,...,cm.
11.4 Hypergraph Edge-Colorings and Baranyai?s Theorem
In a mathematics workshop with mn mathematicians in n different areas, each area
consisting ofmmathematicians, we want to create a collaboration network. For this purpose,
137
we would like to schedule daily meetings between groups of size three, so that (i) two persons
of the same area meet one person of another area, (ii) each person has exactly r meetings
each day, and (iii) every two persons of the same area have exactly ? meetings with each
person of another area by the end of the workshop. Using hypergraph amalgamations, in
[7] I proved a general result regarding factorizations of a family of multipartite hypergraphs,
and as a corollary I showed that the above scheduling can be done if: 3 cwm rm, 2 cwm rnm and
r cwm 3?pn?1q`m2?.
Let `rnsh ? denote the set of all h-subsets of rns :? t1,...,nu. Let Khn ? prns,`rnsh ?q. The
problem of finding 1-factorizations for Khn remained an unsolved problem for 120 years until
it was settled by Baranyai (1975) [15]. Since then not much has been done in this area and
many problems remain open.
Here wediscuss a different approach (amalgamationsand detachments) toextend Baranyai?s
results and to answer various related questions. An immediate corollary of Theorem 11.3
is that the obvious necessary conditions for ?Khn to be pr1,...,rkq-factorizable are also suf-
ficient. Let Khp1,...,pn ? pV,Eq be a hypergraph with vertex partition tV1,...,Vnu, |Vi| ? pi
for 1 ? i ? n, and E ? te ? V : |e| ? h,|eXVi| ? 1 for 1 ? i ? nu. Another consequence
of Theorem 11.3 is that the obvious necessary conditions for ?Khp1,...,pn to be pr1,...,rkq-
factorizable are also sufficient.
11.4.1 The Berge-Johnson Problem
For a matrix A, let Aj denote the jth column of A, and let spAq denote the sum of all
the entries of A. Let RT ? rris1?k, ?T ? r?is1?m and HT ? rhis1?m be three vectors with
ri,?i P N, and hi P t1,...,nu for 1 ?i?m, such that h1...,hm are distinct.
Let ?KHp1,...,pn be a hypergraph with vertex partition tV1,...,Vnu, |Vi| ?pi for 1 ?i?n
such that there are ?i edges of size hi incident with every hi vertices, at most one vertex
from each part for 1 ? i ? m (so no edge is incident with more than one vertex of a part).
Here is another interesting corollary of Theorem 11.3:
138
Theorem 11.5. ?KHp1...,pn is pr1,...,rkq-factorizable iff p1 ? ??? ? pn :? p, spRq ?
?m
i?1?i
`n?1
hi?1
?ph
i?1, and there exists a non-negative integer matrix A ? raijsk?m such that
AH ?npR, and spAjq ??j`nh
j
?ph
j for 1 ?j ?m.
Baranyai [15, 16] solved the case of h1 ? ??? ? hm, ?1 ? ...,?m ? 1, p1 ? ??? ? pm,
r1 ? ??? ?rk. Berge and Johnson [21], (and later Brouwer and Tijdeman [26], respectively)
considered (and solved, respectively) the case of hi ? i, 1 ? i ? m, p1 ? ??? ? pm ? ?1 ?
??? ??m ?r1 ? ??? ?rk ? 1.
11.4.2 Baranyai-Katona Conjecture
Let m be the least common multiple of h and n, and let a?m{h. Define
K ? tt1,...,hu,th`1,...,2hu,...,tpa?1qh`1,pa?1qh`2,...,ahuu,
where the elements of the sets are considered mod n. The families obtained from K by
permuting the elements of the underlying set rns are called wreaths. If h divides n, then
a wreath is just a partition. It was conjectured that Khn can be decomposed into disjoint
wreaths [54]. In connection with this conjecture, I am currently working on the connectivity
of factors [12, 13].
11.4.3 Connected Factorizations
In [12], I solved the following problem which was suggested by Katona:
Theorem 11.6. ?Khn is pr1,...,rkq-factorizable iff h cwm rin for 1 ? i ? k, and ?ki?1ri ?
?`n?1h?1?. Moreover, for 1 ?i?k an ri-factor is connected if ri ? 2.
This can be considered as a connected version of Baranyai?s Theorem. In particular if
? ? 1, and h ? r1 ? ??? ? rk ? 2, this implies the classical result of Walecki that the edge
set of Kn can be partitioned into Hamiltonian cycles iff n is odd. A related problem due to
Bermond (1978) asked for conditions under which one can decompose Khn into Hamiltonian
139
cycles. I am interested in the following more general problem that relates my work to the
results of Nash-Williams [68], and their extensions [18]:
Problem 5. Find necessary and sufficient conditions for an edge-colored hypergraph F to
have a fair detachment in which each color class is k-edge-connected.
So far [13], I have been able to solve this problem when all edges of F are of size at
most 3, and k ? 2. This, in particular, implies another Baranyai-type theorem (h ? 3) in
which each factor is 2-edge-connected.
11.4.4 Kneser Graphs and the Middle Levels Problem
The Kneser graphKpn,hq has as vertices theh-subsets of rns. Two vertices are adjacent
if the corresponding h-subsets are disjoint. It is widely conjectured that all Kneser graphs
but the Petersen graph, Kp5,2q, have Hamiltonian cycles. Let n ? 2h` 1. The bipartite
Kneser Graph Hpn,hq has as its partite sets the h- and pn?hq-subsets of rns. Two vertices
A and B from different partite sets are adjacent if the h-subset A is contained in the pn?hq-
subset B. It is conjectured that Hp2h` 1,hq is Hamiltonian. Using Baranyai?s Theorem,
partial results to these two conjectures are given in [30, 32]. I am interested in working on
these two conjectures.
11.5 Extending Partial Decompositions and Graph Embedding Problems
In this section and the next section I describe the usefulness of amalgamations in solving
embedding problems. For example the main result in [5] provides a short proof for the
following theorems (see [9]): Ak-edge-coloring ofKm can be embedded into (i) a Hamiltonian
decomposition of Km`n(Hilton [44]), (ii) an pr1,...,rkq-factorization of Km`n(Johnson [51])
iff the obvious necessary conditions are satisfied. Embedding Hamiltonian cycles in complete
multipartite graphs is considered in [48] but the problem is still open and I am interested in
working on it. When a1 ? ??? ?ap :? a, let Kpappq;?,?q denote Kpa1,...,ap;?,?q. In [10],
we asked:
140
Problem 6. When can a graph decomposition of Kpappq;?,?q be extended to a Hamiltonian
decomposition of Kpapp`rq;?,?q for r ? 0?
We proved [10]:
Theorem 11.7. Let f : E ? C be a k-edge coloring for Kpappq;?,?q, and let ?j denote
the number of components of color class j. For 1 ? j ? k, define sj ? ?j pmod rq with
1 ?sj ?r, and suppose ?kj?1sj ?kr??a2`r2?. Then f can be embedded into a Hamiltonian
decomposition of Kpapp`rq;?,?q iff the obvious necessary conditions are satisfied.
We used this general result to give a complete solution to Problem 6 for allr ? ??a`p?1a?1.
We also solved the problem when r is as small as possible in two different senses, namely
when r ? 1 and when r ? ??a ?p`1 [10].
11.6 Embedding Problems for Hypergraphs
Over 35years ago, Cameron asked [29]: Under what conditions can partial1-factorizations
of Khn be extended to 1-factorizations? In [11] we considered a more general problem for
h? 3. We proved that
Theorem 11.8. Suppose that n? 2m` tp1`?8m2 ?16m?7q{2u. Then an edge-coloring
of K3m can be embedded into an r-factorization of K3n iff the obvious necessary conditions are
satisfied.
One can assume that not only the hyperedges of size 3 are colored, but so are all the
hyperedges of ?pieces? of hypergraphs (i.e. n and `n2? copies of the hyperedges in K2m and
K1m, respectively) that are built up to size 3 when the new vertices are added. In this case
we solved the problem completely in [11]:
Theorem 11.9. An edge-coloring ofK3mYnK2mY`n2?K1m can be extended to anr-factorization
of K3n iff the obvious necessary conditions are satisfied.
141
Brouwer, Schrijver and Baranyai [17, 25] studied special cases of Cameron?s Problem
and conjectured that: A 1-factorization of Khm can be extended to a 1-factorization of Khn iff
h divides both m and n, and n ? 2m. H?aggkvist and Hellgren settled this conjecutre [40].
The more general question I am interested in working on is the conditions under which one
can extend an equitable edge-coloring of Khm into a factorization of Khn for n?m.
11.7 Matroids
I am also interested to study amalgamations and detachments for matroids. Finding
companion results for matroid will lead to interesting matroid decomposition and embedding
results.
142
Bibliography
[1] B. Alspach, H. Gavlas, Cycle decompositions of Kn and Kn?I. J. Combin. Theory Ser.
B 81 (2001), 77?99.
[2] L.D. Andersen, A.J.W. Hilton, Generalized Latin rectangles I: Construction and de-
composition. Discrete Math. 31 (1980), 125?152.
[3] L.D. Andersen, A.J.W. Hilton, Generalized Latin rectangles II: Embedding, Discrete
Math. 31 (1980), no. 3, 235?260.
[4] L.D. Andersen, C.A. Rodger, Decompositions of complete graphs: Embedding par-
tial edge-colourings and the method of amalgamations. Surveys in Combinatorics Lond
Math Soc Lect Note Ser 307 (2003) 7?41.
[5] M.A. Bahmanian, C.A. Rodger, Multiply balanced edge colorings of multigraphs, J.
Graph Theory 70 (2012) 297?317.
[6] M.A. Bahmanian, Detachments of amalgamated 3-uniform hypergraphs: factorization
consequences, to appear in Journal of Combinatorial Designs.
[7] M.A. Bahmanian, Mathematicians collaboration problem, submitted for publication
(2010).
[8] M.A. Bahmanian, Detachments of hypergraphs I: the Berge-Johnson problem, to appear
in Combinatorics, Probability and Computing.
[9] M.A. Bahmanian, C.A. Rodger, What are amalgamations?, to appear in Quaderni di
Matematica.
[10] M.A. Bahmanian, C.A. Rodger, Embedding an edge-colored Kpa,p;?,?q into a Hamil-
tonian decomposition of Kpa,p`r;?,?q, to appear in Graphs and Combinatorics.
[11] M.A. Bahmanian, C.A. Rodger, Extending partial edge-colorings of complete 3-uniform
hypergraphs to r-factorizations, 8 pages, to appear in J. Graph Theory.
[12] M.A. Bahmanian, Connected Baranyai?s theorem, submitted for publication (2012).
[13] M.A. Bahmanian, Amalgamations of almost regular edge-colourings of hypergraphs,
preprint (2012).
[14] M.A. Bahmanian, Polynomial time parallelisms, unpublished manuscript (2011).
143
[15] Zs. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and
finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd?os on his 60th birthday), Vol.
I, pp. 91?108. Colloq. Math. Soc. Janos Bolyai, Vol. 10, North-Holland, Amsterdam,
1975.
[16] Zs. Baranyai, The edge-coloring of complete hypergraphs I, J. Combin. Theory B 26(3)
(1979), 276?294.
[17] Zs. Baranyai, 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.
[18] A.R. Berg, B. Jackson, T. Jord?an, Highly edge-connected detachments of graphs and
digraphs, J. Graph Theory 43 (2003), 67?77.
[19] C. Berge, Graphs, Third revisited edition, North-Holland, 1991.
[20] C. Berge, Hypergraphs, North-Holland, Amsterdam, 1989.
[21] C. Berge, E.L. Johnson, Coloring the edges of a hypergraph and linear programming
techniques. Studies in integer programming (Proc. Workshop, Bonn, 1975), pp. 65?78.
Ann. of Discrete Math., Vol. 1, North-Holland, Amsterdam, 1977.
[22] R.C. Bose, T. Shimamoto, Classification and analysis of partially balanced incomplete
block designs with two associate classes, J. Amer. Statist. Assoc. 47, (1952). 151?184.
[23] D. Bryant, Hamilton cycle rich two-factorizations of complete graphs, J. Combin. Des.
12 (2004), no. 2, 147?155.
[24] A.E. Brouwer, On the edge-colouring property for the hereditary closure of a complete
uniform hypergraph., Mathematisch Centrum, Afdeling Zuivere Wiskunde. No. ZW
95/77. [Mathematical Center, Decision Theory Section, No. ZW 95/77] Mathematisch
Centrum, Amsterdam, 1977. iii+15 pp.
[25] A.E. Brouwer, A. Schrijver, Uniform hypergraphs, in: A. Schrijver (ed.), Packing and
Covering in Combinatorics, Mathematical Centre Tracts 106, Amsterdam (1979), 39?73.
[26] A.E. Brouwer, R. Tijdeman, On the edge-colouring problem for unions of complete
uniform hypergraphs. Discrete Math. 34 (1981), no. 3, 241?260
[27] D. Bryant and D. Horsley, A proof of Lindner?s conjecture on embeddings of partial
Steiner triple systems, J Combin Des 17 (2009), 63?89.
[28] H. Buchanan II, Graph factors and Hamiltonian decompositions, Ph.D. Dissertation,
West Virginia University (1997).
[29] P.J. Cameron, Parallelisms of complete designs, London Mathematical Society Lec-
ture Note Series, No. 23. Cambridge University Press, Cambridge-New York-Melbourne
(1976).
144
[30] Y. Chen, Kneser graphs are Hamiltonian for n ? 3k. J. Combin. Theory Ser. B 80
(2000), no. 1, 69?79.
[31] Y. Chen, Triangle-free Hamiltonian Kneser graphs. J. Combin. Theory Ser. B 89 (2003),
no. 1, 1?16.
[32] Y. Chen, Z. F?uredi, Hamiltonian Kneser graphs. Combinatorica 22 (2002), no. 1, 147?
149.
[33] N. Deo, P. Micikevicius. Generating edge-disjoint sets of quadruples in parallel for the
molecular conformation problem. Congr. Numer. vol. 143, (2000) 81?96 .
[34] N. Deo, P. Micikevicius, On one-factorization of complete 3-uniform hypergraphs.
Congr. Numer. 158 (2002), 153?161
[35] J. Doyen, R.M. Wilson, Embeddings of Steiner triple systems. Discrete Math. 5 (1973),
229?239.
[36] M.N. Ferencak, A.J.W. Hilton, Outline and amalgamated triple systems of even index,
Proc. London Math. Soc. (3) 84 (2002), no. 1, 1?34.
[37] H.L. Fu, C.A. Rodger, Group divisible designs with two associate classes: n ? 2 or
m? 2, J. Combin. Theory Ser. A 83 (1998), 94?117.
[38] H.L. Fu, C.A. Rodger, 4-cycle group-divisible designs with two associate classes, Com-
bin. Probab. Comput. 10 (2001), 317?343.
[39] H.L. Fu, C.A. Rodger, D.G. Sarvate, The existence of group divisible designs with first
and second associates, having block size 3, Ars Combin. 54 (2000), 33?50.
[40] R. H?aggkvist, T. Hellgren, Extensions of edge-colourings in hypergraphs. I. Combina-
torics, Paul Erd?os is eighty, Vol. 1, 215?238, Bolyai Soc. Math. Stud., J?anos Bolyai
Math. Soc., Budapest, 1993.
[41] M. Hall, An existence theorem for Latin squares. Bull. Amer. Math. Soc. 51 (1945)
387?388.
[42] A.J.W. Hilton, The reconstruction of Latin squares with applications to school
timetabling and to experimental design, Combinatorial optimization, II (Proc. Conf.,
Univ. East Anglia, Norwich, 1979). Math. Programming Stud. No. 13 (1980), 68?77.
[43] A.J.W. Hilton, Canonical edge-colorings of locally finite graphs, Combinatorica 2(1)
(1982), 37?51.
[44] A.J.W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin. Theory B
36 (1984), 125?134.
[45] A.J.W. Hilton, Outlines of Latin squares, Combinatorial design theory, 225?241, North-
Holland Math. Stud., 149, North-Holland, Amsterdam, 1987.
145
[46] A.J.W. Hilton, M. Johnson, Some results on the Oberwolfach problem, J. London Math.
Soc. (2) 64 (2001), no. 3, 513?522.
[47] A.J.W. Hilton, M. Johnson, C.A. Rodger, E.B. Wantland, Amalgamations of connected
k-factorizations, J. Combin. Theory B 88 (2003), 267?279.
[48] A.J.W. Hilton, C.A. Rodger, Hamiltonian decompositions of complete regular s-partite
graphs, Discrete Math. 58 (1986), 63?78.
[49] B. Jackson, T. Jord?an, Non-separable detachments of graphs, Dedicated to Crispin St.
J. A. Nash-Williams, J. Combin. Theory Ser. B 87 (2003), 17?37.
[50] E.L. Johnson, On the edge-coloring property for the closure of the complete hyper-
graphs, Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976),
Ann. Discrete Math. 2 (1978), 161?171.
[51] M. Johnson, Amalgamations of factorizations of complete graphs, J. Combin. Theory
B 97 (2007), 597?611.
[52] W.R. Johnstone, Decompositions of complete graphs, Bull. London Math. Soc. 32
(2000), no. 2, 141?145.
[53] D. Jungnickel, Graphs, networks and algorithms, Third edition, Springer, Berlin, 2008.
[54] G.O.H. Katona, R?enyi and the combinatorial search problems, Studia Sci. Math. Hun-
gar. 26 (1991) 363?378.
[55] M. Khatirinejad, P.R.J. ?Osterg?ard, A census of one-factorizations of the complete 3-
uniform hypergraph of order 9. Australas. J. Combin. 47 (2010), 239?245
[56] T.P Kirkman, On a problem in combinations, Camb. Dublin Math. J. 2 (1847) 191?204.
[57] R. Laskar, B. Auerbach, On decomposition of r-partite graphs into edge-disjoint Hamil-
ton circuits, Discrete Math. 14 (1976), 265?268.
[58] C.D. Leach, C.A. Rodger, Non-disconnecting disentanglements of amalgamated 2-
factorizations of complete multipartite graphs, J. Combin. Des. 9 (2001), 460?467.
[59] C.D. Leach, C.A. Rodger, Fair Hamilton decompositions of complete multipartite
graphs, J. Combin. Theory Ser. B 85 (2002), no. 2, 290?296.
[60] C.D. Leach, C.A. Rodger, Hamilton decompositions of complete multipartite graphs
with any 2-factor leave, J. Graph Theory 44 (2003), 208?214.
[61] C.D. Leach, C.A. Rodger, Hamilton decompositions of complete graphs with a 3-factor
leave, Discrete Math. 279 (2004), 337?344.
[62] C.C. Lindner, A partial Steiner triple system of order n can be embedded in a Steiner
triple system of order 6n`3. J. Combinatorial Theory Ser. A 18 (1975), 349?351.
146
[63] C.C. Lindner, C.A. Rodger, Generalized embedding theorems for partial Latin squares.
Bull. Inst. Combin. Appl. 5 (1992), 81?99.
[64] E. Lucas, R?ecr?eations Math?ematiques, Vol. 2, Gauthiers Villars, Paris, 1883.
[65] C.J.H. McDiarmid, The solution of a timetabling problem, J. Inst. Math. Appl. 9 (1972),
23?34.
[66] L. McCauley, C.A. Rodger, Hamilton cycle rich 2-factorizations of complete multipartite
graphs, Graphs Combin. 24 (2008), no. 1, 47?52.
[67] C.St.J.A. Nash-Williams, Edge-disjoint hamiltonian circuits in graphs with vertices of
large valency, Studies in Pure Mathematics, papers presented to Richard Rado (Aca-
demic Press, London and New York, 1971).
[68] C.St.J.A. Nash-Williams, Connected detachments of graphs and generalized Euler trails.
J. London Math. Soc. 31 (1985), pp. 17?29.
[69] C.St.J.A. Nash-Williams, Detachments of graphs and generalised Euler trails, in: I.
Anderson (Ed.), Surveys in Combinatorics 1985, London Mathematical Society, Lecture
Note Series, Vol. 103, Cambridge University Press, Cambridge, 1985, pp. 137?151.
[70] C.St.J.A. Nash-Williams, Amalgamationsof almost regular hyperedge-colourings of sim-
ple graphs, J. Combin. Theory B 43 (1987) 322?342.
[71] R. Peltesohn, Das Turnierproblem f?ur Spiele zu je dreien, Inaugural dissertation, Berlin,
1936.
[72] K. Rajan, N. Deo. Computational experience with a parallel algorithm for tetrangle
inequality bound smoothing. Bulletin of Mathematical Biology, vol. 61, 987?1008, 1999.
[73] D.K. Ray-Chaudhuri, R.M. Wilson, The existence of resolvable designs, in A Survey
of Combinatorial Theory, J. N. Srivastava et al. (Editors), North-Holland, Amsterdam,
1973, pp. 361?376.
[74] C.A. Rodger, E.B. Wantland, Embedding edge-colorings into 2-edge-connected k-
factorizations of Kkn`1, J. Graph Theory 19 (1995), 169?185.
[75] H.J. Ryser, A combinatorial theorem with an application to latin rectangles, Proc.
Amer. Math. Soc. 2 (1951) 550?552.
[76] M. ?Sajna, Cycle decompositions ofKn andKn?I, PhD Thesis, Simon Fraser University
(1999).
[77] M. ?Sajna, Cycle decompositions III: complete graphs and fixed length cycles. J. Combin.
Des. 10 (2002) 27?78.
[78] M. Tarsi, On the decomposition of a graph into stars. Discrete Math. 36 (1981) 299?304.
147
[79] M. Tarsi, Decomposition of a complete multigraph into simple paths: nonbalanced
handcuffed designs. J. Combin. Theory Ser. A 34 (1983) 60?70.
[80] D. de Werra, Balanced schedules, INFOR?Canad. J. Operational Res. and Information
Processing 9 (1971), 230?237.
[81] D. de Werra, Equitable colorations of graphs, Rev. Fran. Inf. Rech. Oper. 5 (1971), 3?8.
[82] D. de Werra, A few remarks on chromatic scheduling, Combinatorial programming:
methods and applications (Proc. NATO Advanced Study Inst., Versailles, 1974), pp.
337?342. NATO Advanced Study Inst. Ser., Ser. C: Math. and Phys. Sci., Vol. 19,
Reidel, Dordrecht, 1975.
[83] D. de Werra, On a particular conference scheduling problem. INFOR?Canad. J. Op-
erational Res. and Information Processing 13 (1975), no. 3, 308?315.
[84] J.H. van Lint, R.M. Wilson, A course in combinatorics, Second edition, Cambridge
University Press, Cambridge, 2001.
148