{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R122",
  "content_hash": null,
  "slug": "cdg-claim-countably-infinite-chromatic-number",
  "type": "claim",
  "title": "The cube-distance graph has countably infinite chromatic number",
  "summary": "Every finite coloring of the integers contains a same-colored pair at a positive cube distance, so the graph has chromatic number \\(\\aleph_0\\).",
  "relevance": "This records a result, observation, or conjecture used to assess the target problem.",
  "relevance_source": "derived",
  "body": "Let \\(D=\\{n^3:n\\geq1\\}\\). Bergelson and Leibman's polynomial van der Waerden theorem, applied to the zero polynomial and \\(p(n)=n^3\\), gives two same-colored integers \\(x\\) and \\(x+n^3\\) in every finite coloring of \\(\\mathbb Z\\). Those vertices are adjacent in \\(G(\\mathbb Z,D)\\), so no finite coloring is proper. The graph is countable, which supplies the upper bound \\(\\aleph_0\\).\n\nThis refutes the candidate value \\(3\\). Guerreiro, Ruzsa, and Silva describe the same fact by saying that the positive values of \\(p\\) form a chromatically intersective set, or a ladder. The square-distance and triangular-distance cases follow from the same polynomial theorem.",
  "status": "established",
  "evidence_grade": "sourced",
  "scope": {
    "kind": "universal",
    "statement": "the integer distance graph whose allowed distances are all positive cubes"
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://people.math.osu.edu/leibman.1/preprints/psz.pdf",
      "locator": "Bergelson and Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems, Theorem C and Corollary 1.11"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://people.math.osu.edu/leibman.1/preprints/psz.pdf",
    "locator": "Bergelson and Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems, Theorem C and Corollary 1.11"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R123",
      "title": "Polynomial value sets are chromatically intersective",
      "object_type": "claim",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "R120",
      "title": "Exact cube-distance colorings on small windows",
      "object_type": "artifact",
      "relation": "tests",
      "direction": "incoming"
    },
    {
      "slug": "chromatic-number-cube-distance-graph",
      "title": "chromatic number cube distance graph",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}