Large cliques in sparse random intersection graphs (Q528977)

Summary: An intersection graph defines an adjacency relation between subsets \(S_1,\dots, S_n\) of a finite set \(W=\{w_1,\dots, w_m\}\): the subsets \(S_i\) and \(S_j\) are adjacent if they intersect. Assuming that the subsets are drawn independently at random according to the probability distribution \(\mathbb{P}(S_i=A)=P(|A|){\binom{m}{|A|}}^{-1}\), \(A\subseteq W\), where \(P\) is a probability on \(\{0, 1, \dots, m\}\), we obtain the random intersection graph \(G=G(n,m,P)\). We establish the asymptotic order of the clique number \(\omega(G)\) of~ a sparse random intersection graph as \(n,m\rightarrow+\infty\). For \(m = \Theta(n)\) we show that the maximum clique is of size \[ (1-\alpha/2)^{-\alpha/2}n^{1-\alpha/2}(\ln n)^{-\alpha/2}(1+o_P(1)) \] in the case where the asymptotic degree distribution of \(G\) is a power-law with exponent \(\alpha \in (1,2)\). It is of size \(\frac {\ln n} {\ln \ln n}(1+o_P(1))\) if the degree distribution has bounded variance, i.e., \(\alpha>2\). We construct a simple polynomial-time algorithm which finds a clique of the optimal order \(\omega(G) (1-o_P(1))\).