Diameters of random bipartite graphs (Q788749)

This paper concerns random bipartite graphs in the space G(m,n;p). Such a graph's vertex set is the disjoint union of an m-set V and an n-set W, and each of the mn possible edges, independently of the others, is present with probability p and absent with probability 1-p. More precisely, the authors take a sequence of such graphs, the n-th graph being in \(G(n)=G(m(n),n;p(n))\), where \(\{\) m(n)\(\}\) is a sequence of positive integers with m(n)\(\leq n\) and \(\{\) p(n)\(\}\) is a sequence of probabilities. Using terminology that is common in random graph theory (but unfortunately somewhat at odds with that of probability theory), they say that a property of graphs holds for almost all graphs in G(n) if its probability approaches 1 as n \(\to \infty\). They prove two main theorems. Theorem A states roughly that if m(n) is sufficiently small (approximately of order /(n log n)) and p(n) is not too small, then it is true of almost every graph in G(n) that any two vertices in V have a common neighbor in W. (For such graphs the diameter is thus no greater than 4.) Theorem B essentially determines the (common) diameter of almost all graphs in G(n) when m(n) is at least (log \(n)^ 4/p(n)\), under some additional conditions on the growth of m(n) and p(n). The proof of Theorem B especially is an instructive demonstration of some proof techniques in random graph theory, containing lemmas that are interesting on their own. The paper concludes with a result connecting the above model for random bipartite graphs with the other commonly-considered model: that in which the edge set is chosen at random from among all possible sets of a given size. The connection is provided for all convex properties of graphs; the diameter properties considered in Theorems A and B are convex.