Combinatorial Constructions For Threshold Schemes

This dissertation investigates two kinds of combinatorial designs, Kirkman packing designs and large sets of group-divisible designs. They can be used to construct threshold schemes.In Chapter 2. we show how to form (2.iu)-threshold schemes by using Kirkman packing designs KPD({w. s*}, v)s. For v = 2 (mod 3), KPD({3, 5*}, v)s are used to construct (2, 3)-threshold schemes. With both direct and recursive constructions, we solve the existence of KPD({3, 5*}. i')s, leaving 11 possible exceptions of v.In 1989, Schellenberg and Stinson showed that (2,3)-threshold schemes can be constructed from large sets of group-divisible designs. In order to study the existence of LS(2n41)s, we define in Chapter 3 a special large set, called *LS(2n). Recursive constructions for *LS(2")s are also presented, including a product construction, two tripling constructions and a quadrupling construction. Except possibly when n 6 {18} U {2m + 2 : m = 1,5 (mod 6)}, the existence of *LS(2n)s is solved.In Chapter 4. we first give the necessary condition for LS(2"41)s. Then we use *LS(2n) and its generalization LS(2U+2, 2U+2) to show that the necessary condition is also sufficient, except possibly when n {12,36,48, 144} U {n > 0 : n = 6m, m = 1, 5 (mod 6)}.In Chapter 5, we improve the known results on KPD({3,4*}, u)s by giving the constructions for five values of v. We also obtain some new results on KPD({4, s*}, v)s for s = 5, 6. Finally, we present some open problems for further study.