Distance-2-matchings of random graphs (Q1889893): Difference between revisions

The paper under review studies what it calls distance-2-matchings in the random graph \(G(n,M)\) on \(n\) labelled vertices (which has \(M\) edges, all possible sets of \(M\) edges being equiprobable). A 2-matching in a graph \(G=(V,E)\) is defined to be a set of edges \(\{a_{1}b_{1},\dots, a_{n}b_{n}\}\) such that, for each \(i\neq j\), we have \(a_{i}\not\sim a_{j}\), \(a_{i}\not\sim b_{j}\), \(a_{j}\not\sim b_{i}\) and \(b_{j}\not\sim b_{i}\). This notion has been studied in other contexts, under the name of an induced matching. Denote by \(M_{2}(G)\) the number of edges in the largest distance-2-matching of a graph \(G\). The main result of the paper under review is a concentration result for the random variable \(M_{2}=M_{2}(G(n,M))\). More precisely it is shown that, for \(\varepsilon>0\), we have \[ P\left(| M_{2}-{\mathbb E}(M_{2}) | >2\varepsilon \sqrt{M}\right)<2\exp(-\varepsilon^{2}/2). \] Here \({\mathbb E}\) denotes expectation (in \(G(n,M)\)). The basic idea of the proof is, unsurprisingly, the use of martingales with bounded differences. A simple lemma is used to show that if one edge is adjoined to an existing graph \(G\), the largest distance-2-matching in the new graph has cardinality within one of \(M_{2}(G)\). This gives the Lipschitz condition and so the standard Azuma-Hoeffding inequality comes into play. What we need now is some kind of lower bound on \({\mathbb E}(M_{2})\). The author succeeds in obtaining such a bound: for example, it implies that if \(M=c(n-1)/2\) (\(c>0\)) then \[ {\mathbb E}(M_{2})\geq \frac{c(n-1)}{2[2c^{2}+2c+1]}-\omega(n) \] where \(\omega(n)\) tends to 0 arbitrarily slowly. This in turn is enough to show that for such values of \(M\) the random variable \(M_{2}(G(n,M))\) is sharply concentrated around its mean. The main idea in the lower bound on \(M_{2}\) is to move from the graph \(G\) to another graph \(L_{2}(G)\) whose vertices are the edges of \(G\), two such being adjacent if and only if one of the four possible edges between these two edges is present in \(G\). Thus \(M_{2}(G)=\alpha(L_{2}(G))\). We now use the lower bound on the independence number of a graph in terms of the sum of (reciprocals of) degrees of vertices: the terms in this sum can be bounded below via estimates \(Z_{ik'}\), the number of edges different from a given edge \(ik'\) which are not incident to either \(i\) or \(k'\) or a vertex adjacent to \(i,k'\). An application to the \` single-frequency-allocation-problem\'\, is outlined.