Distribution of $k$-matchings in a random graph

47 Views Asked by At

Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a disjoint union of $k$ edges. Let $X$ be a random variable equal to the number of subgraphs in $G(n,p)$ which are isomorphic to the $k$-matchings. I want to investigate the distribution of $X$.

Clearly for any fixed set of $2k$ vertices $(x_1, y_1, x_2, y_2, ..., x_k,y_k)$ from $G(n,p)$ the probability that there is an edge from ever $x_i$ to every $y_i$ is $p^{k}$. Therefore $\mathbb{E}(X) = 2k!\binom{n}{2k}p^{k}$. But what is the (approximate) distribution of $X$.

For concreteness I am interested in situations where say $p= \frac{1}{3}$ and I'd like to bound the tail probabilities `Chernoff style', i.e. I'd like to be able to bound from above $\mathbb{P}(X \le \frac{1}{a} \mathbb{E}(X)\,) $. Again for concretness say set $a=5$.

I'm sure this must be a studied problem but I'm not familiar with the literature in this area so any pointers would be greatly appreciated!