2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I didn't thought of that direction, but that's probably will solve my problem, I'll try and see what I get. Thanks! $\endgroup$
    – Snufsan
    Jan 8 '16 at 18:24
  • $\begingroup$ Okay using Chernoff bound I showed that X is concentrated around it's mean, but I cant convince myself that I do have a matching of that size. Could you guild me how to show that? $\endgroup$
    – Snufsan
    Jan 9 '16 at 15:12
  • $\begingroup$ Whoops! I changed the post. I was not thinking right when thinking that there is necessarily a matching of size $X/2$. You change still show that $Y$ is concentrated about its mean (try Chebyshev's inequality). I am not sure how you are using Chernoff's bound to show that $X$ is concentrated about its mean, because $X$ is not binomially distributed (the trials are not independent). $\endgroup$
    – D Poole
    Jan 10 '16 at 21:07
  • $\begingroup$ Yeah I already got that and used chebyshev.. Thanks $\endgroup$
    – Snufsan
    Jan 10 '16 at 22:48
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please consider use Math Jax when typing mathematical text. Apart from the nice look, it makes the text searchable so any user who uses the Math.SE search engine can find it and possibly upvote the answer/question. $\endgroup$ Mar 13 '19 at 10:06

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.