Combing braids

I’m going to a conference next week, and it’s all about braids! So I thought I would write a wee post on combing, a technique which dates back to Artin in the 1940s. In fact the paper where he introduces the concept of combing finishes with the following amusing warning:

“Although it has been proved that every braid can be deformed into a similar normal form the writer is convinced that any attempt to carry this out on a living person would only lead to violent protests and discrimination against mathematics. He would therefore discourage such an experiment.” – Artin 1946

but I really don’t see it as so bad!

Combing is a technique for starting with any braid (see my introductory post on braids here) and ending up with a braid in which first the leftmost strand moves and the others stay put, then the next strand moves while the rest stay put etc etc. It’s much nicer to show this in pictures.

We want to start with any old braid, say this one:

original

 

and transform it into a braid where the strands move one at a time, like the following one. I’ve coloured the strands here so you can see that, reading the braid from top to bottom, first the red strand moves (i.e. all crossing involve the red strand, until it is finished), and then the green, and then the blue.

final coloured

 

For convenience I’ll only look at braids called pure braids, where each strand starts and ends at the same position. You can easily comb non-pure braids, you just need to add an appropriate twist right at the end to make them finish in the correct positions.

So how do we do this? Consider the first strand, I’ve coloured it red to make it clear. We want all the crossings between red and black strands to happen before (higher up than) a crossing of two black strands. So in this case the crossing circled in yellow are okay, because they happen lower down than any crossing involving the red strand. The crossings circled in blue and green need to be changed.

strand 1 highlight

 

We can slide some crossings of black strands down past the red and black crossings, as they don’t interfere. Here we can do it with the crossing circled in blue, as shown:

strand 1 step 1

 

We can start to do it with the crossing circled in green, but we encounter a problem as it wont simply slide past the red strand crossing below it. Moving this crossing down requires using some of the braid relations (see braid post) to replace a few crossings with an equivalent section in which the red strand moves first, as follows:

strand 1 step 2

Even though this braid looks different than the previous one they are in fact the same (you can always test this with string!). Now we have a braid in which the first strand moves before any others. Since all the first stand action is now at the top of the braid, we can now ignore the first strand all together, and consider the rest of the braid, as show below:

strand 1 forgetting

 

we only need to consider the following section now, and again we can put this into a form where only the first strand moves.

strand 2 beginning

In this case using braid relations gives us the following:

strand 2 final

And we can now ignore the green strand!

strand 2 forgetting

Colouring the first strand in this final section gives us no crossing that don’t involve the first strand:

strand 3 start

and we colour the last strand yellow for fun!

strand 3

Remembering all the pieces we have ignored gives us the full combed braid, where we focus on the leftmost strand until it ‘runs out of moves’ before looking to the next one.

final coloured

And this is exactly the same as the original braid, which looks a lot messier when coloured:

original coloured

Why might we want to do this? In some cases it makes mathematical proofs a lot easier. For me, recently I have been focusing only on what the first strand is doing, and so I want a technique to push the other strands down and away!

Advertisements

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?

Persistent Homology

A sample of the pictures we will look at this week:

cech_1 cech_2 cech_3 cech_4

Next week I’m going to the Young Topologists Meeting 2015, at EPFL in Lausanne, Switzerland. Over 180 young topologists are going and many of them will give short talks on their research. Alongside this, there are two invited speakers who will give mini lecture series:

  • Gunnar Carlsson of Stanford University, lecturing about Methods of applied topology
  • Emily Riehl of Harvard University, lecturing about Infinity category theory from scratch

I’ll try to write something about these courses, and this post will be a wee introduction to a tool introduced by Gunnar Carlsson which considers topology of data clouds: persistent homology. The pictures in this post were drawn by Paul Horrocks during our joint dissertation at undergrad: points to Paul!

The idea of persistent homology is to use a tool of topology – homology – to understand something about the structure or shape of a set of data points. But topology is to do with spaces, for example manifolds or surfaces. Therefore we want to make a space out of our data before we can work out the homology.

We do this by plotting our set of points, and around each point we draw a ball. This ball has a radius and we can vary the size of this radius:

Smaller radius

cech_1

Larger radius

cech_3

Once we have drawn these balls, we join two of the points by a line if their corresponding balls intersect, and colour in triangles formed by three lines if the balls corresponding to the three points of the triangle have a patch where they all intersect. For different radii we get different structures.

Smaller radius

cech_2

here only two of the balls intersected so there is only one line

Larger radius

cech_4

here many more balls intersected, and there is also one three way intersection.

We can also do this in higher dimensions: drawing a tetrahedron between 4 points if there is a four way intersection and so on.

Now we can work out the homology of the spaces we have created. Because we can do this for lots of different radii, we can vary the radius of the balls slowly, and see which features in the homology persist, hence the name! The persistent features are then considered to be the ‘interesting’ ones to think about.

If the radius is too small, we will have no structure and if it is too big then all the points will be joined together (think about this!) so it is only in a range that we have interesting homology. We can draw something called a barcode to tell us about this range, below is an example. Each bar is an interesting feature and the radius grows bigger from left to right. As the radius grows some of the features appear and dissappear.

barcode

For the radii indicated with dotted lines, the data set in question and its structure for balls of that radius are shown below:

complexes

Hopefully I will have more to say about this after my trip!

Determinant vs Permanent

The determinant and the permanent are famous polynomials in the world of maths (some say the determinant is the most famous in the world). We are unable to compare the complexity of the determinant with the permanent, and this is an important hurdle in complexity theory. A google search for “determinant vs. permanent” returns 432,000 results, which amounts to a very big hurdle. It is closely related to the P vs. NP problem.

Given a 2 \times 2 matrix M = \left( \begin{matrix} a & b \\ c & d \end{matrix} \right), the determinant is ad - bc. The less familiar permanent is ad + bc. Both are polynomials in the entries, a, b, c and d, of the matrix.

In general, the permanent is what we get when we put a “+” sign everywhere we see a “-” in the expression for the determinant.

Despite this apparent similarity, the two polynomials behave very differently.

Gaussian Elimination is an algorithm that allows us to calculate the determinant quickly. In the UK, you learn at school aged 17. The algorithm might seem laborious: a 3 \times 3 matrix requires about 30 operations. But, at O(n^3) operations for a matrix of size n, it is a very fast algorithm for matrices.

In contrast, there is no known polynomial-time algorithm for calculating the permanent; there is no known O(n^r) algorithm for any r. An active line of research is to try to write the permanent of a smaller matrix as the determinant of a much larger matrix. Here is an example in the case of a 3 \times 3 matrix:

Permanental Adjacency Matrix
Expressing the permanent as the determinant of a larger matrix, using adjacency matrices of graphs.

This picture is taken from Jan Draisma’s article on “Geometry, Invariants and the Search for Elusive Complexity Bounds” from the March 2nd SIAM news. It depicts a method by Bruno Grenet to find the permanent of a smaller matrix as the determinant of a larger matrix.

The method shows that we can find the permanent of a matrix of size n by finding the determinant of a matrix of size 2^n -1. It works as follows:

  1. We make the partially ordered set (poset) formed from all possible subsets of the numbers \{ 1, 2, \cdots, n \}. Its graph it the diagram shown on the left hand side of the above picture.
  2. We make paths in our poset by starting with the empty set, and adding in elements one at a time until we have all the numbers \{ 1, 2, \cdots, n \}.
  3. Next we make the matrix, on the right hand side of the picture. First, we label the rows and columns of the matrix by the 2^n - 1 non-empty subsets of \{ 1, 2, \cdots, n \}.
  4. The entries of the matrix are given by the weighting of the edge of the graph that goes from the column’s index to the row’s index in the poset picture.
  5. Each term in the determinant of the matrix corresponds to a path in the graph.

Here is Bruno Grenet’s paper from 2012.