Degree sequences of random digraphs and bipartite graphs

Abstract

We investigate the joint distribution of the vertex degrees in three models\nof random bipartite graphs. Namely, we can choose each edge with a specified\nprobability, choose a specified number of edges, or specify the vertex degrees\nin one of the two colour classes. This problem can alternatively be described\nin terms of the row and sum columns of random binary matrix or the in-degrees\nand out-degrees of a random digraph, in which case we can optionally forbid\nloops. It can also be cast as a problem in random hypergraphs, or as a\nclassical occupancy, allocation, or coupon collection problem. In each case,\nprovided the two colour classes are not too different in size nor the number of\nedges too low, we define a probability space based on independent binomial\nvariables and show that its probability masses asymptotically equal those of\nthe degrees in the graph model almost everywhere. The accuracy is sufficient to\nasymptotically determine the expectation of any joint function of the degrees\nwhose maximum is at most polynomially greater than its expectation.\n