***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 26th February, 3:00 in Fine Hall 224.
 
Speaker: Ruidong Wang (Georgia Tech)

Title: Dimension and matchings in comparability and incomparability graphs

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.

                       -----------

Next week: Ori Parzanchevski

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)