Colouring Steiner systems with specified block colour patterns (Q5948973): Difference between revisions

A colouring of a design \((V, {\mathcal B})\) is a surjective mapping \(\varphi : V \rightarrow C\) where \(C\) is the set of colours. In this paper the authors consider colourings in which only specified block colouring patterns are allowed. In the case of Steiner triple systems there are three possible colouring patterns in which a triple can be coloured, viz. type \(a\) (\(\times\) \(\times\) \(\times\), monochromatic), type \(b\) (\(\times\) \(\times\) \(\square\), two-coloured or bichromatic), and type \(c\) (\(\times\) \(\square\) \(\blacksquare\), three-coloured or polychromatic). In a colouring of type \(S\) where \(S \subset \{a,b,c\}\), \(S \neq \emptyset\), only triples with colour patterns from \(S\) are allowed. In a \(k\)-colouring of type \(S\), all \(k\) colours must be used, as the mapping \(\varphi\) is surjective; however, not all colour patterns of \(S\) must occur. Given an Steiner triple system \((V, {\mathcal B})\) define \(\Omega_S(V, {\mathcal B}) = \{k: (V, {\mathcal B})\) has a \(k\)-colouring of type \(S\}\), and the feasible set \(\Omega_S(v) = \bigcup \Omega_S(V, {\mathcal B})\) with the union taken over all \(\text{STS}(v)\) with \(v = |V|\). The only colouring type that appears not to have been considered earlier is \(ac\), and the authors show that \(\Omega_{ac}(v) = \text{ODD}(v)\) if \(v \equiv 3, 9 \pmod{18}\), and \(= \text{ODD}(v) \setminus \{3 \}\) otherwise, where \(\text{ODD}(v) = \{t: v \equiv 1 \pmod{2}\) and \(1 \leq t \leq v\}\). In the remainder of the paper the authors study the Steiner systems \(S(2,4,v)\) in which the five distinct colouring patterns are type \(A\) (\(\times\) \(\times\) \(\times\) \(\times\), monochromatic), type \(B\) (\(\times\) \(\times\) \(\times\) \(\square\), two coloured of pattern \(3+1\)), type \(C\) (\(\times\) \(\times\) \(\square\) \(\square\), two-coloured of pattern \(2+2\)), type \(D\) (\(\times\) \(\times\) \(\square\) \(\blacksquare\), three-coloured), and type \(E\) (\(\times\) \(\square\) \(\blacksquare\) \(\diamond\), four-coloured or polychromatic). The authors deal with some of the 31 distinct types of colourings. By analogy with STSs, the types \(A\), \(E\) and \(ABCDE\) are trivial in that, for all admissible orders \(v \equiv 1, 4 \pmod{12}\), \(\Omega_A\{v\} = \{1\}\), \(\Omega_E\{v\} = \{v\}\), and \(\Omega_{ABCDE}\{v\} = \{1, 2, \dots , v\}\). By analogy with a similar result for STSs, this implies that if an \(S(2,4,v)\) is \(S\)-uncolourable, then \(S \subseteq \{B, C, D\}\). The authors show that a colouring of an \(S(2,4,v)\) of type \(C\) exists only for the trivial design with \(v = 4\). They then proceed to obtain a range of partial results for the types \(B\), \(AB\), \(D\), \(AD\), \(AC\) and \(AE\). While there are several remaining questions concerning the existence of colourings of these and other types, the authors provide considerable insight into the problem, for example, they conjecture that an \(S(2,4,v)\) with a 2-colouring of type \(AC\) exists for all \(v \equiv 4 \pmod{12}\).