2019/11/05 by Darryn Bryant, Bryant, Darryn, Ajani De Vas Gunasekara +3
Engineering · Medicine · #05B07 (Primary) #68Q25 (Secondary) #Chronic Lymphocytic Leukemia Research #Chronic Myeloid Leukemia Treatments #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1911.02196
openalex publication_date 2019/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A partial Steiner triple system of order u is a pair (U,\A)\nwhere U is a set of u elements and \A is a set of triples of\nelements of U such that any two elements of U occur together in at most one\ntriple. If each pair of elements occur together in exactly one triple it is a\nSteiner triple system. An embedding of a partial Steiner triple system\n(U,\A) is a (complete) Steiner triple system (V,\B) such\nthat U \⊆ V and \A \⊆ \B. For a given\npartial Steiner triple system of order u it is known that an embedding of\norder v \≥ 2u+1 exists whenever v satisfies the obvious necessary\nconditions. Determining whether "small" embeddings of order v < 2u+1 exist is\na more difficult task. Here we extend a result of Colbourn on the\n\NP-completeness of these problems. We also exhibit a family of\ncounterexamples to a conjecture concerning when small embeddings exist.\n