Distance-2-Matchings of Random Graphs

C.M. Reidys

Los Alamos National Laboratory, MS M997, CCS-5, Los Alamos, NM 87545, USA

reidys@lanl.gov

Annals of Combinatorics 8 (1) p.93-101 March, 2004

Abstract:

In this paper we study the maximal size
of a distance-*2*-matching in a random graph
*G*_{n, M}, i.e., the probability space consisting of subgraphs of
the complete graph over n vertices, *K*_{n}, having exactly *M* edges and uniform probability measure.
A distance-2-matching in a graph *Y*, *M*_{2}, is a set of *Y*-edges
with the property that for any two elements every pair of their 4 incident vertices has *Y*-distance* 2*. Let M_{2}(*Y*)
be the maximal size of a distance-2-matching in *Y*.
Our main results are the derivation of a lower bound for
*M*_{2}(*Y*) and a sharp concentration result
for the random variable
for *M*=*c* (*n*-1)/2 with *c* > 0.

References:

1. N. Alon, J. Spencer, and P. Erdös, The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, A Wiley-Interscience Publication, John Wiley & Sons, New York, 1992.

2. K. Azuma, Weighted sum of certain dependent variables, Tohoku Math. J. 3 (1967) 357–367.

3. B. Bollobás, Random Graphs, Academic Press, London, 1985.

4. J.L. Doob, Stochastic Processes, John Wiley & Sons, New York, 1953.

5. M. Karonski, J. Jaworski, and A. Rucinski, Eds., Random Graphs, Chapter 1, North-Holland Publishing Co., Amsterdam, 1987.

6. B. Maurey, Construction de suites symmétriques, C. R. Acad. Sci. Paris Sér. A-B 289 (1979) A679–A681.