I'm trying to solve an exercise from "Probability and computing: Randomized algorithms and probabilistic analysis" by Michael Mitzenmacher and Eli Upfal:
A hyper graph $H$ is a pair $(V,E)$ where $V$ is the set of vertices and $E$ is the set of hyper edges (i.e. a certain set of subsets of $V$). We call $H$ "$r$-uniform" if each hyper edge has size $r$. A "dominating set" $S$ in $H$ is a set of vertices such that every hyper edge $e$ intersects $S$.
Let $H=(V,E)$ be an $r$-uniform hyper graph with $n$ vertices and $m$ edges. Why must there be a dominating set of size $\leq (m+n \ln r)/r$? Why must there be a dominating set of size $\leq np+(1-p)^r m$ for every real number $0 \leq p \leq 1$?
Does anybody have an idea for a solution? I'm pretty sure it should be solved using the probabilistic method but I'm just really having a hard time of pinpointing a specific solution.
Also if anybody knows of a solution manual for the entire book I'd like a reference please.
Thanks
EDIT (October 2016): I am a professor who teaches a course using this book. I have edited the question to make it harder for my students to google, since this is the only place online currently where an answer to this exercise can be found. In general, it's very hard to find good, accessible problems about randomized algorithms, so I'd be really happy if people would stop putting solutions online for the few good problems we have.
Let $T$ be a set of vertices constructed as follows:
For each vertex $v$ in $V$, $v$ is included in $T$ independently with probability $p$, $p$ to be determined.
Let $X$ = $| T |$ . It is obvious that $E[X]$=$np$.
For each edge $S$ in $E$, let $Y_{s}$ be the random variable which indicates whether $S\cap{T}=\emptyset$. $Y_{s}=\begin{cases}1 & S\cap{T}=\emptyset\\ 0 &otherwise\end{cases}$. It is obvious that $E[Y_{s}]=\left(1-p\right)^r$
Let random variable $Y$ be the number of such edges, by linearity of expectation, it holds that $E[Y]=\sum_{e\in{E}}{E[Y_{s}]} =m\left(1-p\right)^r$.
Note that although $T$ is not necessarily an blocking set, it can be modified to one if we add one endpoint of those edges that have no endpoint in $T$ into $T$. Let $T'$ be the resulting set. It is obvious that $T'$ is an blocking set since every edge has a endpoint in it.
Since there are $Y$ such edges, there are at most $Y$ vertices that are added to make it become $T'$ . Therefore, $|T'|<= X+Y$. By linearity of expectation, $E|T'|<= E[X+Y]=np+m(1-p)^{r}<=np+me^{-pr}$;
The right hand side is minimized at $p=\frac{\ln{\frac{mr}{n}}}{r}$, and the minimum is $\frac{n\ln{\left(\frac{mr}{n}+1\right)}}{r}$. Notice that $\frac{n\ln{\left(\frac{mr}{n}+1\right)}}{r}<=\frac{\left(m+n\ln{r}\right)/r}{r}$, paying attention that $\frac{m}{n}<=1$.