Embedding partial Steiner triple systems with few triples

Abstract

It was proved in 2009 that any partial Steiner triple system of order $u$ has an embedding of order $v$ for each admissible integer $v\ge 2u+1$. This result is best-possible in the sense that, for each $u\ge 9$, there exists a partial Steiner triple system of order $u$ that does not have an embedding of order $v$ for any $v<2u+1$. Many partial Steiner triple systems do have embeddings of orders smaller than $2u+1$, but little has been proved about when these embeddings exist. In this paper we construct embeddings of orders less than $2u+1$ for partial Steiner triple systems with few triples. In particular, we show that a partial Steiner triple system of order $u\ge 62$ with at most $\frac{u^2}{50}-\frac{11u}{100}-\frac{116}{75}$ triples has an embedding of order $v$ for each admissible integer $v\ge \frac{8u+17}{5}$.

20 pages, 0 figures