Special Block-Colourings of Steiner 2-Designs

Abstract

<p> Let t, k, v be three positive integers such that 2 ≤ t < k ≤ v. A Steiner system S(t, k, v) is a pair (V, B) where |V| = v and B is a collection of k-subsets of V, called blocks, such that every t-subset of V occurs in exactly one block in B. When t = 2, the Steiner system S(2, k, v) is sometimes called a Steiner 2-design.</p> <p> Given a Steiner 2-design, S = (V, B), with general block size k, a block-colouring of S is a mapping ¢ : B ---> C, where C is a set of colours. If |C| = n, then ¢ is an n-block-colouring. In this thesis we focus on block-colourings for Steiner 2-designs with k = 4 with some results for general block size k.</p> <p> In particular, we present known results for S(2, 4, v)s and the classical chromatic index. A classical block-colouring is a block-colouring in which any two blocks containing a common element have different colours. The smallest number of colours needed in a classical block-colouring of a design S = (V, B), denoted by x'(S), is the classical chromatic index.</p> <p> We also discuss n-block-colourings of type π, where π = ( π1, π2, ... , πs ) is a partition of the replication number r = v-1/k-1 for a Steiner system S(2,k,v). In particular, we focus on 8(2,4,v)s and the partitions (2, 1, 1, ... , 1), (3, 1, 1 ... , 1), and partitions of the form π = (π1, π2, ... , πs), where |πj -πil ≤ 1 for all 1 ≤ i < j ≤ s. These latter partitions are called equitable partitions and the corresponding block-colourings are called equitable block-colourings.</p> <p> Finally, we present results on the T-chromatic index for S(2, 4, v )s for various configurations T. The T-chromatic index for a Steiner system S(2, k, v), S, is the minimum number of colours needed to colour the blocks of S such that there are no monochromatic copies of T. In particular, we focus on configurations containing 2 lines and configurations containing 3 lines for both S(2, 4, v)s and general S(2, k, v)s. </p>