Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Can you only pair adjacent nodes? If not then I don't really see how the graph structure comes into this. –  Robert Mastragostino May 28 '12 at 18:30
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. –  MJD May 28 '12 at 18:30
    
@RobertMastragostino: no, not just only adjacent nodes. –  Qiang Li May 28 '12 at 18:45
    
@MarkDominus: OK, let's assume it is complete graph. How to prove your $\log n$ result? –  Qiang Li May 28 '12 at 18:46
    
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. –  MJD May 28 '12 at 18:50

1 Answer 1

This is a case of Randomized Rumor Spreading. Normally, one uses one of the following three models for rumor spreading in graphs:

Push model: In each round, every white vertex calls an adjacent vertex, and colors them white.

Pull model: In each round, every black vertex calls an adjacent vertex, and if they call a white vertex, they become white themselves.

Push/Pull model: In each round, both of the above happen.

When you consider different random graph models, such as the Erdős–Rényi Model, or the Preferential Attachment model, you can get bounds of $\log n$ or better. This also holds for complete graphs.

Actually, there would be cases for your model where the vertices do not become white. Consider for example a path on 4 vertices, where the end vertex is white. In each round, you pick a perfect matching, and there is only one of those. In this case, the other end of the path will never become white.

share|improve this answer
    
Thanks for the reference! I actually was just wondering if you could summarize a simple understandable proof for complete graph the $\log n$ bound. –  Qiang Li May 28 '12 at 19:08
1  
That can be found here: maths.bris.ac.uk/~maajg/teaching/complexnets/rumours.pdf –  utdiscant May 28 '12 at 19:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.