An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$.
Consider the following simple 1-round randomized algorithm:
each node $v$ picks a random real number $r_v \in [0, 1]$ and then, $v$ joins a set $S$ if its random number is a local minima, that is, if $r_v < r_u$ for all neighbors $u$ of $v$.
I need to prove that, with high probability, the set $S$ is a $(2, O(\log n))$-ruling set.
Proving the $\alpha=2$ part is easy, because from the creation of $S$, only one vertex in $N(v) \cup \{v\}$ can be a local minima, and will be in $S$. Which means that the minimal distance between vertices in $S$ is $2$.
However, I can't manage to prove the $\beta$ part.
Help would be appreciated!
For each vertex $v$, let $D_i$ be the number of vertices at distance $i$ from $v$. Let $m_i$ be the minimum of the labels in $D_i$.
See if you can show the following claims.
For any $i$, if $E_i: m_i < \min(m_1, \cdots, m_{i - 1})$ does not happen, then there is a local minima at distance at most $i$ from $v$.
Let $n_i = |D_i|$. Then $\mathbb{P}(E_i) = n_i / (n_0 + n_1 + \cdots + n_i)$, and the events $E_i$ are independent.
We have $$\prod_{i = 1}^{3\log_2 n} \mathbb{P}(E_i) < n^{-2}.$$