Proof of graph theory on dominating sets

Question

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.

Answer 1

Some of what you have written isn't right in terms of what appears in the exponents; perhaps this is a formatting error rather than errors in the source material.

The neighbourhood of $v$ has more than $np$ vertices, so less than $n-np$ out of $n$ vertices are not neighbours of $v$. Thus the probability that a random vertex is not in the neighbourhood is $< (1-p)$, and the probability that none of the $np$ random vertices are is $<(1-p)^{np}$.

Now $(1-p)\leq e^{-p}$ from looking at the graphs, so $(1-p)^{np}\leq e^{-n^2p}=e^{-\log n}=\frac1n$.

Since the probability that a particular vertex $v$ is not covered is $<1/n$, the chance that some vertex is not covered is $<\frac1n\times n$ by adding up all the individual probabilities. Since the probability is less than $1$, it is possible that this doesn't happen, i.e. you chose a dominating set. So a dominating set must exist.