Combinatorics fun with complexes

5 Apr

Last weekend I spoke at the Graduate Student Combinatorics Conference in Clemson, in one of those parallel sessions, so there were two other speakers slotted for the same 25 minute slot.  But those two didn’t show up, so I ended up being a “plenary speaker”!  Everyone came to my talk, which is funny because I’m in geometric group theory, not combinatorics.  But I got a lot of compliments afterward even though I only got through 2/3 of the prepared material (oops that’s what happens when you don’t practice/finish the talk 2 hours before showtime).  Related: I don’t think this is humblebragging, I believe in real bragging- you’re awesome, shouldn’t you tell people about it?

Anyways, I enjoyed the first graduate talk I saw, by a grad student at KU named Bennet Goeckner [I still am not sure about etiquette for blogging but I think I’ll start using peoples’ names instead of just linking to their websites.  If they get mad at me for google hits then I’ll go back to just links.]  It was based on a paper he coauthored with three professors, so I thought I’d tell you a bit about it.

I didn’t know anything about combinatorics before going to this conference.  Like, I didn’t even know it was a field of study, despite posting about an open problem in it almost exactly two years ago.  So I was very happy that in this first talk he defined an abstract simplicial complex, which is a basic object of study in combinatorics (at least, it came up in a ton of later talks).  This is a subset D of the set of subsets of {1, 2, 3,…, n} that follows a rule: if a is in D, and b is a subset of a, then b is also in D.  Example: if the set {1,2,3} is in D, then that means all of these sets are in D too: {1},{2},{3},{1,2},{2,3},{1,3}.  Here’s why we call it simplicial: you can see all of this information if you draw a triangle (a.k.a. a 2-simplex)!

simplex

Big picture of triangle contains all the info on the right (+smile!)

Might as well be thorough: the set of subsets is called the power set, so the power set of {1,2,3} is what we listed above, plus the entire set and the empty set.  Note that in our example, we have 8 sets in the power set of a 3-element set.  This is not a coincidence!  In general, a power set will have 2^n elements, if the original set had elements.

Also, a n-simplex is the convex hull of (n+1) points in space: so 3 points in 2 space makes a triangle.  4 points in 3 space makes a tetrahedron, a.k.a. a 3-simplex.  5 points in 4 space makes a 4-simplex.

nsimplices

0,1,2, and 3-simplices

So whenever you have abstract objects that satisfy the simplicial condition, you can build an abstract simplicial complex out of them.

Here’s an example from the talk: X=<1 2 3, 2 3 4>.  Convince yourself that this is two triangles glued together along an edge labeled by 2 and 3.  We can build a lattice that encodes the subset information in a different way then the triangles picture.  I also love this example because the lattice looks like a heart, and I ❤ lattices!

heartlattice

Red lines indicate that the bottom set is contained as a subset in the top set

We say a simplicial complex is partitionable if you can cut it up into Boolean intervals that end in the top layer (but start at some layer).  The picture shows you the partitioning, and you can kind of tell by looking what a Boolean interval is (it describes the skeleton of a n-cube for some n).

partitioned.png

This simplicial complex was partitionable… but my heart isn’t (it belongs to GGT)

It’s a little hard to show that things aren’t partitionable.  Here’s an example that probably showed up in the talk but I didn’t write it down: Y= <1 2 3, 3 4 5>.

bowtie.png

Simplex and lattice, plus a happy person wearing a bowtie!

If we make one of the partitions that contains the bottom empty set and one of the top sets, we can’t make the rest into partitions that start at the top.

parting

No way to partition remaining 5 sets

Their paper answers a conjecture from 1979, which asked if all Cohen-Macaulay simplicial complexes are partitionable (Cohen-Macaulay has something to do with homology, which we haven’t done here but my friend Jeremy has a mathy post about it).  They said haha no!  They took a counterexample in something else, called Ziegler’s Ball, chopped it up a little bit, glued a bunch of copies of it to itself, and built something surprisingly nice (with 16 vertices) that is not partitionable.  This has applications in commutative algebra, besides being a fun combinatorial thing.  The paper is relatively short and approachable if you’re a grad student looking for something fun to read, and they ask three questions for further research at the end!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: