Disjoint chains and matchings in posets

02/16/2010 - 12:15pm
02/16/2010 - 1:10pm
Shahriar Shahriari (Pomona College)

Let [n] = {1, 2, ..., n} be a set with n elements. Assume that A_1, ..., A_m are subsets of size k and B_1, ..., B_m are subsets of size h. Furthermore, assume that A_i is a subset of B_i for i = 1 ... m. Can you find m disjoint skipless chains in the poset of subsets of [n] that joins the As to the Bs? A skipless chain from A_i to B_i is a collection of h-k+1 subsets C_0 = A_i, C_1, C_2, ..., C_{h-k-1}, C_{h-k} = B_i such that C_{j-1} is a subset of C_j and has one less element than C_j. We will introduce a new matching property that allows us to discuss this question in general partially ordered sets.

Millikan 208 (Pomona College)