## “Bulletin Board”

School of Mathematics - June 19, 2002

### Mathematical Talk

#### 40% of a Conjecture of FurediShahriar ShahriariAssociate Dean of the College & Professor of Mathematics Pomona College June 19, 200215:00 - 16:00School of Mathematics, IPM

40% of a Conjecture of Furedi

Shahriar Shahriari
Associate Dean of the College & Professor of Mathematics
Pomona College

June 19, 2002
15:00 - 16:00
School of Mathematics, IPM

Abstract:

In this talk, I will report on joint work with Timothy Hsu, Mark Logan, and Christopher Towse on a fifteen year old conjecture of Füredi on chain partitions of a Boolean lattice.

Consider all 8 subsets of {1,2,3} and organize them into the following chains'':

 Æ Í {1}
 Í
 {1, 2} Í {1,2, 3}
 {2}
 Í
 {2,3}
 {3}
 Í
 {1,3}

You have now partitioned these subsets into chains with sizes 4, 2 & 2. But could you partition the 1024 subsets of {1, ¼,10} into 16 chains of size 5 and 236 chains of size 4?

Let [n] = {1,¼,n} and let 2[n] denote the poset of subsets of [n] ordered by inclusion. A collection of subsets A0 Ì ¼ Ì Ak of [n] is called a chain of size k+1 in 2[n]. In this talk we discuss a construction that partitions 2[n] into a collection of chains such that the size of the shortest chain is approximately [ 1/2] Ön and the size of the longest chain is roughly Ö{nlogn}.

This result is motivated by conjectures of Griggs and Füredi on chain partitions of 2[n]. Let m = (m1 ³ ... ³ ml) be a partition of 2n into positive parts. In 1988, Griggs made a conjecture that gives a necessary and sufficient condition for the existence of a partition of 2[n] into chains of sizes m1,...,ml. Earlier, Füredi had considered a special case of the Griggs conjecture and asked if 2[n] can be partitioned into (n || (ën/2 û)) chains such that the size of every chain is one of two consecutive integers. In such a (hypothetical) construction, the size of the shortest chain will be approximately Ö{p/2}Ön. In contrast, our construction gives a chain partition with the correct number of chains, and with minimal chain size roughly [ 1/2]Ön.

Abstract in PDF format.