Random Dense Bipartite Graphs and Directed Graphs with Specified Degrees
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...[Show more]
|Collections||ANU Research Publications|
|Source:||Random Structures and Algorithms|
|01_Greenhill_Random_Dense_Bipartite_Graphs_2009.pdf||7.22 MB||Adobe PDF|
Request a copy
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.