Diameters of random bipartite graphs
type: Item
instance of: scholarly article
title: Diameters of random bipartite graphs
zbMATH Open document ID: 0532.05051
DOI: 10.1007/BF02579152
author: Béla Bollobás
author: Victor Klee
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3843800
zbMATH Keywords: bipartite graphs
zbMATH Keywords: diameter
zbMATH Keywords: convex properties
MaRDI profile type: Publication
cites work: Multi-Component Systems and Structures and Their Reliability
cites work: Counting Coloured Graphs of High Connectivity
cites work: Q4769056
cites work: On the strength of connectedness of a random graph
cites work: Q3898520
cites work: Q5628166
cites work: Q5517743
cites work: Hamiltonian circuits in random graphs
full work available at URL: https://doi.org/10.1007/bf02579152
OpenAlex ID: W2080633915
description: scientific article; zbMATH DE number 3843800