{
  "id": "1412.2725",
  "version": "v1",
  "published": "2014-12-08T20:31:36.000Z",
  "updated": "2014-12-08T20:31:36.000Z",
  "title": "Finitary Coloring",
  "authors": [
    "Alexander E. Holroyd",
    "Oded Schramm",
    "David B. Wilson"
  ],
  "categories": [
    "math.PR"
  ],
  "abstract": "Suppose that the vertices of $Z^d$ are assigned random colors via a finitary factor of independent identically distributed (iid) vertex-labels. That is, the color of vertex $v$ is determined by a rule that examines the labels within a finite (but random and perhaps unbounded) distance $R$ of $v$, and the same rule applies at all vertices. We investigate the tail behavior of $R$ if the coloring is required to be proper (that is, if adjacent vertices must receive different colors). When $d\\geq 2$, the optimal tail is given by a power law for 3 colors, and a tower (iterated exponential) function for 4 or more colors (and also for 3 or more colors when $d=1$). If proper coloring is replaced with any shift of finite type in dimension 1, then, apart from trivial cases, tower function behavior also applies.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-08T20:31:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60G10",
      "05C15",
      "37A50"
    ],
    "keywords": [
      "finitary coloring",
      "tower function behavior",
      "assigned random colors",
      "finitary factor",
      "trivial cases"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.2725H"
    }
  }
}