{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R331",
  "content_hash": null,
  "slug": "gmstg8-claim-certified-current-interval",
  "type": "claim",
  "title": "The certified interval is 1 to slightly below 3/2",
  "summary": "The exact eight-vertex maximum remains open in this record; current certificates give 1 <= gamma_8 < 3/2 - 10^-36.",
  "relevance": "For Largest subtour-LP gap among eight-vertex graph metrics, record gmstg8-claim-certified-current-interval (“The certified interval is 1 to slightly below 3/2”) records a bound, answer, status fact, or structural consequence. The record states: The exact eight-vertex maximum remains open in this record; current certificates give 1 <= gamma_8 < 3/2 - 10^-36.",
  "relevance_source": "recorded",
  "body": "Let\n\\[\n\\gamma_8=\\max_H\\frac{\\operatorname{TSP}(d_H)}{\\operatorname{SUBT}(d_H)},\n\\]\nwhere \\(H\\) runs through connected simple eight-vertex graphs and \\(d_H\\) is its shortest-path metric. The current certified interval is\n\\[\n\\boxed{1\\leq\\gamma_8<\\frac32-10^{-36}}.\n\\]\nThe lower endpoint is attained by \\(H=C_8\\). Its metric tour optimum and subtour optimum are both 8, as checked by `gmstg8-artifact-cycle-eight-certificate`.\n\nKarlin, Klein, and Oveis Gharan prove that there is an \\(\\epsilon>10^{-36}\\) such that every metric TSP instance has a tour of expected cost at most \\((3/2-\\epsilon)\\) times the subtour-LP optimum. Every graph metric in this finite family is a metric TSP instance, so their theorem gives the displayed strict upper bound.\n\nThis interval is deliberately conservative. It records only bounds whose hypotheses and certificates have been checked. The exact maximum requires the isomorph-free LP sweep described below.",
  "status": "established",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "bounded",
    "statement": "all shortest-path metrics of connected simple graphs on eight vertices",
    "bounds": {
      "vertices": {
        "min": 8,
        "max": 8
      },
      "connected_unlabeled_graphs": {
        "min": 11117,
        "max": 11117
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/2105.10043",
      "locator": "Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, abstract and main theorem; lower endpoint certificate in this dataset"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/2105.10043",
    "locator": "Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan, A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP, abstract and main theorem; lower endpoint certificate in this dataset"
  },
  "models": [],
  "relations": [
    {
      "slug": "R328",
      "title": "Exact C8 tour and subtour-LP certificate",
      "object_type": "artifact",
      "relation": "verifies",
      "direction": "incoming"
    },
    {
      "slug": "R330",
      "title": "Primary-source audit found bounds and a neighboring finite enumeration",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "R327",
      "title": "Isomorph-free connected graph corpus manifest",
      "object_type": "artifact",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "graph-metric-subtour-gap-eight",
      "title": "graph metric subtour gap eight",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}