# Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability

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$$.

Let $$G$$ be graph which is nearly regular, with all degrees in $$[k,2k]$$.

Consider the following creation of the set $$S$$:

each vertex $$v$$ chooses a random number $$r_v$$ uniformly in $$[0,1]$$. If $$r_v$$ is local minima, namely $$r_v < r_u$$ for any neighbor $$u \in N(v)$$, then $$v$$ joins the set $$S$$.

I want to show that with high-probability, it has a set $$S$$ which is a $$(2,O(\log n))$$ ruling set.

Proving the $$\alpha$$ part is easy, because from the creation of $$S$$, only one vertex in $$N^{+}(v)$$ can be a local minima, and will be in $$S$$.

Proving the $$\beta$$ part is more difficult.

I can prove that $$Pr[S \cap N^{+}(v) \ne \emptyset]$$ for every $$v$$ with high probability. But not sure how to continue from here.

Help would be appreciated

I was about to complain that this statement:

Then, I can prove that $$Pr[S \cap N^{+}(v) \ne \emptyset]$$ for every $$v$$ with high probability

is probably wrong, because it would imply a stronger result, namely that nearly regular graphs have a $$(2, 1)$$ ruling set w.h.p.

But then I realised that, not only does this stronger claim actually hold, an even stronger claim holds, and is almost trivial to show:

Theorem: Every graph has a $$(2, 1)$$ ruling set.

Proof sketch: Choose any vertex $$v$$, add it to $$S$$, and remove it and its neighbours (which have distance 1 from $$v$$). Repeat until no vertices remain. Every pair of vertices in $$S$$ have distance $$\ge 2$$ since the only vertices with distance 1 are neighbours, and we removed all of those.

This claim is stronger than the original in three ways: It applies to every graph (not just nearly regular graphs), always (not just w.h.p.), and $$1 < \log n$$ except on a finite number of graphs.

This makes me wonder if you missed a condition.

• First of all, thanks for the answer. Moreover, you were right, I missed a condition, the question asks about a specific set $S$ to be a ruling set. Commented Jul 13, 2023 at 18:52