2
$\begingroup$

I'm reading Introduction to Random Graphs by Frieze and Karonski. Theorem 6.2 determines the threshold for the appearance of a perfect matching in $\mathbf{G}_{n,p}$:

Let $\omega=\omega(n)$, $c>0$ be a constant, and let $p=\frac{\ln n+c_n}{n}$. Then: $$\lim_{n\rightarrow\infty}\mathbb{P}\left({\bf G}_{n,p}\;{\rm has}\;{\rm a}\;{\rm perfect}\;{\rm matching}\right)=\begin{cases} 0 & {\rm if}\;c_{n}\rightarrow-\infty\\ e^{-e^{-c}} & {\rm if}\;c_{n}\rightarrow c\\ 1 & {\rm if}\;c_{n}\rightarrow\infty \end{cases}.$$

The proof begins with the following assertion:

We will for convenience only consider the case where $c_n=\omega\rightarrow\infty$ and $\omega=o(\ln n)$. If $c_n\rightarrow -\infty$ then there are isolated vertices w.h.p. and our proof can easily be modified to handle the case $c_n\rightarrow c$.

After thoroughly going over the details of the proof, I still struggle with seeing how to modify the proof for the case $c_n\rightarrow c$. If anyone happens to be familiar with the textbook and/or able to give me some direction, that would be very helpful.

Let me sum up where my problem is. Leaving the two technical lemmas aside (6.3 and 6.4), the main idea is to use staged exposure $\mathbf{G}_{n,p}=\mathbf{G}_{n,p_1}\cup \mathbf{G}_{n,p_2}$ with $p_1=\frac{\ln n+\frac{\omega}{2}}{n}$ and $p_2\sim\frac{\omega}{2n}$, and then showing that if $\mathbf{G}_{n,p_1}$ doesn't already contain a PM, then adding each edge of $\mathbf{G}_{n,p_2}$ one by one has a good chance of increasing the size of the maximum matching at each step.
However, it seems quite crucial that $\delta(\mathbf{G}_{n,p_1})\geq 1$ (which ensures that we can use Lemma 6.4) and that w.h.p. $\mathbf{G}_{n,p_2}$ contains at least $s=\frac{\omega n}{4}=\omega(n)$ edges, which ensures $\mathbb{P} \left( \mathrm{Bin} \left(s,\frac{\alpha^2}{2}\right)< \frac{n}{2} \right)=o(1)$. Both facts do not carry out to the case $c_n\rightarrow c$, so I cannot see how the the same ideas would work.

$\endgroup$
1
  • 1
    $\begingroup$ You're right that this seems puzzling. The first issue - that $\delta(G_{n,p_1}) \ge 1$ w.h.p. - isn't concerning: that's where we'd get the probability $e^{-e^{-c}}$ from. But we can no longer reserve $\omega(n)$ edges: when $np - \ln n = c_n \to c$, if we want $np_1 - \ln n \to c$, we must have $p_2 = o(\frac1n)$, giving us only $o(n)$ edges in reserve. $\endgroup$ Commented Oct 7, 2021 at 18:25

1 Answer 1

Reset to default
1
$\begingroup$

Here's an attempt at resolving this, maybe not the cleanest.

As in the original proof, split $\mathbb G_{n,p} = \mathbb G_{n,p_1} \cup \mathbb G_{n,p_2}$, but this time with the following properties:

  • $\mathbb G_{n,p_1}$ consists of a giant component together with $o(n)$ isolated vertices, whp.
  • $\mathbb G_{n,p_2}$ has $\omega(n)$ edges, whp.

Now partially expose the edges of $\mathbb G_{n,p_2}$ to split them into $E_1 \cup E_2$, where $E_1$ are the edges incident on an isolated vertex of $\mathbb G_{n,p_1}$. We can say that:

  • $\mathbb G_{n,p_1} \cup E_1$ is connected with probability tending to $e^{-e^{-c}}$, because $\mathbb G_{n,p}$ is connected with that probability, and $E_2$ can't help us with the isolated vertices.
  • $|E_2| = \omega(n)$ whp, because each edge has an $o(1)$ probability of being incident on one of the $o(n)$ isolated vertices.

From now on, assume $\mathbb G_{n,p_1} \cup E_1$ is connected. Then the technical lemmas of the proof should now be valid for $\mathbb G_{n,p_1} \cup E_1$, because all the claims are either already valid for $\mathbb G_{n,p_1}$, or else need minimum degree $1$. (This needs checking; the technical lemmas are pretty technical and I didn't bother. But it ought to be true.) In particular, a uniformly random edge still has a constant probability of increasing the size of the matching.

The edges of $E_2$ are not uniformly random, but they are random enough for the same results to apply: conditional on our partial exposure, they are uniformly chosen from $\binom n2 - o(n^2)$ possibilities. So we can still say that with $\omega(n)$ tries to boost the matching, we will have enough successful boosts to get to a perfect matching in $\mathbb G_{n,p}$.

$\endgroup$
1
  • $\begingroup$ Thank you very much Misha! I appreciate your time and your great answers. I'll try to sit and work out the details. $\endgroup$ Commented Oct 8, 2021 at 8:28

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.