One way of trying to avoid dependence on ordering is the use of randomized algorithms. Essentially, by processing the vertices in a random order, you can potentially avoid (with a high probability)...

L. I need help with this discrete math problem (question 7). Thanks in advance!

Extracted text: One way of trying to avoid dependence on ordering is the use of randomized algorithms. Essentially, by processing the vertices in a random order, you can potentially avoid (with a high probability) any particularly bad orderings. So, consider the following randomized algorithm for constructing independent sets: First, starting with an empty set I, add each vertex of G to I independently with probability p Next, for any edges with both vertices in I, delete one of the two vertices from I (at random) Note – in the second step, deleting one vertex from I may remove multiple edges from I! Return the final set I Question 7: Argue that the expected size of I after Step 2 is greater than or equal to the following: p|V] – p?|E|


Extracted text: Let's consider an undirected graph G that for any vertices, i, j E I and there is no edge between i and į in E. A set i is a maximal independent set if no additional vertices of V can be added to I without violating its independence. Note, however, that a maximal independent set is not necessarily the largest independent set in G. Let a(G) denote the size of the largest maximal independent set in G. = (V,E). An independent subset is a subset I cV such