Mathematics – Combinatorics
Scientific paper
2007-01-22
Mathematics
Combinatorics
Corrected the name of a cited author. A concise version has been accepted by Random Structures and Algorithms
Scientific paper
Let S and T be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence S in one part and T in the other; equivalently, binary matrices with row sums S and column sums T. In particular, we find precise formulae for the probabilities that a given bipartite graph is edge-disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out-degrees S and in-degrees T. In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums S and column sums T.
Greenhill Catherine
McKay Brendan D.
No associations
LandOfFree
Random dense bipartite graphs and directed graphs with specified degrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Random dense bipartite graphs and directed graphs with specified degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random dense bipartite graphs and directed graphs with specified degrees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-516486