Diffusion of the dead - The maths of zombie invasions. Part 3, Diffusive motion.

As discussed previously, we are going to model the zombie motion using the diffusion equation. In this post we introduce the gritty details. I've interpreted the mathematical symbols intuitively, so, if you stick with it, you should find yourself understanding more than you ever thought you could.

It is impossible to overstate the importance of the diffusion equation. Wherever the movement of a modelled species can be considered random and directionless, the diffusion equation will be found. This means that by understanding the diffusion equation we are able to describe a host of different systems such as heat conduction through solids, gases (e.g. smells) spreading out through a room, proteins moving round the body, molecule transportation in chemical reactions and rainwater seeping through soil, to name but a few of the great numbers of applications.

If you've never come across diffusion before, or want to know more about it's basic properties the video below is a very good primer, although feels very much like a "Look around you" episode.

The mathematical treatment of diffusion begins by defining the variables that we will need. Let the density of zombies at a point $x$ and at a time $t$ be $Z(x,t)$ then the density has to satisfy the diffusion equation,

\begin{equation}
\frac{\partial Z}{\partial t}(x,t)=D\frac{\partial^2 Z}{\partial x^2}(x,t).
\end{equation}
To some an equation can be scarier than any zombie, but fear not. I am going to break this equation down into bits so that you are able to see the reality behind the mathematics.

Notice that the equation is made up of two terms, the left-hand side and the right-hand side, which are defined to be equal. Explicitly, the left-hand side is known as the time derivative and it simply tell us how the zombie density is changing over time,
\begin{equation}
\frac{\partial Z}{\partial t}(x,t)=\text{rate of change of $Z$ over time at a point $x$}.
\end{equation}

Although the numerical value of this term is important, what is more important is if the term is positive or negative. Specifically, if $\partial Z/\partial t$ is positive then $Z$ is increasing at that point in time, and, vice-versa, if $\partial Z/\partial t$ is negative then $Z$ is decreasing. Thus, we use this term to tell us how the zombie population is changing over time.

The term on the right-hand side is known as the second spatial derivative and it is a little more complicated than the time derivative. Essentially it encapsulates the idea that the zombies move from areas of high density to areas of low density (i.e. they spread out). To aid your intuitive understanding of this term see Figure 1.

Figure 1. A typical initial zombie density graph. There are regions of high zombie activity, e.g. a graveyard, and there are regions of low zombie density, e.g. your local library.

In the figure, there are initially more zombies on the left of the space than the right. Just before the peak in density the arrow (which is the tangent to the curve known as the spatial derivative, or $\partial Z/\partial x$ at this point) is pointing upwards. This means that as $x$ increases, so does the zombie density, $Z$. At this point

\begin{equation}
\frac{\partial Z}{\partial x}=\textrm{rate of change of $Z$ as $x$ increases} > 0.
\end{equation}

Just after the peak the arrow is pointing down thus, at this point,

\begin{equation}
\frac{\partial Z}{\partial x}=\textrm{rate of change of $Z$ as $x$ increases} < 0.
\end{equation}

Thus, at the peak, the spatial derivative is decreasing, because it goes from positive to negative. This, in turn, means that the second derivative is negative at the peak, because a negative second derivative means the first derivative is decreasing. This is analogous to statements made above about the sign of the time derivative and the growth, or decay, of the zombie population.

In summary, our hand wavy argument tells us that at local maximum $\partial^2 Z/\partial x^2<0$. Using the equality of the diffusion equation, this means that at a local maximum the time derivative is negative and, thus, the density of zombies is decreasing. A similar argument shows that the population of zombies at a local minimum increases. In summary, we see that diffusion causes zombies to move from regions of high density to low density.

Finally, we mention the factor $D$, which is called the diffusion coefficient. $D$ is a positive constant that controls the rate of movement. Specifically, the larger $D$ is the faster the zombies spread out.

And with that you now understand one of the most important partial differential equations in all of mathematics. That wasn't too hard was it? Next time we discuss the solution of the diffusion equation including some simulations and Matlab code for you to try yourself.

Diffusion of the dead - The maths of zombie invasions. Part 2, Important questions you need to ask in a zombie outbreak.

We begin modelling a zombie population in the same way that a mathematician would approach the modelling of any subject. We, first, consider what questions we want to ask, as the questions will direct which techniques we use to solve the problem. Secondly, we consider what has been done before and what factors were missing in order to achieve the answers we desire. This set of blog posts will consider three questions:

1. How long will it take for the zombies to reach us?
2. Can we stop the infection?
3. Can we survive?

In order to answer these questions I, Ruth Baker, Eamonn Gaffney and Philip Maini focused on the motion of the zombies as their speed and directionality would have huge effects on these three questions. Explicitly, we used a mathematical description of diffusion as a way to model the zombies motion. This was discussed in a previous post, but I recap the main points here.

• The original zombie infection article by Robert Smith? did not include zombie, or human movement.
• Zombies are well known for is their slow, shuffling, random motion. The end of Dawn of the Dead (shown in the YouTube clip below) gives some great footage of zombies just going about their daily business.
• This random motion is perfectly captured through the mathematics of diffusion.

Of course, there is plenty of evidence to suggest that zombies are attracted to human beings, as they are the predator to our prey. However, as we will see, we are going to be over run on a time scale of minutes! Thus, although mathematicians can model directed motion, and chasing, these additional components complicate matters. Further, random motion leads to some nice simple scaling formulas that can be used to quickly calculate how long you approximately have left before you meet a zombie.

Another simplifying assumption that we make is that we can model the zombie (and human) populations as continuous quantities. Again, this is incorrect as zombies are discrete units (even if they are missing body parts). Since we are making an assumption we will create an error in our solution. But how big is this error? In particular, if the error in the assumption is smaller than the errors in our observable data set then we do not have to worry too much. The error introduced by this assumption is actually dependent on the size of the population we are considering. The more individuals you have, you more the population will act like a continuous quantity. Since there are a lot of corpses out there, we do not think this assumption is too bad.

Note that we could model the motion of each zombie individually, however,  the computing power needed by such a simulation is much larger than the continuum description, which can be solved completely analytically. This is particularly important in the case of the zombie apocalypse, where time spent coding a simulation, may be better spent scavenging.

These are the basic assumptions we made when modelling a zombie population. Although I have tried to justify them you may have reservations about their validity. That is the very nature of mathematical modelling; try the simplest thing, first, and compare it to data. If you reproduce the phenomena that you are interested in then you have done your job well. However, if there is a discrepancy between the data and your maths then you have to revisit your assumptions and adapt them to make them more realistic.

Next time we contend with the equations and model the motion of the zombie as a random walker.

Diffusion of the dead - The maths of zombie invasions. Part 1, For those who can't wait.

Many years ago I posted a blog post about an academic article I had written about zombies. Finally, the article was published in Mathematical Modelling of Zombies. The book is designed to be readable by anyone with an interest in mathematics. However, those with an numerical background will find that it pushes them further as it does not shy away from clearly displaying the mathematics, whilst explaining the methods behind the madness.

As always, thank you to Martin Berube
for the use of his zombie image.

The articles range over a number of fields and are simply a means to dress up our everyday techniques in a way that is more palatable for a non-mathematical audience. Of course not all of you will want to shell out for the book. Thus, I've decided to essentially serialize the chapter in the next few posts, thus, we will be looking at all of the results of our paper and, hopefully, I'll be explaining the mathematics more clearly, so that any one is able to follow it. I may even throw in a matlab code or two, so that anyone is able to reproduce the results.

For those of you who are just interested in a quick review, you can read The Times article, or my brief version on the University of Oxford's Mathematical Institute website. Alternatively, if you are too tired to read you can always watch, or listen to a recorded version from the Athens Science Festival, Cambridge Science Festival, or on The Science of Fiction radio show. Finally, you could always see me live, when I'm giving one of my talks.

Next time, we will start at the beginning by modelling the zombie motion.

Prime Venn diagrams

Last time I gave a rigorous proof that if a number, N, was composite then the N-set Venn diagram could not be rotationally symmetric. Further, as we have seen previously, the 2-, 3- and 5-set diagrams (reproduced below) do have rotational symmetric forms.

Surely, the evidence suggests that all Venn diagrams with prime numbers of sets have rotational symmetric forms, right?

Well, of course, "suggestion" isn't good enough for mathematicians. We demand logical proof more rigorous than any other science. 

Surprisingly, this question has only been laid to rest relatively recently. In fact, up until 1992 some people thought that a rotational form of the 7-set diagram did not exist at all. The 7-set rotationally symmetric diagram was first created by Branko Grünbaum, whilst he was actually trying to disprove its existence!

A 7-set rotational Venn diagram.

There the problem stayed until 1999, when Peter Hamburger introduced a new idea of how to generate such diagrams [1]. Using his technique he pushed the bounds to 11 sets. Two examples of such diagrams can be found below.

Building on Hamburger's technique Jerrold Griggs, Carla Savage and Charles Killian demonstrated that it was possible to produce rotationally symmetric Venn diagrams whenever the number of sets is prime [2]. Unfortunately, the proof of this claim is quite complex and far beyond my capabilities to convey in a simple and intuitive way. However, for those seeking more details, the reference can be found below.

So, the question was finally laid to rest. Or was it? As I originally stated when we first started discussing rotationally symmetric diagrams, mathematicians love to abstract any property they can. Hence, once a problem has been solved a mathematician will try to solve the problem once again under heavier constraints.

Thus, mathematicians are now looking for Venn diagrams that are "simple". A Venn diagram is simple if at all points there are at most two sets crossing each other. In the diagrams above the constructions are so complicated that at some points three or more sets cross each other at the same point.

The question of existence and how to create a simple rotationally symmetric Venn diagram is still open. However, in 2012 Khalegh Mamakani and Frank Ruskey produced the first example of a simple symmetric 11-Venn diagram [11]. This has been reproduced below.

Zooming into the Venn diagram (below) we see the intricate details of all the curves passing through one another. Yet, by definition, we can be sure that there are only ever at most two sets crossing at each point.

As we have reached the edges of our current knowledge we come to the end of my posts regarding rotationally symmetric Venn diagrams. I hope you have enjoyed learning about these beautiful diagrams just as much as I have enjoyed creating them.

Next time, something completely different!

________________________________________________________________

________________________________________

[1] Doodles and Doilies, Non-Simple Symmetric Venn Diagrams. Peter Hamburger.
[2] Venn Diagrams and Symmetric Chain Decompositions in the Boolean Lattice. Jerrold Griggs, Charles E. Killian, Carla D. Savage.
[3] A New Rose: The First Simple Symmetric 11-Venn Diagram. Khalegh Mamakani and Frank Ruskey.

Primes, composites and rotationally symmetric Venn diagrams

Last time I boldly stated that if a Venn diagram is made up of $N$ sets, where $N$ is a composite number, i.e. not prime [1], then the Venn diagram can never be rotationally symmetric.

Before we prove the statement we first define the "rank" of the section in a Venn diagram.

The rank of a section is the number of sets, which the section is a part of.

For example, in the 2-set Venn diagram, the region outside of the circles has rank zero, because any point out there is in neither set. The sections on the extreme left and right of the circles each have rank 1, because they are a member of the either the right or left sets only. Finally, the overlapping region in the center has rank 2, because this section belongs to both sets.

Using this definition we can now head towards proving the initial statement. We do this by combining three smaller proofs concerning a general $N$-set Venn diagram. Explicitly, we

1. count how many sections there are of each rank;
2. show that in a rotationally symmetric Venn diagram these ranks must be divisible by $N$;
3. prove that the ranks are divisible by $N$ if and only if $N$ is prime.

Without further delay the three theorems and proofs can be found below.

Theorem 1
Suppose $k$ is an integer where $0\leq k\leq N$ then in an $N$-set Venn diagram there are
\begin{equation}
\frac{N!}{k!(N-k)!},
\end{equation}
sections of rank $k$ [2].

Proof 1
In order to help our intuition in counting the sections of a given rank we consider the 1-, 2-, 3-, 4-set Venn diagrams and summarise their details in the table below.

Number of sections of each rank		Rank
		0	1	2	3	4
Venn diagram size	0 sets	1
	1 set	1	1
	2 sets	1	2	1
	3 sets	1	3	3	1
	4 sets	1	4	6	4	1

The pattern of numbers within the table maybe familiar to you, as it is the famous Pascal's triangle. We may have expected these numbers to appear in this formation, because the numbers in Pascal's triangle represent exactly the quantity we are trying to calculate. Namely, the $(k+1)^{th}$ number in the $(N+1)^{th}$ row of Pascal's triangle tells us how many ways there are of choosing $k$ objects from $N$ objects. Note that we need to use the $(k+1)^{th}$ number and not the $k^{th}$ number, because the first number of each row deals with the trivial section, which is in none of the sets. Similarly, we use $(N+1)^{th}$ row and not the $N^{th}$ row because the first row deals the trivial Venn diagram of 0 sets.

To cement this idea, suppose we have three objects {A,B,C}. How many different ways are there of choosing two objects from these three (under the assumption that ordering doesn't matter)? Explicitly, there are three ways, {A,B}, {B,C} and {A,C}. This is exactly the answer we get from Pascal's triangle if we look at the third number on the fourth row. Because of this identification we normally call the numbers $N$ choose $k$, or, $_NC_k$, for short.

There are many ways to calculate the coefficients of Pascal's triangle. The quickest way is to use the formula [3]
\begin{equation}
_NC_k= \frac{N!}{k!(N-k)!}.
\end{equation}

Theorem 2
If an $N$-set Venn diagram is rotationally symmetric the number of section of a given rank $k$, where $0\leq k\leq N$, must be divisible by $N$.

Proof 2
By definition, an $N$-set Venn diagram is rotationally symmetric if it has $N$ orders of rotational symmetry. This means that if we find the rotational center of the diagram and split the diagram into equal sectors of $2\pi/N$ radians (or $360/N$ degrees) each sector should "look" identical. For example, have a look at the 3-set Venn diagram which has been split into thirds. Each third contains sections with exactly the same rank.

We deduce that the total sum of sections with rank $k$ (where $0\leq k\leq N$ [4]) must be divisible by $N$. Suppose it wasn't true, we would not be able to divide the sections of rank $k$ into $N$ identical parts and therefore our diagram could not have $N$ identical sectors, suggesting that the diagram wasn't rotationally symmetric. In order to avert this contradiction we conclude that $N$ divides the total number of sections with rank $k$ for all values of $k$, where $0\leq k\leq N$.

  

Theorem 3

\begin{equation}
_NC_k= \frac{N!}{k!(N-k)!},
\end{equation}
is divisible by $N$ for all values of $k$ such that $0\leq k\leq N$ if and only if $N$ is prime.

Proof 3

Firstly, suppose $N$ is prime. Consider $N$ choose $k$, which has a simplified form
\begin{equation}
_NC_k= \frac{N(N-1)(N-2)\dots(N-k+1)}{k(k-1)(k-1)\dots1},
\end{equation}
for all  $0\leq k\leq N$. Note $_NC_k$ is an integer and that the top of the fraction has a prime factor $N$, which does not cancel down because there is no factor of $N$ on the bottom. Thus, $_NC_k$ contains a factor of $N$, and so it is divisible by $N$.

Conversely, suppose $N$ is composite. Choose $p$ to be the smallest prime factor of $N$, and define $n=N/p$ then
\begin{equation}
_NC_p=\frac{N(N-1)(N-2)\dots(N-p+1)}{p!}=\frac{n(N-1)(N-2)\dots(N-p+1)}{(p-1)!}.
\end{equation}
Now if $_NC_p$ is divisible by $N$ the top of the fraction must contain a factor of $N$ and therefore a factor of $p$. Because $N=np$ and we already have a factor of $n$ on the top then $p$ must divide at least one of the factors of $N-1$, $N-2$, ..., or $N-p+1$. But $p$ divides $N$, so it does not divide any of these other factors. Once again the only way out of the contradiction is to conclude that when $N$ is composite $N$ does not divide $_NC_p$ and, hence, $_NC_k$ is divisible by $N$ for all values of $k$ such that  $0\leq k\leq N$ if and only if $N$ is prime.

Putting these three theorems together we generate the proof we were originally searching for.

Theorem 4
If $N$ is a composite number then the $N$-set Venn diagram is not rotationally symmetric.

Proof 4

• By proof 1 the total number of sections of a given rank is given by $_NC_k$.
• By proof 2 if a Venn diagram is rotationally symmetric the total number of sections of a given rank must be divisible by $N$ for all $0\leq k\leq N$ .
• We conclude that if a Venn diagram is rotationally symmetric $_NC_k$ must be divisible by $N$ for all  $0\leq k\leq N$.
• Finally, by  proof 3, $_NC_k$ is be divisible by $N$ for all  $0\leq k\leq N$ if and only if $N$ is prime.

Therefore, if $N$ is composite $N$ does not divide $_NC_k$ for all  $0\leq k\leq N$ and, hence, the Venn diagram cannot be rotationally symmetric.

We finish this week's post by noting that, although we have proven that an $N$-set Venn diagram is not rotationally symmetric when $N$ is composite, this does not mean that it is rotationally symmetric if $N$ is prime. We will discuss more about this point next time.

________________________________________________________________

________________________________________

[1] For those of you who may have forgotten the definition: a positive number is prime if and only if it was only two distinct integer factors, which are itself and 1. For example 2, 3, 5 and 7 are all prime numbers. However, 9 is not a prime number, because 3$\times$3=9 and the factors of 9 are 1, 3 and 9. Any number that is not prime (other than 1) is called composite. The number 1 is a special case as it is neither prime nor composite. It is called a unit.

[2] The exclamation mark symbol $n!$ represents the product of all positive integers up to and including  $n$, i.e. $n!=1\times2\times3\times...\times n$.

[3] Ok, I've slightly cheated and not proven that this formula does give us the numbers that we want. However, if you want to read more about the connection between the Pascal numbers and the formula see this post.

[4] Note that we have excluded $k=0$ and $k=N$, why is that?

Back to rotationally symmetric Venn diagrams

Over the past few posts we have been considering Venn diagrams, their properties and their uses. Although we are usually more concerned with what goes into the Venn diagram sets than their actual shape mathematicians like to abstract everything they can get their hands upon. Thus, they very quickly stopped thinking about the things inside the sets and simply began to consider the properties of the diagrams themselves.

An algorithm for creating a Venn diagram with any numbers of sets was quickly found. For example, Anthony Edwards showed that a diagram containing any number of sets can be constructed using symmetric wavy curves as shown in the animation below.

Anthony Edwards' construction of a diagram which will contain the intersection of all sets. However, it is not a true Venn diagram as, although all possible intersections do appear, some of the intersections appear more than once.

Having solved the basic problem of showing existence further constraints where added to the problem. In particular, mathematicians asked whether it was possible to create rotationally symmetric Venn diagrams. To be honest, I have no idea why rotational symmetry is so highly prized, other than it quite aesthetically pleasing.

A rotationally symmetric Venn diagram of $N$ sets is simply a Venn diagram that can be rotated around its centre, such that after $360/N$ degrees (or $2\pi/N$ radians) the graph looks the same as it did initially. With small numbers of sets rotationally symmetric Venn diagrams are fairly easy to produce. For example below are $N=$2, 3 and 5 set diagrams.

Unfortunately, we are unable to create a rotationally symmetric Venn diagram with 4 sets. As we have seen previously, the 4 set diagram cannot be created using circles. Instead, ovals can be used, as seen below.

Of course, just presenting one 4 set diagram that is not rotationally symmetric is not a proof that such a representation does not exist. Perhaps there is a 4 set Venn diagram with non-regular shaped sets that is rotationally symmetric? Fortunately, there is a simple proof that shows that only prime number set diagrams could possibly be rotationally symmetric. Next time I will reproduce the proof that for any composite number $N$ the accompanying $N$ set Venn diagram cannot be rotationally symmetric.

Dangerous caterpillars solution

Figure 1. The usual suspects.

Last time I asked if we could work out which caterpillars from Figure 1 are safe based on the following rules:

1. If a caterpillar has blue eyes or spots it is dangerous. If a caterpillar has both, we can't tell if it is dangerous.
2. All safe caterpillars have more than one of the following features: teeth, blue eyes, spots, or spikes.
3. Caterpillars with both teeth and spots are dangerous.

As I suggested Venn diagrams are expertly suited to this kind of puzzle. 

To solve the puzzle using Venn diagrams we, first, decide what our sets are going to be. In the clues there are 4 features that are discussed: teeth, blue eyes, spots and spikes. Thus, we construct a Venn diagram of these four qualities and insert the caterpillars to their appropriate spaces. This can be seen in Figure 2. Note that in this specific problem we have to use the full Venn diagram form of the four sets, rather than the Euler diagram that we discussed, previously.

Figure 2. Separating the caterpillars into types.

Now that we have our diagram we use the clues to remove sections and restrict the safe caterpillar possibilities.

The simplified Venn diagrams corresponding to each of the clues can be seen in Figure 3. For example, the first clue states that animals with blue eyes and spots (but, perhaps, not both) are dangerous. Thus, we remove the sections corresponding to the blue eyed caterpillars and the spots. However, the region over which they intersect is left, because we can't be sure if those caterpillars are dangerous or not.

Figure 3. Removing sections of the Venn diagram based on the clues. Left: the blanked out section corresponds to either having blue eyes or spots, but not both. Center: removing the sections with only one feature. Right: removing the section with teeth and spots.

This process is carried out for all three clues. Finally, we put together only the sections that remain in all three diagrams in Figure 3 to get Figure 4.

Figure 4. Only one caterpillar left.

As you see will from Figure 4 there are only 3 sections of the Venn diagram left. These include two sections in the blue eyes and spots region. Because of rule 1, we cannot tell if those sections are safe, or not. Luckily, there are no caterpillars in these regions, so no risks need be taken. The only caterpillar left has both spikes and teeth... would you trust this guy?