suppose I have n nodes, and I pick at random a partial matching (i.e. disjoints edges) containing $$\alpha n$$ edges.
How can I show the probability of having at least one edge which both of its endpoints are in the first $$c = \epsilon\sqrt{n/\alpha}$$ nodes is at least $$\Omega(\epsilon^2)$$
Is it implied somehow by the birthday paradox?
Thanks!
Good catch, it is basically the birthday paradox. Here is a proof sketch -- I can expand some of the details if necessary.
First, the number of matched vertices among the first $c$ vertices is tightly concentrated around $2\alpha c$ -- in a way that can be quantified by standard Chernoff bounds. That way, you can basically reduce to the following problem: given a random perfect matching of $2\alpha n$ vertices, what is the probability that there is an edge contained in a (fixed) set of $2\alpha c$ vertices?
One way to see this distribution is to first generate for each vertex independently a random integer between $1$ and $\alpha n$ (which is the classical birthday paradox setting), and then condition on these integers corresponding to a matching. Observe that the conditioning only makes collisions more likely. In other words, the probability that there is no edge contained in the set of $2\alpha c$ vertices is at most $$1\left(1-\frac{1}{\alpha n}\right)\ldots\left(1-\frac{2\alpha c-1}{\alpha n}\right)\le \exp(-K\alpha c^2/n),$$ for some constant $K$. Picking $c=\varepsilon\sqrt{n/\alpha}$ gives the desired bound.