Small Dominating Sets

Aug 30, 2021. Small dominating sets in connected graphs by @Busybee_mou
Aug 30, 2021
Feature on homepage

@Busybee_mou's approach to a graph theory puzzle

Here's the original tweet thread:
Select a random subset such that each is chosen with probability , independently.
An edge is crossing if it is between vertices and such that precisely one of and is in .
Let be the subset of all vertices not in such that has NO friend (I mean neighbour) in . Clearly then the union is a subset for which, every vertex not in has a friend in . Note that
What is ?
[Turns out to be , reveal toggle to see why.]
For a vertex to be in (keep in mind that as is random, too is a random subset), it must be the case that neither not ANY of its friends has been chosen to be included in
If denotes the number of friends of, then:
Via linearity of expectations, we get:
since .

So now, we have to minimize the function over . We have , which is increasing as long as and decreasing as long as . Thus, the minimum is attained at . This yields:

A different way of selecting . Suppose we fix p and we select uniformly randomly out of all possible subsets of cardinality of . Define the same as before. For to be in , neither nor any of its friends can be included in , which means that in that case must have been chosen from among subsets of cardinality of , where indicates the set of all friends of . Thus:
This actually gives only a slight improvement over the previous bound, and this improvement becomes insignificant for large.