Random Dense Bipartite Graphs and Directed Graphs with Specified Degrees
-
Altmetric Citations
Greenhill, Catherine; McKay, Brendan
Description
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]
dc.contributor.author | Greenhill, Catherine | |
---|---|---|
dc.contributor.author | McKay, Brendan | |
dc.date.accessioned | 2015-12-10T22:22:13Z | |
dc.identifier.issn | 1042-9832 | |
dc.identifier.uri | http://hdl.handle.net/1885/52579 | |
dc.description.abstract | 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. | |
dc.publisher | John Wiley & Sons Inc | |
dc.source | Random Structures and Algorithms | |
dc.subject | 0-1 matrix | |
dc.subject | Asymptotic enumeration | |
dc.subject | Bipartite graph | |
dc.subject | Digraph | |
dc.subject | Directed graph | |
dc.subject | Random graph | |
dc.title | Random Dense Bipartite Graphs and Directed Graphs with Specified Degrees | |
dc.type | Journal article | |
local.description.notes | Imported from ARIES | |
local.identifier.citationvolume | 35 | |
dc.date.issued | 2009 | |
local.identifier.absfor | 080202 - Applied Discrete Mathematics | |
local.identifier.ariespublication | u3594520xPUB250 | |
local.type.status | Published Version | |
local.contributor.affiliation | Greenhill, Catherine, University of New South Wales | |
local.contributor.affiliation | McKay, Brendan, College of Engineering and Computer Science, ANU | |
local.description.embargo | 2037-12-31 | |
local.bibliographicCitation.issue | 2 | |
local.bibliographicCitation.startpage | 137 | |
local.bibliographicCitation.lastpage | 270 | |
local.identifier.doi | 10.1002/rsa.20273 | |
dc.date.updated | 2016-02-24T10:17:31Z | |
local.identifier.scopusID | 2-s2.0-68349134993 | |
local.identifier.thomsonID | 000268819000005 | |
Collections | ANU Research Publications |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
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.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator