Tag Archives: cube complex

Phylogenetic trees

2 Aug

I just listened to a two hour talk on phylogenetic trees, and they seem fun enough that I thought I’d share them with you!  Sorry I literally forgot to post last week, and then I realized I did not take notes on the stuff I wanted to post about (more pictures by Aaron Fenyes)- here’s a photo that I took and wanted to explain:

20160719_114650

Something twisted representation something skein algebra something unit tangent bundle

Instead, you’ll read about the basics behind the research of my friend Gillian (no website), which is being supported somehow by people who want to know about cancer.  First, some background: the field of study of phylogenetic trees is inspired by and informs applications in evolutionary biology.  All of the life-forms today (or at some slice of time) all trace back to a root life-form at time 0.  Each current life-form follows a series of branching away from the root to get to where it is now

Then we can represent this evolution via a labeled rooted binary tree: the root represents the root life-form at time 0, and each branching of the tree represents a different evolution.  The labels mark which life-form is which.  Of course this model isn’t perfect (I can’t find the word for it but it’s a thing where two different species evolve separately from the same ancestor, then meet again and make one species.  If we were to represent this information in a graph, it’d make a cycle and not be a tree), but it’s been fruitful.

Spindle_diagram

The rooted binary tree of the wikipedia picture: node 0 is the root life-form, then 1-7 are the life-forms at our current time.

Now let’s mathify this.  We’d like to encode the evolutionary information into our tree.  We’ve already decided that all life-forms will end at the same time (now), so if we just assign lengths to each of the non-leaf edges this will automatically determine the lengths of the leaf edges.  A leaf in a tree is a vertex with only one neighbor, and we call the edge leading to that vertex a leaf-edge.  Let’s call the non-leaf edges interior edges.  In the picture above, we have 5 non-leaf edges, which determine a tree with 7 leaves.  Using this exact configuration of labels and edges, we have five degrees of freedom: we can make those interior edges whatever lengths we want, as long as they are positive numbers.  So in math-terms, the set of phylogenetic trees (aka rooted, binary, labeled trees) in this configuration forms a positive orthant of \mathbb{R}^5.  You can smoothly change any one of the edges to a slightly longer or shorter length, and still have a phylogenetic tree with the same combinatorial data.

octant

This is from the paper I’m writing, but it does show that in 3D, there are 8 orthants cut by the three axes (red dot is the origin).  The pink box represents a single orthant.

What about phylogenetic trees with different combinatorial data?  Say, with different labels or different branching, but the same number of leaves and the same number of interior edges?  First we need to figure out what we mean by ‘different’.  For instance, the following picture from the seminal paper in this field shows three trees that don’t immediately look the same, but we don’t count as different:

Why aren’t they different?  Because they encode the same data for each life-form: reading from node 0 we see that first 1 branches off, then 2, then 3 and 4 in all three cases.  There’s some combinatorics here with partitions that you can do (one can label a tree with a set of partitions).  However, changing the labels so that first 2 branches off, then 1, then 3 and 4 will be a different phylogenetic tree.  In fact I can smoothly go from one to the other in the space that we’re creating: first I shrink the length of the green edge below to zero, which takes us to the middle tree (not binary!), and then extend the blue edge.

axis

Shrink the colored edges to get the same tree in the middle (not a binary tree)

We’re going to add these non-binary trees with one less edge length to our space.  Remember the tree on the left has an entire positive orthant, and the tree on the right has an entire positive orthant.  Shrinking the green length to zero means that we’re moving to one side of the left orthant: so we add this axis to our space (we have \{x,y\in \mathbb{R}^2: \ x,y\geq 0\} instead of strictly greater than 0).  We can glue the green and blue orthants together along this axis.  Here’s a picture from the paper:

spacetrees

Notice that they also have the origin filled in, with a tree with no interior edges.  This is the cone point of this space.  Now we’re finally ready to describe the space of phylogenetic trees: within each combinatorial structure/labeling, we have a Euclidean orthant in (n-2) dimensions.  Then these orthants are glued together along their axes in a specific way, and all of them are connected to the cone point.  This is called BHV(n), short for Billera-Holmes-Vogtmann space (in the paper they call it T(n) but that’s confusing to everyone else).  Here’s the picture of T(4):

t4

Each triangle represents an infinite orthant

There are 15 different orthants glued together in this picture, because the number of labelled rooted binary trees on n vertices is (2n-3)!!.  The double !! means you only multiply the odds, a.k.a. (2n-3)(2n-5)(2n-7)… This is also known as Schroeder’s fourth problem , which as far as I can tell was open for 100 years.  Pretty cool!

If you truncate BHV(n) so it’s not infinite (just pick some compact bound), then it forms a nonpositively curved cube complex, and we love those!  CAT(0) cube complexes are great.  I haven’t blogged too much about them (first terrible post and then those truncated Haglund notes) but they are the basis of all that I do and the number one thing I talk about when I give math talks.  Whoops!  The gist is that you glue cubes together in not-terrible ways, and then the resulting complex has great and fun properties (like you can cut it in half the way you want to).

That’s about all I have to say about this!  Gillian is working on some stuff about putting a probability measure on BHV(n) [you can’t do it with certain conditions], embedding it into a small enough Euclidean space that still preserves some of its features, and finding an isometrically embedded copy of the phylogenetic tree inside BHV(n) instead of just the coordinate point.  Also, fun fact to prove to yourself (actually please don’t scoop my friend), find the automorphism group of BHV(n)!  It’s just the symmetric group on some number that has to do with n (n+1 or something like that; I can’t remember and didn’t take notes).

Again, the main reference for this is the seminal paper that should also be accessible as it’s meant for biologists and statisticians.

Advertisement

Tags: , ,

Link

Hi from Israel!

3 Feb

Hi from Israel!

I’m at Young Geometric Group Theory II, the second international meeting of grad students, postdocs, and young faculty in GGT.  My new goals for the year, mathematically are:

a) Always ask a question in our small weekly GGT seminar with my advisor and a few grad students

b) Type up something related to each conference I attend

So here’s the first lecture from the four-lecture minicourse that Frederic Haglund is giving us on CAT(0) cube complexes.  Remember my blog post on special cube complexes and how that was not so great for non-mathematicians?  These are pure notes so they’re really aimed at someone like me: beginning-middle graduate students.

Tags: , , , ,

So tubular! Err… cubular

10 Dec

What I’m reading right now: Special Cube Complexes, a 2008 paper by Frederic Haglund and Dani Wise.  Recently Ian Agol proved the Virtual Haken Conjecture , which was a Big Deal in math (this link is LONG but a very well written non-math-person friendly summary of 30 years of math).  In fact, one of my professors from undergraduate, Jesse Johnson, wrote a nice little blog post on what it might mean for the future of low dimensional topology.  Basically, Agol used this special cube complex stuff to prove  this Big Deal, which means that we might be able to use these to prove Lots of Big Deal and Little Deal theorems.  So let’s get into what these guys are.

Update: I just found out that it’s my turn to give the talk in our little colloquium this week.  There’s seven of us, four are my advisor’s students (I guess he’s not technically my adviser yet) and three are in related fields.  So every two months or so, you have to give a half hour talk on some math you’re learning about.  We aren’t supposed to talk about our research, but I think I get a pass since it’s still my first year.  So this post is a prelude to my talk!

A cube complex is an object built by gluing a whole bunch of Euclidean cubes together.  So a one-dimensional cube complex is built by gluing a bunch of lines together; that is, it’s a (mathematical) graph.  And a two-dimensional cube complex is built by gluing a bunch of squares together.  The gluings can happen in funky ways though, and special cube complexes are objects where these pathologies don’t happen.

We’ll define these topologies in terms of hyperplanes.  So if I have a square [-1,1]\times [-1,1],  I’ll have two hyperplanes running through it: one at 0\times [-1,1] and one at $[-1,1]\times 0$.  In the picture below, which is taken from the 11th page of this paper, the red lines are hyperplanes, and the gray lines represent the cubes they’re cutting through.  To be special, we need our cube complex to a) not self-intersect, b) have no one-sided hyperplanes, c) not directly self-osculate, and e) have no two hyperplanes that inter-osculate.  Turns out that case d) hyperplanes indirectly self-osculate is OK.

Pathologies cube complexes (these guys are not special, but don't tell their parents I said that)

Pathologies of cube complexes (these guys are not special, but don’t tell their parents I said that).

Really quick, notice that a cube complex is special if and only if its two skeleton is (the part made up of filled-in squares).  That’s why we can just use this picture.

So what’s so special about special cube complexes?  The ultimate idea is that given a cube complex, if none of these funky things happens, I’ll be able to cut along the hyperplanes and have nice things happen.  That’s how we get to the Big Deal.  But that’s neither here nor there; this post is about a Smaller Deal: that a cube complex is special if and only if it corresponds to a right angled Artin group, that is, that there’s some graph so that our cube complex has an isometry into the Salvetti complex of that graph.

Turns out google image searching “Salvetti complex” is utterly useless, so I’ll just describe it.  Start with a single vertex.  Now given a graph \Gamma, we add one loop to this vertex for each vertex x_i in \Gamma.  For any edge in \Gamma, say it’s (x_i,x_j), we attach a square that looks like this:

Pub crawl that winds up back at the first bar invite idea: be there or be a torus!

Pub crawl that winds up back at the first bar invite idea: be there or be a torus!

So far we have the standard 2-complex for the group A(\Gamma) = \langle x_i: i\in\text{Vertices}(\Gamma): [x_i,x_j]: (x_i,x_j)\in\text{Edges}(\Gamma)\rangle, which is the definition of a right angled Artin group.  Now to make the Salvetti complex, we attach an n-torus for every n-cycle in our graph.  So if there was a triangle in our graph, we get a corresponding 3-torus in the Salvetti complex.  And the fundamental group of our Salvetti complex is that right angled Artin group.

To restate our deal, we’re saying that special cube complexes always have some graph \Gamma so that we can see our cube complex somewhere in the corresponding Salvetti complex, and everything still looks nice.  More formally and rigidly, we’re saying that X is special if and only if there’s an immersion from X into some Salvetti complex, which is a local isometry on the 2-skeleton.

Proof in one direction: Suppose I’ve got a local isometry from the 2-skeleton of my cube complex X to a Salvetti complex.  Since the Salvetti complex is special from how we built it, and local isometries keep things tidy (you can’t uncross intersecting hyperplanes, for instance), that means my 2-skeleton is also special.  So from our remark above, X is special.

Proof in the other direction: Say my cube complex is special.  Then make a graph with vertices being the hyperplanes of X, and edges connecting intersecting hyperplanes.  Now make the Salvetti complex of this graph.  We can map X into the complex by sending an edge to the vertex of the hyperplane that crosses it, and then extend the rest of the map.  It’s a hop and skip (no jumping allowed) that this map is, in fact, a local isometry on the level of 2-skeleta.

Right angled Artin groups have really nice properties and are fun stuff, so this little theorem can lead to a whole bunch of conclusions.  Phew, first math blog post.  I’ll get better at these, I promise.  I have to figure out what audience I’m writing for.

Tags:

%d bloggers like this: