Graph has $3n$ vertices and every two has common neigbour. Show there is a dominant set with $n$ vertices.

Question

A town has $3n$ citizens. Any two persons in the town have at least one common friend in this same town. Show that one can choose a group consisting of $n$ citizens such that every person of the remaining $2n$ citizens has at least one friend in this group of $n$.

I'm interested in an explanation of this probabilistic solution.

I don't understand what is that random sample of $np$ vertices. Is $np$ an integer?!? And what is this replacement? And what is this union $S$ about?

Answer 1

Often in proofs like this, there's an implicit "floor" or "ceiling" to make the relevant quantities into integers, which only slightly affects the final results. To make the solution a little clearer, let $k = \lceil np \rceil$ (the least integer $\geq np$).

By a random sample of $np$ vertices with replacement, they mean that $k$ vertices $x_1, \dots, x_k$ are chosen uniformly and independently at random (i.e. so $x_1, \dots, x_k$ are i.i.d. uniform vertices). You might imagine a process of picking the $k$ vertices randomly, one after another, putting the chosen vertex back after each choice (so it can be picked again). The union $S$ of the vertices is just the set containing the chosen vertices $x_1, \dots, x_k$.

The rest of the proof can be rephrased as:

Note that $|S| \leq k \leq np+1$. Now the probability that a particular fixed vertex $v$ fails to have a neighbor in $S$ is strictly less than $(1 - p)^k$, because we need each of $k$ samples to miss the neighborhood of $v$. This is at most $(1-p)^{np} \leq e^{-np^2} \leq e^{-\log n} = n^{-1}$. Therefore a union bound over the $n$ choices of $v$ produces the result.