## 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.

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.

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.

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:

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:

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:

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

In this case using braid relations gives us the following:

And we can now ignore the green strand!

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

and we colour the last strand yellow for fun!

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.

And this is exactly the same as the original braid, which looks a lot messier when 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!

## Mapping class groups and curves in surfaces

Firstly, thanks to Rachael for inviting me to write this post after meeting me at the ECSTATIC conference at Imperial College London, and to her and Anna for creating such a great blog!

My research is all about surfaces. One of the simplest examples of a surface is a sphere. We are all familiar with this – think of a globe or a beach ball. Really we should think of this beach ball as having no thickness at all, in other words it is 2-dimensional. We are allowed to stretch and squeeze it so that it doesn’t look round, but we can’t make every surface in this way. The next distinct surface we come to is the torus. Instead of a beach ball, this is like an inflatable ring (see this post by Rachael). We say that the genus of the torus is 1 because it has one “hole” in it. If we have $g$ of these holes then the surface has genus $g$. The sphere doesn’t have any holes so has genus 0. We can also alter a surface by cutting out a disc. This creates an edge called a boundary component. If we were to try to pass the edge on the surface, we would fall off. Here are a few examples of surfaces.

As with the sphere, topology allows us to deform these surfaces in certain ways without them being considered to be different. The classification of surfaces tells us that if two surfaces have the same genus and the same number of boundary components then they are topologically the same, or homeomorphic.

Now that we have a surface, we can start to think about its properties. A recurring theme across mathematics is the idea of symmetries. In topology, the symmetries we have are called self-homeomorphisms. Strictly speaking, all of the self-homeomorphisms we will consider will be orientation-preserving.

Let’s think about some symmetries of the genus 3 surface.

Here is a rotation which has order 2, that is, if we apply it twice, we get back to what we started with.

Here is another order 2 rotation.

And here is a rotation of order 3. Remember that we are allowed to deform the surface so that it looks a bit different to the pictures above but still has genus 3.

However, not all symmetries of a surface have finite order. Let’s look at a Dehn twist. The picture (for the genus 2 surface) shows the three stages – first we cut along a loop in the surface, then we rotate the part of the surface on just one side of this loop by one full turn, then we stick it back together.

A Dehn twist has infinite order, that is, if we keep on applying it again and again, we never get back to what we started with.

If we compose two homeomorphisms (that is, apply one after the other) then we get another homeomorphism. The self-homeomorphisms also satisfy some other properties which mean that they form a group under composition. However, this group is very big and quite nasty to study, so we usually consider two homeomorphisms to be the same if they are isotopic. This is quite a natural relationship between two homeomorphisms and roughly means that there is a nice continuous way of deforming one into the other. Now we have the set of all isotopy classes of orientation-preserving self-homeomorphisms of the surface, which we call mapping classes. These still form a group under composition – the mapping class group. This group is much nicer. It still (usually) has infinitely many elements, but now we can find a finite list of elements which form a generating set for the group. This means that every element of the group can be made by composing elements from this list. Groups with finite generating sets are often easier to study than groups which don’t have one.

An example of a mapping class group appears in Rachael’s post below. The braid group on $n$ strands is the mapping class group of the disc with $n$ punctures (where all homeomorphisms fix the boundary pointwise). Punctures are places where a point is removed from the surface. In some ways punctures are similar to boundary components, where an open disc is removed, but a mapping class can exchange punctures with other punctures.

So how can we study what a mapping class does? Rachael described in her post how we can study the braid group by looking at arcs on the punctured disc. Similarly, in the pictures above of examples of self-homeomorphisms the effect of the homeomorphism is indicated by a few coloured curves. More precisely, these are simple closed curves, which means they are loops which join up without any self-intersections. Suppose we are given a mapping class for a surface but not told which one it is. If we are told that it takes a certain curve to a certain other curve then we can start to narrow it down. If we get information about other curves we can narrow it down even more until eventually we know exactly what the mapping class is.

Now I can tell you a little about what I mainly think about in my research: the curve graph. In topology, a graph consists of a set of points – the vertices – with some pairs of vertices joined by edges.

Each vertex in the curve graph represents an isotopy class of curves. As in the case of homeomorphisms, isotopy is a natural relationship between two curves, which more or less corresponds to pushing and pulling a curve into another curve without cutting it open. For example, the two green curves in the picture are isotopic, as are the two blue curves, but green and blue are not isotopic to each other.

Also, we don’t quite want to use every isotopy class of curves. Curves that can be squashed down to a point (inessential) or into a boundary component (peripheral) don’t tell us very much, so we will ignore them. Here are a few examples of inessential and peripheral curves.

We now have infinitely many vertices, one for every isotopy class of essential, non-peripheral curves, and it is time to add edges. We put an edge between two vertices if they have representative curves which do not intersect. So if two curves from these isotopy classes cross each other we can pull one off the other by an isotopy. Here’s an example of some edges in the curve graph of the genus 2 surface. In the picture, all of the curves are intersecting minimally, so if they intersect here they cannot be isotoped to be disjoint.

I should emphasise that this is only a small subgraph of the curve graph of the genus 2 surface. Not only does the curve graph have infinitely many vertices, but it is also locally infinite – at each vertex, there are infinitely many edges going out! This isn’t too hard to see – if we take any vertex, this represents some curve (up to isotopy). If we cut along this curve we get either one or two smaller surfaces. These contain infinitely many isotopy classes of curves, none of which intersects the original curve.

So why is this graph useful? Well, as we noted above, we can record the effect of a mapping class by what it does to curves. Importantly, the property of whether two curves are disjoint is preserved by a mapping class. So not only does a mapping class take vertices of the curve graph (curves) to vertices, but it preserves whether or not two vertices are connected by an edge. Thus a mapping class gives us a map from the curve graph back to itself, where the vertices may be moved around but, if we ignore the labels, the graph is left looking the same. We say that the mapping class group has an isometric action on the curve graph, so to every element of the group we associate an isometry of the graph, which is a map which preserves distances between elements. The distance between two points in the graph is just the smallest number of edges we need to pass along to get from one to the other. When we have an isometric action of a group on a space, this is really useful for studying the geometry of the group, but that would be another story.

## SIAGA: Polyhedral Geometry

### Seven pictures from Applied Algebra and Geometry: Picture #3

The Society for Industrial and Applied Mathematics, SIAM, has recently released a journal of Applied Algebra and Geometry called SIAGA. The poster for the journal features seven pictures. In this blog post I will talk about the third picture. See here for my blog posts on pictures one and two. And see here for more information on the new journal.

In the first section of this post “The Context”, I’ll set the mathematical scene and in the second section “The Picture” I’ll talk about this particular image, representing Polyhedral Geometry.

# The Context

A polyhedron is a combinatorial object that crops up in many places. For example, it is the shape of the feasible region for a linear optimization problem. It is a convex shape in $d$-dimensional space $\mathbb{R}^d$ described by an intersection of finitely many closed half-spaces $P = \{ x \in \mathbb{R}^n : Ax \leq b \}$
where $A$ is a $d \times n$ matrix describing the angles of the half spaces, and $b \in \mathbb{R}^d$ encodes their translational information.

A compatible collection of polyhedra is called a polyhedral complex. It is possible to associate a polyhedral complex to an algebraic variety, allowing us to use combinatorial tools to understand the variety. A typical way to do this is via the methods of toric geometry. This approach has been applied in areas such as phylogenetics, integer programming, economics, biochemical reaction networks and computer vision (from where this particular picture arose).

Tropical geometry gives one method, called tropicalization, for getting a polyhedral complex from an algebraic variety. The new object gives us useful information. For example, the dimension of the original variety equals that of the new polyhedral complex and the latter is much easier to compute.

Polyhedral geometry also arises at the interface with the life sciences. For instance, Gheorghe Craciun recently announced a proof of the Global Attractor Conjecture for toric dynamical systems. This result is important for systems biology, and polyhedral fans play a key role in the proof.

# The Picture

This picture describes one example of using polyhedral tools to understand an algebraic variety, this shedding light on the application from which the variety arose.

In the field of computer vision, and in the real world, ‘taking a photo’ is a map from the three-dimensional world to a two-dimensional world. As any good photographer knows, the resulting features of the photo depends heavily on the angle and location of the camera.

We photograph three-dimensional projective space $\mathbb{P}^3$. Each camera, $A$, is a $3 \times 4$ matrix which determines a map $\mathbf{x} \mapsto A\mathbf{x}$ to two-dimensional projective space $\mathbb{P}^2$. This map tells us where each point of the original world ends up in the photograph.

More information can be gained by considering multiple cameras $( A_1 , A_2, A_3)$ at different locations. Then we have a map from the real world to three photographs:
$\phi : \mathbb{P}^3 \dashrightarrow (\mathbb{P}^2)^3$
$\mathbf{x} \longmapsto (A_1 \mathbf{x}, A_2 \mathbf{x}, A_3 \mathbf{x} )$.

The closure of the image of this map is an irreducible variety. For example, if the $A_i$ are the coordinate projections, the variety in $(\mathbb{P}^2)^3$ is cut-out by the Gröbner basis
$\{ z_0 y_2 - x_0 z_2 , z_1 x_2 - x_1 z_2, z_0 y_1 - y_0 z_1, x_0 y_1 x_2 - y_0 x_1 y_2 \} \text{ .}$
When we take the initial monomials of these generators, their zero-set decomposes into seven pieces: one copy of $\mathbb{P}^1 \times \mathbb{P}^1 \times\mathbb{P}^1$, and six copies of $\mathbb{P}^1 \times\mathbb{P}^2$.

Our picture shows the three-dimensional shape we get from this zero-set when we identify each projective space $\mathbb{P}^i$ with the $i$-simplex. For example, $\mathbb{P}^2$ corresponds to the two-dimensional simplex $\Delta_2$ – the triangle – under the map:

$\mathbb{P}^2 \ni (x_0:x_1:x_2) \longleftrightarrow \frac{1}{x_0 + x_1 + x_2} (x_0 , x_1, x_2) \in \Delta_2$

and we identify $\mathbb{P}^1$ with the one-dimensional simplex $\Delta_1$ – the unit-length line.

Our zero-set is represented by a collection of polytopes which are faces of $(\Delta_2)^3$. The $\mathbb{P}^1 \times\mathbb{P}^1 \times\mathbb{P}^1$ corresponds to $\Delta_1 \times \Delta_1 \times \Delta_1$. This is the dark blue cube. Each of the six pieces $\mathbb{P}^2 \times\mathbb{P}^1$ correspond to $\Delta_2 \times \Delta_1$. This gives the six triangular prisms in the picture.

Each piece has been separated a little to make it easier to see, and the close-by parallel faces show how the different parts meet. Meeting at a triangle $\Delta_2$ means the projective spaces meet at a copy of $\mathbb{P}^2$. If the shared facet is a square $\Delta_1 \times \Delta_1$, the projective spaces meet at a copy of $\mathbb{P}^1 \times\mathbb{P}^1$. The original picture, and other nice ones, can be found in the paper “A Hilbert Scheme in Computer Vision” by Aholt, Sturmfels and Thomas (2013). It was made using Michael Joswig’s software Polymake.