On the existence of Even and k-divisible-Matchings Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classifled information. Emilia Moore Certiflcate of Approval: Christopher Rodger Professor Mathematics and Statistics Dean Hofiman, Chair Professor Mathematics and Statistics Peter Johnson Professor Mathematics and Statistics Nedret Billor Professor Mathematics and Statistics Joe F. Pittman Interim Dean Graduate School On the existence of Even and k-divisible-Matchings Emilia Moore A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Fulflllment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 10, 2008 On the existence of Even and k-divisible-Matchings Emilia Moore Permission is granted to Auburn University to make copies of this dissertation at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Vita Emilia Anna Moore, daughter of Piotr and Anna Lusnia, was born on October 3, 1982, in Garwolin, Poland. She graduated from Loveless Academic Magnet Program High School in Montgomery, Alabama, in 2000. She then attended Huntingdon College in Montgomery, Alabama, for three years and graduated magna cum laude with Bachelor of Art degrees in Mathematics and Computer Science in May 2003. She entered the PhD program at Auburn University, in June 2003 and was awarded a Master of Science degree in Mathematics in May 2006. iv Dissertation Abstract On the existence of Even and k-divisible-Matchings Emilia Moore Doctor of Philosophy, May 10, 2008 (M.S., Auburn University, 2006) (B.A., Huntingdon College, 2003) 98 Typed Pages Directed by Dean Hofiman The concept of an an even matching was flrst introduced by Billington and Hofiman. They were used to flnd gregarious 4-cycle decompositions of K8t(a);b with a and b odd. Their paper contains even matchings of type (fi8;fl) for fi, fl even and 0 ? fl ? 4fi. This paper considers the necessary and su?cient conditions for the existence of even matchings as well as k-divisible matchings. We present a construction of even matchings and 3-divisible matchings of type (a1;a2;:::;ap) provided the necessary conditions are satisfled. v Acknowledgments The author wishes to express her appreciation for her family members Jakub, Pawel, Anna and Piotr who have given of their love throughout her life. She would like to thank her husband Robert for his abundant support, guidance and love. The author would also like to thank the numerous families who have supported her throughout her life, the Jinrights, the Henrys, the Lindleys and the Stakelys. The author would also like to thank the professors from her advisory committee for their contribution to this dissertation, with special thanks to Dr. Dean Hofiman for the considerable time, thought, and energy which he used in order to further the author?s progress in her studies of design theory. vi Style manual or journal used Journal of Approximation Theory (together with the style known as \aums"). Bibliography follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speciflcally LATEX) together with the departmental style-flle aums.sty. vii Table of Contents 1 Introduction 1 1.1 Even Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Existence of Even Matchings 4 2.1 Necessary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Su?ciency of Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2.1 Any number of parts of the same size . . . . . . . . . . . . . . . . 7 2.2.2 Five parts of any size . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Seven parts of any size . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.4 Nine parts of any size . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.5 p ? 1 (mod 4) parts of any size . . . . . . . . . . . . . . . . . . . . 32 2.2.6 p ? 3 (mod 4) parts of any size . . . . . . . . . . . . . . . . . . . . 38 3 Existence of k-divisible-Matchings 44 3.1 Necessary conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2 3-divisible-matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.1 Any number of parts of the same size . . . . . . . . . . . . . . . . 48 3.2.2 Seven parts of any size . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2.3 Ten parts of any size . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.4 p ? 1 (mod 6) parts of any size . . . . . . . . . . . . . . . . . . . . 61 3.2.5 p ? 4 (mod 6) parts of any size . . . . . . . . . . . . . . . . . . . . 67 3.3 k-divisible-matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.3.1 Any number of parts of the same size . . . . . . . . . . . . . . . . 72 3.3.2 2k +1 parts of any size . . . . . . . . . . . . . . . . . . . . . . . . 74 3.3.3 3k +1 parts of any size . . . . . . . . . . . . . . . . . . . . . . . . 83 Bibliography 90 viii Chapter 1 Introduction 1.1 Even Matchings In a recent paper by Dean Hofiman and Elizabeth Billington a deflnition of an even matching was introduced [1]. Deflnition 1.1 Let a1;:::;ap be non-negative integers. We deflne the complete mul- tipartite graph K(a1;a2;:::;ap) as the graph whose vertex set is partitioned into parts A1;:::;Ap of size a1;:::;ap respectively. Two vertices are adjacent if and only if they are in two difierent parts. Deflnition 1.2 Let a1;a2;:::;ap be non-negative integers, and let Ai denote the vertex partite set of size ai, for 1 ? i ? p. Then for the graph K(a1;a2;:::;ap), the ordered set M = (M1;M2;:::;Mp) is an even matching of type (a1;a2;:::;ap) if 1. for each i, 1 ? i ? p, the set Mi is a perfect matching in the graph K(a1;a2;:::;ap)nAi, and 2. every edge of K(a1;a2;:::;ap) lies in an even number of matchings Mi (this number could be zero). We will refer to this as the \evenness" condition. In the above mentioned paper, a limited number of even matchings was used to help construct gregarious 4-cycle decompositions of K(a;a;a;a;a;a;a;a;b) for odd size parts and a ? 3. The matchings used were of the form (fi8;fl) for all even fi and fl, with 0 ? fl ? 4fi. We wanted to know the necessary and su?cient conditions for the existence 1 of even matchings. Throughout the paper we will use the notation (ap) to represent a matching type with p parts of size a. In Chapter 2 we prove the following theorem. Theorem 1.3 Assume even matchings of the types (02h;22h;4h?2), (13h+c;3h?c;6h? 3 ? 2c), (1h+c;33h?c;10h ? 5 ? 2c), (1h+c;32h?c;7h;14h ? 7 ? 2c) for h ? c, (14h;i) for 3 ? i ? 4h ? 3 odd, (14h?1;j;i) for 3 ? i ? 4h ? 1 and 3 ? j ? i odd, and (02h+1;22h+1;4h) exist. Assume a1 ? a2 ? ::: ? ap and deflne n = Ppi=1 ai. An even matching of the type (a1;:::;ap) exists if and only if 1. p is odd, 2. 2ap +ap?1 ? n, 3. either ai are even for all 1 ? i ? p or ai are odd for all 1 ? i ? p and p ? 1 (mod 4), 4. 2(p?2)ap ? (p?3)n. In Chapter 3 we will generalize this notion to that of k-divisible-matchings and consider the existence problem for them. More precisely, we prove the following theorem. Theorem 1.4 Assume 3-divisible-matchings of the types (04h;22h;4h?2), (14h+c;32h?c;10h?5?2c), (12h+c;34h?c;7h;14h?7?2c) for 0 ? c ? 2h?3, (16h;i) for 3 ? i ? 6h ? 3 odd, (16h?1;j;i) for 3 ? i ? 6h ? 1 and 3 ? j ? i odd, and (04h+2;22h+1;4h) exist. Assume a1 ? a2 ? ::: ? ap and deflne n = Ppi=1 ai. A 3-divisible-matching of the type (a1;:::;ap) exists if and only if 1. p ? 1 (mod 3), 2 2. 2ap +ap?1 ? n, 3. Either all ai are even or all ai are odd and p is odd. 4. (2p?5)ap ? (p?4)n. 3 Chapter 2 Existence of Even Matchings 2.1 Necessary conditions In this Section we present the necessary conditions for the existence of even match- ings of type (a1;a2;:::;ap). Let us deflne the set S2 = f(a1;:::;ap)j an even matching on the graph K(a1;:::;ap) existsg. We assume a1 ? a2 ? ::: ? ap and deflne n = Ppi=1 ai. The necessary conditions are as follows: 1. p is odd, 2. 2ap +ap?1 ? n, 3. either ai are even for all 1 ? i ? p or ai are odd for all 1 ? i ? p and p ? 1 (mod 4), 4. 2(p?2)ap ? (p?3)n. Let us conflrm the above conditions. We assume that (M1;:::;Mp) is an even matching of the type (a1;:::;ap). 1. Each vertex (element of Ai) will be used in p?1 edges of Spi=1 Mi, and the number of edges that vertex is in must be even, equivalently p?12 must be an integer. Therefore p must be odd. 4 2. For every i < p, n ? ai ? 2ap ? 0, since we must have enough vertices in each K(a1;:::;ap)nAi to \match" the vertices of the largest part. Since a1 ? a2 ? ::: ? ap, it is su?cient that n?ap?1 ?2ap ? 0 ) 2ap +ap?1 ? n. 3. Since each Mi is to be a perfect matching, (Ppi=1 ai)?ai must be even for all i; hence all ai have same parity. The \evenness" condition requires Pp i=1 n?ai 2 = (p?1)n 2 be even. Therefore either all ai are even, or all ai are odd and p?1 2 even, hence p ? 1 (mod 4). 4. None of the edges in Mp use vertices in Ap. There must be enough edges in M1[M2[:::[Mp?1 not intersecting Ap to satisfy the evenness condition. So, n?ap 2 ? p?1X i=1 n?ai ?2ap 2 = (p?2)n?(2p?3)ap 2 ; hence 2(p?2)ap ? (p?3)n: Notice that, by Property 4, p > 3. 2.2 Su?ciency of Conditions The paper by Billington and Hofiman contains the following Lemmas regarding even matchings. Lemma 2.1 If M = (M1;M2;:::;Mp) is an even matching of type (a1;a2;:::;ap) and N = (N1;N2;:::;Np) is an even matching of type (b1;b2;:::;bp), on disjoint vertex sets, then 5 M [N = (M1 [N1;M2 [N2;:::;Mp [Np) is an even matching of type (a1 + b1;a2 + b2;:::;ap +bp). Lemma 2.2 If M = (M1;M2;:::;Mp) is an even matching of type (a1;a2;:::;ap) and N = (N1;N2;:::;Nq) is an even matching of type (a1;b2;:::;bq), then there exists an even matching for K(a1;a2;:::;ap;b2;b3;:::;bq) of type (a1;a2;:::;ap;b2;b3;:::;bq). UsingtheaboveLemma2.2wecaninductivelyconstructevenmatchingsoftype(c1;c2;:::;cr), for any r ? 9, from matchings with flve, (a1;a2;a3;a4;a5), and seven, (b1;b2;:::;b7), parts. This construction is limited as the converse of Lemma 2.2 is not true. We use the following Lemma in various proofs throughout the paper. Lemma 2.3 If the graph K(a1;:::;ap) satisfles the four necessary conditions and ai is even for all i, then there exists a perfect matching on K(a1;:::;ap). Proof: By property 2, ap < n2. Also, the total number of vertices is even. The rest of the proof is trivial. ? The following Lemmas are useful when working with even matchings. Lemma 2.4 If a1;:::;ap are even and (a1;:::;ap) is in S2, then (02n;a1;:::;ap) is also in S2 for any integer n. Proof: Let (M1;:::;Mp) be an even matching of type (a1;:::;ap). Let N be any perfect matching on K(a1;:::;ap). By Lemma 2.3, N exists. We construct an even matching of K(02n;a1;:::;ap) as follows. M0i = N for 1 ? i ? kn M0j+kn = Mj for 1 ? j ? p Clearly this is an even matching. ? 6 Lemma 2.5 If a1;:::;ap;b2;:::;bq are all even and (a1;:::;ap), (0;b2;:::;bq) are both in S2, then (b2;:::;bq;a1;:::;ap) is in S2. Proof: Let (M1;:::;Mp) be an even matching of type (a1;:::;ap) and (N1;:::;Nq) be an even matching of type (0;b2;:::;bq). Let R be any perfect matching on K(a1;:::;ap). By Lemma 2.3, R exists. We construct an matching of K(b2;:::;bq;a1;:::;ap) as follows. M0i = Ni+1 [R for 1 ? i ? q ?1 M0j+q?1 = N1 [Mj for 1 ? j ? p Since p?1 and q ?1 are both even this is an even matching. ? In the next Sections we will consider p = 5, p = 7 and p = 9. Then we will generalize the argument for any odd p. 2.2.1 Any number of parts of the same size Let us consider even matchings of the type (a5) and (a7), with a even in the latter case. It is su?cient to consider (1;1;1;1;1), (2;2;2;2;2) and (2;2;2;2;2;2;2). We can then use Lemma 2.1, with an appropriate number of copies of (2;2;2;2;2) or (2;2;2;2;2;2;2), to construct even matchings of types (a5) and (a7). Also, using Lemma 2.2 we can construct even matchings of type (ap) for any odd p ? 5. Through out the paper we let the parts of K(a1;:::;ap) be f1;10;100;1000;14;:::;1a1?1g;:::;fp;p0;p00;p000;p4;:::;pap?1g. We let f10;pg be the edge joining 10 and p. The following is an even matching of type (1;1;1;1;1): M1: ff2;3g;f4;5gg M2: ff1;3g;f4;5gg 7 M3: ff1;5g;f2;4gg M4: ff1;5g;f2;3gg M5: ff1;3g;f2;4gg Here is an even matching of type (2;2;2;2;2): M1: ff2;3g;f4;5g;f20;30g;f40;50gg M2: ff3;4g;f5;10g;f30;40g;f50;1gg M3: ff1;2g;f4;5g;f10;20g;f40;50gg M4: ff2;3g;f5;10g;f20;30g;f50;1gg M5: ff3;4g;f10;20g;f30;40g;f1;2gg Here is an even matching of type (2;2;2;2;2;2;2): M1: ff2;3g;f20;4g;f30;40g;f5;6g;f50;7g;f60;70gg M2: ff3;4g;f30;5g;f40;50g;f6;7g;f1;60g;f10;70gg M3: ff4;5g;f40;6g;f50;60g;f1;7g;f2;70g;f10;20gg M4: ff5;6g;f50;7g;f60;70g;f1;2g;f10;3g;f20;30gg M5: ff6;7g;f1;60g;f10;70g;f2;3g;f20;4g;f30;40gg M6: ff1;7g;f2;70g;f10;20g;f3;4g;f30;5g;f40;50gg M7: ff1;2g;f10;3g;f20;30g;f4;5g;f40;6g;f50;60gg 2.2.2 Five parts of any size In this Section we will give even matchings of type (a1;a2;a3;a4;a5). Since p = 5 ? 1 (mod 4) we can have all parts of even size or all parts of odd size. We will describe how to use Lemma 2.1 with (2;0;0;2;2) to construct an even matching (a1;:::;a5) from (1;1;1; ; ) or (0;2; ; ; ). 8 Here are the \building blocks" we will use. (0;0;2;2;2) M1: ff3;5g;f30;4g;f40;50gg M2: ff3;40g;f4;5g;f30;50gg M3: ff4;5g;f40;50gg M4: ff3;5g;f30;50gg M5: ff3;40g;f30;4gg (0;2;2;2;2) M1: ff2;40g;f3;50g;f4;20g;f5;30gg M2: ff3;40g;f4;50g;f5;30gg M3: ff2;40g;f4;50g;f5;20gg M4: ff2;30g;f3;50g;f5;20gg M5: ff2;30g;f3;40g;f4;20gg To flnd an even matching of type (a1;:::;a5) we use the following algorithm. 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist and we stop. If a1 = 0 and a2 = 0;2 or a1 = a2 = a3 = 1 look at the listing below to flnd the even matching. Otherwise continue below. 2. Subtract (2;0;0;2;2) to obtain (a1 ?2;a2;a3;a4 ?2;a5 ?2). 3. If necessary, rearrange the terms to ensure that the sequence is nondecreasing. 4. Repeat the above steps until you obtain (1; ; ; ; ) or (0; ; ; ; ). 9 5. Subtract (0;2;0;2;2) and rearrange the terms when necessary until you obtain (1;1; ; ; ) or (0;2; ; ; ). 6. Subtract (0;0;2;2;2) and rearrange the terms when necessary until you obtain (1;1;1; ; ). 7. Look up the obtained matching in the list provided below. Let us consider the four necessary conditions during the \subtracting process." 1. p = 5 is not afiected. 2. If (a1;a2;a3;a4;a5) satisfles 2a5+a4 ? a1+:::+a5, then (a1?2;a2;a3;a4?2;a5?2) satisfles 2(a5 ?2) + (a4 ?2) ? (a1 ?2) + a2 + a3 + (a4 ?2) + (a5 ?2). We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us con- sider the following cases: Case 1: If after such rearranging a5 ? 2 is not the largest, but the second largest part, then a3 = a5. So we started with (a1;a2;a5;a5;a5) and now have (a1 ?2;a2;a5 ?2;a5 ?2;a5). By Properties 2 and 4, (a1 ?2;a2;a5 ?2;a5 ?2;a5) is in S2 as long as 6 ? a1 + a2. Let us consider the cases when a1 + a2 < 6. We could have (1;1;a5;a5;a5), (1;3;a5;a5;a5), (0;0;a5;a5;a5), (0;2;a5;a5;a5), (0;4;a5;a5;a5) and (2;2;a5;a5;a5). Each one of those is listed below. Case 2: If after rearranging a5 ?2 is not the largest or second largest part, then a2 = ::: = a5. So we started with (a1;a5;a5;a5;a5) and now have (a1 ? 2;a5 ? 2;a5 ?2;a5;a5). By Properties 2 and 4, (a1 ?2;a5 ?2;a5 ?2;a5;a5) is in S2 as long as 6 ? a1 + a5. Let us consider the cases when a1 + a5 < 6. We could have (1;1;1;1;1), (1;3;3;3;3), (0;2;2;2;2), (0;4;4;4;4) and (2;2;2;2;2). Each one of 10 those is included in Case 1. Case 3: If after rearranging a5 ? 2 is the largest, but a4 ? 2 is not the second largest part, then a3 = a4. So we started with (a1;a2;a4;a4;a5) and now have (a1 ?2;a2;a4 ?2;a4;a5 ?2). By Property 2, (a1 ?2;a2;a4 ?2;a4;a5 ?2) is in S2 as long as a5 6= a1 +a2 +a4. Let us consider the case when a5 = a1 +a2 +a4, then by Property 4, a4 = a5 and we had (a1;a2;a5;a5;a5). But since by assumption a5 = a1 + a2 + a4 = a1 + a2 + a5, we have 0 = a1 + a2, hence we started with (0;0;a5;a5;a5) which is discussed below and shown to be in S2. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;a2;a3;a4;a5) satisfles 3a5 ? a1 +a2 +a3 +a4 +a5, then (a1 ?2;a2;a3;a4 ? 2;a5?2) satisfles 3(a5?2) ? (a1?2)+a2+a3+(a4?2)+(a5?2). The problems that arise with rearranging the terms were discussed under Property 2. Therefore, each time we subtract we obtain a member of S2. When we reach (1;1;1; ; ) or (0;2; ; ; ) all four conditions are satisfled. Hence, an even matching of such a type exists. Following is a list of all even matchings of type (1;1;1; ; ). (1;1;1;1;1) was given in Section 2.2.1 (1;1;1;3;3): M1: ff2;50g;f3;40g;f400;500g;f4;5gg M2: ff1;4g;f3;5g;f40;50g;f400;500gg M3: ff1;500g;f2;400g;f4;5g;f40;50gg M4: ff1;500g;f2;50g;f3;5gg M5: ff1;4g;f2;400g;f3;40gg 11 (1;1;a5;a5;a5)=(1;1;1;1;1)+a5?12 copies of (0;0;2;2;2) (1;3;a5;a5;a5)=(1;1;1;1;1)+(0;2;2;2;2)+a5?32 copies of (0;0;2;2;2) Following are even matchings of types (0;2; ; ; ). (0;0;2;2;2) given in Section 2.2.2 By Property 2, an even matching of type (0;0;a3;a4;a5) must satisfy a5 ? a3. Since a3 ? a5 by deflnition, we must have types (0;0;a5;a5;a5). (0;0;a5;a5;a5) from a5=2 copies of (0;0;2;2;2) (0;2;2;2;2) given in Section 2.2.2 By Properties 2 and 4 the possible elements of S2 with a1 = 0 and a2 = 2 are of the form (0;2;a5 ?2;a5;a5) or (0;2;a5;a5;a5). (0;2;a5 ?2;a5;a5) = (0;2;0;2;2) + a5?22 copies of (0;0;2;2;2) (0;2;a5;a5;a5)= (0;2;2;2;2) + a5?22 copies of (0;0;2;2;2) (0;4;a5;a5;a5)= 2 copies of (0;2;2;2;2) + a5?42 copies of (0;0;2;2;2) (2;2;a5;a5;a5)= (2;2;2;2;2) + a5?22 copies of (0;0;2;2;2) We now have even matchings of type (a1;a2;a3;a4;a5) as long as (a1;a2;a3;a4;a5) satisfles the necessary conditions. 2.2.3 Seven parts of any size Let us now consider even matchings of type (a1;:::;a7) where the sequence is non- decreasing, i.e. a1 ? ::: ? a7. Since p = 7 6? 1 (mod 4), all parts must be of even size. Similar to the case of flve parts, to flnd an even matching of type (a1;:::;a7) we use the following algorithm. 12 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = a2 = a3 = 0 and a4 = 0;2 or K = (0;0;2;2;2;2;2) look up the matching in list provided. Otherwise continue below. 2. For 0 ? i ? 3 repeat the following steps. 3. If 5a7 = 2n skip down to the Special Case 1 section. If a5 = a6 and a7 = a1 + ::: + a5 skip down to Special Case 2 section. Otherwise continue below. 4. Subtract (0i;2;04?i;2;2). 5. If necessary, rearrange the terms to ensure that the sequence is nondecreasing. 6. Repeat steps 3-5 until you obtain (0;0;0;2; ; ; ). 7. The even matchings of type (0;0;0;2; ; ; ) are listed below. Let us consider the four necessary conditions during steps 3-5 of the algorithm. 1. p = 7 is not afiected. 2. If (a1;:::;a7) satisfles 2a7+a6 ? a1+:::+a7, then (a1?2;a2;a3;a4;a5;a6?2;a7?2) satisfles 2(a7 ?2) + (a6 ?2) ? (a1 ?2) +a2 +a3 +a4 +a5 + (a6 ?2) + (a7 ?2). We are, however, rearranging the terms. Let us consider the following cases: Case 1: If after such rearranging a7 ?2 is not the largest, but the second largest part, then a5 = a7. So we started with (a1;a2;a3;a4;a7;a7;a7) and now have (a1? 2;a2;a3;a4;a7?2;a7?2;a7). By Properties 2 and 4, (a1?2;a2;a3;a4;a7?2;a7? 2;a7) is in S2 as long as 4 ? a1+a2+a3+a4 and 12?a7 ? 2a1+2a2+2a3+2a4. Let 13 us consider the case when a1+a2+a3+a4 < 4. We could have (0;0;0;0;a7;a7;a7) or (0;0;0;2;a7;a7;a7). Each one of those is discussed and shown to be an element of S2 below. Let us consider the case when 12?a7 > 2a1+2a2+2a3+2a4. We could have (0;0;0;0;2;2;2);(0;0;0;0;4;4;4);:::;(0;0;0;0;10;10;10), (0;0;0;2;2;2;2); (0;0;0;2;4;4;4);(0;0;0;2;6;6;6) or (0;0;2;2;2;2;2). Each one of those is shown to be in S2. Case 2: If after rearranging a7 ? 2 is not the largest or second largest part, then a4 = ::: = a7. So we started with (a1;a2;a3;a7;a7;a7;a7) and now have (a1 ? 2;a2;a3;a7 ? 2;a7 ? 2;a7;a7). By Properties 2 and 4, (a1 ? 2;a2;a3;a7 ? 2;a7?2;a7;a7) is in S2 as long as 6?a7 ? a1+a2+a3 and 12?3a7 ? 2a1+2a2+2a3. Let us consider the cases when 6?a7 > a1+a2+a3 or 12?3a7 > 2a1+2a2+2a3. We could have (0;0;0;2;2;2;2), (0;0;0;4;4;4;4) or (0;0;2;2;2;2;2). Each one of those is in S2. Case 3: If after rearranging a7?2 is the largest, but a6?2 is not the second largest part, then a5 = a6. So we started with (a1;a2;a3;a4;a6;a6;a7) and now have (a1?2;a2;a3;a4;a6?2;a6;a7?2). By Property 2, (a1?2;a2;a3;a4;a6?2;a6;a7?2) is in S2 as long as a7 6= a1+:::+a5. The case when a7 = a1+:::+a5 and a5 = a6 is discussed below as Special Case 2. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;:::;a7) satisfles 5a7 < 2(a1+:::+a7), then (a1?2;a2;a3;a4;a5;a6?2;a7?2) satisfles 5(a7?2) ? 2((a7?2)+a2+a3+a4+a5+(a6?2)+(a7?2)). If 5a7 = 2n we 14 refer to Special Case 1. Problems arising from rearranging the terms are discussed under item 2 above. Therefore, each time we repeat steps 2-5 we obtain an element of S2 and if we reach (0;0;0;2; ; ; ) all four conditions are satisfled. Notice that the above holds for the remaining steps of the algorithm. So it is su?cient to give even matchings of type (0;0;0;2; ; ; ) and consider the special cases mentioned above. Let us consider the Special Case 1. We deflne the set SP1 as the set of all matching types satisfying the four necessary conditions and 3a7 = 2(a1 + ::: + a6). We construct an even matching of type K = (a1;:::;a7) 2 SP1 by induction. We start by subtracting (0;0;0;2;2;2;4) to obtain K0 = (a1;a2;a3;a4 ?2;a5 ?2;a6 ?2;a7 ?4). As long as no rearranging is necessary K0 is in SP1. If rearranging is necessary, we started with K = (a1;a2;a6;a6;a6;a6;a7) and now have K00 = (a1;a2;a6 ? 2;a6 ? 2;a6 ? 2;a6;a7 ? 4). This is always in SP1. This concludes the inductive argument, since each time we repeat this process we obtain a smaller element of SP1. Thus Special Case 1 is solved. Now let us consider Special Case 2. If a5 = a6 and a7 = a1 + ::: + a5 we have types of the form (a1;a2;a3;a4;a7 ? (a1 + ::: + a4);a7 ? (a1 + ::: + a4);a7). We will construct an even matching of such type as follows: a1=2 copies of (2;0;0;0;2;2;4), a2=2 copies of (0;2;0;0;2;2;4), a3=2 copies of (0;0;2;0;2;2;4), a4=2 copies of (0;0;0;2;2;2;4) and (a7 ?2(a1 + ::: + a4))=2 copies of (0;0;0;0;2;2;2). Notice that by Property 4, a7 ? 2(a1 + ::: + a4). This concludes Special Case 2. 15 The following are even matchings of type (0;0;0;2; ; ; ). (0;0;0;0;2;2;2): M1: ff5;7g;f6;70g;f50;60gg M2: ff5;60g;f6;70g;f50;7gg M3: ff5;6g;f60;70g;f50;7gg M4: ff5;60g;f6;7g;f50;70gg M5: ff6;7g;f60;70gg M6: ff5;7g;f50;70gg M7: ff5;6g;f50;60gg By Property 2, an even matching of type (0;0;0;0;a5;a6;a7) exists if a7 ? a5. Hence we must have (0;0;0;0;a7;a7;a7). (0;0;0;0;a7;a7;a7) from a7=2 copies of (0;0;0;0;2;2;2) (0;0;0;2;2;2;2): M1: ff4;5g;f6;7g;f40;50g;f60;70gg M2: ff4;5g;f6;7g;f40;70g;f50;60gg M3: ff4;5g;f6;7g;f40;70g;f50;60gg M4: ff5;70g;f50;60g;f6;7gg M5: ff4;7g;f40;6g;f60;70gg M6: ff4;7g;f40;50g;f5;70gg M7: ff4;5g;f40;6g;f50;60gg (0;0;0;2;2;2;4): M1: ff4;5g;f6;70g;f60;7g;f40;700g;f50;7000gg M2: ff4;700g;f40;6g;f5;7000g;f50;70g;f60;7gg 16 M3: ff4;7g;f40;700g;f5;7000g;f50;60g;f6;70gg M4: ff5;700g;f50;7000g;f6;7g;f60;70gg M5: ff4;700g;f40;7000g;f6;7g;f60;70gg M6: ff4;7g;f40;7000g;f5;700g;f50;70gg M7: ff4;5g;f40;6g;f50;60gg In general, by Property 2, an even matching of type (0;0;0;2;a5;a6;a7) exists if a5 ? a7 ?2. (0;0;0;2;a7;a7;a7) from (0;0;0;2;2;2;2) and (a7 ?2)=2 copies of (0;0;0;0;2;2;2) (0;0;0;2;a7 ?2;a7;a7) from (0;0;0;2;0;2;2) and (a7 ?2)=2 copies of (0;0;0;0;2;2;2) Since a7 ? 2, a7 ?2 ? 0. (0;0;0;2;a7?2;a7?2;a7) from (0;0;0;2;2;2;4) and (a7?4)=2 copies of (0;0;0;0;2;2;2) Since a7 ?2 ? 2, a7 ?4 ? 0. (0;0;0;4;4;4;4)= 2 copies of (0;0;0;2;2;2;2) Hence we have even matchings of type (a1;:::;a7). 2.2.4 Nine parts of any size Notice that when p = 9 condition 4 becomes 7a9 ? 3n which is equivalent to 4a9 ? 3(a1 + ::: + a8). Condition 2 is a9 ? a1 + ::: + a7. With the use of Lemma 2.4 flnding an even matching of type (0;0;a3;:::;a9) simply requires the even matching (a3;:::;a9), which we constructed in the previous Section. Let us now consider even matchings of type (a1;a2;a3;a4;a5;a6;a7;a8;a9) where a1 ? a2 ? a3 ? a4 ? a5 ? a6 ? a7 ? a8 ? a9. Since p = 9 ? 1(mod 4), we can have all 17 parts of odd or all parts of even size. Similar to the case of flve or seven parts, to flnd an even matching of type (a1;a2;a3;a4;a5;a6;a7;a8;a9) we use the following algorithm. 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = a2 = a3 = a4 = a5 = 0, a6 = 2 or a1 = a2 = a3 = a4 = a5 = a6 = a7 = 1 or K = (0;0;0;0;2;2;2;2;2) or K = (0;0;0;0;2;2;2;2;6) look up the matching in list provided. Otherwise continue below. 2. For 0 ? i ? 5 repeat the following steps. 3. If 7a9 = 3n skip down to the Special Case 1 section. If 7a9 = 3n?2 skip down to the Special Case 2 section. If a7 = a8 and a9 = a1 +a2 +a3 +a4 +a5 +a6 +a7 skip down to Special Case 3 section. Otherwise continue below. 4. Subtract (0i;2;06?i;2;2). 5. If necessary, rearrange the terms to ensure that the parts are in a nondecreasing sequence. 6. Repeat steps 3-5 until you obtain (0;0;0;0;0;2; ; ; ) or (1;1;1;1;1;1;1; ; ). If at any point K = (0;0;0;0;2;2;2;2;2) or K = (0;0;0;0;2;2;2;2;6) look it up. 7. If 7a9 = 3n skip down to the Special Case 1 section. If 7a9 = 3n?2 skip down to the Special Case 2 section. If a7 = a8 and a9 = a1 +a2 +a3 +a4 +a5 +a6 +a7 skip down to Special Case 3 section. Otherwise continue below. 8. Subtract (06;2;2;2). 18 9. If necessary, rearrange the terms to ensure that the parts are in a nondecreasing sequence. 10. Repeat until you obtain (1;1;1;1;1;1;1; ; ). 11. The even matchings of type (0;0;0;0;0;2; ; ; ) and (1;1;1;1;1;1;1; ; ) are listed below. Let us consider the four necessary conditions during steps 2-5 of the algorithm. 1. p = 9 is not afiected. 2. If (a1;a2;a3;a4;a5;a6;a7;a8;a9) satisfles a9 ? a1+a2+a3+a4+a5+a6+a7, then (a1 ?2;a2;a3;a4;a5;a6;a7;a8 ?2;a9 ?2) satisfles a9 ?2 ? a1 ?2+a2 +a3 +a4 + a5 + a6 + a7. We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging a9 ? 2 is not the largest, but the second largest part, then a7 = a9. So we started with (a1;a2;a3;a4;a5;a6;a9;a9;a9) and now have (a1 ? 2;a2;a3;a4;a5;a6;a9 ? 2;a9 ? 2;a9). By Properties 2 and 4 (a1 ? 2;a2;a3;a4;a5;a6;a9 ? 2;a9 ? 2;a9) is in S2 as long as 4 ? a1 + ::: + a6 and 18 ? 2a9 ? 3(a1 + ::: + a6). Let us consider the cases when 4 > a1 + ::: + a6 or 18 ? 2a9 > 3(a1 + ::: + a6). We could have (0;0;0;0;0;0;a9;a9;a9) or (0;0;0;0;0;2;a9;a9;a9). Each one of those is discussed and shown to be in S2. Case 2: If after rearranging a9 ?2 is not the largest or second largest part, then a6 = a9. So we started with (a1;a2;a3;a4;a5;a9;a9;a9;a9) and now have (a1 ? 2;a2;a3;a4;a5;a9 ?2;a9 ?2;a9;a9). By Properties 2 and 4 (a1;a2;a3;a4;a5;a9 ? 2;a9?2;a9;a9) is in S2 as long as 6?a9 ? a1+:::+a5 and 18?5a9 ? 3(a1+:::+a5). 19 Let us consider the cases when 6?a9 > a1+:::+a5 or 18?5a9 > 3(a1+:::+a5). We could have (0;0;0;0;0;2;2;2;2), (0;0;0;0;0;4;4;4;4) or (0;0;0;0;2;2;2;2;2). Each one of those is in S2. Case 3: If after rearranging a9 ? 2 is the largest, but a8 ? 2 is not the sec- ond largest part, then a7 = a8. So we started with (a1;a2;a3;a4;a5;a6;a8;a8;a9) and now have (a1 ? 2;a2;a3;a4;a5;a6;a8 ? 2;a8;a9 ? 2). By Property 2, (a1 ? 2;a2;a3;a4;a5;a6;a8?2;a8;a9?2) is in S2 as long as a9 6= a1 +:::+a7. The case when a9 = a1 +:::+a7 and a7 = a8 is discussed below as Special Case 3. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;a2;a3;a4;a5;a6;a7;a8;a9) satisfles 4a9 < 3(a1 + ::: + a8) ? 2, then (a1 ? 2;a2;a3;a4;a5;a6;a7;a8 ? 2;a9 ? 2) satisfles 4(a9 ? 2) ? 3(a1 + ::: + a8 ? 4). If 7a9 = 3n we refer to Special Case 1. If 7a9 = 3n?2 we refer to Special Case 2. Problems arising from rearranging the terms are discussed under Property 2. Therefore, each time we repeat steps 2-5 we obtain an element of S2. Notice that the above holds for the remaining steps of the algorithm. So it is su?cient to give even matchings of type (0;0;0;0;0;2; ; ; ) and (1;1;1;1;1;1;1; ; ) and consider the special cases mentioned above. Let us consider the Special Case 1. We need to flnd even matchings for (a1;:::;a9) satisfying the four necessary conditions and 4a9 = 3(a1 + ::: + a8). Let us refer to these as matching type SP1 S2. Say we need K = (a1;a2;:::;a8; 3(a1+:::+a8)4 ) 2 SP1. We will build it by induction. 20 We consider parts of odd size flrst. We start by subtracting P = (16;3;3;9) to obtain K0 = (a1 ?1;:::;a6 ?1;a7 ?3;a8 ?3; 3(a1+:::+a8)4 ?9). Since 3(a1+:::+a8)4 ? a1 +:::+a7 in K we have 3(a1+:::+a8)4 ?9 ? a1 +:::+a7?9 in K0. Also, 4(3(a1+:::+a8)4 ?9) = 3(a1 + :::+a8?12). Therefore K0 is in S2. However, if rearranging is necessary and we obtain K00 = (a1?1;:::;a5?1;a7?3;a8?3;a6?1; 3(a1+:::+a8)4 ?9) instead of K0, we must have a6?1 = a8?3+2 or a6 = a8. Hence we started with (a1;:::;a5;a8;a8;a8; 3(a1+:::+a8)4 ). In this case instead of subtracting P = (16;3;3;9), we subtract Q = (15;5;5;5;15) to obtain K0 = (a1?1;:::;a5?1;a8?5;a8?5;a8?5; 3(a1+:::+a8)4 ?15). Notice that 4(3(a1+:::+a8)4 ? 15) = 3(a1+:::+a8?20) and 3(a1+:::+a8)4 ?15 ? a1+:::+a7?15 in K0 and so K0 2 S2. However, if rearranging is necessary and results in K00 = (a1 ?1;:::;a4 ?1;a8 ?5;a8 ? 5;a8?5;a5?1; 3(a1+:::+a8)4 ?15) we must have a5?1 = a8?5+2 or a5 = a8?2. So we started with K = (a1;:::;a4;a8?2;a8;a8;a8; 3(a1+:::+a8)4 ). Notice that by Property 2, we have 3(a1+:::+a4+4a8?2)4 ? a1+:::+a4+3a8?2, which implies 2 ? a1+:::+a4. However, we know that since ai ? 1 for all i, 4 ? a1 + ::: + a4. Therefore, 3(a1+:::+a4+4a8?2)4 ? a1 +:::+a4 +3a8 ?4. In this case we go back to subtracting P = (16;3;3;9) to obtain K0 = (a1 ? 1;:::;a4 ? 1;a8 ? 3;a8 ? 1;a8 ? 3;a8 ? 3; 3(a1+:::+a8)4 ? 9) which would be rearranged to K00 = (a1?1;:::;a4?1;a8?3;a8?3;a8?3;a8?1; 3(a1+:::+a8)4 ?9). Notice that 3(a1+:::+a8)4 ?9 ? a1+:::+a4+3a8?13 and 4(3(a1+:::+a8)4 ?9) = 3(a1+:::+a8?12) and K00 2 S2. Because a4 ? a8 it is not possible for the rearranging to result in (a1 ? 1;a2 ? 1;a3 ? 2;a8 ? 3;a8 ? 3;a8 ? 3;a8 ? 1;a4 ? 1; 3(a1+:::+a8)4 ? 9). One more rearranging issue needs to be addressed. Is it possible for a8 ?3 ? 3(a1+:::+a8)4 ?9 + 2 or a8 ? 5 ? 3(a1+:::+a8)4 ? 15 + 2? It is su?cient to show that a8 < 3(a1+:::+a8)4 ? 8. If a8 = 3(a1+:::+a8)4 ?8 we have K = (a1;:::;a7;3(a1 +:::+a7)?32;3(a1 +:::+a7)?24) 21 and by Property 2, this implies 3(a1+:::+a7)?24 ? a1+:::+a7. So a1+:::+a7 ? 12, and this is only possible if K = (16;3;3;9) which is given below. This shows that when we complete this step, we obtain an element of SP1. Forpartsofevensizewestartbysubtracting(04;24;6)toobtainK0 = (a1;:::;a4;a5? 2;:::;a8 ?2; 3(a1+:::+a8)4 ?6). As long as no rearranging is necessary K0 is in SP1. If rearranging is necessary, we started with K = (a1;a2;a3;a8;:::;a8; 3(a1+:::+a8)4 ) and now have K00 = (a1;a2;a3;a8 ?2;:::;a8 ?2;a8; 3(a1+:::+a8)4 ?6). This is in SP1 as long as ?16 ? a1 +a2 +a3 +a8 which is always true for elements of S2. This concludes the induction argument, since each time we perform the above we obtain a smaller element of SP1. This concludes Special Case 1. Let us consider the Special Case 2. We need to flnd even matchings for (a1;:::;a9) satisfying the four necessary conditions and 4a9 = 3(a1 + ::: + a8)?2. Let us refer to these as matching type SP2 S2. Say we need K = (a1;a2;:::;a8; 3(a1+:::+a8)?24 ) 2 SP2. We will build it by reducing the matching to an element of SP1 which is considered above. We start with parts of odd size. First, subtract P = (17;3;7) to obtain K0 = (a1?1;:::;a6?1;a7?1;a8?3; 3(a1+:::+a8)?24 ?7). Since 3(a1+:::+a8)?24 ? a1+:::+a7 in K we have 3(a1+:::+a8)?24 ?7 ? a1+:::+a7?7 in K0. Also, 4(3(a1+:::+a8)?24 ?7) = 3(a1+ :::+a8?10) which takes us back to Special Case 1. However, if rearranging is necessary and we obtain K00 = (a1 ?1;a2 ?2;:::;a5 ?1;a6 ?1;a8 ?3;a7 ?1; 3(a1+:::+a8)?24 ?7) instead of K0, we must have a7 ? 1 = a8 ? 3 + 1 or a7 = a8. Hence we started with (a1;:::;a5;a6;a8;a8; 3(a1+:::+a8)?24 ). In this case instead of subtracting P = (17;3;7), we subtract Q = (15;3;5;5;13) to obtain K0 = (a1 ? 1;:::;a5 ? 1;a6 ? 3;a8 ? 5;a8 ? 22 5; 3(a1+:::+a8)?24 ? 13). Notice that 4(3(a1+:::+a8)?24 ? 13) = 3(a1 + ::: + a8 ? 18) and 3(a1+:::+a8)?2 4 ?13 ? a1 + ::: + a7 ?13 in K 0 taking us to Special Case 1. However, if rearranging is necessary and results in K00 = (a1?1;:::;a4?1;a5?1;a8?5;a8?5;a6? 3; 3(a1+:::+a8)?24 ?13) we must have a6 ?3 = a8 ?5 + 2 or a6 = a8. So we started with K = (a1;:::;a4;a5;a8;a8;a8; 3(a1+:::+a8)?24 ). In this case we subtract M = (15;7;7;7;19) instead of P or Q. This gives K0 = (a1?1;:::;a5?1;a8?7;a8?7;a8?7; 3(a1+:::+a8)?24 ? 19) which is back in Special Case 1. If rearranging is necessary, we have a5 = a8 ? 4 and K00 = (a1 ?1;:::;a8 ?7;a8 ?7;a8 ?7;a8 ?5; 3(a1+:::+a8)?24 ?19) which came from K = (a1;:::;a4;a8 ? 4;a8;a8;a8; 3(a1+:::+a8)?24 ). Notice that by Property 2, we have 3(a1+:::+a4+4a8?4) 4 ? a1 + ::: + a4 + 3a8 ?4, which implies 2 ? a1 + ::: + a4. However, we know that since ai ? 1 for all i, 4 ? a1 + ::: + a4. Therefore, 3(a1+:::+a4+4a8?4)4 ? a1+:::+a4+3a8?6. In this case we go back to subtracting P = (17;3;7) to obtain K0 = (a1?1;:::;a4?1;a8?5;a8?1;a8?1;a8?3; 3(a1+:::+a8)?24 ?7) which would be rearranged to K00 = (a1 ?1;:::;a4 ?1;a8 ?5;a8 ?3;a8 ?1;a8 ?1; 3(a1+:::+a8)?24 ?7). Notice that 3(a1+:::+a8) 4 ?7 ? a1+:::+a4+3a8?11 and 4( 3(a1+:::+a8)?2 4 ?7) = 3(a1+:::+a8?10) and K00 2 S2 and under Special Case 1. Because a4 ? a8 it is not possible for the rearranging to result in (a1 ? 1;a2 ? 1;a3 ? 2;a8 ? 5;a8 ? 3;a8 ? 1;a8 ? 1;a4 ? 1; 3(a1+:::+a8)?24 ? 7). One more rearranging issue needs to be addressed. Is it possible for a8 ? 3 ? 3(a1+:::+a8)?2 4 ?7+2, a8 ?5 ? 3(a1+:::+a8)?2 4 ?13+2 or a8 ?7 ? 3(a1+:::+a8)?2 4 ?17+2? It is su?cient to show that a8 < 3(a1+:::+a8)?24 ? 8. If a8 = 3(a1+:::+a8)?24 ? 8 we have K = (a1;:::;a7;3(a1+:::+a7)?34;3(a1+:::+a7)?26) and by Property 2, this implies 3(a1 + ::: + a7) ? 26 ? a1 + ::: + a7. So a1 + ::: + a7 ? 13, and this is only possible if K = (17;3;7) which is given below or K = (14;33;5;13) = (17;3;7) + (04;24;6) or 23 K = (13;35;13) = (17;3;7)+(03;24;0;6). This shows that when we complete this step, we obtain an element of SP1. And we continue with the second step in Special Case 1. Forpartsofevensizewestartbysubtracting(05;23;4)toobtainK0 = (a1;:::;a5;a6? 2;a7 ?2;a8 ?2; 3(a1+:::+a8)?24 ?4). As long as no rearranging is necessary K0 is in SP1. If rearranging is necessary, we started with K = (a1;a2;a3;a4;a8;:::;a8; 3(a1+:::+a8)?24 ) and now have K00 = (a1;a2;a3;a4;a8 ?2;a8 ?2;a8 ?2;a8; 3(a1+:::+a8)?24 ?4). This K00 is in SP1 as long as ?12 ? a1 + ::: + a4 which is always true. This concludes Special Case 2. Now let us consider Special Case 3. If a7 = a8 and a9 = a1+:::+a7 we have types of the form (a1;a2;a3;a4;a5;a6;a9?(a1+ ::: + a6);a9 ?(a1 + ::: + a6);a9). We will construct an even matching of such type as follows: a1=2copiesof(2;0;0;0;0;0;2;2;4), a2=2copiesof(0;2;0;0;0;0;2;2;4), ..., a6=2 copies of (0;0;0;0;0;2;2;2;4) and a9?2(a1 +:::+a6)=2 copies of (0;0;0;0;0;0;2;2;2). Notice that by Property 4 a9 ? 2(a1 +:::+a6). This concludes Special Case 3. Thefollowingareevenmatchingsoftype(0;0;0;0;0;2; ; ; )and(1;1;1;1;1;1;1; ; ). (0;0;0;0;0;0;2;2;2): from Lemma 2.4 By Property 2, an even matching of type (0;0;0;0;0;0;a7;a8;a9) exists if a9 ? a7. Hence we must have (0;0;0;0;0;0;a9;a9;a9). (0;0;0;0;0;0;a9;a9;a9) from a9=2 copies of (0;0;0;0;0;0;2;2;2) (0;0;0;0;0;2;2;2;2): from Lemma 2.4 (0;0;0;0;0;2;2;2;4): from Lemma 2.4 (0;0;0;0;2;2;2;2;2): from Lemma 2.4 By Property 2, an even matching of type (0;0;0;0;0;2;a7;a8;a9) exists if a7 ? a9 ?2. 24 (0;0;0;0;0;2;a9;a9;a9) from (0;0;0;0;0;2;2;2;2) and (a9 ?2)=2 copies of (0;0;0;0;0;0;2;2;2) (0;0;0;0;0;2;a9 ?2;a9;a9) from (0;0;0;0;0;2;0;2;2) and (a9 ?2)=2 copies of (0;0;0;0;0;0;2;2;2) Since a9 ? 2, a9 ?2 ? 0. (0;0;0;0;0;2;a9 ?2;a9 ?2;a9) from (0;0;0;0;0;2;2;2;4) and (a9 ?4)=2 copies of (0;0;0;0;0;0;2;2;2) Since a9 ?2 ? 2, a9 ?4 ? 0. (0;0;0;0;2;2;2;2;6): M1: ff5;9g;f50;60g;f6;90g;f7;9000g;f70;900g;f8;94g;f80;95gg M2: ff5;94g;f50;95g;f6;9000g;f60;900g;f7;90g;f70;80g;f8;9gg M3: ff5;9g;f50;9000g;f6;90g;f60;900g;f7;8g;f70;95g;f80;94gg M4: ff5;6g;f50;9000g;f60;900g;f7;90g;f70;95g;f8;9g;f80;94gg M5: ff6;94g;f60;95g;f7;900g;f70;9000g;f8;9g;f80;90gg M6: ff5;9g;f50;90g;f7;9000g;f70;900g;f8;94g;f80;95gg M7: ff5;94g;f50;95g;f6;9000g;f60;900g;f8;9g;f80;90gg M8: ff5;9g;f50;90g;f6;94g;f60;95g;f7;900g;f70;9000gg M9: ff5;6g;f50;60g;f7;8g;f70;80gg (0;0;0;0;0;4;4;4;4)= 2 copies of (0;0;0;0;0;2;2;2;2) (1;1;1;1;1;1;1;1;1): given in Section 2.2.1 (1;1;1;1;1;1;1;1;3): M1: ff2;900g;f3;90g;f4;5g;f6;8g;f7;9gg M2: ff1;900g;f3;7g;f4;5g;f6;90g;f8;9gg 25 M3: ff1;900g;f2;8g;f4;6g;f5;9g;f7;90gg M4: ff1;6g;f2;900g;f3;90g;f5;9g;f7;8gg M5: ff1;9g;f2;90g;f3;900g;f4;6g;f7;8gg M6: ff1;2g;f3;4g;f5;900g;f7;90g;f8;9gg M7: ff1;9g;f2;90g;f3;900g;f4;5g;f6;8gg M8: ff1;2g;f3;4g;f5;900g;f6;90g;f7;9gg M9: ff1;6g;f2;8g;f3;7g;f4;5gg (1;1;1;1;1;1;1;1;5): M1: ff2;9000g;f3;4g;f5;90g;f6;94g;f7;900g;f8;9gg M2: ff1;94g;f3;90g;f4;9000g;f5;900g;f6;8g;f7;9gg M3: ff1;2g;f4;9000g;f5;90g;f6;94g;f7;9g;f8;900gg M4: ff1;94g;f2;9000g;f3;90g;f5;6g;f7;900g;f8;9gg M5: ff1;2g;f3;94g;f4;9000g;f6;90g;f7;9g;f8;900gg M6: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f7;8gg M7: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f6;8gg M8: ff1;2g;f3;94g;f4;9000g;f5;900g;f6;90g;f7;9gg M9: ff1;2g;f3;4g;f5;6g;f7;8gg (1;1;1;1;1;1;1;3;3): M1: ff2;80g;f3;900g;f4;90g;f5;8g;f6;800g;f7;9gg M2: ff1;800g;f3;8g;f4;80g;f5;900g;f6;90g;f7;9gg M3: ff1;800g;f2;80g;f4;900g;f5;8g;f6;90g;f7;9gg M4: ff1;9g;f2;90g;f3;900g;f5;80g;f6;800g;f7;8gg M5: ff1;800g;f2;80g;f3;8g;f4;900g;f6;90g;f7;9gg 26 M6: ff1;9g;f2;90g;f3;900g;f4;800g;f5;80g;f7;8gg M7: ff1;9g;f2;80g;f3;900g;f4;800g;f5;8g;f6;90gg M8: ff1;9g;f2;3g;f4;90g;f5;900g;f6;7gg M9: ff1;800g;f2;3g;f4;80g;f5;8g;f6;7gg (1;1;1;1;1;1;1;3;5): M1: ff2;94g;f3;90g;f4;800g;f5;900g;f6;8g;f7;9g;f80;9000gg M2: ff1;800g;f3;94g;f4;9000g;f5;90g;f6;900g;f7;80g;f8;9gg M3: ff1;9g;f2;8g;f4;80g;f5;90g;f6;900g;f7;9000g;f800;94gg M4: ff1;94g;f2;9000g;f3;800g;f5;80g;f6;900g;f7;90g;f8;9gg M5: ff1;9g;f2;8g;f3;90g;f4;80g;f6;900g;f7;9000g;f800;94gg M6: ff1;94g;f2;9000g;f3;800g;f4;900g;f5;80g;f7;90g;f8;9gg M7: ff1;800g;f2;94g;f3;5g;f4;900g;f6;90g;f8;9g;f80;9000gg M8: ff1;2g;f3;94g;f4;9000g;f5;900g;f6;90g;f7;9gg M9: ff1;2g;f3;5g;f4;800g;f6;8g;f7;80gg (1;1;1;1;1;1;1;3;7): M1: ff2;95g;f3;96g;f4;8g;f5;900g;f6;90g;f7;9g;f80;9000g;f800;94gg M2: ff1;96g;f3;7g;f4;95g;f5;94g;f6;9000g;f8;9g;f80;90g;f800;900gg M3: ff1;96g;f2;95g;f4;9000g;f5;6g;f7;9g;f8;90g;f80;900g;f800;94gg M4: ff1;96g;f2;95g;f3;94g;f5;900g;f6;90g;f7;80g;f8;9g;f800;9000gg M5: ff1;96g;f2;95g;f3;7g;f4;94g;f6;90g;f8;9g;f80;900g;f800;9000gg M6: ff1;96g;f2;95g;f3;800g;f4;94g;f5;900g;f7;9g;f8;90g;f80;9000gg M7: ff1;2g;f3;96g;f4;95g;f5;94g;f6;9000g;f8;9g;f80;90g;f800;900gg M8: ff1;96g;f2;95g;f3;94g;f4;9000g;f5;900g;f6;90g;f7;9gg 27 M9: ff1;2g;f3;800g;f4;8g;f5;6g;f7;80gg (1;1;1;1;1;1;1;5;5): M1: ff2;9g;f3;80g;f4;8000g;f5;900g;f6;7g;f8;90g;f800;9000g;f84;94gg M2: ff1;9g;f3;800g;f4;8000g;f5;900g;f6;9000g;f7;80g;f8;90g;f84;94gg M3: ff1;8g;f2;9g;f4;9000g;f5;800g;f6;90g;f7;80g;f8000;900g;f84;94gg M4: ff1;2g;f3;80g;f5;800g;f6;9000g;f7;9g;f8;90g;f8000;900g;f84;94gg M5: ff1;2g;f3;4g;f6;7g;f8;9g;f80;90g;f800;900g;f8000;9000g;f84;94gg M6: ff1;9g;f2;80g;f3;94g;f4;84g;f5;900g;f7;8000g;f8;90g;f800;9000gg M7: ff1;2g;f3;4g;f5;6g;f8;9g;f80;90g;f800;900g;f8000;9000g;f84;94gg M8: ff1;2g;f3;94g;f4;9000g;f5;900g;f6;90g;f7;9gg M9: ff1;8g;f2;80g;f3;800g;f4;84g;f5;6g;f7;8000gg (1;1;1;1;1;1;1;5;7): M1: ff2;9g;f3;80g;f4;8000g;f5;900g;f6;9000g;f7;96g;f8;90g;f800;95g;f84;94gg M2: ff1;96g;f3;95g;f4;8000g;f5;900g;f6;9000g;f7;80g;f8;90g;f800;9g;f84;94gg M3: ff1;8g;f2;9g;f4;9000g;f5;96g;f6;90g;f7;80g;f800;95g;f8000;900g;f84;94gg M4: ff1;9000g;f2;6g;f3;95g;f5;900g;f7;8000g;f8;90g;f80;96g;f800;9g;f84;94gg M5: ff1;2g;f3;4g;f6;95g;f7;96g;f8;9g;f80;90g;f800;900g;f8000;9000g;f84;94gg M6: ff1;9000g;f2;95g;f3;94g;f4;84g;f5;800g;f7;9g;f8;90g;f80;96g;f8000;900gg M7: ff1;2g;f3;4g;f5;96g;f6;95g;f8;9g;f80;90g;f800;900g;f8000;9000g;f84;94gg M8: ff1;96g;f2;95g;f3;94g;f4;9000g;f5;900g;f6;90g;f7;9gg M9: ff1;8g;f2;6g;f3;80g;f4;84g;f5;800g;f7;8000gg (1;1;1;1;1;1;1;7;7): M1: ff2;96g;f3;4g;f5;6g;f7;86g;f8;9g;f80;90g;f800;900g;f8000;9000g;f84;94g;f85;95gg 28 M2: ff1;9g;f3;84g;f4;9000g;f5;800g;f6;95g;f7;8g;f80;90g;f8000;900g;f85;94g;f86;96gg M3: ff1;2g;f4;96g;f5;6g;f7;86g;f8;9g;f80;90g;f800;9000g;f8000;900g;f84;94g;f85;95gg M4: ff1;9g;f2;96g;f3;86g;f5;6g;f7;8g;f80;90g;f800;9000g;f8000;900g;f84;95g;f85;94gg M5: ff1;86g;f2;90g;f3;900g;f4;8000g;f6;80g;f7;96g;f8;9g;f800;9000g;f84;94g;f85;95gg M6: ff1;9g;f2;85g;f3;86g;f4;96g;f5;94g;f7;8g;f80;90g;f800;9000g;f8000;900g;f84;95gg M7: ff1;2g;f3;4g;f5;6g;f8;9g;f80;90g;f800;900g;f8000;9000g;f84;94g;f85;95g;f86;96gg M8: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f6;95g;f7;96gg M9: ff1;86g;f2;85g;f3;84g;f4;8000g;f5;800g;f6;80g;f7;8gg (1;1;1;1;1;1;3;3;9): M1: ff2;98g;f3;4g;f5;96g;f6;95g;f7;94g;f70;900g;f700;97g;f8;9g;f80;90g;f800;9000gg M2: ff1;90g;f3;9000g;f4;900g;f5;6g;f7;95g;f70;94g;f700;97g;f8;9g;f80;96g;f800;98gg M3: ff1;90g;f2;98g;f4;900g;f5;96g;f6;95g;f7;94g;f70;80g;f700;97g;f8;9g;f800;9000gg M4: ff1;98g;f2;97g;f3;96g;f5;94g;f6;9000g;f7;95g;f70;900g;f700;800g;f8;9g;f80;90gg M5: ff1;9g;f2;90g;f3;900g;f4;9000g;f6;95g;f7;8g;f70;94g;f700;97g;f80;96g;f800;98gg M6: ff1;2g;f3;9000g;f4;95g;f5;94g;f7;9g;f70;90g;f700;900g;f8;98g;f80;97g;f800;96gg M7: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f6;95g;f8;98g;f80;97g;f800;96gg M8: ff1;98g;f2;97g;f3;96g;f4;95g;f5;94g;f6;9000g;f7;9g;f70;90g;f700;900gg M9: ff1;2g;f3;4g;f5;6g;f7;8g;f70;80g;f700;800gg (1;1;1;1;1;3;5;5;13): M1: ff2;912g;f3;600g;f4;60g;f5;94g;f6;9g;f7;96g;f70;900g;f700;9000g;f7000;910g;f74;911g; f8;90g;f80;97g;f800;98g;f8000;99g;f84;95gg M2: ff1;98g;f3;97g;f4;96g;f5;6g;f60;80g;f600;94g;f7;99g;f70;900g;f700;910g;f7000;911g; f74;912g;f8;9g;f800;90g;f8000;9000g;f84;95gg 29 M3: ff1;98g;f2;912g;f4;99g;f5;95g;f6;9g;f60;80g;f600;94g;f7;96g;f70;900g;f700;800g; f7000;910g;f74;911g;f8;90g;f8000;9000g;f84;97gg M4: ff1;912g;f2;911g;f3;910g;f5;98g;f6;94g;f60;95g;f600;96g;f7;99g;f70;900g;f700;9000g; f7000;8000g;f74;84g;f8;9g;f80;97g;f800;90gg M5: ff1;9g;f2;90g;f3;900g;f4;9000g;f6;94g;f60;95g;f600;96g;f7;8g;f70;80g;f700;910g; f7000;911g;f74;912g;f800;98g;f8000;99g;f84;97gg M6: ff1;2g;f3;97g;f4;96g;f5;95g;f7;9g;f70;90g;f700;900g;f7000;9000g;f74;94g;f8;98g; f80;99g;f800;910g;f8000;911g;f84;912gg M7: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f6;95g;f60;96g;f600;97g;f8;98g;f80;99g; f800;910g;f8000;911g;f84;912gg M8: ff1;912g;f2;911g;f3;910g;f4;99g;f5;98g;f6;95g;f60;96g;f600;97g;f7;9g;f70;90g; f700;900g;f7000;9000g;f74;94gg M9: ff1;2g;f3;600g;f4;60g;f5;6g;f7;8g;f70;80g;f700;800g;f7000;8000g;f74;84gg (1;1;1;1;1;5;5;5;15): M1: ff2;6000g;f3;97g;f4;96g;f5;94g;f6;914g;f60;90g;f600;900g;f64;912g;f7;8g;f70;910g; f700;913g;f7000;95g;f74;911g;f80;9g;f800;98g;f8000;9000g;f84;99gg M2: ff1;99g;f3;600g;f4;60g;f5;95g;f6;9g;f6000;96g;f64;97g;f7;900g;f70;9000g;f700;912g; f7000;913g;f74;914g;f8;90g;f80;911g;f800;98g;f8000;910g;f84;94gg M3: ff1;64g;f2;98g;f4;911g;f5;6g;f60;97g;f600;96g;f6000;95g;f7;900g;f70;9000g;f700;912g; f7000;913g;f74;914g;f8;90g;f80;9g;f800;94g;f8000;910g;f84;99gg M4: ff1;914g;f2;913g;f3;912g;f5;910g;f6;9g;f60;90g;f600;900g;f6000;96g;f64;97g;f7;99g; f70;80g;f700;800g;f7000;95g;f74;911g;f8;98g;f8000;9000g;f84;94gg M5: ff1;9g;f2;90g;f3;900g;f4;9000g;f6;914g;f60;97g;f600;96g;f6000;95g;f64;912g;f7;99g; 30 f70;910g;f700;913g;f7000;8000g;f74;84g;f8;98g;f80;911g;f800;94gg M6: ff1;99g;f2;98g;f3;97g;f4;96g;f5;95g;f7;9g;f70;90g;f700;900g;f7000;9000g;f74;94g; f8;910g;f80;911g;f800;912g;f8000;913g;f84;914gg M7: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f6;95g;f60;96g;f600;97g;f6000;98g;f64;99g; f8;910g;f80;911g;f800;912g;f8000;913g;f84;914gg M8: ff1;914g;f2;913g;f3;912g;f4;911g;f5;910g;f6;95g;f60;96g;f600;97g;f6000;98g; f64;99g;f7;9g;f70;90g;f700;900g;f7000;9000g;f74;94gg M9: ff1;64g;f2;6000g;f3;600g;f4;60g;f5;6g;f7;8g;f70;80g;f700;800g;f7000;8000g;f74;84gg (1;1;1;1;1;7;7;7;19) : M1: ff2;66g;f3;7g;f4;98g;f5;97g;f6;90g;f60;915g;f600;900g;f6000;84g;f64;910g;f65;911g; f70;9g;f700;914g;f7000;917g;f74;94g;f75;95g;f76;96g;f8;912g;f80;913g;f800;99g;f8000;916g; f85;9000g;f86;918gg M2: ff1;86g;f3;99g;f4;700g;f5;8000g;f6;97g;f60;915g;f600;900g;f6000;916g;f64;910g;f65;911g; f66;914g;f7;912g;f70;9g;f7000;98g;f74;94g;f75;95g;f76;96g;f8;90g;f80;913g;f800;918g; f84;917g;f85;9000gg M3: ff1;911g;f2;910g;f4;915g;f5;94g;f6;90g;f60;98g;f600;74g;f6000;916g;f64;7000g;f65;75g; f66;914g;f7;9g;f70;97g;f700;900g;f76;96g;f8;912g;f80;913g;f800;99g;f8000;9000g;f84;917g; f85;95g;f86;918gg M4: ff1;918g;f2;917g;f3;916g;f5;914g;f6;80g;f60;800g;f600;99g;f6000;910g;f64;911g; f65;912g;f66;913g;f7;9g;f70;97g;f700;900g;f7000;98g;f74;94g;f75;84g;f76;96g;f8;90g; f8000;9000g;f85;95g;f86;915gg M5: ff1;9g;f2;90g;f3;900g;f4;9000g;f6;95g;f60;96g;f600;97g;f6000;98g;f64;99g;f65;910g; f66;911g;f7;912g;f70;8g;f700;914g;f7000;917g;f74;94g;f75;84g;f76;85g;f80;913g;f800;918g; 31 f8000;916g;f86;915gg M6: ff1;911g;f2;910g;f3;99g;f4;98g;f5;97g;f7;9g;f70;90g;f700;900g;f7000;9000g;f74;94g; f75;95g;f76;96g;f8;912g;f80;913g;f800;914g;f8000;915g;f84;916g;f85;917g;f86;918gg M7: ff1;9g;f2;90g;f3;900g;f4;9000g;f5;94g;f6;95g;f60;96g;f600;97g;f6000;98g;f64;99g; f65;910g;f66;911g;f8;912g;f80;913g;f800;914g;f8000;915g;f84;916g;f85;917g;f86;918gg M8: ff1;918g;f2;917g;f3;916g;f4;915g;f5;914g;f6;97g;f60;98g;f600;99g;f6000;910g; f64;911g;f65;912g;f66;913g;f7;9g;f70;90g;f700;900g;f7000;9000g;f74;94g;f75;95g;f76;96gg M9: ff1;86g;f2;66g;f3;7g;f4;700g;f5;8000g;f6;80g;f60;800g;f600;74g;f6000;84g;f64;7000g; f65;75g;f700;8g;f76;85gg Hence we have even matchings of type (a1;:::;a9). 2.2.5 p ? 1 (mod 4) parts of any size In this Section we will give a general construction of even matchings of type (a1;:::;a4h+1) for any positive integer h ? 3. Since p ? 1 (mod 4) we can have all parts of even size or all parts of odd size. We will need \building blocks" similar to the ones used before. (04h?2;2;2;2): from Lemma 2.4 (04h?3;2;2;2;2): from Lemma 2.4 Notice that when p = 4h+1 condition 4 becomes 2hap ? (2h?1)(a1 +:::+ap?1) and condition 2 remains ap ? a1 + ::: + ap?2. We can construct an even matching of type (0;0;a3;:::;ap) inductively. We start with the even matching (a3;:::;ap) (as long as it exists) and apply Lemma 2.4. To flnd an even matching of type (a1;:::;a4h+1) we use the following algorithm. 32 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = ::: = ap?4 = 0, ap?3 = 2 or a1 = ::: = ap?2 = 1 or K = (04h?4;2;2;2;2;2) or K = (04h?4;2;2;2;2;6) look up the matching in list provided. Otherwise continue below. 2. If 2hap = (2h?1)(a1+:::+ap?1)?2c for 0 ? c ? 2h?3 skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1+:::+ap?2 skip down to Special Case (2h?1) section. Otherwise continue below. 3. Subtract (2;04h?2;2;2) to obtain (a1 ?2;a2;:::;ap?1 ?2;ap ?2). 4. If necessary, rearrange the terms to ensure a nondecreasing sequence. 5. Repeat steps 2-4 until you obtain (0; 4h) or (1; 4h). 6. If 2hap = (2h?1)(a1+:::+ap?1)?2c for 0 ? c ? 2h?3 skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1+:::+ap?2 skip down to Special Case (2h?1) section. Otherwise continue below. 7. For 4h?3 ? j ? 1 repeat the following steps. 8. Subtract (04h?2?j;2;0j;2;2). 9. If necessary, rearrange the terms to ensure the sequence is nondecreasing. 10. Repeat until you obtain (04h?1?j; j+2) or (14h?1?j; j+2). 11. Stop when you obtain (04h?3;2; ; ; ) or (14h?1; ; ). 33 12. The even matchings of type (04h?3;2; ; ; ) and (14h?1; ; ) will need to be given. Let us consider the four necessary conditions during steps 2-5 of the algorithm. 1. p = 4h+1 is not afiected. 2. If (a1;:::;ap) satisfles ap ? a1 + :::+ ap?2, then (a1 ?2;a2;:::;ap?1 ?2;ap ?2) satisfles ap ?2 ? a1 ?2+a2 +:::+ap?2. We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging ap ?2 is not the largest, but the second largest part, then ap?2 = ap. So we started with (a1;:::;ap?3;ap;ap;ap) and now have (a1 ?2;a2;:::;ap?3;ap ?2;ap ?2;ap). By Properties 2 and 4 this is in S2 as long as 4 ? a1 + ::: + ap?3 and 12h ? 6 ? (2h ? 2)ap ? (2h ? 1)(a1 + ::: + ap?3), which is equivalent to a1+:::+ap?3 ? 6? 2h?22h?1ap. Let us consider the cases when 4 > a1+:::+ap?3 or a1+:::+ap?3 < 6?2h?22h?1ap. We could have (04h?2;ap;ap;ap), (04h?3;2;ap;ap;ap) or (04h?4;2;2;2;2;2). Each one of those is in S2. Case 2: If after rearranging ap ? 2 is not the largest or second largest part, then ap?3 = ap. So we started with (a1;:::;ap?4;ap;ap;ap;ap) and now have (a1 ?2;a2;:::;ap?4;ap ?2;ap ?2;ap;ap). By Properties 2 and 4 this is in S2 as long as 6?ap ? a1 +:::+ap?4 and 6? 4h?32h?1ap ? a1 +:::+ap?4. Let us consider the cases when 6?ap > a1 +:::+ap?4 or 6? 4h?32h?1ap > a1 +:::+ap?4. We could have (04h?3;2;2;2;2), (04h?3;4;4;4;4) or (04h?4;2;2;2;2;2). Each one of those is in S2. Case 3: If after rearranging ap ?2 is the largest, but ap?1 ?2 is not the second largest part, then ap?2 = ap?1. So we started with (a1;:::;ap?3;ap?1;ap?1;ap) and now have (a1 ?2;a2;:::;ap?3;ap?1 ?2;ap?1;ap ?2). By Property 2, this is 34 in S2 as long as ap 6= a1 + ::: + ap?2. The case when ap = a1 + ::: + ap?2 and ap?2 = ap?1 is discussed below as Special Case (2h?1). 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;:::;ap) satisfles 2hap ? (2h ? 1)(a1 + ::: + ap?1) ? 4(h ? 1), then (a1 ? 2;a2;:::;ap?2;ap?1?2;ap?2) satisfles 2h(ap?2) ? (2h?1)(a1 +:::+ap?1?4). Each Special Case (c+1) section covers the instances when 2hap = (2h?1)(a1 + ::: + ap?1)?2c for 0 ? c ? 2h?3. Problems arising from rearranging the terms are discussed under condition 2. Therefore, each time we repeat steps 2-5 we obtain an element of S2. Notice that the above holds for the remaining steps of the algorithm. So it is su?cient to give even matchings of type (04h?3;2; ; ; ) and (14h?1; ; ) and consider the special cases mentioned above. Let us consider the Special Case (c+1) for 0 ? c ? 2h?3. We need to flnd even matchings for (a1;:::;ap) satisfying the four necessary condi- tions and 2hap = (2h?1)(a1 +:::+ap?1)?2c. Let us refer to these as matching type SP(c + 1) S2. Say we need K = (a1;a2;:::;ap?1; (2h?1)(a1+:::+ap?1)?2c2h ) 2 SP(c + 1). We will build it by induction. We consider parts of odd size flrst. If h ? c ? 0, we start by subtracting P1 = (13h+c;3h?c;6h? 3 ? 2c) to obtain K0 = (a1 ? 1;:::;a3h+c ? 1;a3h+c+1 ? 3;:::;a4h ? 3; (2h?1)(a1+:::+ap?1)?2c2h ? (6h ? 3 ? 2c)). Since necessary conditions 2 and 4 were sat- isfled in K, they are still satisfled in K0. Also, K0 2 SP1. However, if rearranging is necessary and we obtain K00 = (a1 ?1;:::;a3h+c+1 ?3;a3h+c+2 ?3;:::;a4h?3;a3h+c? 35 1; (2h?1)(a1+:::+ap?1)?2c2h ?(6h?3?2c)) instead of K0, we must have a3h+c?1 = a4h?3+2 or a3h+c = a4h. Hence we started with K = (a1;:::;a3h+c?1;a4h;:::;a4h; (2h?1)(a1+:::+ap?1)?2c2h ). In this case instead of sub- tracting P1 = (13h+c;3h?c;6h?3?2c), we subtract P2 = (1h+c;33h?c;10h?5?2c) to ob- tainK0 = (a1?1;:::;ah+c?1;ah+c+1?3;:::;a4h?3; (2h?1)(a1+:::+ap?1)?2c2h ?(10h?5?2c)). Notice that as long as no rearranging is necessary, K0 2 SP1. We will also subtract P2 if h ? c < 0, which means we start with ap > 6h ? 3 ? 2c. However, if rearranging is necessary and results in K00 = (a1 ? 1;:::;ah+c?1 ? 1;ah+c+1 ? 3;:::;a4h ? 3;ah+c ? 1; (2h?1)(a1+:::+ap?1)?2c2h ?(10h?5?2c)) we must have ah+c = a4h. So we started with K = (a1;:::;ah+c?1;a4h;:::;a4h; (2h?1)(a1+:::+ap?1)?2c2h ). In this case we subtract P3 = (1h+c;32h?c;7h;14h?7?2c) instead of P1 or P2. We then get K0 = (a1?1;:::;ah+c?1? 1;a4h?1;a4h?3;:::;a4h?3;a4h?7;:::;a4h?7; (2h?1)(a1+:::+ap?1)?2c2h ?(14h?7?2c)) which is rearranged to K00 = (a1?1;:::;ah+c?1?1;a4h?3;:::;a4h?3;a4h?7;:::;a4h? 7;a4h ?1; (2h?1)(a1+:::+ap?1)?2c2h ?(14h?7?2c)). Satisfying the conditions 2 and 4, this K00 is always in SP1. This shows that when we complete this step, we obtain an element of SP1. For parts of even size we start by subtracting (02h+c;22h?c;4h ? 2 ? 2c) to ob- tain K0 = (a1;:::;a2h+c;a2h+c+1 ?2;:::;a4h ?2; (2h?1)(a1+:::+ap?1)?2c2h ?(4h?2?2c)). As long as no rearranging is necessary K0 is in SP1. If rearranging is necessary, we started with K = (a1;:::;a2h+c?1;a4h;:::;a4h; (2h?1)(a1+:::+ap?1)?2c2h ) and now have K00 = (a1;:::;a2h+c?1;a4h ? 2;:::;a4h ? 2;a4h; (2h?1)(a1+:::+ap?1)?2c2h ? (4h ? 2 ? 2c)). This is in SP1 as long as (c ? 1)a4h ? 8h2 + 8h + 4ch ? a1 + ::: + a2h+c?1 which is equivalent to a4h?2 ? a4h+12h?1 when c = 2h?3 (worst case scenario). By Property 2, this 36 inequality is always true for elements of S2. Notice that no matter what SP(c + 1) we start with, after the flrst subtraction, we will continue the induction process with SP1 or c = 0. By induction, this concludes Special Case (c+1). We take any element of SP(c+1) and subtract to get a smaller element of SP1. Now let us consider Special Case (2h?1). If ap?2 = ap?1 and ap = a1 +:::+ap?2 we have types of the form (a1;a2;:::;ap?3;ap? (a1 + ::: + ap?3);ap ? (a1 + ::: + ap?3);ap). We will construct an even matching of such type as follows: aj=2 copies of (0j?1;2;04h?2?j;2;2;4) for each 1 ? j ? 4h ? 2, and ap ?2(a1 + ::: + ap?3)=2 copies of (04h?2;2;2;2). Notice that by Property 4 ap ? 2(a1 +:::+ap?3). This concludes Special Case (2h?1). The following are even matchings of type (04h?3;2; ; ; ) and (14h?1; ; ) and other matchings used in the above construction. (04h?2;2;2;2): from Lemma 2.4 By Property 2, an even matching of type (04h?2;ap?2;ap?1;ap) exists if ap ? ap?2. Hence we must have (04h?2;ap;ap;ap). (04h?2;ap;ap;ap) from ap=2 copies of (04h?2;2;2;2) (04h?3;2;2;2;2): from Lemma 2.4 (04h?3;2;2;2;4): from Lemma 2.4 By Property 2, an even matching of type (04h?3;2;ap?2;ap?1;ap) exists if ap?2 ? ap?2. (04h?3;2;ap;ap;ap) from (04h?3;2;2;2;2) and (ap ?2)=2 copies of (04h?2;2;2;2) (04h?3;2;ap ?2;ap;ap) from (04h?3;2;0;2;2) and (ap ?2)=2 copies of (04h?2;2;2;2) Since ap ? 2, ap ?2 ? 0. 37 (04h?3;2;ap ?2;ap ?2;ap) from (04h?3;2;2;2;4) and (ap ?4)=2 copies of (04h?2;2;2;2) Since ap ?2 ? 2, ap ?4 ? 0. (04h?4;2;2;2;2;2): from Lemma 2.4 (04h?4;2;2;2;2;6): from Lemma 2.4 (02h;22h;4h?2): Needed; not yet found. The remaining (02h+c;22h?c;4h?2?2c) for 0 < c ? 2h?3 are obtained from Lemma 2.4 (14h+1): given in Section 2.2.1 For h ? c, (13h+c;3h?c;6h?3?2c): Needed; not yet found. (1h+c;33h?c;10h?5?2c): Needed; not yet found. (1h+c;32h?c;7h;14h?7?2c): Needed; not yet found. In the following families of matchings we use i;j odd. For 3 ? i ? 4h?3, (14h;i): Needed; not yet found. For 3 ? i ? 4h?1 and 3 ? j ? i, (14h?1;j;i): Needed; not yet found. Hence we have even matchings of type (a1;:::;a4h+1). 2.2.6 p ? 3 (mod 4) parts of any size In this Section we will give a general construction of even matchings of type (a1;:::;a4h+3) for any positive integer h ? 2. Since p ? 3 (mod 4) we can only have all parts of even size. We will use \building blocks" similar to the ones above. (04h;2;2;2): from Lemma 2.4 (04h?1;2;2;2;2): from Lemma 2.4 38 Notice that when p = 4h+3 condition 4 becomes (2h+1)ap ? 2h(a1 +:::+ap?1) and condition 2 remains ap ? a1+:::+ap?2. We can still construct an even matching of type (0;0;a3;:::;ap) inductively. We start with the even matching (a3;:::;ap) (as long as it exists) and apply Lemma 2.4. To flnd an even matching of type (a1;:::;a4h+3) we use the following algorithm. 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = ::: = ap?4 = 0, ap?3 = 2 or K = (04h?2;2;2;2;2;2) or K = (04h?2;2;2;2;2;6) look up the matchingin list provided. Otherwise continuebelow. 2. If (2h + 1)ap = 2h(a1 + ::: + ap?1) ? 2c, for 0 ? c ? 2h ? 2, skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1 + ::: + ap?2 skip down to Special Case (2h) section. Otherwise continue below. 3. Subtract (2;04h;2;2) to obtain (a1 ?2;a2;:::;ap?1 ?2;ap ?2). 4. If necessary, rearrange the terms to ensure a nondecreasing sequence. 5. Repeat steps 2-4 until you obtain (0; 4h+2). 6. If (2h+1)ap = 2h(a1+:::+ap?1)?2c for 0 ? c ? 2h?2 skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1 + ::: + ap?2 skip down to Special Case (2h) section. Otherwise continue below. 7. For 4h?1 ? j ? 1 repeat the following steps. 8. Subtract (04h?j;2;0j;2;2). 39 9. If necessary, rearrange the terms to ensure the sequence is nondecreasing. 10. Repeat until you obtain (04h+1?j; j+2). 11. Stop when you obtain (04h?1;2; ; ; ). 12. The even matchings of type (04h?1;2; ; ; ) will need to be given. Let us consider the four necessary conditions during steps 2-5 of the algorithm. 1. p = 4h+3 is not afiected. 2. If (a1;:::;ap) satisfles ap ? a1 + :::+ ap?2, then (a1 ?2;a2;:::;ap?1 ?2;ap ?2) satisfles ap ?2 ? a1 ?2+a2 +:::+ap?2. We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging ap ?2 is not the largest, but the second largest part, then ap?2 = ap. So we started with (a1;:::;ap?3;ap;ap;ap) and now have (a1 ?2;a2;:::;ap?3;ap ?2;ap ?2;ap). By Properties 2 and 4 this is in S2 as long as 4 ? a1 + ::: + ap?3 and a1 + ::: + ap?3 ? 6 ? 2h?12h ap. Let us consider the cases when 4 > a1 + ::: + ap?3 or a1 + ::: + ap?3 < 6? 2h?12h ap. We could have (04h;ap;ap;ap), (04h?1;2;ap;ap;ap) or (04h?2;2;2;2;2;2). Each one of those is in S2. Case 2: If after rearranging ap ? 2 is not the largest or second largest part, then ap?3 = ap. So we started with (a1;:::;ap?4;ap;ap;ap;ap) and now have (a1 ?2;a2;:::;ap?4;ap ?2;ap ?2;ap;ap). By Properties 2 and 4 this is in S2 as long as 6?ap ? a1 +:::+ap?4 and 6? 4h?12h ap ? a1 +:::+ap?4. Let us consider the cases when 6?ap > a1 +:::+ap?4 or 6? 4h?12h ap > a1 +:::+ap?4. We could have (04h?1;2;2;2;2), (04h?1;4;4;4;4) or (04h?2;2;2;2;2;2). Each one of those is 40 in S2. Case 3: If after rearranging ap ?2 is the largest, but ap?1 ?2 is not the second largest part, then ap?2 = ap?1. So we started with (a1;:::;ap?3;ap?1;ap?1;ap) and now have (a1 ?2;a2;:::;ap?3;ap?1 ?2;ap?1;ap ?2). By Property 2, this is in S2 as long as ap 6= a1 + ::: + ap?2. The case when ap = a1 + ::: + ap?2 and ap?2 = ap?1 is discussed below as Special Case (2h). 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;:::;ap) satisfles (2h + 1)ap ? 2h(a1 + ::: + ap?1) ? 2(2h ? 1), then (a1 ? 2;a2;:::;ap?2;ap?1?2;ap?2) satisfles (2h+1)(ap?2) ? 2h(a1 +:::+ap?1?4). Each Special Case (c+1) section covers the instances when (2h+1)ap = 2h(a1 + ::: + ap?1)?2c for 0 ? c ? 2h?2. Problems arising from rearranging the terms are discussed under condition 2. Therefore, each time we repeat steps 2-5 we obtain an element of S2. Notice that the above holds for the remaining steps of the algorithm. So it is su?cient to give even matchings of type (04h?1;2; ; ; ) and consider the special cases mentioned above. Let us consider the Special Case (c+1). As with p = 1 (mod 4) we deflne the set SP(c+1) as the set of all matching types satisfying the four necessary conditions and (2h + 1)ap = 2h(a1 + ::: + ap?1)?2c. We construct an even matching of type K = (a1;:::;a4h+3) 2 SP(c+1) by induction. We start by subtracting (02h+c+1;22h?c+1;4h?2c) to obtain K0 = (a1;:::;a2h+c+1;a2h+c+2? 2;:::;a4h+2 ?2; (2h)(a1+:::+ap?1)?2c2h+1 ?(4h?2c)). As long as no rearranging is necessary K0 is in SP1. If rearranging is necessary, we started with 41 K = (a1;:::;a2h+c;a4h+2;:::;a4h+2; (2h)(a1+:::+ap?1)?2c2h+1 ) and now have K00 = (a1;:::;a2h+c;a4h+2?2;:::;a4h+2?2;a4h+2; (2h)(a1+:::+ap?1)?2c2h+1 ?(4h?2c)). This is always in SP1. Notice that no matter what SP(c+1) we start with, after the flrst subtraction, we will continue the induction process with SP1 (i.e. c = 0). This concludes the inductive argument, since each time we repeat this process we obtain a smaller element of SP1. Thus Special Case (c+1) is solved. Now let us consider Special Case (2h). If ap?2 = ap?1 and ap = a1 +:::+ap?2 we have types of the form (a1;a2;:::;ap?3;ap? (a1 + ::: + ap?3);ap ? (a1 + ::: + ap?3);ap). We will construct an even matching of such type as follows: aj=2 copies of (0j?1;2;04h?j;2;2;4) for each 1 ? j ? 4h, and ap ?2(a1 +:::+ap?3)=2 copies of (04h;2;2;2). This concludes Special Case (2h). The following are even matchings of type (04h?1;2; ; ; ) and other matchings used above. (04h;2;2;2): from Lemma 2.4 By Property 2, an even matching of type (04h;ap?2;ap?1;ap) exists if ap ? ap?2. Hence we must have (04h;ap;ap;ap). (04h;ap;ap;ap) from ap=2 copies of (04h;2;2;2) (04h?1;2;2;2;2): from Lemma 2.4 (04h?1;2;2;2;4): from Lemma 2.4 By Property 2, an even matching of type (04h?1;2;ap?2;ap?1;ap) exists if ap?2 ? ap?2. (04h?1;2;ap;ap;ap) from (04h?1;2;2;2;2) and (ap ?2)=2 copies of (04h;2;2;2) (04h?1;2;ap ?2;ap;ap) from (04h?1;2;0;2;2) and (ap ?2)=2 copies of (04h;2;2;2) Since ap ? 2, ap ?2 ? 0. 42 (04h?1;2;ap ?2;ap ?2;ap) from (04h?1;2;2;2;4) and (ap ?4)=2 copies of (04h;2;2;2) Since ap ?2 ? 2, ap ?4 ? 0. (04h?2;2;2;2;2;2): from Lemma 2.4 (04h?2;2;2;2;2;6): from Lemma 2.4 For c ? 1 we have (02h+c+1;22h?c+1;4h?2c) from Lemma 2.4 (02h+1;22h+1;4h): Needed; not yet found. Therefore we have even matchings for p = 3 (mod 4). Once the missing matchings are found, this proves the su?ciency of the necessary conditions listed in Section 2.1. 43 Chapter 3 Existence of k-divisible-Matchings The results in Chapter 2 can be extended by considering the following deflnition. Deflnition 3.1 Let a1;a2;:::;ap be non-negative integers, and let Ai denote the vertex partite set of size ai, for 1 ? i ? p. Then for the graph K(a1;a2;:::;ap), the ordered set M = (M1;M2;:::;Mp) is a k-divisible-matching of type (a1;a2;:::;ap) if 1. for each i, 1 ? i ? p, the set Mi is a perfect matching in the graph K(a1;a2;:::;ap)nAi, and 2. for each edge e of K(a1;a2;:::;ap), the number of matchings Mi containing e is divisible by k. We will refer to this as the divisibility condition. Previously we considered each edge appearing an even number of times. Notice that even matchings are 2-divisible-matchings. Let us deflne the set Sk = f(a1;:::;ap)j a k-divisible-matching on the graph K(a1;:::;ap) existsg. 3.1 Necessary conditions In this Section we present necessary conditions for the existence of k-divisible- matchingsoftype(a1;a2;:::;ap). Weassumea1 ? a2 ? ::: ? ap anddeflnen = Ppi=1 ai. These necessary conditions are as follows: 1. p ? 1 (mod k), 44 2. 2ap +ap?1 ? n, 3. If k is even: either all ai are even or all ai are odd and p ? 1 (mod 2k). If k is odd: either all ai are even or all ai are odd and p is odd. 4. (2p?k?2)ap ? (p?k?1)n. Notice that condition 4 implies p > k +1. Let us verify the above conditions. 1. Each vertex (element of Ai) will be used in p?1 edges, and the number of edges that vertex is in must be divisible by k, equivalently p?1k must be an integer. Therefore p ? 1 (mod k). 2. For every i, n?ai?2ap ? 0, since we must have enough vertices in each n?ai to \match" the vertices of the largest part. Since a1 ? a2 ? ::: ? ap, it is su?cient that n?ap?1 ?2ap ? 0, i.e. 2ap +ap?1 ? n. 3. Since each Mi is to be a perfect matching, (Ppi=1 ai)?ai must be even for all i; hence all ai have same parity. The \divisibility" condition requires Pp i=1 n?ai 2 = (p?1)n 2 to be divisible by k. Therefore either all ai are even, or if k is even, all ai are odd and p ? 1 (mod 2k) and if k is odd, all ai are odd and p is odd. 4. None of the edges in Mp use vertices in Ap. Therefore there must be enough edges in M1[M2[:::[Mp?1 not intersecting Ap to satisfy the \divisibility" condition. So, (k?1)n?ap2 ? p?1X i=1 n?ai ?2ap 2 = (p?2)n?(2p?3)ap 2 ; 45 which implies (2p?k?2)ap ? (p?k?1)n 5. From the above we have p?k?1 > 0, i.e. p > k +1. It would be very useful to have an analogue of Lemma 2.1 and Lemma 2.2 for k-divisible- matchings. Lemma 3.2 If M = (M1;M2;:::;Mp) is a k-divisible-matching of type (a1;a2;:::;ap) and N = (N1;N2;:::;Np) is a k-divisible-matching of type (b1;b2;:::;bp), on disjoint vertex sets, then M [N = (M1 [N1;M2 [N2;:::;Mp [Np) is a k-divisible-matching of type (a1 +b1;a2 +b2;:::;ap +bp). Proof: Since the number of times each edge appears in M and N is a multiple of k this is a k-divisible-matching. ? Lemma 3.3 If M = (M1;M2;:::;Mp) is a k-divisible-matching of type (a1;a2;:::;ap) and N = (N1;N2;:::;Nq) is a k-divisible-matching of type (a1;b2;:::;bq), then there exists a k-divisible-matching for K(a1;a2;:::;ap;b2;b3;:::;bq) of type (a1;a2;:::;ap;b2;b3;:::;bq). Proof: This proof is very similar to the proof for even matchings. The k-divisible- matching of type (a1;a2;:::;ap;b2;b3;:::;bq) on K(a1;a2;:::;ap;b2;b3;:::;bq) is given by (M1;M2;:::;Mp;N2;N3;:::;Nq): M1 = M1 [N1; 46 Mi = Mi [N1; 2 ? i ? p; Ni = Ni [M1; 2 ? i ? q: This uses the matchings M1;:::;Mp and N1;:::;Nq once, M1 an additional q?1 times, and N1 an additional p ? 1 times. Since p;q ? 1 (mod k) the above is a k-divisible- matching. ? The following are generalizations of Lemmas 2.4 and 2.5. Lemma 3.4 If a1;:::;ap are even and (a1;:::;ap) is an element of Sk, then (0kn;a1;:::;ap) is also an element of Sk for any integer n. Proof: Let (M1;:::;Mp) be a k-divisible-matching of type (a1;:::;ap). Let N be any perfect matching on K(a1;:::;ap). By Lemma 2.3, N exists. We construct a k-divisible- matching of K(0kn;a1;:::;ap) as follows. Mi = N for 1 ? i ? kn Mj+kn = Mj for 1 ? j ? p Clearly this is a k-divisible-matching. ? Lemma 3.5 If a1;:::;ap;b2;:::;bq are all even and (a1;:::;ap), (0;b2;:::;bq) are both elements of Sk, then (b2;:::;bq;a1;:::;ap) is also an element of Sk. Proof: Let (M1;:::;Mp) be a k-divisible-matching of type (a1;:::;ap) and (N1;:::;Nq) be a k-divisible-matchings of type (0;b2;:::;bq). Let R be any perfect matching on K(a1;:::;ap). By Lemma 2.3, R exists. We construct a k-divisible-matching of K(b2;:::;bq;a1;:::;ap) as follows. Mi = Ni+1 [R for 1 ? i ? q ?1 Mj+q?1 = N1 [Mj for 1 ? j ? p Since p?1 and q?1 are both divisible by k this is a k-divisible-matching. ? 47 3.2 3-divisible-matchings Let us consider k = 3-divisible-matchings. By condition 1, p ? 1 (mod 3). We will flrst consider p = 7 and p = 10. Notice that when p = 10 all parts ai must be of even size. 3.2.1 Any number of parts of the same size Let us consider 3-divisible-matchings with all parts of the same size. It is su?cient to consider (17) = (1;1;1;1;1;1;1), (27) = (2;2;2;2;2;2;2) and (210) = (2;2;2;2;2;2;2;2;2;2). We can then use Lemma 3.2, as follows: If a is odd: (a7) = (17)+ a?12 copies of (27). If a is even: (a7) = a2 copies of (27). (a10) = a2 copies of (210). Also, to construct any 3-divisible matching (ap) we use Lemma 3.3. (17) = (1;1;1;1;1;1;1): For 2 ? i ? 8: Mi?1: ffi;i+1g;fi+2;i+3g;fi+4;i+5gji 2Z7g (27) = (2;2;2;2;2;2;2): M1: ff2;3g;f4;5g;f6;7g;f20;30g;f40;50g;f60;70gg M2: ff1;7g;f3;4g;f5;6g;f10;70g;f30;40g;f50;60gg M3: ff1;2g;f4;5g;f6;7g;f10;20g;f40;50g;f60;70gg M4: ff1;7g;f2;3g;f5;6g;f10;70g;f20;30g;f50;60gg M5: ff1;2g;f3;4g;f6;7g;f10;20g;f30;40g;f60;70gg M6: ff1;7g;f2;3g;f4;5g;f10;70g;f20;30g;f40;50gg 48 M7: ff1;2g;f3;4g;f5;6g;f10;20g;f30;40g;f50;60gg (210) = (2;2;2;2;2;2;2;2;2;2): M1: ff2;3g;f20;4g;f30;40g;f5;6g;f50;7g;f60;70g;f80;10g;f8;9g;f90;100gg M2: ff3;4g;f30;5g;f40;50g;f6;7g;f60;8g;f70;80g;f90;1g;f9;10g;f10;100gg M3: ff4;5g;f40;6g;f50;60g;f7;8g;f70;9g;f80;90g;f100;2g;f1;10g;f10;20gg M4: ff5;6g;f50;7g;f60;70g;f8;9g;f80;10g;f90;100g;f10;3g;f1;2g;f20;30gg M5: ff6;7g;f60;8g;f70;80g;f9;10g;f90;1g;f10;100g;f20;4g;f2;3g;f30;40gg M6: ff7;8g;f70;9g;f80;90g;f1;10g;f100;2g;f10;20g;f30;5g;f3;4g;f40;50gg M7: ff8;9g;f80;10g;f90;100g;f1;2g;f10;3g;f20;30g;f40;6g;f4;5g;f50;60gg M8: ff9;10g;f90;1g;f100;10g;f2;3g;f20;4g;f30;40g;f50;7g;f5;6g;f60;70gg M9: ff1;10g;f100;2g;f10;20g;f3;4g;f30;5g;f40;50g;f60;8g;f6;7g;f70;80gg M10: ff1;2g;f10;3g;f20;30g;f4;5g;f40;6g;f50;60g;f70;9g;f7;8g;f80;90gg 3.2.2 Seven parts of any size In this Section we will give 3-divisible-matchings of type K = (a1;:::;a7). Since p = 7 ? 1 (mod 6) we can have all parts of even size or all parts of odd size. We will use a similar algorithm as for even matchings to construct a 3-divisible-matching (a1;:::;a7) from (0;0;0;2; ; ; ) or (1;1;1;1;1; ; ). 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = a2 = a3 = 0 and a4 = 0;2, a1 = ::: = a5 = 1 or K = (0;0;2;2;2;2;2) look up the matching in the list provided. Otherwise continue below. 2. For 0 ? i ? 3 repeat the following steps. 3. Subtract (0i;2;04?i;2;2). 49 4. If necessary, rearrange the terms to ensure that the parts form a nondecreasing sequence. 5. Repeat steps 3-4 until you obtain (0;0;0;2; ; ; ) or (1;1;1;1; ; ; ). If at any point K = (0;0;2;2;2;2;2) look it up. 6. The 3-divisible-matchings of type (0;0;0;2; ; ; ) are listed below. 7. Subtract (0;0;0;0;2;2;2). 8. If necessary, rearrange the terms to ensure that the parts form a nondecreasing sequence. 9. Repeat until you obtain (1;1;1;1;1; ; ). 10. The 3-divisible-matchings of type (1;1;1;1;1; ; ) are listed below. Let us consider the four necessary conditions during the flrst part of the \subtracting process." Notice that for k = 3 and p = 7 condition 4 becomes 3a7 ? n. 1. p = 7 is not afiected. 2. If (a1;:::;a7) satisfles 2a7+a6 ? a1+:::+a7, then (a1?2;a2;a3;a4;a5;a6?2;a7?2) satisfles 2(a7 ?2) + (a6 ?2) ? (a1 ?2) +a2 +a3 +a4 +a5 + (a6 ?2) + (a7 ?2). We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging a7 ?2 is not the largest, but the second largest part, then a5 = a7. So we started with (a1;a2;a3;a4;a7;a7;a7) and now have (a1 ?2;a2;a3;a4;a7 ?2;a7 ?2;a7). By Properties 2 and 4, (a1 ?2;a2;a3;a4;a7 ? 50 2;a7 ? 2;a7) is in S3 as long as 6 ? a1 + ::: + a4. Let us consider the case when a1 + ::: + a4 < 6. We could have (0;0;0;0;a7;a7;a7), (0;0;0;2;a7;a7;a7), (0;0;0;4;a7;a7;a7), (0;0;2;2;a7;a7;a7) or (1;1;1;1;a7;a7;a7). Each one of those is discussed and shown to be in S3. Case 2: If after rearranging a7 ? 2 is not the largest or second largest part, then a4 = ::: = a7. So we started with (a1;a2;a3;a7;a7;a7;a7) and now have (a1 ? 2;a2;a3;a7 ? 2;a7 ? 2;a7;a7). By Properties 2 and 4, (a1 ? 2;a2;a3;a7 ? 2;a7 ? 2;a7;a7) is in S3 as long as 6 ? a1 + a2 + a3 + a7. Let us consider the case when 6 > a1 +a2 +a3 +a7. We could have (0;0;0;2;2;2;2), (0;0;0;4;4;4;4), (0;0;2;2;2;2;2) or (1;1;1;1;1;1;1). Each one of those is covered by Case 1. Case 3: If after rearranging a7?2 is the largest, but a6?2 is not the second largest part, then a5 = a6. So we started with (a1;a2;a3;a4;a6;a6;a7) and now have (a1?2;a2;a3;a4;a6?2;a6;a7?2). By Property 2, (a1?2;a2;a3;a4;a6?2;a6;a7?2) is in S3 as long as a7 6= a1+a2+a3+a4+a5. When a7 = a1+:::+a5 and a5 = a6 we have types of the form (a1;a2;a3;a4;a7?(a1+:::+a4);a7?(a1+:::+a4);a7). By Property 4, this implies a1+:::+a4 ? 0. Hence we must have (0;0;0;0;a6;a6;a7) and a7 ? a6 ? a7. Types (0;0;0;0;a7;a7;a7) are discussed below as valid. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;:::;a7) satisfles 3a7 ? (a1+:::+a7), then (a1?2;a2;a3;a4;a5;a6?2;a7?2) satisfles 3(a7 ?2) ? ((a1 ?2)+a2 +a3 +a4 +a5 +(a6 ?2)+(a7 ?2)). Problems arising from rearranging of the terms are discussed under Property 2. 51 This is also true for the remaining parts of the algorithm. Therefore, each time we subtract we obtain an element of S3. When we reach (1;1;1;1;1; ; ) or (0;0;0;2; ; ; ) all four conditions are satisfled. Here are some \building blocks" we will use throughout this Section. (0;0;0;0;2;2;2): M1: ff5;6g;f50;7g;f60;70gg M2: ff5;70g;f50;60g;f6;7gg M3: ff5;6g;f50;7g;f60;70gg M4: ff5;70g;f50;60g;f6;7gg M5: ff6;7g;f60;70gg M6: ff5;70g;f50;7gg M7: ff5;6g;f50;60gg (0;0;0;2;2;2;2): M1: ff4;7g;f40;6g;f50;60g;f5;70gg M2: ff4;5g;f40;50g;f6;7g;f60;70gg M3: ff4;5g;f40;50g;f6;7g;f60;70gg M4: ff5;70g;f50;60g;f6;7gg M5: ff4;7g;f40;6g;f60;70gg M6: ff4;7g;f40;50g;f5;70gg M7: ff4;5g;f40;6g;f50;60gg (0;0;0;0;0;0;0;2;2;2): M1: ff8;10g;f9;100g;f80;90gg M2: ff8;90g;f80;100g;f9;10gg 52 M3: ff8;90g;f9;100g;f80;10gg M4: ff8;90g;f80;100g;f9;10gg M5: ff8;9g;f80;10g;f90;100gg M6: ff8;9g;f80;10g;f90;100gg M7: ff8;10g;f80;90g;f9;100gg M8: ff9;10g;f90;100gg M9: ff8;10g;f80;100gg M10: ff8;9g;f80;90gg Following is a list of 3-divisible-matchings of type (1;1;1;1;1; ; ). (1;1;1;1;1;1;1) given in Section 3.2.1 (1;1;1;1;1;1;3) : M1: ff2;70g;f3;4g;f5;700g;f6;7gg M2: ff1;7g;f3;700g;f4;70g;f5;6gg M3: ff1;2g;f4;70g;f5;700g;f6;7gg M4: ff1;7g;f2;70g;f3;700g;f5;6gg M5: ff1;2g;f3;700g;f4;70g;f6;7gg M6: ff1;7g;f2;70g;f3;4g;f5;700gg M7: ff1;2g;f3;4g;f5;6gg (1;1;1;1;1;3;3) : M1: ff2;70g;f3;600g;f4;700g;f5;6g;f60;7gg M2: ff1;600g;f3;7g;f4;60g;f5;70g;f6;700gg M3: ff1;600g;f2;70g;f4;700g;f5;6g;f60;7gg M4: ff1;2g;f3;600g;f5;70g;f60;7g;f6;700gg 53 M5: ff1;600g;f2;70g;f3;7g;f4;60g;f6;700gg M6: ff1;2g;f3;7g;f4;700g;f5;70gg M7: ff1;2g;f3;600g;f4;60g;f5;6gg (1;1;1;1;1;5;5) : M1: ff2;60g;f3;700g;f4;6000g;f5;7g;f6;70g;f600;7000g;f64;74gg M2: ff1;74g;f3;700g;f4;6000g;f5;64g;f6;70g;f60;7g;f600;7000gg M3: ff1;6g;f2;60g;f4;70g;f5;7g;f600;7000g;f6000;700g;f64;74gg M4: ff1;74g;f2;7000g;f3;600g;f5;64g;f6;70g;f60;7g;f6000;700gg M5: ff1;6g;f2;7000g;f3;600g;f4;70g;f60;7g;f6000;700g;f64;74gg M6: ff1;74g;f2;7000g;f3;700g;f4;70g;f5;7gg M7: ff1;6g;f2;60g;f3;600g;f4;6000g;f5;64gg Following is a list of 3-divisible-matchings of types (0;0;0;2; ; ; ) as well as (0;0;2;2;2;2;2). (0;0;2;2;2;2;2): M1: ff3;4g;f30;7g;f40;50g;f5;6g;f60;70gg M2: ff3;70g;f30;40g;f4;5g;f50;60g;f6;7gg M3: ff4;5g;f40;50g;f60;70g;f6;7gg M4: ff3;70g;f30;7g;f50;60g;f5;6gg M5: ff3;4g;f30;40g;f60;70g;f6;7gg M6: ff3;70g;f30;7g;f40;50g;f4;5gg M7: ff3;4g;f30;40g;f50;60g;f5;6gg (0;0;0;0;2;2;2) given above (0;0;0;0;a7;a7;a7)=a72 copies of (0;0;0;0;2;2;2) 54 By Property 2, a 3-divisible-matching of type (0;0;0;2;a5;a6;a7) exists if a5 ? a7 ?2. (0;0;0;2;a7;a7;a7) from (0;0;0;2;2;2;2) and (a7 ?2)=2 copies of (0;0;0;0;2;2;2) (0;0;0;2;a7 ?2;a7;a7) from (0;0;0;2;0;2;2) and (a7 ?2)=2 copies of (0;0;0;0;2;2;2) This gives the 3-divisible-matchings of type (a1;:::;a7). 3.2.3 Ten parts of any size Let us now consider 3-divisible-matchings of type K = (a1;a2;a3;a4;a5;a6;a7;a8;a9;a10) where a1 ? a2 ? a3 ? a4 ? a5 ? a6 ? a7 ? a8 ? a9 ? a10. Since p = 10 is even, all parts must be of even size. Similar to the case of seven parts, to flnd a 3-divisible-matching of type (a1;a2;a3;a4;a5;a6;a7;a8;a9;a10) we use the following algorithm. 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = a2 = a3 = a4 = a5 = a6 = 0 and a7 = 0;2 or K = (0;0;0;0;0;2;2;2;2;2) look up the matching in list provided. Otherwise continue below. 2. For 0 ? i ? 6 repeat the following. 3. If 5a10 = 2n skip down to the Special Case 1 section. If a8 = a9 and a10 = a1 + a2 + a3 + ::: + a8 skip down to Special Case 2 section. Otherwise continue below. 4. Subtract (0i;2;07?i;2;2). 5. If necessary, rearrange the terms to ensure that the parts are in a nondecreasing sequence. 55 6. Repeat steps 3-5 until you obtain (0i+1; 9?i) for 0 ? i ? 5 and (06;2; 3) for i = 6 . If at any point K = (0;0;0;0;0;2;2;2;2;2) look it up. 7. Stop when you reach (06;2; ; ; ). The 3-divisible-matchings of type (06;2; ; ; ) are listed below. Let us consider the four necessary conditions during steps 4-6 of the algorithm. 1. p = 10 is not afiected. 2. If (a1;a2;:::;a10) satisfles 2a10 +a9 ? a1 +:::+a10, then (a1 ?2;a2;:::;a9 ?2;a10 ?2) satisfles 2(a10 ?2)+(a9 ?2) ? (a1 ?2)+a2 +:::+a8 +(a9 ?2)+(a10 ?2). We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging a10 ? 2 is not the largest, but the second largest part, then a8 = a10. So we started with (a1;a2;:::;a7;a10;a10;a10) and now have (a1 ? 2;a2;:::;a7;a10 ? 2;a10 ? 2;a10). By Properties 2 and 4 (a1 ? 2;a2;:::;a7;a10?2;a10?2;a10) is in S3 as long as 4 ? a1+:::+a7 and 12?a10 ? 2(a1 + ::: + a7). Let us consider the case when a1 + ::: + a7 < 4. We could have (0;0;0;0;0;0;0;a10;a10;a10) or (0;0;0;0;0;0;2;a10;a10;a10). Each one of those is discussed and shown to be in S3 below. Let us consider the case when 12?a10 > 2(a1+???+a7). We could have (0;0;0;0;0;0;0;2;2;2), (0;0;0;0;0;0;0;4;4;4), :::, (0;0;0;0;0;0;0;10;10;10), (0;0;0;0;0;0;2;2;2;2), (0;0;0;0;0;0;2;4;4;4), (0;0;0;0;0;0;2;6;6;6) or (0;0;0;0;0;2;2;2;2;2). Each one of those is shown to be in S3. 56 Case 2: If after rearranging a10 ?2 is not the largest or second largest part, then a7 = a8 = a10. So we started with (a1;:::;a6;a10;a10;a10;a10) and now have (a1 ?2;a2;:::;a10 ?2;a10 ?2;a10;a10). By Properties 2 and 4 (a1 ?2;a2;:::;a10 ?2;a10 ?2;a10;a10) is in S3 as long as 6?a10 ? a1 +:::+a6 and 12 ? 3a10 ? 2(a1 + ::: + a6). Let us consider the case when 6 ? a10 > a1+:::+a6 or 12?3a10 > 2(a1+:::+a6). We could have (0;0;0;0;0;0;2;2;2;2), (0;0;0;0;0;0;4;4;4;4) or (0;0;0;0;0;2;2;2;2;2). Each one of those is in S3. Case 3: If after rearranging a10 ? 2 is the largest, but a9 ? 2 is not the second largest part, then a8 = a9. So we started with (a1;a2;:::;a7;a9;a9;a10) and now have (a1 ?2;a2;:::;a7;a9 ?2;a9;a10 ?2). By Property 2, (a1 ? 2;a2;:::;a7;a9 ? 2;a9;a10 ? 2) is in S3 as long as a10 6= a1 +:::+a7 +a9. The case when a10 = a1 +:::+a7 +a9 and a8 = a9 is discussed below as Special Case 2. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;a2;:::;a10) satisfles 5a10 < 2(a1+:::+a10), then (a1?2;a2;:::;a9?2;a10?2) satisfles 5(a10 ? 2) ? 2((a1 ? 2) + a2 + ::: + (a9 ? 2) + (a10 ? 2)). If 5a10 = 2n we refer to Special Case 1. Problems arising from rearranging of the terms are discussed under Property 2. Therefore, each time we repeat steps 2-6 we obtain an element of S3. Notice that the above holds for remaining steps of the algorithm. So it is su?cient to give 3-divisible- matchings of type (0;0;0;0;0;0;2; ; ; ) and consider the special cases mentioned above. 57 Let us consider the Special Case 1. We need to flnd 3-divisible-matchings for (a1;:::;a10) satisfying the four necessary con- ditions and 3a10 = 2(a1 +:::+a9). Let us refer to these as matching type SP31 S3. Say we need K = (a1;a2;:::;a9; 2(a1+:::+a9)3 ) 2 SP31. We will build it by induction. We start by subtracting (0;0;0;0;0;0;2;2;2;4) to obtain K0 = (a1;:::;a6;a7 ? 2;a8?2;a9?2; 2(a1+:::+a9)3 ?4). As long as no rearranging is necessary K0 is in SP31. If rearranging is necessary, we started with K = (a1;:::;a5;a9;:::;a9; 2(a1+:::+a9)3 ) and now have K00 = (a1;:::;a5;a9 ?2;a9 ?2;a9 ?2;a9; 2(a1+:::+a9)3 ?4). This is in SP31 as long as 6 ? a1+:::+a5+a9. The only time 6 > a1+:::+a5+a9 is for K = (06;23;4) which is given. We need to consider if it is possible for a9 > 2(a1+:::+a9)3 ?4. This is equivalent to 8 ? a1 + ::: + a8 which is true for all elements of SP31 except K = (06;23;4). By induction, this concludes Special Case 1. We take any element of SP31 and subtract to get a smaller element of SP31. Now let us consider Special Case 2. If a8 = a9 and a10 = a1 +:::+a7 +a9 we have types of the form (a1;a2;:::;a7;a10 ? (a1 + ::: + a7);a10 ? (a1 + ::: + a7);a10). We will construct a 3- divisible-matching of such type as follows: a1=2 copies of (2;0;0;0;0;0;0;2;2;4), a2=2 copies of (0;2;0;0;0;0;0;2;2;4), :::, a7=2 copies of (0;0;0;0;0;0;2;2;2;4) and (a10 ? 2(a1 + ::: + a7))=2 copies of (0;0;0;0;0;0;0;2;2;2). Notice that by Property 4 a10 ? 2(a1 +:::+a7). This concludes Special Case 2. The following are 3-divisible-matchings of type (0;0;0;0;0;0;2; ; ; ) and (0;0;0;0;0;2;2;2;2;2). (0;0;0;0;0;2;2;2;2;2): 58 M1: ff6;7g;f8;9g;f60;10g;f70;80g;f90;100gg M2: ff6;100g;f60;70g;f7;8g;f80;90g;f9;10gg M3: ff6;7g;f60;8g;f70;80g;f9;10g;f90;100gg M4: ff6;7g;f60;8g;f70;80g;f9;10g;f90;100gg M5: ff6;7g;f60;8g;f70;80g;f9;10g;f90;100gg M6: ff7;8g;f70;80g;f9;10g;f90;100gg M7: ff6;100g;f60;10g;f8;9g;f80;90gg M8: ff6;7g;f60;70g;f9;10g;f90;100gg M9: ff6;100g;f60;10g;f7;8g;f70;80gg M10: ff6;7g;f60;70g;f8;9g;f80;90gg (0;0;0;0;0;0;0;2;2;2) was given in Section 3.2.2 By Property 2, a 3-divisible-matching of type (0;0;0;0;0;0;0;a8;a9;a10) exists if a10 ? a8. Hence we must have (0;0;0;0;0;0;0;a10;a10;a10). (0;0;0;0;0;0;0;a10;a10;a10) from a10=2 copies of (0;0;0;0;0;0;0;2;2;2) (0;0;0;0;0;0;2;2;2;2): M1: ff8;9g;f7;90g;f80;10g;f70;100gg M2: ff7;8g;f90;100g;f9;10g;f70;80gg M3: ff7;10g;f70;9g;f8;100g;f80;90gg M4: ff7;90g;f70;100g;f8;9g;f80;10gg M5: ff7;8g;f70;80g;f90;100g;f9;10gg M6: ff7;10g;f70;9g;f80;90g;f8;100gg M7: ff8;9g;f80;10g;f90;100gg M8: ff7;90g;f9;10g;f70;100gg 59 M9: ff7;10g;f8;100g;f70;80gg M10: ff7;8g;f70;9g;f80;90gg (0;0;0;0;0;0;2;2;2;4): M1: ff8;1000g;f7;10000g;f80;90g;f70;100g;f9;10gg M2: ff7;8g;f9;100g;f90;10g;f70;1000g;f80;10000gg M3: ff7;10g;f70;9g;f8;1000g;f80;10000g;f90;100gg M4: ff7;10000g;f70;100g;f8;1000g;f80;90g;f9;10gg M5: ff7;8g;f9;100g;f90;10g;f70;1000g;f80;10000gg M6: ff7;10g;f70;9g;f8;1000g;f80;10000g;f90;100gg M7: ff8;1000g;f80;10000g;f90;100g;f9;10gg M8: ff7;10000g;f90;10g;f70;1000g;f9;100gg M9: ff7;10g;f8;1000g;f70;100g;f80;10000gg M10: ff7;8g;f70;9g;f80;90gg By Property 2, a 3-divisible-matching of type (0;0;0;0;0;0;2;a8;a9;a10) exists if a8 ? a10 ?2. (0;0;0;0;0;0;2;a10;a10;a10) from (0;0;0;0;0;0;2;2;2;2) and (a10 ?2)=2 copies of (0;0;0;0;0;0;0;2;2;2) (0;0;0;0;0;0;2;a10 ? 2;a10;a10) from (0;0;0;0;0;0;2;0;2;2) and (a10 ? 2)=2 copies of (0;0;0;0;0;0;0;2;2;2) Clearly a10 ?2 ? 0 since a10 ? 2. (0;0;0;0;0;0;2;a10 ?2;a10 ?2;a10) from (0;0;0;0;0;0;2;2;2;4) and (a10 ?4)=2 copies of (0;0;0;0;0;0;0;2;2;2) Similarly, a10 ?4 ? 0 since a10 ?2 ? 2. 60 Hence we have 3-divisible-matchings of type (a1;:::;a10). 3.2.4 p ? 1 (mod 6) parts of any size In this Section we will give a general construction of 3-divisible-matchings of type (a1;:::;a6h+1) for any positive integer h ? 2. Since p ? 1 (mod 6) we can have all parts of even size or all parts of odd size. We will need \building blocks" similar to the ones used before. (06h?2;2;2;2): from Lemma 3.4 (06h?3;2;2;2;2): from Lemma 3.4 Notice that when p = 6h+1 condition 4 becomes 2hap ? (2h?1)(a1 +:::+ap?1) and condition 2 remains ap ? a1+:::+ap?2. We can construct a 3-divisible-matching of type (0;0;0;a4;:::;ap) inductively. We start with the 3-divisible-matching (a4;:::;ap) (as long as it exists) and apply Lemma 3.4. To flnd a 3-divisible-matching of type (a1;:::;a6h+1) we use the following algorithm. 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = ::: = ap?4 = 0, ap?3 = 2 or a1 = ::: = ap?2 = 1 or K = (06h?4;2;2;2;2;2) or K = (06h?4;2;2;2;2;6) look up the matching in list provided. Otherwise continue below. 2. If 2hap = (2h?1)(a1+:::+ap?1)?2c for 0 ? c ? 2h?3 skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1+:::+ap?2 skip down to Special Case (2h?1) section. Otherwise continue below. 3. Subtract (2;06h?2;2;2) to obtain (a1 ?2;a2;:::;ap?1 ?2;ap ?2). 61 4. If necessary, rearrange the terms to ensure a nondecreasing sequence. 5. Repeat steps 2-4 until you obtain (0; 6h) or (1; 6h). 6. If 2hap = (2h?1)(a1+:::+ap?1)?2c for 0 ? c ? 2h?3 skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1+:::+ap?2 skip down to Special Case (2h?1) section. Otherwise continue below. 7. For 6h?3 ? j ? 1 repeat the following steps. 8. Subtract (06h?2?j;2;0j;2;2). 9. If necessary, rearrange the terms to ensure the sequence is nondecreasing. 10. Stop when you obtain (06h?3;2; ; ; ) or (16h?1; ; ). 11. The 3-divisible-matchings of type (06h?3;2; ; ; ) and (16h?1; ; ) will need to be given. Let us consider the four necessary conditions during steps 2-5 of the algorithm. 1. p = 6h+1 is not afiected. 2. If (a1;:::;ap) satisfles ap ? a1 + :::+ ap?2, then (a1 ?2;a2;:::;ap?1 ?2;ap ?2) satisfles ap ?2 ? a1 ?2+a2 +:::+ap?2. We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging ap ?2 is not the largest, but the second largest part, then ap?2 = ap. So we started with (a1;:::;ap?3;ap;ap;ap) and now have (a1 ? 2;a2;:::;ap?3;ap ? 2;ap ? 2;ap). By Properties 2 and 4, this is in S3 as 62 long as 4 ? a1 +:::+ap?3 and 12h?6?(2h?2)ap ? (2h?1)(a1 +:::+ap?3), which is equivalent to a1+:::+ap?3 ? 6? 2h?22h?1ap. Let us consider the cases when 4 > a1+:::+ap?3 or a1+:::+ap?3 < 6?2h?22h?1ap. We could have (06h?2;ap;ap;ap), (06h?3;2;ap;ap;ap) or (06h?4;2;2;2;2;2). Each one of those is in S3. Case 2: If after rearranging ap ? 2 is not the largest or second largest part, then ap?3 = ap. So we started with (a1;:::;ap?4;ap;ap;ap;ap) and now have (a1 ?2;a2;:::;ap?4;ap ?2;ap ?2;ap;ap). By Properties 2 and 4, this is in S3 as long as 6?ap ? a1 +:::+ap?4 and 6? 4h?32h?1ap ? a1 +:::+ap?4. Let us consider the cases when 6?ap > a1 +:::+ap?4 or 6? 4h?32h?1ap > a1 +:::+ap?4. We could have (06h?3;2;2;2;2), (06h?3;4;4;4;4) or (06h?4;2;2;2;2;2). Each one of those is in S3. Case 3: If after rearranging ap ?2 is the largest, but ap?1 ?2 is not the second largest part, then ap?2 = ap?1. So we started with (a1;:::;ap?3;ap?1;ap?1;ap) and now have (a1 ?2;a2;:::;ap?3;ap?1 ?2;ap?1;ap ?2). By Property 2, this is in S3 as long as ap 6= a1 + ::: + ap?2. The case when ap = a1 + ::: + ap?2 and ap?2 = ap?1 is discussed below as Special Case (2h?1). 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;:::;ap) satisfles 2hap ? (2h ? 1)(a1 + ::: + ap?1) ? 4(h ? 1), then (a1 ? 2;a2;:::;ap?2;ap?1?2;ap?2) satisfles 2h(ap?2) ? (2h?1)(a1 +:::+ap?1?4). Each Special Case (c+1) section covers the instances when 2hap = (2h?1)(a1 + ::: + ap?1)?2c for 0 ? c ? 2h?3. Problems arising from rearranging the terms are discussed under condition 2. 63 Therefore, each time we repeat steps 2-5 we obtain an element of S3. Notice that the above holds for the remaining steps of the algorithm. So it is su?cient to give 3- divisible-matchings of type (06h?3;2; ; ; ) and (16h?1; ; ) and consider the special cases mentioned above. Let us consider the Special Case (c+1) for 0 ? c ? 2h?3. We need to flnd 3-divisible-matchings for (a1;:::;ap) satisfying the four necessary conditions and 2hap = (2h?1)(a1+:::+ap?1)?2c. Let us refer to these as matching type SP3(c+1) S3. Say we need K = (a1;a2;:::;ap?1; (2h?1)(a1+:::+ap?1)?2c2h ) 2 SP3(c+1). We will build it by induction. We consider parts of odd size flrst. We start by subtractingR1 = (14h+c;32h?c;10h? 5?2c) to obtain K0 = (a1?1;:::;a4h+c?1;a4h+c+1?3;:::;a6h?3; (2h?1)(a1+:::+ap?1)?2c2h ? (10h?5?2c)). Since necessary conditions 2 and 4 were satisfled in K, they are still sat- isfled in K0. Also, K0 2 SP31. However, if rearranging is necessary and we obtain K00 = (a1?1;:::;a4h+c+1?3;a4h+c+2?3;:::;a6h?3;a4h+c?1; (2h?1)(a1+:::+ap?1)?2c2h ?(10h?5? 2c)) instead of K0, we must have a4h+c?1 = a6h?3+2 or a4h+c = a6h. Hence we started with K = (a1;:::;a4h+c?1;a6h;:::;a6h; (2h?1)(a1+:::+ap?1)?2c2h ). In this case instead of subtracting R1 = (14h+c;32h?c;10h?5?2c), we subtract R2 = (12h+c;34h?c;14h?7?2c) to obtain K0 = (a1 ? 1;:::;a2h+c ? 1;a2h+c+1 ? 3;:::;a6h ? 3; (2h?1)(a1+:::+ap?1)?2c2h ? (14h?7?2c)). Notice that as long as no rearranging is necessary, K0 2 SP31. How- ever, if rearranging is necessary and results in K00 = (a1 ?1;:::;a2h+c?1 ?1;a2h+c+1 ? 3;:::;a6h?3;a2h+c?1; (2h?1)(a1+:::+ap?1)?2c2h ?(14h?7?2c)) we must have a2h+c = a6h. So we started with K = (a1;:::;a2h+c?1;a6h;:::;a6h; (2h?1)(a1+:::+ap?1)?2c2h ) and now 64 have K00 = (a1 ?1;:::;a2h+c?1 ?1;a6h ?3;:::;a6h ?3;a6h; (2h?1)(a1+:::+ap?1)?2c2h ). Sat- isfying the conditions 2 and 4, this K00 is always in SP31. This shows that when we complete this step, we obtain an element of SPk1. For parts of even size we start by subtracting (04h+c;22h?c;4h ? 2 ? 2c) to ob- tain K0 = (a1;:::;a4h+c;a4h+c+1 ?2;:::;a6h ?2; (2h?1)(a1+:::+ap?1)?2c2h ?(4h?2?2c)). As long as no rearranging is necessary K0 is in SP31. If rearranging is necessary, we started with K = (a1;:::;a4h+c?1;a6h;:::;a6h; (2h?1)(a1+:::+ap?1)?2c2h ) and now have K00 = (a1;:::;a4h+c?1;a6h ? 2;:::;a6h ? 2;a6h; (2h?1)(a1+:::+ap?1)?2c2h ? (4h ? 2 ? 2c)). This is in SP31. Notice that no matter what SP3(c + 1) we start with, after the flrst subtraction, we will continue the induction process with SP31 (i.e. c = 0). By induction, this concludes Special Case (c+1). We take any element of SP3(c+1) and subtract to get a smaller element of SP31. Now let us consider Special Case (2h?1). If ap?2 = ap?1 and ap = a1 +:::+ap?2 we have types of the form (a1;a2;:::;ap?3;ap? (a1 + ::: + ap?3);ap ? (a1 + ::: + ap?3);ap). We will construct a 3-divisible-matching of such type as follows: aj=2 copies of (0j?1;2;06h?2?j;2;2;4) for each 1 ? j ? 6h?2, and ap ?2(a1 +:::+ap?3)=2 copies of (06h?2;2;2;2). Notice that by Property 4, ap ? 2(a1 +:::+ap?3). This concludes Special Case (2h?1). The following are 3-divisible-matchings of type (06h?3;2; ; ; ) and (16h?1; ; ) and other matchings used in the above construction. (06h?2;2;2;2): from Lemma 3.4 By Property 2, a 3-divisible-matching of type (06h?2;ap?2;ap?1;ap) exists if ap ? ap?2. Hence we must have (06h?2;ap;ap;ap). 65 (06h?2;ap;ap;ap) from ap=2 copies of (06h?2;2;2;2) (06h?3;2;2;2;2): from Lemma 3.4 (06h?3;2;2;2;4): from Lemma 3.4 By Property 2, a 3-divisible-matching of type (06h?3;2;ap?2;ap?1;ap) exists if ap?2 ? ap ?2. (06h?3;2;ap;ap;ap) from (06h?3;2;2;2;2) and (ap ?2)=2 copies of (06h?2;2;2;2) (06h?3;2;ap ?2;ap;ap) from (06h?3;2;0;2;2) and (ap ?2)=2 copies of (06h?2;2;2;2) Since ap ? 2, ap ?2 ? 0. (06h?3;2;ap ?2;ap ?2;ap) from (06h?3;2;2;2;4) and (ap ?4)=2 copies of (06h?2;2;2;2) Since ap ?2 ? 2, ap ?4 ? 0. (06h?4;2;2;2;2;2): from Lemma 3.4 (06h?4;2;2;2;2;6): from Lemma 3.4 (04h;22h;4h?2): Needed; not yet found. The remaining (04h+c;22h?c;4h?2?2c) for 0 < c ? 2h?3 are obtained from Lemma 3.4 (16h+1): given in Section 3.2.1 (14h+c;32h?c;10h?5?2c): Needed; not yet found. (12h+c;34h?c;7h;14h?7?2c): Needed; not yet found. In the following families of matchings we use i;j odd. For 3 ? i ? 6h?3, (16h;i): Needed; not yet found. For 3 ? i ? 6h?1 and 3 ? j ? i, (16h?1;j;i): Needed; not yet found. Once the above missing matchings are found, we will have 3-divisible-matchings of type (a1;:::;a6h+1). 66 3.2.5 p ? 4 (mod 6) parts of any size In this Section we will give a general construction of 3-divisible-matchings of type (a1;:::;a6h+4) for any positive integer h ? 2. Since p ? 4 (mod 6) we can only have all parts of even size. We will use \building blocks" similar to the ones above. (06h+1;2;2;2): from Lemma 3.4 (06h;2;2;2;2): from Lemma 3.4 Notice that when p = 6h+4 condition 4 becomes (2h+1)ap ? 2h(a1+:::+ap?1) and condition 2 remains ap ? a1+:::+ap?2. We can still construct a 3-divisible-matching of type (0;0;0;a3;:::;ap) inductively. We start with the 3-divisible-matching (a3;:::;ap) (as long as it exists) and apply Lemma 3.4. To flnd a 3-divisible-matching of type (a1;:::;a6h+4) we use the following algorithm. 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = ::: = ap?4 = 0, ap?3 = 2 or K = (06h?1;2;2;2;2;2) or K = (06h?1;2;2;2;2;6) look up the matchingin list provided. Otherwise continuebelow. 2. If (2h + 1)ap = 2h(a1 + ::: + ap?1) ? 2c, for 0 ? c ? 2h ? 2, skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1 + ::: + ap?2 skip down to Special Case (2h) section. Otherwise continue below. 3. Subtract (2;06h+1;2;2) to obtain (a1 ?2;a2;:::;ap?1 ?2;ap ?2). 4. If necessary, rearrange the terms to ensure a nondecreasing sequence. 5. Repeat steps 2-4 until you obtain (0; 6h+3). 67 6. If (2h+1)ap = 2h(a1+:::+ap?1)?2c for 0 ? c ? 2h?2 skip down to the Special Case (c+1) section. If ap?2 = ap?1 and ap = a1 + ::: + ap?2 skip down to Special Case (2h) section. Otherwise continue below. 7. For 6h ? j ? 1 repeat the following steps. 8. Subtract (06h+1?j;2;0j;2;2). 9. If necessary, rearrange the terms to ensure the sequence is nondecreasing. 10. Stop when you obtain (06h;2; ; ; ). 11. The 3-divisible-matchings of type (06h;2; ; ; ) will need to be given. Let us consider the four necessary conditions during steps 2-5 of the algorithm. 1. p = 6h+4 is not afiected. 2. If (a1;:::;ap) satisfles ap ? a1 + :::+ ap?2, then (a1 ?2;a2;:::;ap?1 ?2;ap ?2) satisfles ap ?2 ? a1 ?2+a2 +:::+ap?2. We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging ap ?2 is not the largest, but the second largest part, then ap?2 = ap. So we started with (a1;:::;ap?3;ap;ap;ap) and now have (a1?2;a2;:::;ap?3;ap?2;ap?2;ap). By Properties 2 and 4, this is in S3 as long as 4 ? a1 + ::: + ap?3 and a1 + ::: + ap?3 ? 6 ? 2h?12h ap. Let us consider the cases when 4 > a1 + ::: + ap?3 or a1 + ::: + ap?3 < 6? 2h?12h ap. We could have (06h+1;ap;ap;ap), (06h;2;ap;ap;ap) or (06h?1;2;2;2;2;2). Each one of those is in S3. 68 Case 2: If after rearranging ap ? 2 is not the largest or second largest part, then ap?3 = ap. So we started with (a1;:::;ap?4;ap;ap;ap;ap) and now have (a1 ?2;a2;:::;ap?4;ap ?2;ap ?2;ap;ap). By Properties 2 and 4, this is in S3 as long as 6?ap ? a1 +:::+ap?4 and 6? 4h?12h ap ? a1 +:::+ap?4. Let us consider the cases when 6?ap > a1 +:::+ap?4 or 6? 4h?12h ap > a1 +:::+ap?4. We could have (06h;2;2;2;2), (06h;4;4;4;4) or (06h;2;2;2;2;2). Each one of those is in S3. Case 3: If after rearranging ap ?2 is the largest, but ap?1 ?2 is not the second largest part, then ap?2 = ap?1. So we started with (a1;:::;ap?3;ap?1;ap?1;ap) and now have (a1 ?2;a2;:::;ap?3;ap?1 ?2;ap?1;ap ?2). By Property 2, this is in S3 as long as ap 6= a1 + ::: + ap?2. The case when ap = a1 + ::: + ap?2 and ap?2 = ap?1 is discussed below as Special Case (2h). 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;:::;ap) satisfles (2h + 1)ap ? 2h(a1 + ::: + ap?1) ? 2(2h ? 1), then (a1 ? 2;a2;:::;ap?2;ap?1?2;ap?2) satisfles (2h+1)(ap?2) ? 2h(a1 +:::+ap?1?4). Each Special Case (c+1) section covers the instances when (2h+1)ap = 2h(a1 + ::: + ap?1)?2c for 0 ? c ? 2h?2. Problems arising from rearranging the terms are discussed under condition 2. Therefore, each time we repeat steps 2-5 we obtain an element of S3. Notice that the above holds for the remaining steps of the algorithm. So it is su?cient to give 3-divisible- matchings of type (06h;2; ; ; ) and consider the special cases mentioned above. Let us consider the Special Case (c+1). 69 As with p = 1 (mod 6) we deflne the set SP3(c+1) as the set of all matching types satisfying the four necessary conditions and (2h+1)ap = 2h(a1+:::+ap?1)?2c. We con- struct a 3-divisible-matching of type K = (a1;:::;a6h+4) 2 SP3(c+1) by induction. We start by subtracting (04h+c+2;22h?c+1;4h?2c) to obtain K0 = (a1;:::;a4h+c+2;a4h+c+3? 2;:::;a6h+3 ?2; (2h)(a1+:::+ap?1)?2c2h+1 ?(4h?2c)). As long as no rearranging is necessary K0 is in SP31. If rearranging is necessary, we started with K = (a1;:::;a4h+c+1;a6h+3;:::;a6h+3; (2h)(a1+:::+ap?1)?2c2h+1 ) and now have K00 = (a1;:::;a4h+c+1;a6h+3 ? 2;:::;a6h+3 ? 2;a6h+3; (2h)(a1+:::+ap?1)?2c2h+1 ? (4h ? 2c)). This is always in SP31. Notice that no matter what SP3(c+1) we start with, after the flrst subtraction, we will continue the induction process with SP31 (i.e. c = 0). This concludes the inductive argument, since each time we repeat this process we obtain a smaller element of SP31. Thus Special Case (c+1) is solved. Now let us consider Special Case (2h). If ap?2 = ap?1 and ap = a1 +:::+ap?2 we have types of the form (a1;a2;:::;ap?3;ap? (a1 +:::+ap?3);ap ?(a1 +:::+ap?3);ap). We will construct a 3-divisible-matching of such type as follows: aj=2 copies of (0j?1;2;06h+1?j;2;2;4) for each 1 ? j ? 6h+1, and ap ?2(a1 +:::+ap?3)=2 copies of (06h+1;2;2;2). This concludes Special Case (2h). The following are 3-divisible-matchings of type (06h;2; ; ; ) and other matchings used above. (06h+1;2;2;2): from Lemma 3.4 By Property 2, a 3-divisible-matching of type (06h+1;ap?2;ap?1;ap) exists if ap ? ap?2. Hence we must have (06h+1;ap;ap;ap). (06h+1;ap;ap;ap) from ap=2 copies of (06h+1;2;2;2) 70 (06h;2;2;2;2): from Lemma 3.4 (06h;2;2;2;4): from Lemma 3.4 By Property 2, a 3-divisible-matching of type (06h;2;ap?2;ap?1;ap) exists if ap?2 ? ap ?2. (06h;2;ap;ap;ap) from (06h;2;2;2;2) and (ap ?2)=2 copies of (06h+1;2;2;2) (06h;2;ap ?2;ap;ap) from (06h;2;0;2;2) and (ap ?2)=2 copies of (06h+1;2;2;2) Since ap ? 2, ap ?2 ? 0. (06h;2;ap ?2;ap ?2;ap) from (06h;2;2;2;4) and (ap ?4)=2 copies of (06h+1;2;2;2) Since ap ?2 ? 2, ap ?4 ? 0. (06h?1;2;2;2;2;2): from Lemma 3.4 (06h?1;2;2;2;2;6): from Lemma 3.4 For c ? 1 we have (04h+c+2;22h?c+1;4h?2c) from Lemma 3.4 (04h+2;22h+1;4h): Needed; not yet found. Therefore we have 3-divisible-matchings for p = 4 (mod 6). Once the missing matchings are found, this will prove the su?ciency of the necessary conditions listed in Section 3.1. 3.3 k-divisible-matchings When p ? 1 (mod 2k), say p = 2kh + 1, Property 4 is 2khap ? (2kh ? k)(a1 + ::: + ap?1) and when p ? (1 + k) (mod 2k), say p = 2kh + k + 1, it is (2kh + k)ap ? (2kh)(a1 +:::+ap?1). 71 3.3.1 Any number of parts of the same size For the case of same sized parts we need to construct k-divisible-matchings of types (12k+1), (22k+1) and (23k+1). Following are those matchings. (12k+1): M1: ff2;3g;f4;5g;:::;f2k;2k +1gg For 1 ? i ? k: M2i: ff2i+1;2i+2g;f2i+3;2i+4g;:::;f2k +1;1g;:::;f2i?2;2i?1gg For 1 ? i ? k?1: M2i+1: ff2i+2;2i+3g;f2i+4;2i+5g;:::;f2k;2k +1g;:::;f2i?1;2igg And flnally, M2k+1: ff1;2g;f3;4g;:::;f2k?1;2kgg (22k+1): M1: ff2;3g;f4;5g;:::;f2k;2k +1gf20;30g;f40;50g;:::;f(2k)0;(2k +1)0gg For 1 ? i ? k: M2i: ff2i+1;2i+2g;f2i+3;2i+4g;:::;f2k +1;1g;:::;f2i?2;2i?1g; f(2i+1)0;(2i+2)0g;f(2i+3)0;(2i+4)0g;:::;f(2k +1)0;10g;:::;f(2i?2)0;(2i?1)0gg For 1 ? i ? k?1: M2i+1: ff2i+2;2i+3g;f2i+4;2i+5g;:::;f2k;2k +1g;f1;2g;:::;f2i?1;2ig; f(2i+2)0;(2i+3)0g;f(2i+4)0;(2i+5)0g;:::;f(2k)0;(2k+1)0g;f10;20g;:::;f(2i?1)0;(2i)0gg And flnally, M2k+1: ff1;2g;f3;4g;:::;f2k?1;2kg;f10;20g;f30;40g;:::;f(2k?1)0;(2k)0gg It is clear that each edge shows up k times. Take an edge (a;a+1) or (a0;(a+1)0) it will only show up in Mi for all odd i or all even i. It will also not show up in Ma or Ma+1. 72 (23k+1): M1: ff2;3g;f20;4g;f30;40g;:::;f3k?1;3kg;f(3k?1)0;3k +1g;f(3k)0;(3k +1)0gg M2: ff3;4g;f30;5g;f40;50g;:::;f3k;3k +1g;f(3k)0;1g;f(3k +1)0;10gg M3: ff4;5g;f40;6g;f50;60g;:::;f3k +1;1g;f(3k +1)0;2g;f10;20gg For 2 ? i ? k: M3i?1: ff3i;3i+1g;f(3i)0;3i+2g;f(3i+1)0;(3i+2)0g;:::;f3k;3k +1g;f(3k)0;1g; f(3k +1)0;10g;f2;3g;f20;4g;f30;40g;:::;f3i?4;3i?3g;f(3i?4)0;3i?2g; f(3i?3)0;(3i?2)0gg For 2 ? i ? k: M3i: ff3i+1;3i+2g;f(3i+1)0;3i+3g;f(3i+2)0;(3i+3)0g;:::;f3k +1;1g; f(3k +1)0;2g;f10;20g;f3;4g;f30;5g;f40;50g;:::;f3i?3;3i?2g;f(3i?3)0;3i?1g; f(3i?2)0;(3i?1)0gg For 1 ? i ? k?1: M3i+1: ff3i+2;3i+3g;f(3i+2)0;3i+4g;f(3i+3)0;(3i+4)0g;:::;f3k?1;3kg; f(3k?1)0;3k +1g;f(3k)0;(3k +1)0g;f1;2g;f10;3g;f20;30g;:::;f3i?2;3i?1g; f(3i?2)0;3ig;f(3i?1)0;(3i)0gg And flnally, M3k+1: ff1;2g;f10;3g;f20;30g;:::;f3k?2;3k?1gf(3k?2)0;3kg;f(3k?1)0;(3k)0gg Each edge appears 3k+1?13 = k times. Hence it is a k-divisible-matching. 73 3.3.2 2k +1 parts of any size In this Section we will give k-divisible-matchings of type K = (a1;a2;:::;a2k+1). We canhaveallpartsofevensizeorallpartsofoddsize. Wewilluseasimilaralgorithmasfor even matchings to construct a k-divisible-matching from (02k?3;2; ; ; ) or (12k?1; ; ). 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = ::: = a2k?3 = 0, and a2k?2 = 0;2, a1 = ::: = a2k?2 = 1 or K = (02k?4;2;2;2;2;2) look up the matching in list provided. Otherwise continue below. 2. For 0 ? i ? 2k?3 repeat the following steps. 3. Subtract (0i;2;02k?2?i;2;2) and rearrange terms when necessary until you obtain (02k?3;2; ; ; ) or (12k?1; ; ; ). Look the appropriate ones up in list provided. If at any point K = (02k?4;2;2;2;2;2) look it up. 4. Subtract(02k?2;2;2;2)andrearrangetermswhennecessaryuntilyouobtain(12k?1; ; ). Look it up. Let us consider the four necessary conditions during the flrst part of the \subtracting process." Notice that for p = 2k +1 condition 4 becomes 3a2k+1 ? n. 1. p = 2k +1 is not afiected. 2. If (a1;a2;:::;a2k+1) satisfles 2a2k+1 +a2k ? a1 +:::+a2k +a2k+1, then (a1?2;a2;:::;a2k?2;a2k+1?2) satisfles 2(a2k+1?2)+(a2k?2) ? (a1?2)+a2+ :::+ (a2k ?2) + (a2k+1 ?2). We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: 74 Case 1: If after such rearranging a2k+1?2 is not the largest, but the second largest part, then a2k?1 = a2k+1. So we started with (a1;a2;:::;a2k+1;a2k+1;a2k+1) and now have (a1 ? 2;a2;:::;a2k+1 ? 2;a2k+1 ? 2;a2k+1). By Properties 2 and 4 (a1 ?2;a2;:::;a2k+1 ?2;a2k+1 ?2;a2k+1) is in Sk as long as 6 ? a1 +a2 +:::+ a2k?2. Let us consider the case when a1 + a2 + ::: + a2k?2 < 6. We could have (02k?2;a2k+1;a2k+1;a2k+1), (02k?3;2;a2k+1;a2k+1;a2k+1), (02k?3;4;a2k+1;a2k+1;a2k+1), or(02k?4;2;2;a2k+1;a2k+1;a2k+1). Eachoneofthose is discussed and shown to be in Sk below. Case 2: If after rearranging a2k+1?2 is not the largest or second largest part, then a2k?2 = a2k?1 = a2k+1. So we started with (a1;a2;:::;a2k+1;a2k+1;a2k+1;a2k+1) and now have (a1?2;a2;:::;a2k+1?2;a2k+1?2;a2k+1;a2k+1). By Properties 2 and 4 (a1?2;a2;:::;a2k+1?2;a2k+1?2;a2k+1;a2k+1) is in Sk as long as 6 ? a1+a2+ :::+a2k?3+a2k+1. Let us consider the case when 6 > a1+a2+:::+a2k?3+a2k+1. We could have (02k?3;2;2;2;2), (02k?3;4;4;4;4), or (02k?4;2;2;2;2;2). Each one of those is covered by Case 1. Case 3: If after rearranging a2k+1 ?2 is the largest, but a2k ?2 is not the second largestpart, thena2k?1 = a2k. Sowestartedwith(a1;a2;:::;a2k?2;a2k;a2k;a2k+1) and now have (a1 ?2;a2;:::;a2k?2;a2k ?2;a2k;a2k+1 ?2). By Property 2, (a1 ?2;a2;:::;a2k?2;a2k ?2;a2k;a2k+1 ?2) is in Sk as long as a2k+1 6= a1 +a2 + ::: + a2k?2 + a2k. When a2k+1 = a1 + a2 + ::: + a2k?2 + a2k and a2k?1 = a2k we have types of the form (a1;a2;:::;a2k?2;a2k+1 ? (a1 + ::: + a2k?2);a2k+1 ? (a1 + ::: + a2k?2);a2k+1). By Property 4 this implies a1 + a2 + ::: + a2k?2 ? 0. Hence we must have 75 (02k?2;a2k;a2k;a2k+1) and by Property 2, a2k+1 ? a2k ? a2k+1. Types (02k?2;a2k+1;a2k+1;a2k+1) are discussed below as valid. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;a2;:::;a2k;a2k+1) satisfles 3a2k+1 ? (a1 + a2 + ::: + a2k+1), then (a1 ? 2;a2;:::;a2k?2;a2k+1?2) satisfles 3(a2k+1?2) ? ((a1?2)+a2+:::+(a2k?2)+ (a2k+1 ?2)). Problems arising from rearranging of the terms are discussed under Property 2. This is also true for the remaining parts of the algorithm. Therefore, each time we subtract we obtain an element of Sk. We will need the following \building blocks." (02k?2;2;2;2): For 1 ? i ? k?1: M2i?1: ff2k?1;2kg;f(2k?1)0;2k +1g;f(2k)0;(2k +1)0gg M2i: ff2k?1;(2k +1)0g;f(2k?1)0;(2k)0g;f2k;2k +1gg And flnally, M2k?1: ff2k;2k +1g;f(2k)0;(2k +1)0gg M2k: ff2k?1;(2k +1)0g;f(2k?1)0;2k +1gg M2k+1: ff2k?1;2kg;f(2k?1)0;(2k)0gg (02k?3;2;2;2;2): For 1 ? i ? k?1: M2i?1: ff2k?2;2k?1g;f(2k?2)0;(2k?1)0g;f2k;2k +1g;f(2k)0;(2k +1)0gg For 1 ? i ? k?2: 76 M2i: ff2k?2;2k +1g;f(2k?2)0;2kg;f(2k?1)0;(2k)0g;f2k?1;(2k +1)0gg M2k?2: ff2k?1;(2k +1)0g;f(2k?1)0;(2k)0g;f2k;2k +1gg M2k?1: ff2k?2;2k +1g;f(2k?2)0;2kg;f(2k)0;(2k +1)0gg M2k: ff2k?2;2k +1g;f(2k?2)0;(2k?1)0g;f2k?1;(2k +1)0gg M2k+1: ff2k?2;2k?1g;f(2k?2)0;2kg;f(2k?1)0;(2k)0gg (03k?2;2;2;2): For 1 ? i ? k?1: M3i?2: ff3k?1;3kg;f(3k?1)0;3k +1g;f(3k)0;(3k +1)0gg M3i?1: ff3k?1;3k +1g;f(3k?1)0;(3k)0g;f3k;(3k +1)0gg M3i: ff3k?1;(3k)0g;f(3k?1)0;(3k +1)0g;f3k;3k +1gg M3k?2: ff3k?1;(3k)0g;f(3k?1)0;3k +1g;f3k;(3k +1)0gg M3k?1: ff3k;3k +1g;f(3k)0;(3k +1)0gg M3k: ff3k?1;3k +1g;f(3k?1)0;(3k +1)0gg M3k+1: ff3k?1;3kg;f(3k?1)0;(3k)0gg Following is a list of k-divisible-matchings of type (12k?1; ; ). (12k+1) given in Section 3.3.1 (12k;3), k ? 3: M1: ff2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;7g;:::;f2k;2k +1gg M2: ff1;2k +1g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;:::;f2k?1;2kgg M3: ff1;2g;f4;(2k +1)0g;f5;(2k +1)00g;f6;7g;:::;f2k;2k +1gg M4: ff1;2k +1g;f2;(2k +1)0g;f3;(2k +1)00g;f5;6g;:::;f2k?1;2kgg M5: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f6;7g;:::;f2k;2k +1gg M6: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f7;8g;:::;f2k?1;2kgg 77 M7: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;f8;9g;:::;f2k;2k +1gg M8: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;7g;f9;10g;:::;f2k?1;2kgg For 4 ? j ? k M2j?1: ff1;2g;f3;(2k+1)00g;f4;(2k+1)0g;f5;6g;:::;f2j?3;2j?2g;f2j;2j +1g;:::; f2k;2k +1gg For 4 ? j ? k?1 M2j: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;7g;:::;f2j ?2;2j ?1g; f2j +1;2j +2g;:::;f2k?1;2kgg And flnally, M2k: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;7g;:::;f2k?2;2k?1gg M2k+1: ff1;2g;f3;4g;f5;6g;:::;f2k?1;2kgg (12k;5), k ? 5: M1: ff2;(2k+1)0g;f3;4g;f5;(2k+1)00g;f6;(2k+1)000g;f7;8g;f9;(2k+1)4g;f10;11g;:::; f2k;2k +1gg M2: ff1;2k+1g;f3;(2k+1)00g;f4;(2k+1)0g;f5;6g;f7;(2k+1)4g;f8;(2k+1)000g;f9;10g;:::; f2k?1;2kgg M3: ff1;2g;f4;(2k+1)0g;f5;(2k+1)00g;f6;(2k+1)000g;f7;8g;f9;(2k+1)4g;f10;11g;:::; f2k;2k +1gg M4: ff1;2k+1g;f2;(2k+1)0g;f3;(2k+1)00g;f5;6g;f7;(2k+1)4g;f8;(2k+1)000g;f9;10g;:::; f2k?1;2kgg M5: ff1;2g;f3;(2k+1)00g;f4;(2k+1)0g;f6;(2k+1)000g;f7;8g;f9;(2k+1)4g;f10;11g;:::; f2k;2k +1gg M6: ff1;2k+1g;f2;(2k+1)0g;f3;4g;f5;(2k+1)00g;f7;(2k+1)4g;f8;(2k+1)000g;f9;10g;:::; 78 f2k?1;2kgg M7: ff1;2g;f3;(2k+1)00g;f4;(2k+1)0g;f5;6g;f8;(2k+1)000g;f9;(2k+1)4g;f10;11g;:::; f2k;2k +1gg M8: ff1;2k+1g;f2;(2k+1)0g;f3;4g;f5;(2k+1)00g;f6;(2k+1)000g;f7;(2k+1)4g;f9;10g;:::; f2k?1;2kgg M9: ff1;2g;f3;(2k+1)00g;f4;(2k+1)0g;f5;6g;f7;(2k+1)4g;f8;(2k+1)000g;f10;11g;:::; f2k;2k +1gg M10: ff1;2k+1g;f2;(2k+1)0g;f3;4g;f5;(2k+1)00g;f6;(2k+1)000g;f7;8g;f9;(2k+1)4g; f11;12g;:::;f2k?1;2kgg For 6 ? j ? k M2j?1: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;f7;(2k +1)4g;f8;(2k +1)000g;f9;10g;:::; f2j ?3;2j ?2g;f2j;2j +1g;:::;f2k;2k +1gg For 6 ? j ? k?1 M2j: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;(2k +1)000g;f7;8g;f9;(2k +1)4g; f10;11g;:::;f2j ?2;2j ?1g;f2j +1;2j +2g;:::;f2k?1;2kgg And flnally, M2k: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;(2k +1)000g;f7;8g;f9;(2k +1)4g; f10;11g;:::;f2k?2;2k?1gg M2k+1: ff1;2g;f3;4g;f5;6g;:::;f2k?1;2kgg 79 (12k;i), 3 ? i ? 2dk2e?1: M1: ff2;(2k +1)0g;f3;4g;f5;(2k +1)00g;:::;f2i?4;(2k +1)i?2g;f2i?3;2i?2g; f2i?1;(2k +1)i?1g;f2i;2i+1g;:::;f2k;2k +1gg M2: ff1;2k +1g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;:::;f2i?3;(2k +1)i?1g; f2i?2;(2k +1)i?2g;f2i?1;2ig;f2i+1;2i+2g;:::;f2k?1;2kgg M3: ff1;2g;f4;(2k +1)0g;f5;(2k +1)00g;f6;(2k +1)000g;f7;8g;f9;(2k +1)4g;:::; f2i?4;(2k +1)i?2g;f2i?3;2i?2g;f2i?1;(2k +1)i?1g;f2i;2i+1g;:::;f2k;2k +1gg M4: ff1;2k +1g;f2;(2k +1)0g;f3;(2k +1)00g;f5;6g;:::;f2i?3;(2k +1)i?1g; f2i?2;(2k +1)i?2g;f2i?1;2ig;f2i+1;2i+2g;:::;f2k?1;2kgg M5: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f6;(2k +1)000g;f7;8g;f9;(2k +1)4g;:::; f2i?4;(2k +1)i?2g;f2i?3;2i?2g;f2i?1;(2k +1)i?1g;f2i;2i+1g;:::;f2k;2k +1gg M6: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;:::;f2i?3;(2k +1)i?1g; f2i?2;(2k +1)i?2g;f2i?1;2ig;f2i+1;2i+2g;:::;f2k?1;2kgg M7: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;f8;(2k +1)000g;f9;(2k +1)4g;:::; f2i?4;(2k +1)i?2g;f2i?3;2i?2g;f2i?1;(2k +1)i?1g;f2i;2i+1g;:::;f2k;2k +1gg M8: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;(2k +1)000g;f7;(2k +1)4g; f9;10g;:::;f2i?3;(2k +1)i?1g;f2i?2;(2k +1)i?2g;f2i?1;2ig;f2i+1;2i+2g;:::; f2k?1;2kgg For 6 ? i ? k?1: M2i?3: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;f7;(2k +1)4g;f8;(2k +1)000g;:::; f2i?5;2i?4g;f2i?2;(2k+1)i?2g;f2i?1;(2k+1)i?1g;f2i;2i+1g;f2i+2;2i+3g;:::; f2k;2k +1gg M2i?2: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;(2k +1)000g;f7;8g; 80 f9;(2k +1)4g;:::;f2i?4;(2k +1)i?2g;f2i?3;(2k +1)i?1g;f2i?1;2ig; f2i+1;2i+2g;:::;f2k?1;2kgg M2i?1: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;f7;(2k +1)4g;f8;(2k +1)000g;:::; f2i?5;2i?4g;f2i?3;(2k+1)i?1g;f2i?2;(2k+1)i?2g;f2i;2i+1g;f2i+2;2i+3g;:::; f2k;2k +1gg M2i: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;(2k +1)000g;f7;8g; f9;(2k +1)4g;:::;f2i?4;(2k +1)i?2g;f2i?3;2i?2g;f2i?1;(2k +1)i?1g; f2i+1;2i+2g;:::;f2k?1;2kgg M2i+1: ff1;2g;f3;(2k +1)00g;f4;(2k +1)0g;f5;6g;f7;(2k +1)4g;f8;(2k +1)000g;:::; f2i?5;2i?4g;f2i?3;(2k+1)i?1g;f2i?2;(2k+1)i?2g;f2i?1;2ig;f2i+2;2i+3g;:::; f2k;2k +1gg M2i+2: ff1;2k +1g;f2;(2k +1)0g;f3;4g;f5;(2k +1)00g;f6;(2k +1)000g;f7;8g; f9;(2k+1)4g;:::;f2i?4;(2k+1)i?2g;f2i?3;2i?2g;f2i?1;(2k+1)i?1g;f2i;2i+1g; f2i+3;2i+4g;:::;f2k?1;2kgg And flnally, M2k+1: ff1;2g;f3;4g;f5;6g;:::;f2k?1;2kgg (12k?1;3;3) : M1: ff2;(2k +1)0g;f3;(2k)00g;f4;(2k +1)00g;f5;6g;:::;f2k?1;2kg;f(2k)0;2k +1gg M2: ff1;(2k)00g;f3;2k +1g;f4;(2k)0g;f5;(2k +1)0g;f6;7g;:::;f2k?2;2k?1g; f2k;(2k +1)00gg M3: ff1;(2k)00g;f2;(2k +1)0g;f4;(2k +1)00g;f5;6g;:::;f2k?1;2kg;f(2k)0;2k +1gg M4: ff1;2g;f3;(2k)00g;f5;(2k +1)0g;f6;7g;:::;f2k?2;2k?1g;f2k;(2k +1)00g; f(2k)0;2k +1gg 81 M5: ff1;(2k)00g;f2;(2k +1)0g;f3;2k +1g;f4;(2k)0g;f6;7g;:::;f2k;(2k +1)00gg M6: ff1;2g;f3;(2k)00g;f4;(2k+1)00g;f5;(2k+1)0g;f7;8g;:::;f2k?1;2kg;f(2k)0;2k+1gg For 4 ? j ? k: M2j?1: ff1;(2k)00g;f2;(2k +1)0g;f3;2k +1g;f4;(2k)0g;f5;6g;:::;f2j ?3;2j ?2g; f2j;2j +1g;:::;f2k;(2k +1)00gg For 4 ? j ? k?1: M2j: ff1;2g;f3;(2k)00g;f4;(2k +1)00g;f5;(2k +1)0g;f6;7g;:::;f2j ?2;2j ?1g; f2j +1;2j +2g;:::;f2k?1;2kg;f(2k)0;2k +1gg And flnally, M2k: ff1;2g;f3;2k +1g;f4;(2k +1)00g;f5;(2k +1)0g;f6;7g;:::;f2k?2;2k?1gg M2k+1: ff1;2g;f3;(2k)00g;f4;(2k)0g;f5;6g;:::;f2k?1;2kgg The following matchings are needed and are yet unfound. (12k?1;3;i), for 5 ? i ? 2bk2c+1 (12k?1;5;i), for 5 ? i ? 2dk2e+1 (12k?1;7;i), for 7 ? i ? 2bk2c+3 In general, (12k?1;d;i), d ? i ? 2bk2c+ d?12 if d ? 3 (mod4) (12k?1;d;i), d ? i ? 2dk2e+ d?32 if d ? 1 (mod4) Following is a list of k-divisible-matchings of types (02k?3;2; ; ; ) as well as (02k?4;2;2;2;2;2). (02k?4;2;2;2;2;2): For 1 ? i ? k?2: M2i?1: ff2k?3;2k+1g;f(2k?3)0;(2k?2)0g;f2k?2;(2k?1)0g;f2k?1;2kg;f(2k)0;(2k+ 82 1)0gg M2i: ff2k?3;2k?2g;f(2k?3)0;(2k+1)0g;f(2k?2)0;2k?1g;f(2k?1)0;(2k)0g;f2k;2k+1gg Finally, M2k?3: ff2k?2;(2k?1)0g;f(2k?2)0;2k?1g;f2k;2k +1g;f(2k)0;(2k +1)0gg M2k?2: ff2k?3;2k +1g;f(2k?3)0;(2k +1)0g;f(2k?1)0;(2k)0g;f2k?1;2kgg M2k?1: ff2k?3;2k?2g;f(2k?3)0;(2k?2)0g;f2k;2k +1g;f(2k)0;(2k +1)0gg M2k: ff2k?3;2k +1g;f(2k?3)0;(2k +1)0g;f(2k?2)0;2k?1g;f2k?2;(2k?1)0gg M2k+1: ff2k?3;2k?2g;f(2k?3)0;(2k?2)0g;f2k?1;2kg;f(2k?1)0;(2k)0gg (02k?2;2;2;2) given in Section 3:3:2 (02k?2;d;d;d)=d2 copies of (02k?2;2;2;2) (02k?3;2;2;2;2) given in Section 3:3:2 (02k?3;2;d;d;d) from (02k?3;2;2;2;2) and (d?2)=2 copies of (02k?2;2;2;2) (02k?3;2;d;d+2;d+2) from (02k?3;2;0;2;2) and d=2 copies of (02k?2;2;2;2) This gives the k-divisible-matchings with 2k +1 parts. 3.3.3 3k +1 parts of any size In this Section we will give k-divisible-matchings of type K = (a1;a2;:::;a3k+1). We can only have all parts of even size. We will use a similar algorithm as above to construct a k-divisible-matching from (03k?3;2; ; ; ). 1. Check if the four necessary conditions are satisfled. If not, the matching does not exist. If a1 = ::: = a3k?3 = 0, a3k?2 = 0;2 or K = (03k?4;2;2;2;2;2) look up the matching in list provided. Otherwise continue below. 83 2. If 5a3k+1 = 2n skip down to the Special Case 1 section. If a3k?1 = a3k and a3k+1 = a1 +a2 +a3 +:::+a3k?1 skip down to Special Case 2 section. Otherwise continue below. 3. For 0 ? i ? 3k?3 subtract (0i;2;03k?2?i;2;2) and rearrange terms when necessary until you obtain (03k?3;2; ; ; ). Look those up in the list provided. If at any point K = (03k?4;2;2;2;2;2) look it up. Let us consider the four necessary conditions during the flrst part of the \subtracting process." Notice that for p = 3k +1 condition 4 becomes 5a3k+1 ? 2n. 1. p = 3k +1 is not afiected. 2. If (a1;a2;:::;a3k+1) satisfles 2a3k+1 +a3k ? a1 +:::+a3k +a3k+1, then (a1 ?2;a2;:::;a3k ?2;a3k+1 ?2) satisfles 2(a3k+1 ? 2) + (a3k ? 2) ? (a1 ? 2) + a2 + ::: + (a3k ? 2) + (a3k+1 ? 2). We are, however, rearranging the terms to ensure a nondecreasing sequence. Let us consider the following cases: Case 1: If after such rearranging a3k+1?2 is not the largest, but the second largest part, then a3k?1 = a3k+1. So we started with (a1;a2;:::;a3k+1;a3k+1;a3k+1) and now have (a1 ?2;a2;:::;a3k+1 ?2;a3k+1 ?2;a3k+1). By Properties 2 and 4 (a1 ? 2;a2;:::;a3k+1 ?2;a3k+1 ?2;a3k+1) is in Sk as long as 4 ? a1 + a2 + ::: + a3k?2 and 12 ?a3k+1 ? 2(a1 + a2 + ::: + a3k?2). Let us consider the cases when a1 + a2 +:::+a3k?2 < 4 or 2(a1 +a2 +:::+a3k?2) < 12?a3k+1. We could have (03k?2;a3k+1;a3k+1;a3k+1), (03k?3;2;a3k+1;a3k+1;a3k+1) or (03k?4;2;2;2;2;2). Each one of those is discussed 84 and shown to be in Sk below. Case 2: If after rearranging a3k+1?2 is not the largest or second largest part, then a3k?2 = a3k?1 = a3k+1. So we started with (a1;a2;:::;a3k+1;a3k+1;a3k+1;a3k+1) and now have (a1?2;a2;:::;a3k+1?2;a3k+1?2;a3k+1;a3k+1). By Properties 2 and 4 (a1 ?2;a2;:::;a3k+1 ?2;a3k+1 ?2;a3k+1;a3k+1) is in Sk as long as 6?a3k+1 ? a1 +a2 +:::+a3k?3 and 12?3a3k+1 ? 2(a1 +a2 +:::+a3k?3). Let us consider the case when 6?a3k+1 > a1 + a2 + ::: + a3k?3 or 12?3a3k+1 > 2(a1 + a2 + ::: + a3k?3). We could have (03k?3;2;2;2;2), (03k?3;4;4;4;4), or (03k?4;2;2;2;2;2). Each one of those is discussed below. Case 3: If after rearranging a3k+1 ?2 is the largest, but a3k ?2 is not the second largestpart, thena3k?1 = a3k. Sowestartedwith(a1;a2;:::;a3k?2;a3k;a3k;a3k+1) and now have (a1 ?2;a2;:::;a3k?2;a3k ?2;a3k;a3k+1 ?2). By Property 2, (a1 ?2;a2;:::;a3k?2;a3k ?2;a3k;a3k+1 ?2) is in Sk as long as a3k+1 6= a1 +a2 + :::+a3k?2+a3k. The case when a3k?1 = a3k and a3k+1 = a1+a2+:::+a3k?2+a3k is discussed below as Special Case 2. 3. Since we are subtracting zeroes and twos, the parity of the parts is not afiected. Neither is the number of parts. 4. If (a1;a2;:::;a3k;a3k+1) satisfles 5a3k+1 < 2(a1 +a2 +:::+a3k+1), then (a1 ?2;a2;:::;a3k ?2;a3k+1 ?2) satisfles 5(a3k+1 ? 2) ? 2((a1 ? 2) + a2 + ::: + (a3k ? 2) + (a3k+1 ? 2)). The case when 5a3k+1 = 2n is discussed below as Special Case 1. 85 This is also true for the remaining parts of the algorithm. Therefore, each time we subtract we obtain an element of Sk. Let us consider the Special Case 1. We need to flnd even matchings for (a1;:::;a3k+1) satisfying the four necessary condi- tions and 3a3k+1 = 2(a1 +:::+a3k). Let us refer to these as matching type SPk1 Sk. Say we need K = (a1;a2;:::;a3k; 2(a1+:::+a3k)3 ) 2 SPk1. We will build it by induction. We start by subtracting (03k?3;2;2;2;4) to obtain K0 = (a1;:::;a3k?3;a3k?2 ? 2;a3k?1?2;a3k?2; 2(a1+:::+a3k)3 ?4). As long as no rearranging is necessary K0 is in SPk1. If rearranging is necessary, we started with K = (a1;:::;a3k?4;a3k;:::;a3k; 2(a1+:::+a3k)3 ) and now have K00 = (a1;:::;a3k?4;a3k ?2;a3k ?2;a3k ?2;a3k; 2(a1+:::+a3k)3 ?4). This is in SPk1 as long as 6 ? a1 +:::+a3k?4 +a3k. The only time 6 > a1 +:::+a3k?4 +a3k is for K = (03k?3;23;4) which is given. We need to consider if it is possible for a3k > 2(a1+:::+a3k) 3 ?4. This is equivalent to 8 ? a1 +:::+a3k?1 which is true for all elements of SPk1 except K = (03k?3;23;4). By induction, this concludes Special Case 1. We take any element of SPk1 and subtract to get a smaller element of SPk1. Now let us consider Special Case 2. If a3k?1 = a3k and a3k+1 = a1 +:::+a3k?2 +a3k we have types of the form (a1;a2;:::;a3k?2;a3k+1 ?(a1 +:::+a3k?2);a3k+1 ?(a1 + :::+ a3k?2);a3k+1). We will construct a k-divisible-matching of such type as follows: a1=2 copies of (2;03k?3;2;2;4), a2=2 copies of (0;2;03k?4;2;2;4), :::, a3k?2=2 copies of (03k?3;2;2;2;4) and (a3k+1 ? 2(a1 + ::: + a3k?2))=2 copies of (03k?2;2;2;2). Notice that by Property 4 a3k+1 ? 2(a1 +:::+a3k?2). This concludes Special Case 2. 86 Following is a list of k-divisible-matchings of types (03k?3;2; ; ; ) as well as (03k?4;2;2;2;2;2). (03k?4;2;2;2;2;2): For 1 ? i ? k?2: M2i?1: ff3k?3;3k?2g;f(3k?3)0;3k+1g;f(3k?2)0;(3k?1)0g;f3k?1;3kg;f(3k)0;(3k+1)0gg M2i: ff3k?3;(3k+1)0g;f(3k?3)0;(3k?2)0g;f3k?2;3k?1g;f(3k?1)0;(3k)0g;f3k;3k+1gg For k?1 ? i ? 2k?2: Mk?2+i: ff3k?3;3k?2g;f(3k?3)0;3k?1g;f(3k?2)0;(3k?1)0g;f(3k)0;(3k+1)0g;f3k;3k+1gg And flnally, M3k?3: ff3k?2;3k?1g;f(3k?2)0;(3k?1)0g;f(3k)0;(3k +1)0g;f3k;3k +1gg M3k?2: ff3k?3;(3k +1)0g;f(3k?3)0;3k +1g;f(3k?1)0;(3k)0g;f3k?1;3kgg M3k?1: ff3k?3;3k?2g;f(3k?3)0;(3k?2)0g;f3k;3k +1g;f(3k)0;(3k +1)0gg M3k: ff3k?3;(3k +1)0g;f(3k?3)0;3k +1g;f(3k?2)0;(3k?1)0g;f3k?2;3k?1gg M3k+1: ff3k?3;3k?2g;f(3k?3)0;(3k?2)0g;f3k?1;3kg;f(3k?1)0;(3k)0gg (03k?2;2;2;2) given in Section 3:3:1 87 By Property 2, a k-divisible-matching of type (03k?2;a3k?1;a3k;a3k+1) exists if a3k+1 ? a3k?1 ? a3k+1. (03k?2;a3k+1;a3k+1;a3k+1)=a3k+12 copies of (03k?2;2;2;2) (03k?3;2;2;2;2): For 1 ? i ? k?1: M3i?2: ff3k?2;(3k)0g;f(3k?2)0;(3k +1)0g;f3k?1;3kg;f(3k?1)0;3k +1gg M3i?1: ff3k?2;3k?1g;f(3k?2)0;(3k?1)0g;f3k;3k +1g;f(3k)0;(3k +1)0gg M3i: ff3k?2;3k +1g;f(3k?2)0;3kg;f3k?1;(3k +1)0g;f(3k?1)0;(3k)0gg Finally, M3k?2: ff3k?1;3kg;f(3k?1)0;3k +1g;f(3k)0;(3k +1)0gg M3k?1: ff3k?2;(3k)0g;f(3k?2)0;(3k +1)0g;f3k;3k +1gg M3k: ff3k?2;3k +1g;f(3k?2)0;(3k?1)0g;f3k?1;(3k +1)0gg M3k+1: ff3k?2;3k?1g;f(3k?2)0;3kg;f(3k?n1)0;(3k)0gg (03k?3;2;2;2;4): For 1 ? i ? k?1: M3i?2: ff3k?2;(3k+1)000g;f(3k?2)0;(3k+1)0g;f3k?1;(3k+1)00g;f(3k?1)0;(3k)0g;f3k;3k+1gg M3i?1: ff3k?2;3k?1g;f(3k?2)0;(3k+1)00g;f(3k?1)0;(3k+1)000g;f(3k)0;3k+1g;f3k;(3k+1)0gg M3i: ff3k?2;3k+1g;f(3k?2)0;3kg;f3k?1;(3k+1)00g;f(3k?1)0;(3k+1)000g;f(3k)0;(3k+1)0gg Finally, M3k?2: 88 ff3k?1;(3k +1)00g;f(3k?1)0;(3k +1)000g;f(3k)0;(3k +1)0g;f3k;3k +1gg M3k?1: ff3k?2;(3k +1)000g;f(3k?2)0;(3k +1)00g;f3k;(3k +1)0g;f(3k)0;3k +1gg M3k: ff3k?2;3k +1g;f(3k?2)0;(3k +1)0g;f(3k?1)0;(3k +1)000g;f3k?1;(3k +1)00gg M3k+1: ff3k?2;3k?1g;f(3k?2)0;3kg;f(3k?1)0;(3k)0gg By Property 2, a k-divisible-matching of the type (03k?3;2;a3k?1;a3k;a3k+1) exists if a3k+1 ? a3k?1 +2. (03k?3;2;a3k?1;a3k?1;a3k?1) from (03k?3;2;2;2;2) and (a3k?1 ?2)=2 copies of (03k?2;2;2;2) (03k?3;2;a3k?1;a3k?1;a3k?1 +2) from (03k?3;2;2;2;4) and (a3k?1 ?2)=2 copies of (03k?2;2;2;2) (03k?3;2;a3k?1;a3k?1 +2;a3k?1 +2) from (03k?3;2;0;2;2) and a3k?1=2 copies of (03k?2;2;2;2) This gives the k-divisible-matchings with 3k+1 parts. It is left for future research to consider the generalization of k-divisible-matchings with p = 2kh+1 and p = 2kh+k+1 for h ? 2. 89 Bibliography [1] E. J. Billington and D. G. Hofiman, \Equipartite and almost- equipartite gregarious 4-cycle systems," Discrete Mathematics, 2007. To appear. 90