{
  "id": "0809.0141",
  "version": "v2",
  "published": "2008-08-31T18:35:55.000Z",
  "updated": "2010-10-26T17:38:57.000Z",
  "title": "The t-stability number of a random graph",
  "authors": [
    "Nikolaos Fountoulakis",
    "Ross J. Kang",
    "Colin McDiarmid"
  ],
  "comment": "25 pages; v2 has 30 pages and is identical to the journal version apart from formatting and a minor amendment to Lemma 8 (and its proof on p. 21)",
  "journal": "Electron. J. Combin. 17 (2010), #R59",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the maximum order of a t-stable set in G. We investigate the typical values that this parameter takes on a random graph on n vertices and edge probability equal to p. For any fixed 0 < p < 1 and fixed non-negative integer t, we show that, with probability tending to 1 as n grows, the t-stability number takes on at most two values which we identify as functions of t, p and n. The main tool we use is an asymptotic expression for the expected number of t-stable sets of order k. We derive this expression by performing a precise count of the number of graphs on k vertices that have maximum degree at most k. Using the above results, we also obtain asymptotic bounds on the t-improper chromatic number of a random graph (this is the generalisation of the chromatic number, where we partition of the vertex set of the graph into t-stable sets).",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-10-26T17:38:57.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05A16"
    ],
    "keywords": [
      "t-stability number",
      "random graph",
      "t-stable set",
      "maximum degree",
      "edge probability equal"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0809.0141F"
    }
  }
}