The intersection graph of random sets (Q1174144)

A model is investigated where \(n\) subsets \(X_ 1,\dots,X_ n\) of \(\{1,\dots,N\}\) are selected independently at random, where each subset has the same probability \(2^{-N}\). The intersection graph \(G^ n\) of these subsets has \(\{1,2,\dots,n\}\) as vertex set, and \(i\neq j\) are adjacent if \(X_ i\cap X_ j\neq\emptyset\). In this paper, the asymptotic behaviour of the graph \(G^ n\), as \(N\) tends to infinity, is investigated. More precisely, the threshold functions for the graph properties of being complete, having independence number at most 2 or at most 3, or having isolated vertices, are given. For instance, if \(n/2^{N/3}\to\infty\), then \(G^ n\) contains three pairwise nonadjacent vertices, while if \(n/2^{N/3}\to 0\), then \(G^ n\) contains no such three vertices, almost surely.