{
  "id": "1310.8475",
  "version": "v2",
  "published": "2013-10-31T12:31:09.000Z",
  "updated": "2015-04-11T14:56:58.000Z",
  "title": "The Jamming Constant of Uniform Random Graphs",
  "authors": [
    "Paola Bermolen",
    "Matthieu Jonckheere",
    "Pascal Moyal"
  ],
  "comment": "keywords: random graphs, hydrodynamic limit, parking process",
  "categories": [
    "math.PR"
  ],
  "abstract": "By constructing jointly a random graph and an associated exploration process, we define the dynamics of a \"parking process\" on a class of uniform random graphs as a measure-valued Markov process, representing the empirical degree distribution of non-explored nodes. We then establish a functional law of large numbers for this process as the number of vertices grows to infinity, allowing us to assess the jamming constant of the considered random graphs, i.e. the size of the maximal independent set discovered by the exploration algorithm. This technique, which can be applied to any uniform random graph with a given degree distribution, can be seen as a generalization in the space of measures, of the differential equation method introduced by Wormald.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-10-31T12:31:09.000Z",
      "title": "The Jamming Constant of Random Graphs",
      "abstract": "Using a configuration approach, we define the dynamics of the \"parking process\" on random graphs as a measure-valued Markov process. We then establish a functional law of large numbers when the number of vertices grows to infinity. This allows us to characterize the jamming constant of various random graphs.",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-04-11T14:56:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60J25",
      "05C80",
      "60B12"
    ],
    "keywords": [
      "random graphs",
      "jamming constant",
      "configuration approach",
      "measure-valued markov process",
      "functional law"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.8475B"
    }
  }
}