Small Embeddings of Partial Steiner Triple Systems. Issue 8 (28th June 2013)

• Record Type: Journal Article
• Authors: Horsley, Daniel
• Is Part Of: Journal of combinatorial designs. Volume 22:Issue 8(2014:Aug.)
• Page Start: 343
• Page End: 365
• Publication Date: 2013-06-28
• Subjects: Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21359
• Languages: English
• ISSNs: 1063-8539

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>It was proved in 2009 that any partial Steiner triple system of order <italic>u</italic> has an embedding of order <italic>v</italic> for each admissible <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp412" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21359:jcd21359-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>v</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn><mml:mi>u</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></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" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21359:jcd21359-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>u</mml:mi><mml:mo>≥</mml:mo><mml:mn>9</mml:mn></mml:mrow></mml:math></alternatives>, there exists a partial Steiner triple system of order <italic>u</italic> that does not have an embedding of order <italic>v</italic> for any <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgxpp433" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21359:jcd21359-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>v</mml:mi><mml:mo><</mml:mo><mml:mn>2</mml:mn><mml:mi>u</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></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" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21359:jcd21359-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>2</mml:mn><mml:mi>u</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></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 <italic>v</italic> 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" /><mml:math display="inline" altimg="urn:x-wiley:10638539:media:jcd21359:jcd21359-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>v</mml:mi><mml:mo><</mml:mo><mml:mn>2</mml:mn><mml:mi>u</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></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.</p> </abstract>