Random Oxford Graphs

by Jonah Blasiak, Princeton U. and Rick Durrett, Cornell U.

Biologists use an Oxford grid to indicate the relationship between two genomes. It is a matrix with g(i,j)=1 if part of chromosome i in the species A is homologous to part of chromosome j in species B. The corresponding Oxford graph is the bipartite graph obtained by letting the chromosomes of species A be vertices on the left and chromosomes of species B be vertices on the right and with an edge from i on the left to j on the right if g(i,j)=1. In this paper, we investigate properties of randomly chosen members of G^r₁(m,n,t), the set of bipartite graphs with m left vertices, n right vertices, t edges chosen with replacement from the set of possible edges, and each vertex of degree at least one. The main results are computation of the thresholds for the emergence of a giant component and for the graph to be connected, and an asymptotic formula for the expected number of trees with i left and j right vertices.

Preprint as a PDF file June 4, 2004 version