The Metamorphosis of 2-fold Triple Systems into Maximum Packings of 2Kn with 4-cycles by Stacie Elizabeth McClanahan 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 6, 2011 Copyright 2011 by Stacie Elizabeth McClanahan Approved by Charles C. Lindner, Chair, Distinguished University Professor of Mathematics and Statistics Chris Rodger, Scharnagel Professor of Mathematics and Statistics Dean Hoffman, Professor of Mathematics and Statistics Mariusz Meszka, Professor, AGH University of Science and Technology, Krak?w, Poland ii Abstract The graph is called a hinge. A hinge system of order n is a pair (X, H) where H is a collection of edge disjoint hinges which partition the edge set of 2Kn with vertex set X. Let (X, H) be a hinge system and D the collection of double edges from the hinges. Let H*= D\H (= the 4-cycles left over when the double edges are removed). If the edges of D can be arranged into a collection of 4-cycles D*, then (X, H*U D*) is a 2-fold 4-cycle system called a metamorphosis of (X, H) into (X, H*U C*). In a previous work, it was shown that the spectrum for hinge systems having a metamorphosis into a 2-fold 4-cycle system is precisely the set of all 12) (mod 9or 4, 1, ,0?n . In this thesis, we extend that result by showing that the spectrum for hinge systems having a metamorphosis into a maximum packing of 2Kn with 4-cycles is precisely the set of all 10 12) (mod 10or 7, 6, ,3 ??n . No such systems exist for n = 6 or 7. We point out that if we partition each hinge in a hinge system into a pair of triangles, we have a 2-fold triple system, hence, the title of this thesis. iii Acknowledgments Above all else, I thank God for giving me the strength and ability to accomplish everything I have done. Thank you to my Mom and Dad, without whom I would have never been able to go back to school with a young child at home. Thank you, Dad, for supporting me mathematically and emotionally through the process of going back to school. Thank you both for supporting me and Ryleigh for the past three years and for watching Ryleigh so often so that I could do this. I want to especially thank Ryleigh, without whom I would not have had the motivation to try to go back to school. Thank you for making me want to be a better person. iv Table of Contents Abstract???????????????????????????????????ii Acknowledgments??????????????????????????????..iii 1 Introduction?????.????????..????????????????.?..1 2 2-fold 4-cycle Systems with Holes?????.????????..???..?..???..10 3 The 12n + 3 Construction??...???????????????????????13 4 The 12n + 6 Construction???????????...????????????....?27 5 The 12n + 7 Construction??...??????????.??????????...??48 6 The 12n + 10 Construction??...????????????????????.?.?63 7 Summary?.??????????????????????????.??.??..77 References????????????????????????????..?????78 1 CHAPTER 1 INTRODUCTION A Steiner triple system (STS) of order n is a pair (X, T) where T is a collection of edge disjoint triangles (or triples) which partitions the edge set of Kn (the complete undirected graph on n vertices with vertex set X). Below is everybody?s favorite Steiner triple system. Example 1.1 (STS (7)) It is well-known that the spectrum for Steiner triple systems, the set of all n such that a STS of order n exists, is precisely the set of all 6) (mod 3or 1?n [1]. A 2-fold triple system of order n is a pair (X, T) where T is a collection of edge disjoint triples which partitions the edge set of 2Kn (every pair of vertices are connected by 2 edges) with vertex set X. K7 Example 1.2 (2-fold triple system of order 9) The spectrum for 2-fold triple systems is precisely the set of all Finally, a 2-fold 4-cycle system of order disjoint 4-cycles which partitions Example 1.3 (2-fold 4-cycle system of order 9) 2K9 2 3). (mod 1or 0?n n, is a pair (X, C) where C is a collection of edge the edge set of 2Kn with vertex set X. [2] 3 The spectrum for 2-fold 4-cycle systems is precisely the set of all 4) (mod 1or 0?n [3]. Since the spectrum for 2-fold triple systems and 2-fold 4-cycle systems agree when 12) (mod 9or 4, 1, ,0?n , it is quite natural to ask if we can find any connections between 2-fold triple systems and 2-fold 4-cycle systems having the same order. The answer to this question is obviously yes or we wouldn?t be talking about 2-fold triple systems and 2-fold 4-cycle systems. In what follows, we will use the following notation: Let (X, T) be a 2-fold triple system of order 12) (mod 9or 4, 1, ,0?n . Then T is always even. Let H be a pairing of the triples of T into hinges (see Example 1.2). In everything that follows, (X, H) will be called a hinge system. If we remove the double edges from each hinge in H, what remains are 4-cycles. Denote by H* the remaining 4-cycles and by D the double edges. If we can arrange the double edges in D into a collection of 4 cycle system called a metamorphosis precise, let (X, H) be a hinge system 4-cycles. Then (X, H*U D*) is a 2 system (X, H) into the 2-fold 4-cycle system Example 1.4 (metamorphosis of Example 1.2 into Example 1.3) T 4 -cycles D*, then (X, H*U D*) is a 2 of (X, H) into the 4-cycle system (X, H*U D* and D* be an arrangement of D (the double edges -fold 4-cycle system called a metamorphosis of the (X, H*U D*). -fold 4- ). To be of H) into hinge H 5 U U In [4], a complete solution of the hinge system metamorphosis problem is given. Theorem 1.5 (M. Gionfriddo and C. C. Lindner [4]) There exists a hinge system of every order 12) (mod 9or 4, 1, ,0?n having a metamorphosis into a 2-fold 4-cycle system. square6 D H* D* H* 6 The object of this thesis is to generalize this result to all hinge systems as follows. As previously mentioned above, the spectrum for hinge systems is precisely the set of all n ?0, 1, 3, 4, 6, 7, 9, or 10 (mod 12). For n ?3, 6, 7, and 10 (mod 12), there does not exist a 2-fold 4- cycle system, but there does exist a maximum packing. Therefore an obviously question arises: For which n ?3, 6, 7, and 10 (mod 12), does there exist a hinge system of order n having a metamorphosis into a maximum packing of 2Kn with 4-cycles? So that there is no confusion in what follows, if n ?3, 6, 7, and 10 (mod 12), a maximum packing of 2Kn into 4-cycles is an edge disjoint collection of 4-cycles which partitions the edges of 2Kn into 4-cycles and a double edge (called the leave). So the problem we will examine in this thesis is the following: PROBLEM Does there exist for each n ?3, 6, 7, and 10 (mod 12) a hinge system of order n, having a metamorphosis into a maximum packing of 2Kn with 4-cycles with leave a double edge? 7 Example 1.6 (metamorphosis of a hinge system of order 10 into a maximum packing of 2K10 with 4-cycles) U U D H 8 U U D* H* 9 We give a complete solution of this problem with the following theorem. Theorem 1.7 For all 10 12) (mod 10or 7, 6, 3, ??n , there exists a hinge system of order n having a metamorphosis into a maximum packing of 2Kn with 4-cycles. (No such metamorphoses exist for n = 6 or n = 7.) square6 We will organize our results into 7 chapters: an introduction, 2-fold 4-cycle systems with holes, the 12n + 3 Construction, the 12n + 6 Construction, the 12n +7 Construction, the 12n + 10 Construction, and a summary. 10 CHAPTER 2 2-FOLD 4-CYCLE SYSTEMS WITH HOLES Before beginning with our constructions, we will need a few preliminary results. We will start with a very famous theorem due to Dominque Sotteau. Theorem 2.1 [5] The complete bipartite graph K2n, 2m can be partitioned into 2k-cycles if and only if (i) nmk and ? and (ii) nmk 4|2 . square6 An immediate result of this theorem is the following corollary. Corollary 2.2 2K2n, 2n can always be partitioned into 4-cycles. square6 Now let H = {h1, h2, h3, ?, ht} be a collection of pairwise disjoint subsets of the set X called holes. We will denote by 2hi = { | ihyx =},{ } and by 2H = {2h1, 2h2, 2h3, ?, 2ht}. Let 2Kn have vertex set X and let C be a collection of 4-cycles which partitions 2Kn\2H based on X. We will call (X, C) a 2-fold 4-cycle system with holes 2H. Example 2.3 (2-fold 4-cycle system of order 5 with two holes of size 2) ?? ? = ><><= 4)} 2, 5, (1, 5), 3, 4, (1, 2), 5, 3, (1, 3), 4, 2, {(1, C and }5 4, ,3 2,{ H2 Lemma 2.4 There exists a 2-fold 4-cycle system of order 4n + 1 with 2n holes of size 2 for all .514 ?+n 11 Proof Let X = {1, 2, 3, ?, n}, S = U}{? (X ? {1, 2, 3, 4}), and define a collection C of 4-cycles as follows: (1) For each Xx? , define a copy of Example 2.3 on U}{? ({x} ? {1, 2, 3, 4}) and place these 4-cycles in C. (2) For each yx ? , partition 2K4, 4 with parts {x} ? {1, 2, 3, 4} and {y} ? {1, 2, 3, 4} into 4-cycles and place these 4-cycles in C. Then (S, C) is a 2-fold 4-cycle system of order 4n + 1 with 2n holes of size 2. square6 We will need the following two examples for the next lemma. Example 2.4 (2-fold 4-cycle system of order 7 with three holes of size 2) ?? ??? ??????= ><><><= 6)} 2, 5, (1, 6), 2, 5, (1, 4), 2, 3, (1, 5), 3, 6, ,{ 6}, 4, 5, ,( 3), 5, 4, ,( 4), 6, 3, ,( 1), 3, 2, ,( 2), 4, 1, ,{( C and }7 ,6,5 4, ,3 2,{ H2 Example 2.5 (2-fold 4-cycle system of order 7, with one hole of size 3 and two holes of size 2 ?? ??? ????= ><><>?<= 6)} 2, 5, (1, 6), 2, 5, (1, 4), 2, 3, ,1{ 4}, 2, 3, ,1( 5), 4, 6, ,( 6), 3, 5, ,( 3), 5, 4, ,( 4), 6, 3, ,{( C and }6 ,5,4 3, ,2 1, ,{ H2 12 Lemma 2.6 There exists a 2-fold 4-cycle system of order 4n + 3 with 2n + 1 holes of size 2. Proof Let X = {1, 2, 3, ?, n}, S = U},,{ 321 ??? (X ? {1, 2, 3, 4}), and define a collection C of 4-cycles as follows: (1) Define a copy of Example 2.4 on U},,{ 321 ??? {(1, 1), (1, 2), (1, 3), (1, 4)} and place these 4-cycles in C. (2) For each 2?i , place a copy of Example 2.5 on U},,{ 321 ??? {(i, 1), (i, 2), (i, 3), (i, 4)} in C with the proviso that one of the holes is < 321 ,, ??? > and the other two are <(i, 1), (i, 2)> and <(i, 3), (i, 4)>. (3) For each yx ? , partition 2K4,4 with parts {x} ? {1, 2, 3, 4} and {y} ? {1, 2, 3, 4} into 4-cycles and place these 4-cycles in C. Then (X, C) is a 2-fold 4-cycle system of order 4n + 3 with 2n + 1 holes of size 2. square6 13 CHAPTER 3 THE 12n + 3 CONSTRUCTION Write 12n + 3 = 3(4n + 1). Let Q = {1, 2, 3, 4, ?, 4n + 1} and set X = Q ?{1, 2, 3}. Define a collection of hinges, H, as follows: (1) Let (Q, o) be an idempotent antisymmetric quasigroup of order 4n + 1 and for each Q?? yx , place the hinge <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)> in H. The missing edges between Q ?{1} and Q ?{2} are precisely the double edges <(x, 1), (x, 2)>, all ?x Q. 14 (2) Now let ? be the cycle ? = (1 2 3 4 ?. 4n + 1) and (Q, o) an idempotent commutative quasigroup of order 4n + 1. For each Q?? yx , place the hinge <(x, 2), (y, 2), (( )yxo , 3), (( )?yxo , 3)> in H. The missing edges between Q ?{2} and Q ?{3} are precisely the edges ((x, 2), (x, 3)) and ((x, 2), (x?, 3)) for all ?x Q. 15 (3) Let ? and (Q, o) be as in part (2) and for each Q?? yx , place the hinge <(x, 3), (y, 3), (( )yxo , 1), (( ) 1??yxo , 1)> in H. The missing edges between Q ?{3} and Q ?{1} are precisely the edges ((x, 3), (x, 1)) and ((x, 3), (x?-1, 1)) for each ?x Q. 16 (4) For each ?x Q, use the missing edges <(x, 1), (x, 2)> in (1), the missing edges ((x, 2), (x, 3)) and ((x, 2), (x?, 3)) in (2) and the missing edges ((x, 3), (x, 1)) and ((x?, 3), (x =(x?)?-1, 1)) in (3) to construct the hinge Place this hinge in H. It is straightforward to see that (X, H) is a hinge system of order 12n + 3. The metamorphosis is the following: (a) Remove all double edges from the hinges in (1), (2), (3), and (4). 17 (b) Let (Q, F) be a partition 2K4n+1\{<2, 3>, <4, 5>, <6, 7>, ?, <4n, 4n + 1>} into 4- cycles on both Q ?{1} and Q ?{2} (Lemma 2.4) and form the graph given below: Partition this into 4n 4-cycles with the double edge <(1, 1), (1, 2)> left over. This uses all of the removed edges of types (1), (2), and (4). Since 14Q += n , we can organize the double edges on Q ?{3} into 4-cycles, which uses all of the edges in (1). Combining (a) and (b) produces a 2-fold 4-cycle system of order 12n + 3 with leave the double edge <(1, 1), (1, 2)> in (b); i. e., a metamorphosis of the hinge system (X, H) into a maximum packing of 2K12n+3 with 4-cycles. 18 Theorem 3.1 There exists a hinge system of order 12n + 3 having a metamorphosis into a maximum packing of 2K12n+3 into 4-cycles for all 12n + 3 15? . square6 We will illustrate this construction with an example for 12n + 3 = 15. Example 3.2 (metamorphosis of a hinge system of order 15 into a maximum packing of 2K15 with 4-cycles) The following is the construction of the hinge system for n = 15, where we have renamed the ordered pairs as follows: (1, 1) barb2right 1 (1, 2) barb2right 6 (1, 3) barb2right 11 (2, 1) barb2right 2 (2, 2) barb2right 7 (2, 3) barb2right 12 (3, 1) barb2right 3 (3, 2) barb2right 8 (3, 3) barb2right 13 (4, 1) barb2right 4 (4, 2) barb2right 9 (4, 3) barb2right 14 (5, 1) barb2right 5 (5, 2) barb2right 10 (5, 3) barb2right 15 (1) Let (Q, o) be the following idempotent antisymmetric quasigroup of order 5 and for each Q?? yx , place the hinge <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)> in H. o 1 2 3 4 5 1 1 3 5 2 4 2 5 2 4 1 3 3 4 1 3 5 2 4 3 5 2 4 1 5 2 4 1 3 5 19 The following are the 10 hinges of this type. The missing edges between Q ?{1} and Q ?{2} are precisely the double edges <(x, 1), (x, 2)>, all ?x Q. (2) Now let ? be the cycle ? = (1 2 3 4 5) and (Q, o) the following idempotent commutative quasigroup of order 5. For each Q?? yx , place the hinge <(x, 1), (y, 1), ( yx o , 2), (( )?yxo , 2)> in H. The following are the 10 hinges of this type. The missing edges between Q and ((x, 2), (x?, 3)) for all 20 ?{2} and Q ?{3} are precisely the edges (( ?x Q. o 1 2 3 4 1 1 4 2 5 2 4 2 5 3 3 2 5 3 1 4 5 3 1 4 5 3 1 4 2 x, 2), (x, 3)) 5 3 1 4 2 5 21 (3) Let ? and (Q, o) be as in part (2) and for each Q?? yx , place the hinge <(x, 3), (y, 3), ( yx o , 1), (( ) 1??yxo , 1)> in H. The following are the 10 hinges of this type. The missing edges between Q ?{3} and Q ?{1} are precisely the edges ((x, 3), (x, 1)) and ((x, 3), (x?-1, 1)) for each ?x Q. o 1 2 3 4 5 1 1 4 2 5 3 2 4 2 5 3 1 3 2 5 3 1 4 4 5 3 1 4 2 5 3 1 4 2 5 22 (4) For each ?x Q, use the missing edges <(x, 1), (x, 2)> in (1), the missing edges ((x, 2), (x, 3)) and ((x, 2), (x?, 3)) in (2) and the missing edges ((x, 3), (x, 1)) and ((x?, 3), (x =(x?)?-1, 1)) in (3) to construct the hinges The following are the 5 hinges of this type. 23 Then (X, H) is a hinge system of order 15. The metamorphosis is as follows: (a) Remove all double edges from the hinges in (1), (2), (3), and (4). (b) Let (Q, F) be a partition 2K5\{<2, 3>, <4, 5>} into 4-cycles on both Q ?{1} and Q ?{2} (see Lemma 2.4). This gives us the following 4-cycles. Form the graph given below: We can partition this into <(1, 1), (1, 2)> left over. 24 the following four 4-cycles with the double edge 25 This uses all of the removed edges of types (1), (2), and (4). Since 5Q = , we can organize the double edges on Q ?{3} into 4-cycles as follows. Combining (a) and (b) produces a 2-fold 4-cycle system of order 15 with leave the double edge in <(1, 1), (1, 2)> in (b); i. e., a metamorphosis of the hinge system (X, H) into a maximum packing of 2K15 with 4-cycles. H = {<1, 2, 10, 8>, <1, 3, 10, 9>, <1, 4, 7, 8>, <1, 5, 9, 7>, <2, 3, 9, 6>, <2, 4, 6, 10>, <2, 5, 8, 9>, <3, 4, 10, 7>, <3, 5, 7, 6>, <4, 5, 6, 8>, <6, 7, 14, 15>, <6, 8, 12, 13>, <6, 9, 15, 11>, <6, 10, 13, 14>, <7, 8, 15, 11>, <7, 9, 13, 14>, <7, 10, 11, 12>, <8, 9, 11, 12>, <8, 10, 14, 15>, <9, 10, 12, 13>, <11, 12, 4, 3>, <11, 13, 2, 1>, <11, 14, 5, 4>, <11, 15, 3, 2>, <12, 13, 5, 4>, <12, 14, 3, 2>, <12, 15, 1, 5>, <13, 14, 1, 5>, <13, 15, 4, 3>, <14, 15, 2, 1>, <1, 6, 11, 12>, <2, 7, 12, 13>, <3, 8, 13, 14>, <4, 9, 14, 15>, <5, 10, 15, 11>}. H*U D* = {(1, 8, 2, 10), (1, 9, 3, 10), (1, 8, 4, 7), (1, 7, 5, 9), (2, 6, 3, 9), (2, 10, 4, 6), (2, 9, 5, 8), (3, 7, 4, 10), (3, 6, 5, 7), (4, 8, 5, 6), (6, 15, 7, 14), (6, 13, 8, 12), (6, 11, 9, 15), (6, 14, 10, 13), (7, 11, 8, 15), (7, 14, 9, 13), (7, 12, 10, 11), (8, 12, 9, 11), (8, 15, 10, 14), (9, 13, 10, 12), (11, 3, 12, 4), (11, 1, 13, 2), (11, 4, 14, 5), (11, 2, 15, 3), (12, 4, 13, 5), (12, 2, 14, 3), (12, 5, 15, 1), (13, 5, 14, 1), (13, 3, 15, 4), (14, 1, 15, 2), (1, 12, 6, 11), (2, 13, 7, 12), 26 (3, 14, 8, 13), (4, 15, 9, 14), (5, 11, 10, 15), (1, 4, 3, 5), (1, 3, 4, 2), (1, 4, 2, 5), (1, 3, 5, 2), (6, 9, 8, 10), (6, 8, 9, 7), (6, 9, 7, 10), (6, 8, 10, 7), (2, 3, 8, 7), (2, 3, 8, 7), (4, 5, 10, 9), (4, 5, 10, 9), (11, 14, 15, 12), (11, 13, 12, 15), (11, 14, 13, 15), (11, 13, 14, 12), (12, 13, 15, 14), <1, 6>} 27 CHAPTER 4 THE 12n + 6 CONSTRUCTION There does not exist a hinge system of order 6 having a metamorphosis into a maximum packing of 2K6 with 4-cycles. So, we begin this chapter by showing the nonexistence for n = 6. Example 4.1 (the nonexistence of a metamorphosis for n = 6) Let (X, H) be a hinge system of order 6 and let D be the 5 double edges in the hinges. It is IMPORTANT to note that, considered as a 2-fold triple system (X, T), each triple contains exactly one edge from the double edges in D. Now suppose that D contains a 4-cycle (1, 2, 3, 4). Since each of (1, 2), (2, 3), (3, 4), and (4, 1) is half of a double edge in D, D contains the 4-cycle of double edges (<1, 2>, <2, 3>, <3, 4>, <4, 1>). Since each of the ten triples in T contain exactly one edge from D, the two triples in T containing the edge (1, 2) must look like {1, 2, 5} and {1, 2, 6}. 28 Similarly, T must contain triples that look like {3, 4, 5}, {3, 4, 6}, {2, 4, 5}, {2, 4, 6}, {1, 3, 5} and {1, 3, 6}. This forces the remaining edges in 2K6 to look like <1, 4>, <2, 3>, and <5, 6>. These edges cannot be paired into two triples, much less a hinge. It follows that D cannot contain even one 4-cycle, much less two. 29 We have the following lemma. Lemma 4.2 There does not exist a hinge system of order 6 having a metamorphosis into a maximum packing of 2K6 with 4-cycles. square6 We can now proceed to the 12n + 6 construction which will produce a hinge system of every order 18612 ?+n having a metamorphosis into a maximum packing of 2K12n+6 with 4-cycles. Write 12n + 6 = 3(4n + 2). Let Q = {1, 2, 3, ?, 4n + 2} and set X = Q 3}. 2, ,1{? Define a collection of hinges H as follows: (1) Let ( )o Q, be an idempotent antisymmetric quasigroup of order 4n + 2. For each Q ?? yx , place the hinge <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)> in H. 30 The missing edges between Q ?{1} and Q ?{2} are precisely the double edges <(x, 1), (x, 2)> for all ?x Q. (2) Now let ( )o Q, be an idempotent antisymmetric quasigroup of order 4n + 2 with holes H } ,..., ,{ 1 221 += nhhh of size 2. (a) For each hole, ?= } ,{ yxhi H, place the hinge <(x, 2), (y, 2), (x, 3), (y, 3)> in H. 31 (b) For each yx ? belonging to different holes of H, place the hinge <(x, 2), (y, 2), ( yx o , 3), ( xy o , 3)> in H. The missing edges between Q ?{2} and Q ?{3} are precisely the 4-cycles ((x, 2), (x, 3), (y, 2), (y, 3)) for each hole ?= } ,{ yxhi H. 32 (3) Now let ( )o Q, be an idempotent antisymmetric quasigroup of order 4n + 2 with holes H } ,..., ,{ 1 221 += nhhh of size 2. (a) For each hole, ?= } ,{ yxhi H, place the hinge <(x, 3), (y, 3), (x, 1), (y, 1)> in H. (b) For each yx ? belonging to different holes of H, place the hinge <(x, 3), (y, 3), ( yx o , 1), ( xy o , 1)> in H. 33 The missing edges between Q ?{3} and Q ?{1} are precisely the 4-cycles ((x, 3), (x, 1), (y, 3), (y, 1)) for each hole ?= } ,{ yxhi H. (4) We can now combine the missing edges in (1), (2), and (3) into hinges as follows: For each hole } ,{ yxhi = , we have the following missing edges 34 which can be partitioned into the 2 hinges <(x, 1), (x, 2), (x, 3), (y, 3)> and <(y, 1), (y, 2), (y, 3), (x, 3)>. Place these two hinges in H for each hole } ,{ yxhi = . As with the 12n + 3 construction, it is straightforward to see that (X, H) is a hinge system of order 12n + 6. The metamorphosis is the following: (a) Remove all double edges from the hinges in (1), (2), (3), and (4). (b) Let (Q, F) be a partition of 2K4n+2\{<1, 2>, <3, 4>, ?, <4n + 1, 4n + 2>} into 4-cycles on both Q ?{1} and Q ?{2} and form the graph given below: 35 and partition this into 4n 4-cycles (nothing is left over). This uses up all of the removed edges of types (1), (2), and (4). Since |Q|= 4n + 2 (the order of a maximum packing of order 4n + 2 with leave a double edge), we can organize the double edges on Q ?{3} into 4-cycles with a double edge left over. Combining (a) and (b), gives a maximum packing of 2K12n+6 with 4-cycles with leave the double edge in Q ?{3}. Theorem 4.3 There exists a hinge system of order 12n + 6 having a metamorphosis into a maximum packing of 2K12n+6 into 4-cycles for all 18612 ?+n . There does not exist such a system of order 6. square6 36 The following is the construction of a hinge system for 12n + 6 = 18, having a metamorphosis into a 2-fold 4-cycle system. We have renamed the ordered pairs as follows: (1, 1) barb2right 1 (1, 2) barb2right 7 (1, 3) barb2right 13 (2, 1) barb2right 2 (2, 2) barb2right 8 (2, 3) barb2right 14 (3, 1) barb2right 3 (3, 2) barb2right 9 (3, 3) barb2right 15 (4, 1) barb2right 4 (4, 2) barb2right 10 (4, 3) barb2right 16 (5, 1) barb2right 5 (5, 2) barb2right 11 (5, 3) barb2right 17 (6, 1) barb2right 6 (6, 2) barb2right 12 (6, 3) barb2right 18 Example 4.4 (metamorphosis of a hinge system of order 18 into a maximum packing of 2K18 with 4 cycles) (1) Let ( )o Q, be an idempotent antisymmetric quasigroup of order 6. For each Q ?? yx , place the hinge <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)> in H. The following are the 15 hinges of this type. ? 1 2 3 4 5 6 1 1 3 4 5 6 2 2 4 2 1 6 3 5 3 5 6 3 1 2 4 4 6 5 2 4 1 3 5 2 4 6 3 5 1 6 3 1 5 2 4 6 37 The missing edges between Q ?{1} and Q ?{2} are precisely the double edges <(x, 1), (x, 2)>, x = 1, 2, 3, 4, 5, 6. 38 (2) Now let ( )o Q, be an idempotent antisymmetric quasigroup of order 6 with holes H = {{1, 2}, {3, 4}, {5, 6}}. o 1 2 3 4 5 6 1 1 2 5 6 3 4 2 2 1 6 5 4 3 3 6 5 3 4 1 2 4 5 6 4 3 2 1 5 4 3 2 1 5 6 6 3 4 1 2 6 5 (a) For each hole, ?= } ,{ yxhi H, place the hinge <(x, 2), (y, 2), (x, 3), (y, 3)> in H. 39 The following are the three hinges of this type. (b) For each yx ? belonging to different holes of H, place the hinge <(x, 2), (y, 2), ( yx o , 3), ( xy o , 3)> in H. The following are the twelve hinges of this type. 40 The missing edges between Q ?{2} and Q ?{3} are precisely the 4-cycles {(x, 2), (x, 3), (y, 2), (y, 3)} for each hole ?= } ,{ yxhi H. 41 (3) Now let ( )o Q, be an idempotent antisymmetric quasigroup of order 6 with holes H = {{1, 2}, {3, 4}, {5, 6}}. ? 1 2 3 4 5 6 1 1 2 5 6 3 4 2 2 1 6 5 4 3 3 6 5 3 4 1 2 4 5 6 4 3 2 1 5 4 3 2 1 5 6 6 3 4 1 2 6 5 (a) For each hole, ?= } ,{ yxhi H, place the hinge <(x, 3), (y, 3), (x, 1), (y, 1)> in H. The following are the three hinges of this type. 42 (b) For each yx ? belonging to different holes of H, place the hinge <(x, 3), (y, 3), ( yx o , 1), ( xy o , 1)> in H. The following are the 12 hinges of this type. 43 The missing edges between Q ?{3} and Q ?{1} are precisely the 4-cycle {(x, 3), (x, 1), (y, 3), (y, 1)} for each hole ?= } ,{ yxhi H. (4) We can now combine the missing edges in (1), (2), and (3) into hinges as follows: For each hole } ,{ yxhi = , we have the following missing edges which can be combined into the 2 hinges <(x, 1), (x, 2), (x, 3), (y, 3)> and <(y, 1), (y, 2), (y, 3), (x, 3)>. Place these two hinges in H. 44 The following are the six hinges of this type. Then (X, H) is a hinge system of order 18. The metamorphosis is as follows: If we remove all double edges from the hinges in (1), (2), (3) and (4), we can partition the edges of 2K6\{<1, 2>, <3, 4>, <5, 6>} on Q ?{1} and Q ?{2} into the following 4-cycles. 45 With the remaining double edges between Q ?{1} and Q ?{2}, we can form the following 4-cycles. This uses all of the edges of types (1), (2), and (4). The remaining double edges form 2K6 on Q ?{3} and can be rearranged into the following 4-cycles with the leave a double edge. 46 This gives a maximum packing of 2K18 with 4-cycles with leave the double edge on Q ?{3}. H = {<1, 2, 9, 10>, <1, 3, 11, 10>, <1, 4, 11, 12>, <1, 5, 12, 8>, <1, 6, 8, 9>, <2, 3, 7, 12>, <2, 4, 12, 11>, <2, 5, 9, 10>, <2, 6, 11, 7>, <3, 4, 7, 8>, <3, 5, 8, 12>, <3, 6, 10, 11>, <4, 5, 7, 9>, <4, 6, 9, 8>, <5, 6, 7, 10>, <7, 8, 13, 14>, <9, 10, 15, 16>, <11, 12, 17, 18>, <7, 9, 17, 18>, <7, 10, 18, 17>, <7, 11, 15, 16>, <7, 12, 16, 15>, <8, 9, 18, 17>, <8, 10, 17, 18>, <8, 11, 16, 15>, <8, 12, 15, 16>, <9, 11, 13, 14>, <9, 12, 14, 13>, <10, 11, 14, 13>, <10, 12, 13, 14>, <13, 14, 1, 2>, <15, 16, 3, 4>, <17, 18, 5, 6>, <13, 15, 5, 6>, <13, 16, 6, 5>, <13, 17, 3, 4>, <13, 18, 4, 3>, <14, 15, 6, 5>, <14, 16, 5, 6>, <14, 17, 4, 3>, <14, 18, 3, 4>, <15, 17, 1, 2>, <15, 18, 2, 1>, <16, 17, 2, 1>, <16, 18, 1, 2>, <1, 7, 13, 14>, <2, 8, 14, 13>, <3, 9, 15, 16>, <4, 10, 16, 15>, <5, 11, 17, 18>, <6, 12, 18, 17>} H*U D* = {(1, 10, 2, 9), (1, 10, 3, 11), (1, 12, 4, 11), (1, 8, 5, 12), (1, 9, 6, 8), (2, 12, 3, 7), (2, 11, 4, 12), (2, 10, 5, 9), (2, 7, 6, 11), (3, 8, 4, 7), (3, 12, 5, 8), (3, 11, 6, 10), (4, 9, 5, 7), (4, 8, 6, 9), (5, 10, 6, 7), (7, 14, 8, 13), (9, 16, 10, 15), (11, 18, 12, 17), (7, 18, 9, 17), (7, 17, 10, 18), (7, 16, 11, 15), (7, 15, 12, 16), (8, 17, 9, 18), (8, 18, 10, 17), (8, 15, 11, 16), (8, 16, 12, 15), (9, 14, 11, 13), (9, 13, 12, 14), (10, 13, 11, 14), (10, 14, 12, 13), (13, 2, 14, 1), (15, 4, 16, 3), (17, 6, 18, 5), (13, 6, 15, 5), (13, 5, 16, 6), (13, 4, 17, 3), (13, 3, 18, 4), (14, 5, 15, 6), (14, 6, 16, 5), (14, 3, 17, 4), (14, 4, 18, 3), (15, 2, 17, 1), (15, 1, 18, 2), (16, 1, 17, 2), (16, 2, 18, 1), (1, 14, 7, 13), (2, 13, 8, 14), (3, 16, 9, 15), (4, 15, 10, 16), (5, 18, 11, 17), (6, 17, 12, 18), (1, 4, 2, 3), (1, 4, 2, 3), (3, 6, 4, 5), (3, 6, 4, 5), (1, 5, 2, 6), 47 (1, 5, 2, 6), (7, 10, 8, 9), (7, 10, 8, 9), (9, 12, 10, 11), (9, 12, 10, 11), (7, 11, 8, 12), (7, 11, 8, 12), (13, 14, 16, 15), (13, 16, 14, 15), (13, 16, 15, 14), (17, 14, 18, 13), (17, 14, 18, 13), (17, 16, 18, 15), (17, 16, 18, 15), <17, 18>} 48 CHAPTER 5 THE 12n + 7 CONSTRUCTION There does not exist a hinge system of order 7 having a metamorphosis into a maximum packing of 2K7 with 4-cycles. So, we begin this chapter by showing the nonexistence for n = 7. Any 2-fold triple system of order 7 with no repeated triples consists of a pair of disjoint Steiner triple systems [2]. So let (S, T1) and (S, T2) be a pair of disjoint triple systems of order 7 and (S, H) any hinge system constructed from T1 and T2. Let D be the collection of 7 double edges from the hinges. Now suppose D contains a 4-cycle (1, 2, 3, 4). Then D must also contain the 4-cycle of double edges (<1, 2>, <2, 3>, <3, 4>, <4, 1>). Since the Steiner triple systems of order 7 is a projective plane (there is only one up to isomorphism.) both T1 and T2 must contain the Pasch Configuration given below: 49 Let {x, a, y} ?T1 and {z, b, w} ? T2. Since (S, T1) and (S, T2) have order 7, we must have {x, a, y} = {z, b, w} = {5, 6, 7}; a contradiction since T1 and T2 are disjoint. Therefore, there does not exist a hinge system of order 7 having a metamorphosis into a maximum packing of 2K7 with 4-cycles. We have the following lemma. Lemma 5.1 There does not exist a hinge system of order 7 having a metamorphosis into a maximum packing of 2K7 with 4-cycles. square6 The following construction will produce a hinge system of every order 19712 ?+n having a metamorphosis into a maximum packing of 2K12n+7 with 4-cycles. Write 12n + 7 = 1 + 3(4n + 2). Let Q = {1, 2, 3, 4, ?, 4n + 2} and let X = 3}) 2, ,1{Q(}{ ?? U . Define a collection of hinges H as follows: 50 (1) For each ?x Q, place the hinge system of order 4 given by and <(x, 2), (x, 3), ?, (x, 1)> in H. (2) Now let (Q, o) be an idempotent antisymmetric quasigroup of order 4n + 2 and for each ?? yx Q, place the three hinges <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)>, <(x, 2), (y, 2), ( yx o , 3), ( xy o , 3)>, and <(x, 3), (y, 3), ( yx o , 1), ( xy o , 1)> in H. 51 Then (X, H) is a hinge system of order 12n + 7. The metamorphosis is as follows: Remove all double edges from (1) and (2). 52 (a) Form the graph: and partition this into a maximum packing of 2K4n+3 with 4-cycles with exactly one double edge left over. (b) Let (Q, F) be a partition of 2K4n+2\{<1, 2>, <3, 4>, ?, <4n + 1, 4n + 2>} into 4-cycles on both Q ? {2} and Q ? {3} and form the graph given below. Partition this graph into 4n 4-cycles with nothing left over. 53 Combining (a) and (b), arranges all of the missing edges into 4-cycles with exactly one double edge left over. We have the following theorem: Theorem 5.2 There exists a hinge system of every order 19712 ?+n having a metamorphosis into a maximum packing of 2K12n+7 with 4-cycles. There does not exist such a system for n = 7.square6 The following example illustrates this theorem. Example 5.3 (metamorphosis of a hinge system of order 19 into a maximum packing with 4- cycles) We have renamed 19?? and renamed the ordered pairs as follows: (1, 1) barb2right 1 (1, 2) barb2right 7 (1, 3) barb2right 13 (2, 1) barb2right 2 (2, 2) barb2right 8 (2, 3) barb2right 14 (3, 1) barb2right 3 (3, 2) barb2right 9 (3, 3) barb2right 15 (4, 1) barb2right 4 (4, 2) barb2right 10 (4, 3) barb2right 16 (5, 1) barb2right 5 (5, 2) barb2right 11 (5, 3) barb2right 17 (6, 1) barb2right 6 (6, 2) barb2right 12 (6, 3) barb2right 18 54 We can define a collection of hinges H, as follows: (1) For each ?x Q, place the following two hinges, <19, (x, 1), (x, 2), (x, 3)> and <(x, 2), (x, 3), 19, (x, 1)> in H. 55 This results in the following 12 hinges: (2) Now let (Q, o) be an idempotent antisymmetric quasigroup of order 6 and for each ?? yx Q, place the three hinges <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)>, <(x, 2), (y, 2), ( yx o , 3), ( xy o , 3)>, and <(x, 3), (y, 3), ( yx o , 1), ( xy o , 1)> in H. ? 1 2 3 4 5 6 1 1 3 4 5 6 2 2 4 2 1 6 3 5 3 5 6 3 1 2 4 4 6 5 2 4 1 3 5 2 4 6 3 5 1 6 3 1 5 2 4 6 56 This results in the following 45 hinges. 57 58 Then (X, H) is a hinge system of order 19. The metamorphosis is as follows: Remove all double edges from (1) and (2). (a) Form the graph: Partition this into a maximum packing of 2K7 with the following 4-cycles and the double edge <6, 19> left over. 59 (b) Let (Q, F) be a partition of 2K6\{<1, 2>, <3, 4>, <5,6>} into 4-cycles on both Q ? {2} and Q ? {3} and form the graph given below. 60 This gives us the following six 4-cycles. We can partition the remaining edges of 2K6\{<1, 2>, <3, 4>, <5, 6>} on Q ?{2} and Q ?{3} into the following 4-cycles. 61 This gives us a metamorphosis of a 2-fold triple system of order 19 into a maximum packing with 4-cycles. H = {<19, 1, 7, 13>, <7, 13, 19, 1>, <19, 2, 8, 14>, <8, 14, 19, 2>, <19, 3, 9, 15>, <9, 15, 19, 3>, <19, 4, 10, 16>, <10, 16, 19, 4>, <19, 5, 11, 17>, <11, 17, 19, 5>, <19, 6, 12, 18>, <12, 18, 19, 6>, <1, 2, 9, 10>, <7, 8, 15, 16>, <13, 14, 3, 4>, <1, 5, 12, 8>, <7, 11, 18, 14>, <13, 17, 6, 2>, <1, 3, 10, 11>, <7, 9, 16, 17>, <13, 15, 4, 5>, <1, 6, 8, 9>, <7, 12, 14, 15>, <13, 18, 2, 3>, <1, 4, 11, 12>, <7, 10, 17, 18>, <13, 16, 5, 6>, <2, 3, 7, 12>, <8, 9, 13, 18>, <14, 15, 1, 6>, <2, 4, 12, 11>, <8, 10, 18, 17>, <14, 16, 6, 5>, <3, 4, 7, 8>, <9, 10, 13, 14>, <15, 16, 1, 2>, <2, 5, 9, 10>, <8, 11, 15, 16>, <14, 17, 3, 4>, <3, 5, 8, 12>, <9, 11, 14, 18>, <15, 17, 2, 6>, <2, 6, 11, 7>, <8, 12, 17, 13>, <14, 18, 5, 1>, <3, 6, 10, 11>, <9, 12, 16, 17>, <15, 18, 4, 5>, <4, 5, 7, 9>, <10, 11, 13, 15>, <16, 17, 1, 3>, <4, 6, 9, 8>, <10, 12, 15, 14>, <16, 18, 3, 2>, <5, 6, 7, 10>, <11, 12, 13, 16>, <17, 18, 1, 4>} H*U D* = {(19, 13, 1, 7), (7, 1, 13, 19), (19, 14, 2, 8), (8, 2, 14, 19), (19, 15, 3, 9), (9, 3, 15, 19), (19, 16, 4, 10), (10, 4, 16, 19), (19, 17, 5, 11), (11, 5, 17, 19), (19, 18, 6, 12), (12, 6, 18, 19), (1, 10, 2, 9), (7, 16, 8, 15), (13, 4, 14, 3), (1, 8, 5, 12), (7, 14, 11, 18), (13, 2, 17, 6), (1, 11, 3, 10), (7, 17, 9, 16), (13, 5, 15, 4), (1, 9, 6, 8), (7, 15, 12, 14), (13, 3, 18, 2), (1, 12, 4, 11), (7, 18, 10, 17), (13, 6, 16, 5), (2, 12, 3, 7), (8, 18, 9, 13), (14, 6, 15, 1), (2, 11, 4, 12), (8, 17, 10, 18), (14, 5, 16, 6), (3, 8, 4, 7), (9, 14, 10, 13), (15, 2, 16, 1), (2, 10, 5, 9), (8, 16, 11, 15), (14, 4, 17, 3), (3, 12, 5, 8), (9, 18, 11, 14), (15, 6, 17, 2), (2, 7, 6, 11), (8, 13, 12, 17), (14, 1, 18, 5), (3, 11, 6, 10), (9, 17, 12, 16), (15, 5, 18, 4), (4, 9, 5, 7), (10, 15, 11, 13), (16, 3, 17, 1), (4, 8, 6, 9), (10, 14, 12, 15), (16, 2, 18, 3), 62 (5, 10, 6, 7), (11, 16, 12, 13), (17, 4, 18, 1), (1, 19, 2, 6), (2, 19, 3, 6), (3, 19, 4, 6), (4, 19, 5, 6), (5, 19, 1, 6), (1, 4, 5, 2), (2, 5, 1, 3), (3, 1, 2, 4), (4, 2, 3, 5), (5, 3, 4, 1), (7, 8, 14, 13), (7, 8, 14, 13), (9, 10, 16, 15), (9, 10, 16, 15), (11, 12, 18, 17), (11, 12, 18, 17), (7, 10, 8, 9), (7, 10, 8, 9), (9, 12, 10, 11), (9, 12, 10, 11), (7, 11, 8, 12), (7, 11, 8, 12), (13, 16, 14, 15), (13, 16, 14, 15), (15, 18, 16, 17), (15, 18, 16, 17), (13, 17, 14, 18), (13, 17, 14, 18), <6, 19>} 63 CHAPTER 6 THE 12n + 10 CONSTRUCTION The introduction to this paper contains an example of a metamorphosis of a hinge system of order 10 into a maximum packing with 4-cycles. So, it is only necessary to give a construction for .221012 ?+n Write 12n + 10 = 1 + 3(4n + 3) and let Q = {1, 2, 3, ?, 4n + 3}. Let X = 3}) 2, ,1{Q(}{ ?? U and define a collection of hinges H as follows: (1) For each ?x Q, place the hinge system of order 4 given by and <(x, 2), (x, 3), ?, (x, 1)> in H. 64 (2) Now let (Q, o) be an idempotent antisymmetric quasigroup of order 4n + 3 and for each ?? yx Q, place the three hinges <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)>, <(x, 2), (y, 2), ( yx o , 3), ( xy o , 3)>, and <(x, 3), (y, 3), ( yx o , 1), ( xy o , 1)> in H. Then (X, H) is a hinge system of order 12n + 10. The metamorphosis is the following: Remove all double edges in (1) and (2). 65 (a) Form the graph and partition this into 4-cycles. (This is possible since 4n + 4 4) (mod 1or 0? ). (b) Let (Q, F) be a partition of 2K4n+3\{<2, 3>, <4, 5>, ?, <4n + 2, 4n + 3>} into 4-cycles (Lemma 2.6) on both Q ? {2} and Q ? {3} and form the graph given below: Partition this graph into 4n + 2 4-cycles with the double edge <(1, 2), (1, 3)> left over. 66 Combining (a) and (b) arranges all of the missing edges into 4-cycles with the edge <(1, 2), (1, 3)> left over. We have the following theorem: Theorem 6.1 There exists a hinge system of every order 101012 ?+n having a metamorphosis into a maximum packing of 2K12n+10 with 4-cycles. square6 The following is the construction of a hinge system of order 12n + 10 = 22, where we have renamed 22?? and renamed the ordered pairs as follows: (1, 1) barb2right 1 (1, 2) barb2right 8 (1, 3) barb2right 15 (2, 1) barb2right 2 (2, 2) barb2right 9 (2, 3) barb2right 16 (3, 1) barb2right 3 (3, 2) barb2right 10 (3, 3) barb2right 17 (4, 1) barb2right 4 (4, 2) barb2right 11 (4, 3) barb2right 18 (5, 1) barb2right 5 (5, 2) barb2right 12 (5, 3) barb2right 19 (6, 1) barb2right 6 (6, 2) barb2right 13 (6, 3) barb2right 20 (7, 1) barb2right 7 (7, 2) barb2right 14 (7, 3) barb2right 21 Example 6.2 (metamorphosis of a hinge system of order 22 into a maximum packing with 4- cycles) Define a collection of hinges H, as follows: (1) For each ?x Q, place the hinge system of order 4 given by and <(x, 2), (x, 3), ?, (x, 1)> in H. 67 The following are the 14 hinges of this type. 68 (2) Now let (Q, o) be an idempotent antisymmetric quasigroup of order 7 and for each ?? yx Q, place the three hinges <(x, 1), (y, 1), ( yx o , 2), ( xy o , 2)>, <(x, 2), (y, 2), ( yx o , 3), ( xy o , 3)>, and <(x, 3), (y, 3), ( yx o , 1), ( xy o , 1)> in H. o 1 2 3 4 5 6 7 1 1 6 4 2 7 5 3 2 4 2 7 5 3 1 6 3 7 5 3 1 6 4 2 4 3 1 6 4 2 7 5 5 6 4 2 7 5 3 1 6 2 7 5 3 1 6 4 7 5 3 1 6 4 2 7 69 The following are the 63 hinges of this type. 70 71 Then (X, H) is a hinge system of order 22. The metamorphosis is as follows. Remove all of the double edges in (1) and (2). (a) Form the graph: 72 This can be partitioned into the following fourteen 4-cycles. (b) Partition 2K7\{<2, 3>, <4, 5>, <6, 7>} into 4-cycles (Lemma 2.6) on both Q ? {2} and Q ? {3}. This gives us the following eighteen 4-cycles. 73 74 (c) Form the graph given below: We can partition this into the following six 4-cycles with a double edge left over. This gives a maximum packing of 2K22 with 4-cycles with leave the double edge <8, 15>. 75 H = {<22, 1, 8, 15>, <8, 15, 22, 1>, <22, 2, 9, 16>, <9, 16, 22, 2>, <22, 3, 10, 17>, <10, 17, 22, 3>, <22, 4, 11, 18>, <11, 18, 22, 4>, <22, 5, 12, 19>, <12, 19, 22, 5>, <22, 6, 13, 20>, <13, 20, 22, 6>, <22, 7, 14, 21>, <14, 21, 22, 7>, <1, 2, 13, 11>, <8, 9, 20, 18>, <15, 16, 6, 4>, <1, 3, 11, 14>, <8, 10, 18, 21>, <15, 17, 4, 7>, <1, 4, 9, 10>, <8, 11, 16, 17>, <15, 18, 2, 3>, <1, 5, 14, 13>, <8, 12, 21, 20>, <15, 19, 7, 6>, <1, 6, 12, 9>, <8, 13, 19, 16>, <15, 20, 5, 2>, <1, 7, 10, 12>, <8, 14, 17, 19>, <15, 21, 3, 5>, <2, 3, 14, 12>, <9, 10, 21, 19>, <16, 17, 7, 5>, <2, 4, 12, 8>, <9, 11, 19, 15>, <16, 18, 5, 1>, <2, 5, 10, 11>, <9, 12, 17, 18>, <16, 19, 3, 4>, <2, 6, 8, 14>, <9, 13, 15, 21>, <16, 20, 1, 7>, <2, 7, 13, 10>, <9, 14, 20, 17>, <16, 21, 6, 3>, <3, 4, 8, 13>, <10, 11, 15, 20>, <17, 18, 1, 6>, <3, 5, 13, 19>, <10, 12, 20, 16>, <17, 19, 6, 2>, <3, 6, 11, 12>, <10, 13, 18, 9>, <17, 20, 4, 5>, <3, 7, 9, 8>, <10, 14, 16, 15>, <17, 21, 2, 1>, <4, 5, 9, 14>, <11, 12, 16, 21>, <18, 19, 2, 7>, <4, 6, 14, 10>, <11, 13, 21, 17>, <18, 20, 7, 3>, <4, 7, 12, 13>, <11, 14, 19, 20>, <18, 21, 5, 6>, <5, 6, 10, 8>, <12, 13, 17, 15>, <19, 20, 3, 1>, <5, 7, 8, 11>, <12, 14, 15, 18>, <19, 21, 1, 4>, <6, 7, 11, 9>, <13, 14, 18, 16>, <20, 21, 4, 2>} H*U D* = {(22, 15, 1, 8), (8, 1, 15, 22), (22, 16, 2, 9), (9, 2, 16, 22), (22, 17, 3, 10), (10, 3, 17, 22), (22, 18, 4, 11), (11, 4, 18, 22), (22, 19, 5, 12), (12, 5, 19, 22), (22, 20, 6, 13), (13, 6, 20, 22), (22, 21, 7, 14), (14, 7, 21, 22), (1, 11, 2, 13), (8, 18, 9, 20), (15, 4, 16, 6), (1, 14, 3, 11), (8, 21, 10, 18), (15, 7, 17, 4), (1, 10, 4, 9), (8, 17, 11, 16), (15, 3, 18, 2), (1, 13, 5, 14), (8, 20, 12, 21), (15, 6, 19, 7), (1, 9, 6, 12), (8, 16, 13, 19), (15, 2, 20, 5), (1, 12, 7, 10), (8, 19, 14, 17), (15, 5, 21, 3), (2, 12, 3, 14), (9, 19, 10, 21), (16, 5, 17, 7), (2, 8, 4, 12), (9, 15, 11, 19), (16, 1, 18, 5), (2, 11, 5, 10), (9, 18, 12, 17), (16, 4, 19, 3), (2, 14, 6, 8), 76 (9, 21, 13, 15), (16, 7, 20, 1), (2, 10, 7, 13), (9, 17, 14, 20), (16, 3, 21, 6), (3, 13, 4, 8), (10, 20, 11, 15), (17, 6, 18, 1), (3, 19, 5, 13), (10, 16, 12, 20), (17, 2, 19, 6), (3, 12, 6, 11), (10, 9, 13, 18), (17, 5, 20, 4), (3, 8, 7, 9), (10, 15, 14, 16), (17, 1, 21, 2), (4, 14, 5, 9), (11, 21, 12, 16), (18, 7, 19, 2), (4, 10, 6, 14), (11, 17, 13, 21), (18, 3, 20, 7), (4, 13, 7, 12), (11, 20, 14, 19), (18, 6, 21, 5), (5, 8, 6, 10), (12, 15, 13, 17), (19, 1, 20, 3), (5, 11, 7, 8), (12, 18, 14, 15), (19, 4, 21, 1), (6, 9, 7, 11), (13, 16, 14, 18), (20, 2, 21, 4), (1, 2, 5, 6), (2, 3, 6, 7), (3, 4, 7, 22), (4, 5, 1, 22), (2, 4, 6, 22), (1, 3, 5, 7), (2, 3, 7, 6), (1, 4, 5, 22), (22, 7, 4, 6), (1, 2, 5, 7), (3, 4, 2, 22), (5, 6, 1, 3), (1, 4, 22, 5), (2, 6, 3, 7), (9, 11, 10, 8), (9, 8, 10, 12), (10, 11, 8, 12), (9, 11, 8, 12), (8, 14, 9, 13), (9, 14, 10, 13), (10, 14, 11, 13), (11, 14, 12, 13), (12, 14, 8, 13), (16, 18, 17, 15), (16, 15, 17, 19), (17, 18, 15, 19), (16, 18, 15, 19), (15, 21, 16, 20), (16, 21, 17, 20), (17, 21, 18, 20), (18, 21, 19, 20), (19, 21, 15, 20), (9, 10, 17, 16), (9, 10, 17, 16), (11, 12, 19, 18), (11, 12, 19, 18), (13, 14, 21, 20), (13, 14, 21, 20), <8, 15>} 77 CHAPTER 7 SUMMARY Combining all of the results in Chapters 1, 2, 3, 4, 5, and 6, we have a proof of Theorem 1.7. Theorem 1.7 There exists a hinge system of order n having a metamorphosis into a maximum packing of 2Kn with 4-cycles if and only if 10. 12) (mod 10or 7, 6, ,3 ??n 2-fold maximum packing of 2Kn with 4-cycles 78 REFERENCES [1] T.P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. J., (1847), 191- 204. [2] C. J. Colbourn and A. Rosa, Triple Systems, Oxford University Press, (1999), 560 pages. [3] C. Huang and A. Rosa, On the existence of balanced bipartite designs, Utilitas Math., 4(1973), 55-75. [4] Mario Gionfriddo and C.C. Lindner, The metamorphosis of 2-fold triple systems into 2-fold 4-cycle systems, JCMCC, 46(2003), 129-139. [5] D. Sotteau, Decompositions of Km,n(K*m,n) into cycles (circuits) of length 2k, J. Combinatorial Theory, Sec. B, 30(1981), 75-78.