Random Oxford graphs

Inspired by a concept in comparative genomics, we investigate properties of randomly chosen members of G 1 ( m , n , t ) , the set of bipartite graphs with m left vertices, n right vertices, t edges, and each vertex of degree at least one. We give asymptotic results for the number of such graphs and the number of ( i , j ) trees they contain. We compute the thresholds for the emergence of a giant component and for the graph to be connected.