Perfect matchings in random intersection graphs (Q2434152): Difference between revisions

This paper studies random uniform intersection graphs \(G_{s}(n,m,d)\), where each of \(n\) vertices, independently of all other vertices, chooses a \(d\)-element subset of an \(m\)-element subset uniformly at random, and we then decree that two vertices are adjacent if and only if the subsets chosen by them have at least \(s\) elements in common. Clearly \(s\leq d\). When vertices are thought of as sensors, and elements of the \(m\)-set as randomly predistributed keys, this is a model of secure wireless sensor networks. Note that there is a constant probability \(p_{e}\) that any pair of vertices are connected, but that there is correlation between which edges are present: for example, an edge \(v_{1}-v_{3}\) is more likely to be present if we know that \(v_{1}-v_{2}\) and \(v_{2}-v_{3}\) are present. The object of the paper under review is to determine the threshold for such a graph to have a perfect matching. We consider a sequence of such graphs \(G_{(n)}=G_{s}(n,m,d)\) where \(m(n)\rightarrow\infty\) as \(n\rightarrow\infty\), and \(s(n)\) and \(d(n)\) can be constant, or tend to infinity slowly with \(n\). The main result is that if \(n\) is even, \(\theta>1\) and \(\gamma\in (0,1)\) then, provided \[ \left( {(s+2)}{d\choose s}^{5}(\log\log(n))^{2} \right)^{(3d-s)/(3(d-s))}\leq \log(n)^{1-\gamma}\qquad \qquad(*) \] and that \(\log(n)-\log^{1/2}( n)\leq np_{e}\leq \theta \log(n )\) we have that, letting \({\mathbb M}\) denote the set of graphs with a perfect matching, \(\delta(G)\) denote the minimum degree of the graph and \(r={d\choose s}\), that \[ | \mathbb{P}(G_{n}\in {\mathbb M})-\mathbb{P}(\delta(G_{(n)})\geq 1)| \leq n^{-(\gamma+o(1))(d-s)/(s(s+2)r^{4})}. \] Using an old result from [\textit{E. Godehardt} et al., ``Isolated vertices in random intersection graphs'', in: A. Fink (ed.) et al., Advances in data analysis, data handling and business intelligence. Proceedings of the 32nd annual conference of the Gesellschaft für Klassifikation e.V., joint conference with the British Classification Society (BCS) and the Dutch/Flemish Classification Society (VOC), Helmut-Schmidt-University, Hamburg, July 2008. Berlin: Springer. 135--145 (2010; \url{doi:10.1007/978-3-642-01044-6_12})] the condition \((*)\) inplies that \[ \lim_{n\rightarrow\infty}\mathbb{P}(\delta(G_{(n)})\geq 1)=\begin{cases} 0& \text{if }\;np_{e}-\log(n)\rightarrow -\infty,\\ 1 & \text{if }\;np_{e}-\log(n)\rightarrow \infty\\ e^{-e^{-x}} & \text{if }\;np_{e}-\log(n)\rightarrow x \end{cases}. \] This then gives us a similar condition for having a perfect matching. In particular, note that the threshold for having a perfect matching is, as in the Erdős-Rényi random graph \(G(n,p_{e})\) with \(n\) vertices and each edge present with probability \(p_{e}\) independently, the same as the threshold for minimum degree 1: in other words, the fact that the edges are correlated in \(G_{s}(n,m,d)\) does not affect the threshold probability for a perfect matching. The rough idea of the proof of the main theorem is to prove a lemma (Lemma 1) which guarantees that a graph with a certain mild expansion property has a perfect matching; to classify vertices as tiny, small or heavy and prove that certain reasonable restrictions on these sets of vertices give the condition in Lemma 1 (this is Lemma 2); and then to check that these restrictions do hold with high probability, using various probabilistic and combinatorial techniques.