On determining when small embeddings of partial Steiner triple systems exist. Issue 8 (17th March 2020)

• Record Type: Journal Article
• Authors: Bryant, Darryn; De Vas Gunasekara, Ajani; Horsley, Daniel
• Is Part Of: Journal of combinatorial designs. Volume 28:Issue 8(2020:Aug.)
• Page Start: 568
• Page End: 579
• Publication Date: 2020-03-17
• Subjects: embeddings -- NP‐completeness -- partial Steiner triple systems; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21715
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: 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.