On determining when small embeddings of partial Steiner triple systems exist

A partial Steiner triple system of order u is a pair ( U , A ) , where U is a set of u elements and A is a set of triples of elements of U such that any two elements of U occur together in at most one triple. If each pair of elements occur together in exactly one triple it is a Steiner triple system . An embedding of a partial Steiner triple system ( U , A ) is a (complete) Steiner triple system ( V , B ) such that U ⊆ V and A ⊆ B . For a given partial Steiner triple system of order u it is known that an embedding of order v ⩾ 2 u + 1 exists whenever v satisfies the obvious necessary conditions. Determining whether “small” embeddings of order v < 2 u + 1 exist is a more difficult task. Here we extend a result of Colbourn on the NP ‐completeness of these problems. We also exhibit a family of counterexamples to a conjecture concerning when small embeddings exist.