Defining topology through interviews. Interview four with Tom Hockenhull.

The next of my  Defining topology through interviews  series is with Tom Hockenhull. Tom is a PhD student in mathematics at Imperial College London and his research is in knot theory. You should also check out the cool topology themed comics he does for chalkdust magazine!

1. What do you say when trying to explain your work to non-mathematicians?

I’m in the odd position that my field gets more intelligible for non-mathematicians the more specific I am (well, to a point). It’s actually quite hard to capture the idea of ‘topology’ in enough generality, I find – but it’s rather easy to explain the subfield of topology I work in, which is knot theory. I usually talk about unknot recognition. If I get a piece of string, tie a knot in it, and then fuse the ends together, I get a knot which is trapped in the string — I can’t untie it without cutting the string again.

creating-a-knot
Tie a knot and fuse the ends

The question is, if you give me a big mess of string, can I tell easily whether I can just straighten it out into a big unknotted loop without cutting the string at all? People can understand quite easily that this is a hard question in general.

knot-tangle
Can you make this into a simple loop of unknotted string without cutting it?

So how might I go about doing it? Well, one way to recognise if two things are different in general is to look at some easy to discern property of them and see if they’re different. For instance, if I’m trying to work out whether two insects are of the same species, I might look at how many legs they have.

bugs
Are these insects from the same species?

If I have a big tangle of string, I might try and work out some property of it that is different from that of a plain loop of string – then I can tell that it’s a different knot altogether. What’s the analogous notion for knots? Well, this is sort of what my work is in: there are a whole bunch of different properties we might try and use to compare knots. One which is easy to understand is the property of being able to colour a picture of the knot using exactly three colours (no less!), so that at each crossing I have three different colours, or all the colours are the same.

coloured-crossing
Colouring a crossing using exactly three colours

You can see that I can’t colour a simple loop of string with three colours (only one) – but I can colour the picture of the knot below.

colouring
However you draw an unknotted loop you can’t colour it using three colours
colouring-trefoil
You can colour this one with exactly three colours!

It follows that I can’t turn one into the other without cutting the string!

2. What would your own personal description of ‘topology’ be?

There’s the standard ‘rubber sheet geometry’ or ‘the study of spaces up to deformation’, which are probably the most generally accurate, although they don’t really tell you much about what doing topology looks like or feels like. I suppose, though, that the problem is that ‘topology’ now encompasses a whole bunch of different areas that are rooted in the same place but are vastly different in their techniques, language and flavour.

3. How does your work relate, if at all, to the Nobel Prize work?

I’m not aware of any direct relevance – although that could be down to my ignorance! The word ‘quantum’ tends to pop up in descriptions of the Nobel work and in relation to a number of things to do with my work, but in my experience the use of the word quantum in my area seems to carry little relevance to its meaning in the world of physics.

Advertisements

Defining topology through interviews. Interview three with Ruben Verresen.

The third interview in my Defining topology through interviews series is with Ruben Verresen, who was a masters student alongside Anna and I. Ruben is now a PhD student at the Max Planck Institute for the Physics of Complex Systems and is one of two physicists I am thrilled to have participating in this series.

1. What do you say when trying to explain your work to non-mathematicians and non-physicists?

Traditionally theoretical physics follows the doctrine of ‘separate but equal’, where theories for different aspects of the universe are quite disjoint, with the smallest scales being described by particle physics and the largest by cosmology. (And perhaps not so ‘equal’ since particle physics is considered the building block for all the rest.) This has changed in recent years. The dusty 18th century divisive thinking is making way for a more thematic structure, as it is slowly becoming clear that various different fields give rise to similar concepts. Instead of defining a topic in terms of some mechanical parameters (e.g. ‘the size of an atom’), one can categorize physics in terms of relevant concepts (such as ‘topology’, more about this later). If you allow me one tacky metaphor, to me concepts are the jewels of physics, forged in the heat of discussion, mined out of theories and eventually polished until they reach their purest form. A successful theoretical framework you can forget after a year, but a beautiful and insightful concept, once germinated in the mind, will never leave you. So when people ask me what I do, I usually just end up talking about one of these concepts (which usually helps my understanding as well).

Three such concepts that I am actively exploring are emergence, quantum entanglement and topology. These three ideas turn out to run quite deeply and seem to be intimately connected—with the Nobel prize recognizing this. Emergence is the idea that the best way to understand something is not by thinking in terms of its constituents but rather by some new effective way of thinking—for example if we want to understand a hurricane, there is not much point in thinking about air molecules.

wave
Waves on the Elbe are an example of emergent phenomena: to understand them we shouldn’t think about water molecules separately, but about collective motions where the molecules lose their individuality.

Entanglement is a less intuitive property about the universe: it says that any two objects—say you and the red eye of Saturn—can share an instantaneous connection, such that one can affect the other faster than the speed of light. Since its discovery 80 years ago, there have been strong disagreements about what this property actually means, but in the last few decades physicists have been discovering that no matter what it ‘is’, it is key to many new physical features, some of which may very well change our future (for example through quantum computing, teleportation, et cetera). And finally there is topology…

2. What would your own personal description of  “topology” be?

I really like this question. There are some standard go-to answers for the general public, but I don’t like them. The first common one is that topology has to do with holes, the typical example being that a coffee mug and a donut are topologically the same because they have the same amount of holes. A second—and closely related—common answer is that topology is about the properties of an object that don’t change if you stretch, squeeze and deform it—but you’re not allowed to tear it! Again, you can imagine a plasticine donut being reshaped into a coffee mug. Maybe I just don’t like these answers because I have heard them too many times before, but more importantly: although they seem easy to understand, I would say they are not. The issue is that they seem very arbitrary: what’s so special about holes? Or about tearing versus stretching? If that’s all you know about topology, there is no reason to think it would be interesting. But it is! Very much so. Aside from leading to beautiful mathematics, in recent years it has been rising to ever increasing prominence in almost all fields of physics. There has even been a feedback effect: studying the topology of quantum fields—a physical question—has given new fundamental insights into mathematics itself. There is no hint of this in the above. Indeed, my biggest peeve with those answers is that there is no fire in them: if I explain topology by comparing a donut to a coffee mug, I can just see my listener slowly turning off. This is an immense pity, since topology is currently one of the most exciting concepts around.

So, what then is topology? Imagine having an object, like a mountain lion, or the universe, or yourself. Now think of all the properties it might have, like height or color or holes. Some of these properties you can assign to arbitrarily small regions: if you know the color of the mountain lion at every small piece of its hide, you can say you know all about the colors of the cat as a whole. We say these properties are local. Topology is simply the study of the properties which are not local! If I look at my door frame, I can assign sizes and lengths to every small piece, and together they add up to for example the height of my door, so height is a local property. But the fact that my door (luckily) has a hole in it is not local: none of the four sides can be said to have a hole, it is only when I take them all at once that it is there. In that sense my (open) door is topologically different from my wall.

door
The topology of my door: you can’t say any of the four sides of my doorframe has a hole, it is only when they are all put together that it’s there. We call such a feature ‘non-local’/topological.

Given this characterization, it is then perhaps not surprising that topology enters in those fields of inquiry where we are learning that ‘the (w)hole is more than the sum of its parts’. It can be a fun game to go outside and try to identify ‘local’ versus ‘non-local’ properties. But maybe we don’t even need to look too far: perhaps the human mind cannot be understood by piecing together local properties of the brain, and somehow only emerges when everything is considered at once.

3. How does your work relate, if at all, to the Nobel prize work?

To better understand what this year’s Nobel Prize in physics is about, we just need to appreciate how and why these three concepts of emergence, entanglement and topology are so closely related. Luckily we are now in a position to do exactly that! To see this, let me just reword and recap:

  • Emergence is the idea that a system consisting of many particles can have properties which cannot be assigned to any of its individual particles, but only emerge when the system is taken as a whole. (H20 molecules do not have ‘wetness’, but a glass of water does.)
  • Quantum entanglement tells us that we cannot think of a ‘thing’ as merely being the sum of its parts. In a classical world we know that if we study each particle in the universe separately, then we know the state and motion of the complete universe. In quantum theory we would know almost nothing, since most of the information is stored in these instantaneous connections between different particles. This is sometimes called quantum non-locality—and it is worth pointing out that this has been experimentally verified!
  • Finally, as explained above, topology is about those properties of a ‘thing’ that cannot be attributed to any arbitrarily small piece of it.

So we see that these three concepts are all about some form of ‘non-locality’. More concretely, the Nobel Prize went to physicists who vastly aided our understanding by theoretically investigating physical systems where (some or all of) these phenomena play a crucial role. Personally I am most excited about this on a conceptual level, as it feels that we are learning something new and deep about how the universe works. But it is also of great importance for the more practical-minded: learning to harness the power of ‘non-locality’ means we have exponentially more possibilities at our disposal. In particular, ‘non-locality’ is often associated to strong stability (because if information is not stored locally it is much harder to accidentally destroy it) and physicists hope it could lead to the development of quantum computing, which is a whole exciting topic in and of itself. But anyway, despite there being deep links between emergence, entanglement and topology, it is still a basic question as to how deep the similarities really run. I’m certainly trying to find out!

Defining topology through interviews. Interview two with Carmen Rovi.

The second of my interviews for the Defining topology through interviews series in with Carmen Rovi. Carmen was a PhD student in mathematics at Edinburgh whilst I did my undergrad, and is now a Postdoctoral Fellow at Indiana University in Bloomington. She works in the exciting world of algebraic surgery theory!

1. What would your own personal description of “topology” be?

Topology studies the geometric properties of spaces that are preserved by continuous deformations. For a topologist any stretching or bending will not change the topological properties of an object, since we concentrate on much more essential aspects. This is why many times we hear the comment that a topologist can’t distinguish her coffee cup from her doughnut! Manifolds are the main examples of topological spaces, with the local properties of Euclidean space in an arbitrary dimension n. They are the higher dimensional analogs of curves and surfaces. For example, a circle is a one-dimensional manifold. Balloons and doughnuts are examples of two dimensional manifolds. A balloon cannot be deformed continuously into a doughnut, so we see that there are essential topological differences between them. An invariant of a topological space is a number or an algebraic structure such that topologically equivalent spaces have the same invariant. For example the essential topological difference between the balloon and the doughnut is calculated by the Euler characteristic, which is 2 for a balloon and 0 for a doughnut.

2. What do you say when trying to explain your work to non-mathematicians?

When I talk to non-mathematicians and I am asked this question I usually say “I do topology, which is an area of mathematics”. Unfortunately the conversation usually ends there when the other person says “mathematics… that’s difficult. I had a hard time in school with that”. Sometimes with a bit of luck they will want to know more and then I can explain that my work lies in a field called “surgery theory”. Like real surgeons, a mathematician doing surgery also does a lot of cutting and sewing. Of course like in real surgery, there are very precise rules for doing this! In the following figure, we perform a surgery on a 2-dimensional sphere. The first step is to cut out two patches (discs) from the sphere. This leaves two holes in the shape of two circles. We can then sew on a handle along those two circles. If we are careful on how we sew things together, we obtain a torus:

Surgery-sphere.jpg

This is an example of how surgery can be used to describe the classification of surfaces: sphere, torus, torus with two holes … Of course, surgery can also be used in much more sophisticated situations and it is a very powerful tool for investigating classification questions in topology. The aim of classifying complicated topological objects gives rise to the description of invariants which give you certain information about the objects you are trying to classify. As we have seen with the work of the physics laureates this year, such invariants can then be applied in “real life” contexts and produce stunning results.

3. How does your work relate, if at all, to the Nobel prize work?

One of the questions that the physics laureates from this year were trying to understand was the electrical conductance in a layer of condensed matter. Experiments done in extremely low temperatures and under very powerful magnetic fields showed that the electrical conductance of the material assumed very precise values, which is extremely rare in this kind of experiments. They also noticed that the conductance changed in steps, when the change in the magnetic field was significant. The strange behaviour of the conductance changing stepwise made them think of topological invariants. Of course, there is a wide gap between having such an intuition and being able to formalise exactly which topological invariant is relevant in this situation. The key invariant for them is called “Chern numbers”, which for me is very surprising as this is an invariant which features frequently in my work.

Defining topology through interviews. First up, Thomas Wasserman.

The first of my Defining topology through interviews  series is with Thomas Wasserman, a PhD student at Oxford University studying mathematics. In particular his work is in the realm of topological quantum field theory.

1. What do you say when trying to explain your work to non-mathematicians?
Suppose you have a bunch of circles. Now imagine some of those circles merging together to one, and some of them splitting themselves in two. This merging and splitting over time sweeps out a surface, an example is shown below.

diagram-1
A surface starting with 3 circles and ending with 2.

We view this surface as a kind of machine that takes your bunch of circles and spits out another bunch of circles. Observe that given two such machines, we can apply one after the other by sticking the first one on top of the second, as long as we have the same number of circles coming out of the first one as going into the second one.

As you’ll see from the other posts, us topologists have a lot of trouble telling circles apart. This means that if we want to say something about machines like this we need to do something clever. Let’s give each circle an extra bit of information and think of it (by flawed analogy) as a colour, chosen from some range of possibilities. On top of merging and splitting circles our machine can now also change the information associated to each circle, for example mix the colours if two circles merge.

If this new feature of our machine sounds completely arbitrary to you, you’re on the right track. In order to use this feature to study the original surface, it needs to be compatible with applying several machines in a row: the big machine formed from smaller machines should do exactly the same to the information as just applying the small machines in succession. I study how one can construct these extra features subject to these requirements.

2. What would your own personal description of ”topology” be?
Topology is the study of shapes. To me, that means studying shapes that you can imagine encountering in nature. As mathematicians, we have developed a way of describing these shapes that allows us to check our intuition about them and study them in a lot of detail. This is what makes topology such an interesting subject; it very explicitly creates a bridge between the intuition we have for the world around us and very abstract mathematical ideas.

3. How does your work relate, if at all, to the Nobel prize work?
My work fits very well into the way of thinking that the Nobel prize work has inspired in the last decades. In condensed matter physics, the area of physics that the Nobel prize work was done in, people spend a lot of time thinking about a type of (composite) particles called anyons. These anyons live on very thin slices of material and have the strange property that the way they behave is described only by their relative movement. That is, the only thing that matters is whether or not they merge, split or braid around each other. For example the image below shows a braiding followed by a merging.

diagram-3
A braiding and merging of 2 anyons (a blue one and a red one).

 

Comparing this kind of behaviour to what we discussed in question one, we can relate them as follows. Suppose that instead of a colour, we assigned a type of particle to each circle. The circles merging then corresponds to the particles merging, and the circles splitting to the particle splitting. The particles winding around each other is encoded by the surface winding around itself, as in the figure below, and this relates to my work on surfaces such as these!

diagram-2
The surface corresponding to the anyon winding and merging in the previous picture.

 

Defining topology through interviews

In the following week I will release a series of interviews with PhD students and Post Docs working in the field of topology. Why? Because Nobel Prize.

chalk-dust-inverse-homotopy-tom-hockenhull
A frame from the Inverse Homotopy, part 1. This is a comic by one of our interviewees, Tom, and can be found in chalkdust magazine.

The 2016 Nobel Prize in Physics was just awarded to three physicists, one half awarded to David J. Thouless, the other half jointly to F. Duncan M. Haldane and J. Michael Kosterlitz “for theoretical discoveries of topological phase transitions and topological phases of matter”.

When I heard the news my interest was peaked and my friends were all like “Hey Rachael, look! It’s topology!” I very quickly realised two things:

  1. that I had no idea what part of topology was being used by these physicists and also
  2. that the vast majority of people online were not defining topology very well (I am not going to point fingers at well established newspapers and websites)

In particular everyone seemed to be going mad about doughnuts and coffee cups and even though this says something about homology – a main player in topology and certainly my closest friend – I fear that it neglects many other really interesting areas that topologists work in.

So I have collected some glorious people that work in different areas of topology, and they will each answer 3 questions for you:

  1. What do you say when trying to explain your work to non-mathematicians?
  2. What would your own personal description of ‘topology’ be?
  3. How does your work relate, if at all, to the Nobel Prize work?

There will of course be pictures involved and hopefully we can all learn how diverse the study of topology can be, as well as a bit more about the 2016 Nobel Prize in Physics.

Hall of mirrors: Coxeter Groups and the Davis Complex

I’ve spent a lot of time this summer thinking about the best way to present maths. When someone gives a talk or lecture they normally write on the board in chalk or present via Beamer slides. Occasionally though, someone comes along with some great hand drawn slides that make listening to a talk that wee bit more exciting. So the images in this blog are part of my tribute to this new idea.

I’ve talked about Coxeter groups before (here), but I’ll start afresh for this post. It is worth mentioning now that Coxeter groups arise across maths, in areas such as combinatorics, geometric group theory, Lie theory etc. as well as topology.

A Coxeter group is a group generated by reflections, and “braid type” relations. Informally, you can imagine yourself standing in the middle of a room with lots of mirrors around you, angled differently. Your reflection in a single mirror can be viewed as a generator of the group, and any other reflection through a series of mirrors can be viewed as a word in the group. Here is a silly picture to show this:

silly picture

Formally, a Coxeter group is defined by a Coxeter matrix on the generating set S. This is an S by S matrix, with one entry for each ordered pair in the generating set. This entry has to be 1 on the diagonal of the matrix or a whole number that is either bigger than 2 or infinity (\infty ) off the diagonal. It also has to be symmetric, having the same entry for (t,s) as (s,t) . See below:

coxeter groups1

Given this matrix you can then define the Coxeter group to be the group generated by S with relations given by the corresponding entry in the matrix.

coxeter groups2

In particular notice that the diagonal of the matrix being 1 gives that each generator squares to the identity, i.e. it is an involution. It can be hard to see what is going on in the matrix so there is a nicer way to display this information: a Coxeter diagram. This is a graph with a vertex for every generator, and edges which tell you the relations, as described below:

coxeter groups3

The relation (st)^{m_{st}} can also be rewritten as ststs...=tstst... where there are m_{st} elements on each side. This is reminiscent of the braid relations, hence why I called them “braid like” before. In the mirror analogy, this says the mirrors are angled towards each other in such a way that you get the same reflection by bouncing between them m times, independent of which of the two mirrors you turn towards to begin with.

There exist both finite and infinite Coxeter groups. Here is an example of a finite Coxeter group, with two generators s and t. If you view them as reflections on a hexagon (as drawn) then doing first s and then t gives a rotation of 120 degrees, and so doing st 3 times gives the identity, as required.

coxeter example

On the other hand, if you add another generator u with a braid-3 relation with both s and t , then the group is infinite. You can imagine tiling the infinite plane with triangles. If you take s , t and u to be reflections in the 3 sides of one of these triangles then they satisfy the relations they need to, and you can use these three reflections to transport the central triangle to any other one. If you think about this for a while, this shows the group is infinite. A (somewhat truncated) picture is shown below.

coxeter example 1

Examples of Coxeter groups don’t just live in 2-D Euclidean space. There is another finite group which acts as reflections on the permutahedron:

coxeter-complex

And other Coxeter groups which act as reflections on the hyperbolic plane.

The mathematical object I am working with at the moment is called the Davis Complex. You can build it out of finite subgroups of a Coxeter group (side note for the mathematicians: taking cosets of finite subgroups and forming a poset which you can then realise). Even infinite Coxeter groups have lots of finite subgroups. The great thing about the Davis complex being built out of finite things is that there is a classification of finite Coxeter groups! What this means is that when you have a finite Coxeter group its diagram either looks like one of the diagrams below, or a disjoint collection of them.

classification of finite coxeter

So because we only have a few diagrams to look at in the finite case, we can prove some things! Right now I am working on some formulas for staring at the Coxeter diagrams and working out the homology of the group. I’m using the Davis complex and all its nice properties to do this. I’ll leave you with a picture of the Davis complex for our first example.

davis example 2

davis example

Deleting edges to save cows – guest post by Dr Kitty Meeks

many-trades

I met Rachael at the LMS Women in Mathematics Day in Edinburgh in April, where I gave a talk about using graph theory to understand the spread of disease in livestock, and she invited me to write a blog on this topic.  Everything I’m going to say here is based on joint work with Dr Jess Enright from the University of Stirling (supported by Scottish Government as part of EPIC: Scotland’s Centre of Expertise on Animal Disease Outbreaks), who knows a lot more about cattle than I do!

It seems obvious that, when we want to understand how a disease spreads through a population, we should consider which members of the population have contact with each other – this simple observation has given rise to the field of Network Epidemiology.  If we’re trying to understand the spread of disease in humans, one of the key challenges is to guess the underlying contact network – who has contact with whom – and a lot of interesting work has been done on this.  Looking at the spread of disease in livestock, however, we don’t have to worry about this: all movements of farm animals have to be reported to the relevant government agencies, so we (well, people I collaborate with, who provide advice to the Scottish government on controlling animal disease outbreaks) know exactly which animals have contact with each other.

Depending on the specific disease we are interested in, there are several different kinds of contact we might need to consider.   If animals need to be in close contact to transmit the disease, then there are two main ways the disease could spread from one farm to another: it could spread between farms that are geographically adjacent (if cows on opposite sides of the fence decide to have a chat) or by trade when an animal is sold from an infected farm to another farm that is not yet infected.  Some other diseases are spread by biting insects, in which case any farm within a certain radius of an infected farm would be at risk.

Mathematically, we can represent these potentially infectious contacts by means of a graph: a vertex is used to represent each farm, and two farms are connected by an edge if there is the potential for the disease to spread from one to the other (in the case of infection due to trade, this would normally be one-way, so we could capture more information by using a directed edge in the direction of the trade).  My first picture illustrates what part of this graph might look like if we are just considering the spread of disease across shared fence lines.  The graph we get in this situation will normally be planar, that is it can be drawn in the plane without any edges crossing (although there are some circumstances where this is not necessarily true, for example if one farmer owns several fields that are not connected to each other).

farms-planar

Now we can add to this graph the contacts that come from trade.  It’s not so obvious what we would expect the graph of trade links to look like, but this is exactly what Jess and I have been trying to understand.

many-trades

First, though, I should explain why we want to know about the structural properties of these contact graphs.  We’re interested in restricting the spread of disease, and Jess and her colleagues are asked by policy makers to investigate how it might be possible, in theory, to modify the network to make it less vulnerable to an epidemic.  When we talk about modifying the network, we’re considering actions that correspond roughly to deleting edges and/or vertices in the graph: to “delete” a vertex, we might vaccinate all animals at the particular farm (so that it can no longer play any role in the transmission of disease), whereas “deleting” an edge might correspond to putting up a double fence-line between two farms (keeping animals on adjacent farms just a little bit further apart) or introducing extra monitoring on a specific trade route.  What do we want to achieve by modifying the network?  Well, there are lots of different parameters we could look at which relate to how vulnerable a particular graph is to an epidemic, but the simplest one we could think of to start with is the maximum component size (the largest number of vertices that can be reached from any single starting vertex in the graph by traveling along edges).  In the picture below, if the farm circled in red is infected, then all of the others are potentially at risk.

cow-network-1

However, if we delete one edge from this network, we can be sure that the disease will not spread to the three farms on the right hand side (now highlighted in green).

cow-network-2

Of course, all of these possible ways to modify the network are costly, so we want to do this in the most efficient way possible, i.e. make the fewest modifications required to achieve our goal.  This motivates the following question: given a graph, what is the minimum number of edges (or vertices) we need to delete so that the maximum components size of the resulting graph is at most h?  This is an example of a graph modification problem, a kind of problem which comes up a lot on theoretical computer science.  It turns out that, like many graph modification problems, this particular problem is NP-complete: unless most mathematicians and computer scientists are wrong, and P=NP, there is no efficient algorithm to answer this question for all possible inputs.  But we don’t have to give up there!  Just because a problem is intractable on arbitrary inputs doesn’t mean we can’t find a fast way to solve it on input graphs with specific structural properties – most of my research is based on exactly this idea – so in order to solve the problem efficiently on the real data we want to understand the structure of the livestock contact networks.

Jess and I haven’t yet considered the general problem as I described it above: instead, we’ve been looking only at the trade network, and only at edge deletion.  This special case is relevant in the management of a particular kind of persistent cattle trade link that exists in Scotland, so it seemed as good a place to start as any.  Thinking about this problem, we did what any graph theorist does when faced with a computationally hard problem: we tried to solve it on trees (graphs that don’t have any cycles, so there’s exactly one way to get between any two vertices).  And, after dealing with a few slightly awkward details, it worked in exactly the way any graph theorist would expect: we can solve the problem recursively, starting with the leaves (vertices with only one neighbour) and working our way up the tree – the fact there are no cycles means we never have to rethink the answers we’ve already calculated.

trees

But cattle trade networks aren’t trees, so is this any use in the real world?  Somewhat surprisingly, the answer seems to be yes!  Although the trade networks aren’t exactly trees, many of them seem to have small treewidth – this is a hard-to-define graph parameter that essentially captures how “tree-like” a particular graph is.  And the great thing about graphs of small treewidth is that algorithms that work on trees can usually be adapted (taking just a bit more time) to work on graphs of small treewidth in exactly the same way.  The next picture shows how the treewidth of the Scottish cattle trade network grows as we add in more trades, based on real data from 2009.  The trades that took place that year are added to the graph one day at a time, and the treewidth (in fact, for technical reasons, an upper bound on the treewidth) of the resulting graph is shown.

2009_data

We can see from this graph that, even if we look at trades taking place in the whole year (much longer than the timescale we would need to consider for many disease outbreaks) the treewidth of the trade network is still less than 20, for a graph that has nearly 3000 vertices and 8000 edges – this is much lower than we would expect for a random graph with the same number of vertices and edges.

Initial experiments suggest that our algorithm that exploits the treewidth performs significantly better on some real datasets than a generic approach based on constraint programming (which doesn’t take into account any structural properties of the data): there were examples where our algorithm found the optimal solution in under a minute, whereas the alternative couldn’t solve the problem in 6 hours.

We’ve really only scratched the surface of this problem, though.  The planar graphs that arise from geographical proximity definitely don’t have small treewidth, so we will need a different approach here – but they certainly have other distinctive structural properties that we hope to exploit.  What interests me most to investigate next, though, is why many cattle trade networks have surprisingly low treewidth: farmers aren’t looking at the horrible definition of this parameter when they decide where to sell their animals, so there’s something else going on here – and if we could find a good way to model this “something else” mathematically, would it let us devise even better algorithms?