{
  "id": "2312.03919",
  "version": "v1",
  "published": "2023-12-06T21:34:37.000Z",
  "updated": "2023-12-06T21:34:37.000Z",
  "title": "Indivisibility and uniform computational strength",
  "authors": [
    "Kenneth Gill"
  ],
  "comment": "21 pages, 4 figures. This work extends the results of Sections 1.2 and 1.3 of the author's Ph.D. thesis at Penn State University",
  "categories": [
    "math.LO",
    "cs.LO",
    "math.CO"
  ],
  "abstract": "A countable structure is indivisible if for every coloring with finite range there is a monochromatic isomorphic subcopy of the structure. Each indivisible structure $\\mathcal{S}$ naturally corresponds to an indivisibility problem $\\mathsf{Ind}\\ \\mathcal{S}$, which outputs such a subcopy given a presentation and coloring. We investigate the Weihrauch complexity of the indivisibility problems for two structures: the rational numbers $\\mathbb{Q}$ as a linear order, and the equivalence relation $\\mathscr{E}$ with countably many equivalence classes each having countably many members. We separate the Weihrauch degrees of both $\\mathsf{Ind}\\ \\mathbb{Q}$ and $\\mathsf{Ind}\\ \\mathscr{E}$ from several benchmark problems, showing in particular that $\\mathsf{C}_\\mathbb{N} \\vert_\\mathrm{W} \\mathsf{Ind}\\ \\mathbb{Q}$ and hence $\\mathsf{Ind}\\ \\mathbb{Q}$ is strictly weaker than the problem of finding an interval in which some color is dense for a given coloring of $\\mathbb{Q}$; and that the Weihrauch degree of $\\mathsf{Ind}\\ \\mathscr{E}_k$ is strictly between those of $\\mathsf{SRT}^2_k$ and $\\mathsf{RT}^2_k$, where $\\mathsf{Ind}\\ \\mathcal{S}_k$ is the restriction of $\\mathsf{Ind}\\ \\mathcal{S}$ to $k$-colorings.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-06T21:34:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "uniform computational strength",
      "indivisibility problem",
      "weihrauch degree",
      "monochromatic isomorphic subcopy",
      "equivalence classes"
    ],
    "tags": [
      "dissertation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}