{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R326",
  "content_hash": null,
  "slug": "gct45-claim-certified-interval",
  "type": "claim",
  "title": "The maximum expected cover time lies in a certified rational interval",
  "summary": "For the maximum expected cover time \\(C_{4,5}\\), the certified interval is \\(19\\le C_{4,5}\\le8534169769/5542680\\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.",
  "relevance": "For Largest expected cover time on the four by five grid, record gct45-claim-certified-interval (“The maximum expected cover time lies in a certified rational interval”) records a bound, answer, status fact, or structural consequence. The record states: For the maximum expected cover time \\(C_{4,5}\\), the certified interval is \\(19\\le C_{4,5}\\le8534169769/5542680\\); the exact maximum and its maximizing starting-vertex symmetry orbit remain unresolved.",
  "relevance_source": "recorded",
  "body": "Write \\(C_{4,5}\\) for the maximum expected cover time. The certified interval is\n\\[\n\\boxed{19\\le C_{4,5}\\le \\frac{8{,}534{,}169{,}769}{5{,}542{,}680}}.\n\\]\nThe upper endpoint is approximately \\(1539.7190\\).\n\nThe grid has 20 vertices, 31 edges, and diameter 7. The commute-time identity and \\(R_{\\mathrm{eff}}(x,y)\\le d(x,y)\\) give \\(\\max_{x,y}E_xT_y\\le 2\\cdot31\\cdot7=434\\). Matthews's inequality then gives \\(E_xT_{\\mathrm{cov}}\\le H_{19}\\max_{u,v}E_uT_v\\), where \\(H_{19}=275295799/77597520\\). Multiplication and reduction yield the displayed upper endpoint. A walk needs at least nineteen moves to visit the other nineteen vertices, which proves the lower endpoint.\n\nThe exact maximum and its maximizing symmetry orbit remain unresolved in this record. The six start orbits have representatives \\((0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\\).",
  "status": "established",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "simple random walk on P_4 square P_5 with the starting vertex visited at time zero, maximized over all twenty starting vertices",
    "bounds": {
      "rows": {
        "min": 4,
        "max": 4
      },
      "columns": {
        "min": 5,
        "max": 5
      },
      "starting_vertices": {
        "min": 20,
        "max": 20
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://doi.org/10.1214/aop/1176991686",
      "locator": "Peter Matthews, Covering problems for Markov chains, Annals of Probability 16 (1988), 1215-1228, cover-time inequality; commute-time identity and effective-resistance bound as recorded in the literature-audit object"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1214/aop/1176991686",
    "locator": "Peter Matthews, Covering problems for Markov chains, Annals of Probability 16 (1988), 1215-1228, cover-time inequality; commute-time identity and effective-resistance bound as recorded in the literature-audit object"
  },
  "models": [],
  "relations": [
    {
      "slug": "R324",
      "title": "Exact rational verifier for the certified interval",
      "object_type": "artifact",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R325",
      "title": "Literature and finite-state audit",
      "object_type": "attempt",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "grid-cover-time-four-by-five",
      "title": "grid cover time four by five",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}