Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm trying to solve exercise 6.7 on page 150 in "Probability and computing-Randomized algorithms and probabilistic analysis" by Michael Mitzenmacher:

A Hypergraph H is a pair of sets (V,E) where V is the set of vertices and E is the set of hyperedges. Every hyperedge in E is a subset of V. An r-uniform hypergraph is one where the size of each edge is r. A dominating set in a hypergraph is a set of vertices V subset of E such that every edge e intersects S. That is S hits every edge of the hypergraph.

Let H=(V,E) be an r-uniform hypergraph with n vertices and m edges. show that there is a dominating set of size at most (m+n*ln(r))/r. also show that there is a dominating set of size at most [np+((1-p)^r)*m] for every real number 0<=p<=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.


share|improve this question
First, this question is off-topic for this website (it is not research-level). See FAQ. Second, you can find a solution (for r=2) in the book "Probabilistic method" by Alon and Spencer, which I would recommend as the best introduction to the subject. –  Boris Bukh May 10 '13 at 14:16
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.