Date: Feb 19, 2013 5:26 AM
Author: Dmitrey Yershov
Subject: Maximum number of iterations (set theory, graph theory)

Hello! This problem seems rather simple, but I can't solve it. Help, please!

Tehere is a set S1={A1, A2, ..., An}, where A1, A2,..., An are some sets. We call some element which belongs to at least one of the sets from S1. After that all sets which contain this element are removed from S1, so we obtain a new set of sets S2. Than the process repeats: we call some element which belongs to at least one of the sets from S2. After that all sets which contain this element are removed from S2, so we obtain a new set of sets S3. And so on, untill Sm is empty set.

The question is: what element do we have to call at each step in order to number of iterations until Sm = "empty set" be maximal?

My hypothesis is: at the k-th iteration we have to call element belonging to the minimum number of sets from Sk.

But how can I prove it? What method of proof can I apply?

I found that the problem about finding maximum number of iterations is equivalent to the following problem on graph. Let's build a graph in the following way: if elements "a" and "b" belongs simultaneously to some set from S1 then vertexes "a" and "b" are linked to each other with the edge. Let all vertexes are filled with white color. We have a brush with red color. Then the problem is: what is the maximum number of "brush strokes" which we should make to fill all vertexes with red color?

When I say "brush stroke" I mean the following action: we touch some vertex with the brush, this vertex and all vertices which are adjacent to this vertex are filled with red color. Of course, we can't make idle "brush strokes".

Maybe this problem could be solved with some standart graph algorithm?