# pessimistic estimators (Turáns theorem)

Pessimistic estimators in the method of conditional probabilities.

In applying the method of conditional probabilities, exact conditional probabilities (or expectations) are sometimes hard to compute. Pessimistic estimators can be used instead. We illustrate the idea by example, using Turán’s theorem.

# Existence proof (Turán’s theorem)

Recall that Turán’s theorem states that any -vertex graph contains an independent set of size at least , where is the average degree.

We assume familiarity with the proof. It considers the vertices in random order, taking them greedily (taking each vertex unless a neighbor has already been taken). The expected size of the resulting independent set is at least , because a vertex with degree has at least a chance of being taken, and .

# Applying the method of conditional probabilities

To guarantee a successful outcome, instead of choosing the next vertex randomly from the remaining vertices at each step, the algorithm should choose the vertex deterministically, so as to keep the conditional expectation of the size of the final set at or above . The next step is to analyze this conditional expectation.

If some vertex is added to the independent set at some point, then no neighbors of will be added after that. Imagine for the analysis that, when is chosen, and all its neighbors are deleted from the graph.

Suppose that some vertices have been considered so far. Let contain those vertices that have been added to the independent set so far. Let denote the remaining (undeleted) vertices.

All vertices in will of course end up in the independent set. Each vertex will be added to provided it is considered before any of its remaining neighbors (in ). This will happen with probability at least , where is the degree of in the original graph. (Indeed, it will happen with probability at least , where is the degree in the remaining graph.) By linearity of expectation, the conditional expectation of the size of the final independent set , given and , is at least

$\Phi _ t ~ =~ |S_ t| + \sum _{v\in V_ t} \frac{1}{d_ v+1}.$

# This is a pessimistic estimator

We’ve calculated above that is a lower bound on the conditional expectation that we care about. To keep the conditional expectation high enough (at or above ), it suffices to keep high enough. The original proof proved that is high enough. So, to keep high enough, it suffices to make each choice to ensure .

Is this always possible? That is, is there always some choice that ensures ? In this case, yes, it is. As we will verify, is a sub-martingale — in expectation, it is non-decreasing in each step: for each , the conditional expectation of , given the current value of , is at least . This ensures that there exists a choice that ensures .

# Verifying the sub-martingale property

Since is not a conditional expectation per se, one has to verify that is a sub-martingale.1 Here, as usual, this verification is a routine calculation, reusing the calculations from the original proof.

Suppose the first vertices have been considered. If the next vertex considered is, say , how will compare to ?

In the case that is not in (that is, is a neighbor of a vertex in ) then is not added to , and by inspection of its definition, .

In the case that is in , vertex is added to , so . That contributes an increase of 1 to . But also decreases because ’s neighbors no longer contribute: for each remaining vertex , let “” denote 1 if is or a neighbor of , and 0 otherwise. When is added, the increase in the pessimistic estimator, , is

$$\label{turan:eqn} 1 – \sum _{w\in V_ t} \frac{[{w}\in N(v)]}{d_{w}+1}.$$

The conditional expectation of , given that , is at most . Thus, the expectation of (\ref{turan:eqn}) above is at least

$1 ~ -~ \sum _{w\in V_ t} \frac{(d_ w+1)/|V_ t|}{d_ w+1} ~ ~ =~ ~ 0.$

We’ve verified that is a sub-martingale.

# Many ways to keep the pessimistic estimator from decreasing

To guarantee success, the algorithm should choose the next vertex to ensure . We’ve verified that this is always possible. More concretely, what choices will ensure this?

If the algorithm next considers some that has already been deleted (that is, and has a neighbor in already), then the vertex will not be taken in the independent set. By inspection, equals . So, considering any deleted vertex (and not taking it) keeps the pessimistic estimator from decreasing.

Otherwise, the algorithm next considers some . In this case (considering the random experiment), the algorithm must add to . As shown above, the increase is at least (\ref{turan:eqn}).

Next are a few different ways to make the choice to ensure that the increase is non-negative. They all lead to minor variations of the same basic greedy algorithm.

# Maximizing the pessimistic estimator

Perhaps the most obvious way is, at each step, to choose so as to maximize . Since is a sub-martingale, this ensures . More concretely, this gives the following algorithm:

Assign each vertex a fixed weight . Repeat until no vertices remain: choose a vertex minimizing the total weight of and its current neighbors; add to and delete and its neighbors. Return .

# In order of increasing original degree

Here’s another way to choose that works: Choose any whose original degree is at most the minimum, over ’s remaining neighbors , of the original degree of . (For example, consider the vertices in order of increasing degree in the original graph.)

By calculation, the lower bound (\ref{turan:eqn}) is non-negative: when a vertex is added, at most vertices in are deleted from the graph, and each of those has .

Here is one such algorithm:

Consider the vertices in order of increasing degree. Add each vertex if, when it is considered, none of its neighbors have been added.

# In order of increasing current degree

Alternatively, the algorithm can choose vertices based on their degree, say , in the remaining graph, instead of the degree in the original graph:

Choose any whose current degree is at most the minimum, over ’s remaining neighbors , of the current degree of .

This choice keeps the increase (\ref{turan:eqn}) non-negative because there are vertices that have , and each of those has .

# Many pessimistic estimators

We’ve seen above that a given pessimistic estimator can justify a variety of algorithms. As the next exercise illustrates, a given existence proof can also give rise to multiple pessimistic estimators. This is useful in designing algorithms.

Exercise 1.

Let denote the number of not-yet-considered neighbors of . (Note .) Define . Show that this is also a valid pessimistic estimator. What algorithms can you derive using it?

Exercise 2.

Instead of defining to be the size of the independent set , define to be the number of vertices such that is considered before any of its neighbors. Apply the method of conditional probabilities with this . What algorithms can you derive this way?

Exercise 3.

Which of the algorithms in this section do you think might find the largest independent sets in practice? Why?

Exercise 4.

Each algorithm above produces an independent set of size at least . Describe examples of graphs for which the algorithms produce independent sets that are much smaller than the maximum possible independent sets.

# Bibliography

## Footnotes

1. If, for some random variable , each was exactly the conditional expectation of , then would necessarily be a sub-martingale (in fact a martingale).