{
  "id": "2211.00835",
  "version": "v1",
  "published": "2022-11-02T02:45:46.000Z",
  "updated": "2022-11-02T02:45:46.000Z",
  "title": "The degree-restricted random process is far from uniform",
  "authors": [
    "Michael Molloy",
    "Erlang Surya",
    "Lutz Warnke"
  ],
  "comment": "32 pages, 3 figures",
  "categories": [
    "math.CO",
    "cs.DM",
    "math.PR"
  ],
  "abstract": "The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1, \\ldots, d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i. Wormald conjectured in 1999 that, for d-regular degree sequences D_n, the final graph of this process is similar to a uniform random d-regular graph. In this paper we show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n. The combinatorial proof technique is our main conceptual contribution: we adapt the switching method to the degree-restricted process, demonstrating that this enumeration technique can also be used to analyze stochastic processes (rather than just uniform random models, as before).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-02T02:45:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60C05",
      "68W20",
      "60G99",
      "90B15"
    ],
    "keywords": [
      "degree sequence",
      "uniform random d-regular graph",
      "final graph",
      "natural algorithmic model",
      "main conceptual contribution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}