{
  "id": "1302.2446",
  "version": "v2",
  "published": "2013-02-11T11:01:42.000Z",
  "updated": "2014-11-11T03:27:49.000Z",
  "title": "Degree sequences of random digraphs and bipartite graphs",
  "authors": [
    "Brendan D. McKay",
    "Fiona Skerman"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a speci?ed probability, choose a speci?ed number of edges, or specify the vertex degrees in one of the two colour classes. This problem can alternatively be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can also be cast as a problem in random hypergraphs, or as a classical occupancy, allocation, or coupon collection problem. In each case, provided the two colour classes are not too different in size nor the number of edges too low, we define a probability space based on independent binomial variables and show that its probability masses asymptotically equal those of the degrees in the graph model almost everywhere. The accuracy is sufficient to asymptotically determine the expectation of any joint function of the degrees whose maximum is at most polynomially greater than its expectation. The resulting theory is analogous to that developed by McKay and Wormald (1997) for general graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-11T11:01:42.000Z",
      "abstract": "We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a specified number of edges, or specify the vertex degrees in one of the two colour classes. This problem can also be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can also be cast as a problem in random hypergraphs, or as a classical occupancy, allocation, or coupon collection problem. In each case, provided the two colour classes are not too different in size or the number of edges too low, we define a probability space based on independent binomial variables and show that its probability masses asymptotically equal those of the degrees in the graph model almost everywhere. The accuracy is sufficient to asymptotically determine the expectation of any joint function of the degrees whose maximum is at most polynomially greater than its expectation. Our starting points are theorems of Canfield, Greenhill and McKay (2008--2009) that enumerate bipartite graphs by degree sequence. The resulting theory is analogous to that developed by McKay and Wormald (1997) for general graphs.",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-11-11T03:27:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60B20",
      "60C05",
      "60K30",
      "05C20",
      "05C07"
    ],
    "keywords": [
      "random digraph",
      "degree sequence",
      "vertex degrees",
      "colour classes",
      "random binary matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.2446M"
    }
  }
}