Graph Theory Seminar
Thursday, March 5, 2015 - 00:05
1 hour (actually 50 minutes)
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.