Let G be a graph with 3n vertices, with the property that every pair of vertices has codegree at least 1. That is, ∀x∀y∃z such that xz and yz are both edges. Show that G has a dominating set of size n.
I do not understand the following proof;i dont understand the part "this is at most $e^{−np2}≤ e^{− log n} = n^{−1}$. Therefore, a union bound over the n choices of v produces the result." and also the neighbor part; if anyone could explain what the last paragraph of the proof means that would be great thanks.
Proof:
The codegree condition implies that the diameter of the graph is at most 2. We prove that every $n$-vertex graph with diameter $\leq 2$ has a dominating set (a subset $S$ of vertices such that every other vertex is either in, or has a neighbor in $S$) of size only $\leq\sqrt{nlogn}+1$
To see this, let $p =\sqrt{log n/n}$
Observe that since the diameter is at most 2, if any vertex has degree ≤ np, then its neighborhood already is a dominating set of suitable size. Therefore, we may assume that all vertices have degree strictly greater than np. It feels “easy” to find a small dominating set in this graph because all degrees are high. Consider a random sample of np vertices (selected uniformly at random, with replacement), and let S be their union. Note that $|S| \leq np$. Now the probability that a particular fixed vertex $v$ fails to have a neighbor in S is strictly less than $(1 −p)^np$, because we need each of np independent samples to miss the neighborhood of v. This is at most $e^{−np2}≤ e^{− log n} = n^{−1}$. Therefore, a union bound over the $n$ choices of $v$ produces the result.