Posted by: JBL | December 4, 2011

(3+1)-avoiding posets

Yan and I recently put a paper on the arXiv that enumerates the graded (3+1)-avoiding posets.  In this post, I kill the adjective “graded” and talk a bit about what (3+1)-avoiding posets are and why they’re interesting.  If you don’t know what a poset is, I’ve included the definition in Note 0 at the bottom of the post.

As with any object as general as posets, we are mostly interested not in results about all posets, but rather in finding particular families of posets with interesting or unexpected properties.  One such family of posets are the (3+1)-avoiding posets.  These are the posets that do not contain four elements, say a, b, c, and d, such that a < b < c and d is incomparable to the other three.  A short digression to explain the name “(3+1)-avoiding”: one natural class of posets are the chains, finite total orders like the first example in the previous paragraph.  A natural name for the chain with n vertices is n, so the chain with three vertices is 3 and the chain with one vertex (the only poset with exactly one vertex) is 1.  There are several natural operations that we can use to combine posets, including the disjoint union, denoted “+”.  Thus, 3+1 is the poset that you get if you add a single isolated vertex to a three-element chain, and a poset is (3+1)-avoiding if it has no four elements that induce the poset 3+1.

It’s a common surprise in combinatorics to find that important objects are characterized by avoiding certain induced subobjects; subposet-avoidance is one particular example of this, and in fact (3+1)-avoiding posets show up in a number of unexpected places.  The simplest and perhaps nicest appearance is in the characterization of semiorders.  Semiorders are posets that arise in the following way: we have a set of data (real numbers generated by some experiment) such that each datapoint has error bars of the same size.  Thus, if two values a and b are separated by at least a fixed distance then we know their true order; but if they are separated by less than this distance, we can’t be certain which value is truly larger.  The relations we can be certain of are the relations of our poset.  It’s not hard to see that this definition is equivalent to the following: a semiorder is a poset whose elements are unit intervals in the real numbers, with one element less than another if and only if it lies entirely to its left.  (Aside: an easy exercise is to show that it doesn’t matter whether our intervals are open or closed.)  The main result of interest is that semiorders are exactly those posets that avoid 3+1 and 2+2.  (If we drop the “unit” in “unit intervals”, we get just (2+2)-avoiding posets.)  These posets have all sorts of nice properties; for example, the number of them with n unlabeled elements is exactly the nth Catalan number, so we immediately know we’re going to get nice combinatorics and lots of connections with other objects.  See Wikipedia and the work of Peter Fishburn for much more information about them.

A second set of connections comes from the following simple observation: a poset P avoids 3+1 if and only if its incomparability graph (i.e., the graph G on the same vertex set such that u is connected to v in G if and only if u is incomparable to v in P) is claw-free, i.e., contains no four vertices a, b, c, d such that d is connected to a, b and c, none of which are connected to each other.  Claw-free graphs are quite interesting; for example, they make an appearance in some recent work of Fadnavis, who proved the following pretty result:

Suppose that we wish to color a graph G with q colors, choosing the color for each vertex at random.  If G is claw-free then to maximize the chance that the resulting coloring is a proper coloring (i.e., no two adjacent vertices have the same color), we should choose colors uniformly at random (i.e., with equal probabilities 1/q).

(Quite surprisingly, this result is not true in general!  To 2-color a star graph with 4 or more points, you’re better off with a more lop-sided distribution.)  Actually this result is just one part of a bigger story; for example, it’s also related to the Stanley-Stembridge conjecture, which asserts that symmetric chromatic polynomial of the comparability graph of a (3+1)-avoiding poset is e-positive.  (For definitions, check the Fadnavis paper, which is really excellent and has a lot of interesting material.)

As an enumerative combinatorialist, all these nice features of (3+1)-avoiding posets make me want to count them.  And, in some sense one should expect this to be not too difficult: claw-free graphs and (3+1)-avoiding posets both have nice structural classifications (due to Chudnovsky & Seymour and to Skandera, respectively), and the related (2+2)-avoiding posets have been enumerated by Bousquet-Mélou, Claesson, Dukes & Kitaev.  But, unfortunately, it seems like none of this is actually directly relevant.  So at least for now, counting (3+1)-avoiding posets remains very much open.

Notes:

0: One of the fundamental objects of combinatorics is the partially ordered set, or poset for short.1  Posets are just what their name suggests: they are given by an order relation (usually denoted <) that is transitive (i.e., a < b and b < c means a < c) and antisymmetric (i.e., we never have a, b such that a < b and b < a), but it is partial in the sense that not every two elements are necessarily comparable (so we might have a \neq b such that neither a < b nor a > b hold).  Obviously posets are a very flexible family of objects, including things like the usual order on the integers \{1, 2, \ldots, n\} (a partial order than happens to be a total order) or the containment order on the subsets of \{1, 2, \ldots, n\} (the Boolean lattice).

1: Does anyone know the history of how this came to be?  As far as I know, MacMahon didn’t do anything with posets, so my assumption is that one can trace it to Rota, but obviously this is not based on anything concrete at all.

About these ads

Responses

  1. [...] do policzenia problemu zliczenia skończonych zbiorów uporzadkowanych unkających (3+1) (patrz: http://concretenonsense.wordpress.com/2011/12/04/3-plus-1-avoiding-posets/ ) w duchu podobnym do tego jak w dowodzie Joyala twierdzenie Cayleya w [...]

  2. Hint: Posets originate from philosophy.

  3. Whether or not they originate in philosophy doesn’t explain how they came to be a central object in combinatorics! But some more words on what they have to do with philosophy might be interesting.


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

Categories

Follow

Get every new post delivered to your Inbox.

Join 76 other followers

%d bloggers like this: