{
  "id": "1009.0792",
  "version": "v3",
  "published": "2010-09-04T00:38:45.000Z",
  "updated": "2021-09-01T14:35:41.000Z",
  "title": "Warmth and mobility of random graphs",
  "authors": [
    "Sukhada Fadnavis",
    "Matthew Kahle",
    "Francisco Martinez-Figueroa"
  ],
  "comment": "This version is a substantial rewrite from earlier versions",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "A graph homomorphism from the rooted $d$-branching tree $\\phi: T^d \\to H$ is said to be cold if the values of $\\phi$ for vertices arbitrarily far away from the root can restrict the value of $\\phi$ at the root. Warmth is a graph parameter that measures the non-existence of cold maps. We study warmth of random graphs $G(n,p)$, and for every $d \\ge 1$, we exhibit a nearly-sharp threshold for the existence of cold maps. As a corollary, for $p=O(n^{-\\alpha})$ warmth of $G(n,p)$ is concentrated on at most two values. As another corollary, a conjecture of Lov\\'asz relating mobility to chromatic number holds for \"almost all\" graphs. Finally, our results suggest new conjectures relating graph parameters from statistical physics with graph parameters from equivariant topology.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-10-09T00:28:42.000Z",
      "abstract": "Brightwell and Winkler introduced the graph parameters warmth and mobility in the context of combinatorial statistical physics. They related both parameters to lower bounds on chromatic number. Although warmth is not a monotone graph property we show it is nevertheless \"statistically monotone\" in the sense that it tends to increase with added random edges, and that for sparse graphs ($p=O(n^{-\\alpha})$, $\\alpha > 0$) the warmth is concentrated on at most two values, and for most $p$ it is concentrated on one value. We also put bounds on warmth and mobility in the dense regime, and as a corollary obtain that a conjecture of Lov\\'asz holds for almost all graphs.",
      "comment": "13 pages, 5 figures",
      "journal": null,
      "doi": null,
      "authors": [
        "Sukhada Fadnavis",
        "Matthew Kahle"
      ]
    },
    {
      "version": "v3",
      "updated": "2021-09-01T14:35:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "random graphs",
      "graph parameters warmth",
      "monotone graph property",
      "lovasz holds",
      "sparse graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1009.0792F"
    }
  }
}