×

Random intersection graphs when \(m=\omega(n)\): An equivalence theorem relating the evolution of the \(G(n,m,p)\) and \(G(n,p)\) models. (English) Zbl 0951.05096

This paper deals with random graph models \(G(n,p)\), \(n\) being the number of vertices of the graph \(G\) and \(p\) the probability of having an edge connecting two vertices, and the random intersection graph models \(G(n,m,p)\) in which each of \(n\) vertices is assigned a random subset from a fixed set of \(m\) elements (an edge being between two vertices when their associated sets have at least one common element). It is shown here that the evolutions, when \(G(n,p)\) is compared with \(G(n,m,p)\), are different for some values of \(m\) and equivalent for others. For \(\alpha> 6\) and \(m= n^\alpha\), the total variation distance between the graph random variables is shown to have limit zero.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and The probabilistic method, Wiley, New York, 1992.
[2] Group representations in probability and statistics, Institute of Mathematical Statistics, Haywood, CA, 1988.
[3] Erd?s, Publ Math Debrecen 6 pp 290– (1959)
[4] Erd?s, MTA Mat Kut Int Kozl 5 pp 17– (1960)
[5] ? Random graphs,? Handbook of combinatorics, Vol. 1, (Editors), M.I.T. Press, Cambridge, 1995, pp. 351-380.
[6] Karo?ski, Combin Probab Comput 8 pp 131– (1999)
[7] ? On the equivalence of two basic models of random graphs,? Random Graphs ’87: Proceedings of the 3rd International Seminar on Random Graphs and Probabilistic Methods in Combinatorics, 1990, pp. 151-157. · Zbl 0746.05056
[8] Marczewski, Fund Math 33 pp 303– (1945)
[9] Graphical Evolution, Wiley, New York, 1985.
[10] Random intersection graphs, Ph.D. dissertation, Department of Mathematical Sciences, The Johns Hopkins University, 1995.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.