1
$\begingroup$

This is not homework. I was asked about the following problem by a friend.

Given a graph with $n$ nodes, initially with only one while node and all the rest are black. Each round, nodes are paired in two, and if any one of them is white, then both of them will become (or remain) white. So on average, how many rounds are needed for all the nodes to become white uniformly?

Please help me. Thank you.

  • 0
    Can you only pair adjacent nodes? If not then I don't really see how the graph structure comes into this.2012-05-28
  • 1
    I don't think you can say anything useful in general, because the expectation will depend so strongly on the details of the graph topology and, in non-regular graphs, on which vertex is initially colored white. For example, a line graph of length $n$ will take somewhere between about $n/2$ and $n$ rounds to change, depending on whether the white vertex is in the middle or at the end, whereas a complete graph will change much faster, I guess in something like $\log n$ rounds.2012-05-28
  • 0
    @RobertMastragostino: no, not just only adjacent nodes.2012-05-28
  • 0
    @MarkDominus: OK, let's assume it is complete graph. How to prove your $\log n$ result?2012-05-28
  • 0
    That is a fair question to which I do not have a good answer. I reasoned like this: if the graph is big, then initially the number of white nodes will roughly double at each step, because there will be few white nodes and so the chance that any particular white node will be paired with another white node, rather than with a black node, will be negligible. And once the graph reaches half white nodes, the chance that a black node will be paired with a white node is about 1/2, so the number of black nodes will approximately halve at each step. So it should go like $\log_2 n$ or so.2012-05-28
  • 0
    @MarkDominus: right, that is very good heuristics. But how to make it formal proof?2012-05-28

1 Answers 1