<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue1" %>
Distance-2-Matchings of Random Graphs
C.M. Reidys
Los Alamos National Laboratory, MS M997, CCS-5, Los Alamos, NM 87545, USA
Annals of Combinatorics 8 (1) p.93-101 March, 2004
AMS Subject Classification: 05C80, 05C70
In this paper we study the maximal size of a distance-2-matching in a random graph Gn, M, i.e., the probability space consisting of subgraphs of the complete graph over n vertices, Kn, having exactly M edges and uniform probability measure. A distance-2-matching in a graph Y, M2, 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 M2(Y) be the maximal size of a distance-2-matching in Y. Our main results are the derivation of a lower bound for M2(Y) and a sharp concentration result for the random variable for M=c (n-1)/2 with c > 0.
Keywords: random graph, martingale, distance-2-matchings


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.