Perfect matchings in random intersection graphs
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.
- Component evolution in a secure wireless sensor network
- Connectivity of the uniform random intersection graph
- Diameter, connectivity, and phase transition of the uniform random intersection graph
- Large independent sets in general random intersection graphs
- On Random Intersection Graphs: The Subgraph Problem
- On the existence of a factor of degree one of a connected random graph
- Sharp threshold functions for random intersection graphs via a coupling method
- The vertex degree distribution of random intersection graphs
- Tree-Matchings in Graph Processes
- Zero–One Laws for Connectivity in Random Key Graphs
- On randomized stopping points and perfect graphs
- Random matchings in regular graphs
- Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
- Perfect matchings in random polyomino chain graphs
- A Fast Perfect-Matching Algorithm in Random Graphs
- \(k\)-connectivity of uniform \(s\)-intersection graphs
- Maximum matchings in a pseudofractal scale-free web
- The coupling method for inhomogeneous random intersection graphs.
- Exact matching of random graphs with constant correlation
- The number of perfect matchings, and the nesting properties, of random regular graphs
This page was built for publication: Perfect matchings in random intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434152)
