Episode 3: Cellular automata, graph theory and brains

In this episode, we talk about cellular automata - including the Game of Life - and graph theory, and interviewed Jonathan Crofts from Nottingham Trent University about his research on complex networks in neuroscience. Find out more about the Biomathematics & Bioinformatics Research Group at Nottingham Trent.

Cellular automata:

• Stephen Hawking’s introduction to the Game of Life
• Clips from lots of Game of Life configurations, cut together like an epic sci-fi movie trailer!
• Game of Life simulator on Wikipedia
• Explanation of, and uses for, cellular automata, at GCSE Bitesize Geography
• An application that uses Brian’s Brain to trigger musical notes.

Graph Theory:

• Graphs, at Wolfram Mathworld
• Seven Bridges of Konigsberg: a puzzle in graph theory

Puzzle: I have a 5 × 5 grid, in which the squares can either be empty (white) or infected (black). The four ‘neighbours’ of each square are the ones directly next to it: up, down, left and right. A square will become infected if two or more of its neighbours are infected. Can you find a set of squares to colour black (‘infect’) which will eventually spread the infection to the whole grid? What’s the smallest number of squares you need to do this?

Solution:

One way to colour the squares so they infect the whole grid is to colour the five squares on the diagonal. This will then infect the cells next to the diagonal, which will then infect the next diagonal rows, and so on until the whole grid is infected. In order to infect the whole grid, you need to colour at least 5 squares (and in general, for an n × n grid, you need to start with n squares coloured). This can be seen by looking at the perimeter of the infected area.

If a square needs two or more infected neighbours in order to become infected, then the perimeter of the infected area can never increase - if you imagine a pair of squares which are both neighbours to a third square, they will infect it. The newly infected square will have two free edges which increase the perimeter by 2, but the edges of the two squares it was neighbouring become absorbed and are no longerpart of the perimeter. The whole shape will then have the same perimeter as the two squares you started with.

If you have a square with three or four neighbours, which then becomes infected, doing so will only ever reduce the perimeter of the infected area. As time passes, and more cells become infected, the perimeter of the infected area can only decrease or stay the same.

This means that in order to infect the whole square grid, the arrangement of coloured squares you start off with must have the same perimeter as the whole square, as this will never increase - and the edge of a 5 × 5 square is 4 × 5 = 20. This means you need at least 5 squares to start with, each of which has perimeter 4.