Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Average size of connected components in grid

  1. Aug 15, 2013 #1
    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.

    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]
  2. jcsd
  3. Aug 18, 2013 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    If we consider a row in the grid, it has a certain number of "runs" in it. My intuition is that there are no more connected components in the whole grid than there are total runs in its rows. Does the expected total number of runs in the rows provide any useful upper bound for the expected number of connected components?
  4. Aug 18, 2013 #3


    User Avatar
    2017 Award

    Staff: Mentor

    Just for clarification: "Adjacent" means "same column, row differs by 1 OR same row, column differs by 1"? So each cell has 4 adjacent cells.

    If that is true and I understand it correctly, the number of connected components grows just linearly with n, and the fraction components/tile goes to zero.

    It is easy to find an upper bound for the average size (=lower limit for the components per tile): Consider non-overlapping 3x3 subgrids. Each subgrid has a probability of 1/16 to have an isolated cell in the middle. With a better pattern, you can get a "cross" every 6 tiles. Therefore, the maximal average size (as defined in post 1) is at most 16*6=96.
  5. Aug 19, 2013 #4

    Cool! I should have thought of that.

    I ran a simulation and got around 7.6 for average component size (random grids of 3000 x 3000). For grids of 300x300 it was 7.5-7.6 so it does seem to be roughly constant.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook