Bicolouring Steiner systems \(S\)(2,4,\(v\))
A colouring of an \(S(2,4,v)\) is a bicolouring if each block is coloured with precisely two colours. An \(S(2,4,v)\) is bicolourable if it admits at least one bicolouring. A bicolouring using exactly \(h\) colours is an \(h\)-bicolouring. The maximum (respectively minimum) number of colours for which there exists a bicolouring of an \(S(2,4,v)\) is its upper (resp. lower) chromatic number. The authors use \(\bar{{\mathcal X}}_{bi}(v)\) (resp. \({\mathcal X}_{bi}(v)\)) to denote the maximum (resp. minimum) upper (resp. lower) chromatic number taken over all \(S(2,4,v)\)s of order \(v\). The numbers \(\bar{{\mathcal X}}_{bi}(v)\), \({\mathcal X}_{bi}(v)\) are well defined, since for every admissible order \(v \equiv 1,4 \pmod{12}\) there exists a bicolourable \(S(2,4,v)\). But for individual systems \(S(2,4,v)\) there may not be a bicolouring. In fact \textit{S. Milici, A. Rosa} and \textit{V. Voloshin} [Discrete Math. 240, 145--160 (2001; Zbl 0983.05015)] have shown that there is a constant \(v^*\) such that for all admissible \(v > v^*\) there exists an \(S(2,4,v)\) without a bicolouring. In this paper the authors show that \(v^*\) is at least \(28\) as all \(S(2,4,v)\)s with \(v \leq 25\) are bicolourable. They also establish an upper bound for \(\bar{{\mathcal X}}_{bi}(v)\), viz. that if an \(S(2,4,v)\) admits a bicolouring and \(v \leq ((3^d-1)/2)\, (d \in N)\), then \(\bar{{\mathcal X}}_{bi}(v) \leq \lfloor d/\log_32 \rfloor - 1\). Analysing some small systems, the authors show that an \(S(2,4,v)\) with \(v \in \{13,16,25,28\}\) can only be bicoloured using either two or three colours, so that \(\bar{{\mathcal X}}_{bi}(v)=3\) for these orders. Finally, using the ``\(3v+1\) construction'', which enables us to build an \(S(2,4,3v+1)\) system from an \(S(2,4,v)\) system, they show that there exist systems admitting bicolourings with an arbitrarily large number of colours. In particular, their result is that for every \(v \equiv 4,13 \pmod{36}\), \(v \geq 13\), there exists a \(3\)-bicolourable \(S(2,4,v)\), and for every \(v \equiv 13,40 \pmod{108}\), \(v \geq 40\), there exists a \(4\)-bicolourable \(S(2,4,v)\). In general, for every \(h \geq 2\) and for every \(v \equiv (3^{h-1}-1)/2, (3^h-1)/2 \pmod{4 \cdot 3^h-1}\), \(v \geq (3^h-1)/2\), there exists an \(h\)-bicolourable \(S(2,4,v)\), and the number of such systems tends to infinity with \(v\).
scientific article; zbMATH DE number 2083736