{
  "id": "1911.02196",
  "version": "v1",
  "published": "2019-11-06T04:16:28.000Z",
  "updated": "2019-11-06T04:16:28.000Z",
  "title": "On determining when small embeddings of partial Steiner triple systems exist",
  "authors": [
    "Darryn Bryant",
    "Ajani De Vas Gunasekara",
    "Daniel Horsley"
  ],
  "comment": "11 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A partial Steiner triple system of order $u$ is a pair $(U,\\mathcal{A})$ where $U$ is a set of $u$ elements and $\\mathcal{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,\\mathcal{A})$ is a (complete) Steiner triple system $(V,\\mathcal{B})$ such that $U \\subseteq V$ and $\\mathcal{A} \\subseteq \\mathcal{B}$. For a given partial Steiner triple system of order $u$ it is known that an embedding of order $v \\geq 2u+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 $\\mathsf{NP}$-completeness of these problems. We also exhibit a family of counterexamples to a conjecture concerning when small embeddings exist.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-11-06T04:16:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05B07",
      "68Q25"
    ],
    "keywords": [
      "partial steiner triple system",
      "small embeddings",
      "determining",
      "elements occur",
      "obvious necessary conditions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}