On the independence number and Hamiltonicity of uniform random intersection graphs (Q650910): Difference between revisions

This paper studies the independence number of random intersection graphs \(G_{n,m,\lambda}\) on \(n\) labelled vertices where each vertex takes from an \(m\)-element set \(S\) one of the \({m\choose \lambda}\) subsets of order \(\lambda\), all such choices being equally likely and all vertices choosing independently. We then say that two vertices are adjacent if and only if their sets intersect. The main results of the paper under review concern existence of Hamilton cycles and independence numbers in these graphs. The first result is that if \(\lambda\geq 2\) and, for some (small) constant \(\epsilon>0\), \(n\geq (1+\epsilon){m\choose \lambda}\log({m\choose \lambda})\), then \textbf{whp} (i.e., with probability tending to 1 as \(n\rightarrow\infty\)) there is a Hamilton cycle. (For \(\lambda=1\) and \(m\geq 2\) the graph is \textbf{whp} disconnected). The argument is a coupon-collecting one. For further progress since the paper under review, see [\textit{M. Blozelnis} and \textit{I. Radavičius}, ``A note on hamiltonicity of uniform random intersection graphs'', Lith. Math. J. 51, No.\,2, 155--161 (2011; Zbl 1226.05226)]. The paper also studies the size of independent sets. If \(m=\lfloor n^{\alpha}\rfloor\) with \(\alpha<1\) and \(\lambda=O(m^{1/4})\), then for a certain number \(c_{0}=c_{0}(\alpha,m,\lambda)\) (a solution of an equation involving these parameters) we have that \textbf{whp} the largest independent set has order not more than \((1+\epsilon)m/(c_{0}\lambda)\). Further, an application of the second moment method shows that we get close to this bound. The authors finally show that in \(G_{n,m,p}\), where, instead of choosing a \(\lambda\)-element subset of \(m\) uniformly at random, each element of \(S\) is in the set of a given vertex with probability \(p\) independently of all other vertices, the independence number is \textbf{whp} at most \((2+o(1))\log(n)/(mp^{2})\) provided \(p(n)\) grows faster than \(\log(n)/n\) and is \(o(\sqrt{\log(n)/m})\) which in turn is \(o(1)\). Again, a second moment method argument allows us to get close to this upper bound, under slightly more restrictive conditions.