On determining when small embeddings of partial Steiner triple systems exist

DOI10.1002/JCD.21715MaRDI QIDQ6187453zbMATH OpenOpenAlexFDO

Authors Darryn Bryant, Ajani De Vas Gunasekara, Daniel Horsley

Publication date 31 January 2024

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.02196

zbMATH Keywords

embeddingsNP-completenesspartial Steiner triple systems

Mathematics Subject Classification ID

Triple systems (05B07)

Abstract: A partial Steiner triple system of order $u$ is a pair $(U,mathcalA)$ where $U$ is a set of $u$ elements and $mathcalA$ 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,mathcalA)$ is a (complete) Steiner triple system $(V,mathcalB)$ such that $UsubseteqV$ and $mathcalAsubseteqmathcalB$. For a given partial Steiner triple system of order $u$ it is known that an embedding of order $vgeq2u+1$ exists whenever $v$ satisfies the obvious necessary conditions. Determining whether "small" embeddings of order $v<2u+1$ exist is a more difficult task. Here we extend a result of Colbourn on the $mathsfNP$-completeness of these problems. We also exhibit a family of counterexamples to a conjecture concerning when small embeddings exist.

Recommendations

• Small embeddings of partial Steiner triple systems
• Embedding partial Steiner triple systems with few triples
• scientific article; zbMATH DE number 3902664
• A conjecture on small embeddings of partial Steiner triple systems
• Small embeddings for partial triple systems of odd index

Cites work

• scientific article; zbMATH DE number 3847402 (Why is no real title available?)
• scientific article; zbMATH DE number 1314686 (Why is no real title available?)
• scientific article; zbMATH DE number 1394639 (Why is no real title available?)
• A conjecture on small embeddings of partial Steiner triple systems
• A proof of Lindner's conjecture on embeddings of partial Steiner triple systems
• Edge-decompositions of graphs with high minimum degree
• Embedding partial Steiner triple systems is NP-complete
• Embedding partial Steiner triple systems with few triples
• Embeddings of Steiner triple systems
• Fractional triangle decompositions in graphs with large minimum degree
• The NP-Completeness of Edge-Coloring

This page was built for publication: On determining when small embeddings of partial Steiner triple systems exist

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187453)