Skip navigation
Skip navigation

Random Dense Bipartite Graphs and Directed Graphs with Specified Degrees

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.authorGreenhill, Catherine
dc.contributor.authorMcKay, Brendan
dc.date.accessioned2015-12-10T22:22:13Z
dc.identifier.issn1042-9832
dc.identifier.urihttp://hdl.handle.net/1885/52579
dc.description.abstractLet 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.publisherJohn Wiley & Sons Inc
dc.sourceRandom Structures and Algorithms
dc.subject0-1 matrix
dc.subjectAsymptotic enumeration
dc.subjectBipartite graph
dc.subjectDigraph
dc.subjectDirected graph
dc.subjectRandom graph
dc.titleRandom Dense Bipartite Graphs and Directed Graphs with Specified Degrees
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume35
dc.date.issued2009
local.identifier.absfor080202 - Applied Discrete Mathematics
local.identifier.ariespublicationu3594520xPUB250
local.type.statusPublished Version
local.contributor.affiliationGreenhill, Catherine, University of New South Wales
local.contributor.affiliationMcKay, Brendan, College of Engineering and Computer Science, ANU
local.description.embargo2037-12-31
local.bibliographicCitation.issue2
local.bibliographicCitation.startpage137
local.bibliographicCitation.lastpage270
local.identifier.doi10.1002/rsa.20273
dc.date.updated2016-02-24T10:17:31Z
local.identifier.scopusID2-s2.0-68349134993
local.identifier.thomsonID000268819000005
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Greenhill_Random_Dense_Bipartite_Graphs_2009.pdf7.22 MBAdobe PDFThumbnail
    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