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-1)!!\binom{n}{2k}p^{k}$. Note here double factorial !! is the product of all even numbers up to $(2k-1)$ of the same parity. 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!

Edit: It turns out that from Theorem 5.6. here https://www.math.cmu.edu/~af1p/BOOK.pdf we know the distribution is normal. All that remains is to work out the variance of $X$. In fact there is a later section on tail probabilities which is also useful.

  • 2
    $\begingroup$ Why is your expectation correct? You should be choosing $2k$ vertices, not just $k$. Can you revise your calculations? $\endgroup$ Commented Jul 6, 2023 at 23:57
  • 1
    $\begingroup$ Also, why $p^{-k}$ and not $p^k$? $\endgroup$ Commented Jul 7, 2023 at 0:23
  • $\begingroup$ thank you I've edited my question $\endgroup$ Commented Jul 7, 2023 at 7:42
  • $\begingroup$ @InuyashaYagami apologies, this factor was not so important to me as it only depends on $k$ but I should have been more careful before posting. $\endgroup$ Commented Jul 7, 2023 at 8:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.