Uniquely 3-colourable Steiner triple systems (Q1865409)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Uniquely 3-colourable Steiner triple systems |
scientific article |
Statements
Uniquely 3-colourable Steiner triple systems (English)
0 references
26 March 2003
0 references
A (weak) 3-colouring of a Steiner triple system \(S\) of order \(v\) (or STS(\(v\))) is an assignment of colours from a set of cardinality 3 to the \(v\) points of \(S\) in such a way that every block contains at least two points with different colours. A 3-colouring is equitable if the cardinalities of the sets of points assigned each colour differ by at most one. If every 3-colouring of \(S\) is equitable then \(S\) is called 3-balanced. A 3-colouring of \(S\) is unique if every other 3-colouring can be obtained from the original colour assignment by a permutation of the colours. The authors define a type-I STS(\(v\)) as a 3-balanced STS(\(v\)) with a unique (necessarily equitable) 3-colouring, and a type-II STS(\(v\)) as an STS(\(v\)) with a unique 3-colouring which is non-equitable. They show that a type-I STS(\(v\)) exists for every admissible \(v \geq 25\). Since it is known that no type-I STS(\(v\)) exists for any \(v \leq 15\), the only remaining undecided cases are \(v = 19\) and \(21\). In addition they show that a type-II STS(\(v\)) exists for every admissible \(v \geq 25\). Since it is known that no type-II STS(\(v\)) exists for any \(v \leq 19\), the only remaining undecided case is \(v = 21\). Group divisible designs with block size 3 and Wilson's fundamental construction are important ingredients in the recursive construction results.
0 references
Steiner triple system
0 references
3-colouring
0 references