The spectrum of maximal partial Steiner triple systems (Q1261007): Difference between revisions

The spectrum \(S^ 3(v)\) is the set of all possible sizes of maximal (that is, nonextendable by adding a triple) partial Steiner triple systems of order \(v\). The maximum value of the spectrum was determined by \textit{Kirkman} [Cambridge and Dublin Math. J. 2, 191-204 (1847)]; the minimum is due to \textit{J. Novák} [Mat. Časopis, Slovensk. Akad. Vied 24, 43-57 (1974; Zbl 0273.05132)]. More recently, \textit{Severn} [C. S. Technical Report \# 172/84, University of Toronto (1984)] completely determined \(S^ 3(v)\) for all odd \(v\); for even \(v\) he determined a major part of the spectrum. In the paper, the authors settle all cases left in doubt by Severn, and thus completely determine the spectrum \(S^ 3(v)\). It is interesting that in all but one case left in doubt before, the values are settled in the negative. The authors' main tool is the application of bounds on the maximum size of a non-bipartite triangle-free graph with all vertices of odd degree.