Goldsmiths’ 2014 Mathematics

Tuesday 22nd July

Networks

Dr Mark Walters

image

http://en.wikipedia.org/wiki/Percolation_theory

In mathematics, percolation theory describes the behaviour of connected clusters in a random graph.

image

The above image shows a three-dimensional site percolation graph.

Consider the two dimensional graph below showing islands in a river connected by bridges.

Imagine that each bridge has a half chance of getting destroyed and half of them do get destroyed. What is the chance we can still cross the river?

In principle this can be solved. There is 2 x E13 possibilities.

image

P is the probability of getting across the bridge and p – 1 is the probability of not getting across the bridge

Consider an infinite square lattice.

image

Suppose we are on the infinite square lattice image. The probability that the edge is open is p and the probability it is closed is 1 – p. Can we drive forever starting from the origin O without going back there or repeating an edge? The answer is we can’t.

image

In the above image the black lines are the open bridges and the red bridges are closed.

Is there any starting point we can drive forever

image

Back to the first picture

image

Probability (we can drive from 0) £ P we can drive from 0 or time t for any t

image

In the image below the green line represents a particular path. Fix the path at length t. What is the chance I can drive along this path (that is the chance all the bridges on it are open)? Just

image

image

Path of length 3 = 36

Number of paths of length

image

What is the chance some paths are open

image

image

Each channel has a ½ chance of being open. 0 if p = 1.

This is exactly the same as the previous examples of cars and bridges. The chance the ship can go along the river = the chance the car can go across the bridge (exactly one car and exactly one ship). So p(ship) + p(car) = 1

P(ship + car) = 0

p(ship) p(car) = ½

Blue lines indicate open channels. If the car can’t drive forever the boat can sail around the origin.

The aim is to show the boat is not likely to be able to sail around the origin.

Fix a cycle about the origin with a length t. What is the probability the boat can sail that loop?

image

The cycle must cross the X axis and not be too far around the origin, somewhere between 0 and t/2. Number of cycles of length t

image

therefore the chance the ship can sail around the origin on a cycle of length t is

image

The chance there is some cycle around the origin is

image

If p is close to 1 this sum is small (i.e. less than 1) there is some chance the car can drive forever from the origin

image

image

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s