Content deleted Content added
m →Probabilistic proof of Turán's theorem: added missing diacritic |
m →The method of conditional probabilities using pessimistic estimators: added missing diacritic |
||
Line 115:
In this case, the random process has |''V''| steps. Each step considers some not-yet considered vertex ''u'' and adds ''u'' to ''S'' if none of its neighbors have yet been added. Let random variable ''Q'' be the number of vertices added to ''S''. The proof shows that ''E''[''Q''] ≥ |''V''|/(''D''+1).
We will replace each random step by a deterministic step that keeps the conditional expectation of ''Q'' at or above |''V''|/(''D''+1). This will ensure a successful outcome, that is, one in which the independent set ''S'' has size at least |''V''|/(''D''+1), realizing the bound in
Given that the first t steps have been taken, let ''S''<sup>(''t'')</sup> denote the vertices added so far. Let ''R''<sup>(''t'')</sup> denote those vertices that have not yet been considered, and that have no neighbors in ''S''<sup>(''t'')</sup>. Given the first t steps, following the reasoning in the original proof, any given vertex ''w'' in ''R''<sup>(''t'')</sup> has conditional probability at least 1/(''d''(''w'')+1) of being added to ''S'', so the conditional expectation of ''Q'' is ''at least''
| |||