- #1

- 151

- 0

**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?