Maximum size antichains and the COLEX order

John Goldwasser[1]

West Virginia University

If B is a collection of sets we say the subset A of B is an antichain if for each pair of distinct sets in A, neither is a subset of the other. The order COLEX on the set of finite subsets of the positive integers is defined by C is less than D if C is a subset of D or if largest element in C which is not in D is less than the largest element in D which is not in C. We find a formula for the maximum size of an antichain in the first m sets in COLEX. It is in terms of a certain new representation of m as a sum of binomial coefficients. We call it the Catalan representation, because of a connection with a generalization of Catalan numbers. The special case when m is a power of 2 is Sperner’s theorem on the maximum size of an antichain in the Boolean lattice.

[1] Joint work with Yongbin Ou (my Ph.D student) and Attila Sali, Hungarian Academy of Sciences

April 21, 2005

At 3:30 in Wallace 430

---