MHB Probability of Having a Totally Dominating Set (Probabilistic Methods)

[joypav]

Problem: A vertex set $S$ in a graph $G$ is said to be totally t-dominating, for a positive integer t, if
$|N(v) \cap S| \geq t$ for all $v \in V (G)$.
Suppose that r, t, n are positive integers such that $r > 2t$ and $t \geq \frac{14}{3}\cdot ln(2n)$, and let $G$ be an r-regular n-vertex graph. Choose a random vertex set $S$ by independently adding each vertex to $S$ with probability p, where $p =\frac{2t}{r}$. Prove that $P[S$ is totally t-dominating$] > \frac{1}{2}$.

I honestly am not sure where to begin with this problem.
I know that $E[|S|] = n \cdot p = n \cdot \frac{2t}{r}$ (the expectation of the size of $S$) and $|E(G)| = \frac{nr}{2}$ (because G is r-regular). I don't know if either of these will be of any use...

Here is what I was thinking.
Fix $v \in V(G)$. $G$ is r-regular, so label each of $v$'s neighbors: $N(v) = \left\{u_1,...,u_r\right\}$.
Let $A_{v,u_i}$ be the event that $u_i \in S$.
Let $X_{v,u_i}$ be the indicator for $A_{v,u_i}$, (i.e. it is equal to 1 if $u_i \in S$ and 0 otherwise).
Let $X_v$= the # of neighbors of $v$ that are in $S$.
Then, $X_v = \sum_{u_i \in N(v)} X_{v,u_i}$.

We "want" $v$ to have at least t neighbors in $S$. So then we'd like to look at $P[X_v \geq t]$.

Then, consider the event $X$: $S$ is totally t-dominating.
We want to show that $P[X] > \frac{1}{2}$.

Is this at all on the right track?

 

[joypav]

Another proof for your consideration (I was busy busy busy working on problems today!).

Proof:
Fix $v \in V(G)$. G is r-regular, so we know $|N(v)|=r$. Label $v$'s neighbors $u_1, ..., u_r$. Let $A_{u_i}$ be the event that $u_i \in S$ and let $X_{u_i}$ be its indicator. Let $X_v = \sum_{i=1}^r X_{u_i}$, (giving the number of neighbors that $v$ has in $S$). Using Chernoff's, we may bound the "bad" event: that $v$ has less than $t$ neighbors in $S$. Apply Chernoff's with,
$$E[X_v] = \sum_{i=1}^r X_{u_i} = r(p) = r(\frac{2t}{r})=2t$$
$$P[|N(v) \cap S| \leq t] = P[X_v \leq t] = P[X_v \leq 2t - t] = P[X_v \leq E[X_v] - t]$$
$$\leq e^{-\frac{t^2}{2(np+t/3)}} = e^{-\frac{t^2}{2(4tn/r+2t/3)}} = e^{-\frac{t^2}{\frac{12tn+2tr}{3r}}} = e^{-\frac{3rt^2}{12tn+2tr}} = e^{-\frac{3rt}{12n+2r}} < e^{-\frac{3(14/3ln(2n)}{14}} = e^{-ln(2n)}$$
Then,
$$\sum_{v \in V(G)} P[|N(v) \cap S| \leq t] = \sum_{v \in V(G)} P[X_v \leq t] < n \cdot e^{-ln(2n)} = e^{ln(n)-ln(2n)} = e^{ln(n/2n)} = e^{ln(1/1)} = \frac{1}{2}$$
If the probability of the "bad" event is less than $\frac{1}{2}$, then the probability of $S$ being totally t-dominating $> 1-\frac{1}{2} = \frac{1}{2}$.