Max matching size in a random graph

Question

Consider the random graph $G(n,\frac{1}{n})$. I'm trying to estimate the size of the maximum matching in $G$.

If we look at one vertex, the expected value of its degree is $\frac{n-1}{n}$ so it seems like with high prob it should be 1.

So if I can show that with high probability half of the vertices has degree $1$, then with high probability the size of maximum match in $G$ would be of size $\frac{n}{4}$, but I couldn't prove it, and I'm looking for a hint on how to show that or something similar to that claim.

Answer 1

First, just because the expected value of a fixed vertex is $\frac{n-1}{n}$ does not mean w.h.p. its degree is 1. In fact, $$ \text{Pr(deg(}v\text{)=1)} = {n-1 \choose 1} \frac{1}{n} \left(1-\frac{1}{n}\right)^{n-2} \approx 1 \cdot e^{-1}. $$ Now if $X$ is the random number of vertices with degree exactly 1, then $E[X] \approx e^{-1} n$.

Let $Y$ be the number of isolated edges. Note that there is clearly a matching that is at least $Y$. Now $$ E[Y] = {n \choose 2} \frac{1}{n} \left(1-\frac{1}{n}\right)^{2(n-2)} \approx \frac{n}{2e^2}. $$ Now at that remains is to show that $Y$ is concentrated around its mean.

Answer 2

I would like to expand on the answer of D Poole, specifically to show the concentration of $Y$.

It is actually really easy if we use the method of bounded differences:

Theorem Suppose that $X_1$, $\cdots$, $X_n \in \mathcal{X}$ are independent, and $f:\mathcal{X}^n\to \mathbb{R}$. Let $c_1,\cdots,c_n$ satisfy $$ \sup_{x_1,\cdots,x_n,x_i'} |f(x_1,\cdots, x_{i-1},x_i,x_{i+1},\cdots, x_n) - f(x_1,\cdots, x_{i-1},x'_i,x_{i+1},\cdots, x_n)|\le c_i$$ for $i=1,\cdots, n$. Then $$\mathrm{P}\{f-\mathbb{E}f\ge t\}\le \exp\left( \frac{-2t^2}{\sum_{i=1}^n c_i^2}\right).$$

Here we have $n \choose 2$ random variables, namely 0-1 variables saying which edges are present in the graph. When we add/remove one edge, the number of isolated edges changes by at most two. Therefore $Y$ is exponentially concentrated around the mean.