Colloquium

Thursday, Nov. 29, 2007

4:00 PM, BAC 219

Speaker: John Goldwasser, West Virginia University, Morgantown, WV

Hosts: Tao Jiang and Dan Pritikin

Title: COLEX, Catalan numbers, and a generalization of Sperner’s theorem

Abstract:

If F is a collection of sets, we say the subset B of F is an antichain if for each pair of sets in B, neither is a subset of the other. 

The order COLEX on the set of finite subsets of the positive integers is defined by C < D if C is a proper subset of D or if

the largest element in C/D is less than the largest element in D/C.  We find a formula for the maximum size of an antichain

in the first m sets in COLEX in terms of a new representation of an integer as a sum of binomial coefficients.  We call it the

Catalan cascade 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.  The formula points the way

to an open conjecture, an antichain analog of the Kruskal-Katona theorem, a fundamental result on the size of the “shadow”

of a collection of sets. 

In spite of the impression you might get from reading the above paragraph, the talk will start from first principles and will

be mostly accessible to people with no background in combinatorics.