Number of adjacents in graph after permutate the nodes

22 Views Asked by At

Given a graph $G=(V,E)$ with $|V| = n$ and $|E| = \frac{\alpha n^2}{2}$, let $\sigma : V \rightarrow V$ be a permutation over $V$ taken randomly and uniformly from all $n!$ possibilities. Define $D = |\{ v \in V : (v, \sigma(v)) \in E \}|$. I want to prove that for all $k >0$, it holds that $\Pr(|D - \alpha n| > k) < 2e^{-k^2/Cn}$ for some constant $C$.
A colleague of mine mentioned that she once saw something similar, solved using martingales (or "exposure martingales"). I tried reading about it, but hopelessly. Any help will be welcome.