Georgia Institute of Technology College of Sciences

Combinatorial mathematics exhibits a number of elegant, simply stated problems that turn out to be surprisingly challenging. In this talk, I report on a problem of this type on which I have been working with Noah Streib, Stephen Young and Ruidong Wang from Georgia Tech, as well as Piotr Micek, Bartek Walczak and Tomek Krawczyk, all computer scientists from Poland. Given positive integers $k$ and $w$, what is the largest integer $t = f(k,w)$ for which there exists a family $\mathcal{F}$ of $t$ vectors in $N^{w}$ so that: \begin{enumerate} \item Any two vectors in the family $\mathcal{F}$ are incomparable in the product ordering; and \item There do not exist two vectors $A$ and $B$ in the family for which there are distinct $i$ and $j$ so that $a_i\ge k +b_i$ and $b_j \ge k + a_j$. \end{enumerate} The Polish group posed the problem to us at the SIAM Discrete Mathematics held in Austin, Texas, this summer. They were able to establish the following bounds: \[ k^{w-1} \le t \le k^w \] We were able to show that the lower bound is essentially correct by showing that there is a constant $c_w$ so that $t \l c_w k^{w-1}$. But recent work suggests that the lower bound might actually be tight.