Small Embeddings of Partial Steiner Triple Systems. Issue 8 (28th June 2013) - Horsley, Daniel
Abstract It was proved in 2009 that any partial Steiner triple system of order u has an embedding of order v for each admissible <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp412" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />v≥2u+1</alternatives>. This result is best possible in the sense that, for each <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp454" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />u≥9</alternatives>, there exists a partial Steiner triple system of order u that does not have an embedding of order v for any <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp433" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />v<2u+1</alternatives>. Many partial Steiner triple systems do have embeddings of orders smaller than <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp4bq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />2u+1</alternatives>, but much less is known about when these embeddings exist. In this paper, we detail a method for constructing such embeddings. We use this method to show that each member of a wide class of partial Steiner triple systems has an embedding of order v for at least half (or nearly half) of the orders <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp475" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />v<2u+1</alternatives> for which an embedding could exist. For some members of this class we are able to completely determine the set of all orders for which the member has an embedding.