Premium
On determining when small embeddings of partial Steiner triple systems exist
Author(s) -
Bryant Darryn,
De Vas Gunasekara Ajani,
Horsley Daniel
Publication year - 2020
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21715
Subject(s) - steiner system , mathematics , combinatorics , conjecture , counterexample , embedding , order (exchange) , discrete mathematics , set (abstract data type) , steiner tree problem , computer science , finance , artificial intelligence , economics , programming language
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.