Dimension and matchings in comparability and incomparability graphs

Graph Theory Seminar
Thursday, March 5, 2015 - 12:05am
1 hour (actually 50 minutes)
Skiles 005
Math, GT
In the combinatorics of posets, many theorems are in pairs, one for chains
and one for antichains. Typically, the statements are exactly the same when
roles are reversed, but the proofs are quite different. The classic pair of
theorems due to Dilworth and Mirsky were the starting point for this
pattern, followed by the more general pair known respectively as the
Greene-Kleitman and Greene theorems dealing with saturated partitions. More
recently, a new pair has been discovered dealing with matchings in the
comparability and incomparability graphs of a poset. We show that if the
dimension of a poset P is d and d is at least 3, then there is a matching
of size d in the comparability graph of P, and a matching of size d in the
incomparability graph of P.