Tutte seminar - William T. Trotter

Duality in the Combinatorics of Posets

Abstract: 

Every 10 years or so, there have been two closely connected theorems in the combinatoricst of posets, one for chains and one for antichains. Typically, the statements are exactly the same when roles are reversed, but the proofs are markedly different. And on rare occasions, there has been a case where there is a natural candidate for a dual statement but it turned out not to be true.
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, we have the pair of theorems due to Duffus-Sands and Howard-Trotter dealing with pairwise disjoint families of subsets. And within the last month, a new pair has been discovered dealing with matchings in the comparability and incomparability graphs of a poset.