Linearly derived Steiner triple systems (Q1378861)

A Steiner triple system of order \(n\) \((\text{STS}(n))\) is derived if it can be extended to a Steiner quadruple system of order \(n+1\), i.e. if one can find \(n(n- 1)(n- 3)/24\) quadruples of elements of the STS such that neither of these contains a triple of the STS, and, moreover, each 3-subset which is not a triple of the STS is contained in exactly one of these quadruples. A 4-subset of elements of an STS is linear if it is the symmetric difference of two triples of the system. An STS is linearly derived if it has an extension in which each of the quadruples in the extension is linear. All geometric systems and Hall triple systems are linearly derived. Neither of the two \(\text{STS}(13)\) is linearly derived, and four of the 80 \(\text{STS}(15)\) are linearly derived [all 80 are known to be derived]. With each STS a graph is associated whose vertices are the linear 4-subsets, with two vertices adjacent if the corresponding linear 4-subsets intersect in three elements. The chromatic number of this graph cannot exceed eight. It is shown that if this graph has chromatic number at most three, the corresponding STS is linearly derived. The paper contains many further interesting results and observations relating linear extendability of STSs and their graphs.