as a follow up from this question :

Suppose that we have a simpler problem, where the probability $p$ is fixed. Of course we could use the above result to proove that almost every graph in the model $\mathcal{G}_{n,n,p}$ contains a perfect matching, saying for instance that $$ p > \frac{\sqrt{n} + \log{n}}{n}$$ for big enough $n$.

However, couldn't we find a more direct result? I've been looking at the probability of findind a set $S$ (size $k$) giving a contradiction for Hall's mariage theorem. With $q=1-p$, we need each element of $S$ not connected to the $n-k-1$ elements not in $N(S)$, therefore : $$ Pr[ |N(S)|<|S| ] \leq q^{nk-k(k-1)}$$

And $$Pr[\nexists \text{ a perfect matching}] \leq \sum_{k=1}^n \binom{n}{k}q^{nk-k(k-1)}$$

But from there, trying to proove that this sum tends to 0, simple binomial approximation $\sim n^k/k!$ gives too large a bound. Would you recommand any other calculation? Thanks


Many approximations to the binomial $\binom nk$ are not symmetric in $k$ and $n-k$, so they perform badly when $k$ is close to $n$. (For example, $\frac{n^k}{k!}$ is somewhere around $e^n$ when $k=n$, even though actually $\binom nn = 1$.)

Here, the sum is almost but not quite symmetric: we can write the power of $q$ as $q^{k(n+1-k)} < q^{k(n-k)}$, and the latter is symmetric. So we can bound the sum by $$ 2 \sum_{k=1}^{n/2} \binom nk q^{k(n-k)} $$ and avoid the problematic values of $k$, getting a sum that's easy to bound using your approximation. It's even enough to write $\binom nk \le n^k$ and get $\binom nk q^{k(n-k)} \le (n \cdot q^{n-k})^k \le (n \cdot q^{n/2})^k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.