Start with an infinite 2d grid of cells, with each cell randomly colored black or white (50% chance). Now take the graph G whose nodes are the cells, and with an edge (A, B) if A and B are adjacent in the grid, and the same color.(adsbygoogle = window.adsbygoogle || []).push({});

What is the average size of a connected component of G? Is it finite, or infinite?

Specifically, let's say you have an nxn grid. G(n) is the graph whose nodes are the cells with an edge (A, B) if A and B are adjacent in the grid and the same color. Let f(n) be the expected number of connected components in G(n), so that [itex]\frac{n^2}{f(n)}[/itex] is the expected average size of connected components in the grid. Find [itex]\lim_{n \rightarrow \infty} \frac{n^2}{f(n)}[/itex]

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Average size of connected components in grid

Loading...

Similar Threads for Average size connected | Date |
---|---|

I Propagation of Error when Taking the Average of Averages | Today at 12:13 PM |

A Averaging over the upper sum limit of a discrete function | Jan 7, 2018 |

I Average profits and losses on a roulette table | Jan 2, 2018 |

I Standard deviation of data after data treatment | Oct 15, 2017 |

Comparing two averages with different group sizes | Aug 17, 2006 |

**Physics Forums - The Fusion of Science and Community**